Thread: Faster bitwise operator

Does anyone know which (x86) instructions those operators boil down to?
All you'd need to do is see how many clock cycles each of those instructions takes and compare their speed, right?

Although, without knowing too much about chip implementations, the only guess I can make as to why one might be faster is that != would just compare the binary representation of the two numbers, whereas < or > would need to check the sign of the variable for a signed int and then compare the numbers (whether the CPU can check the sign and do the compare at the same time, I have no idea).

Originally Posted by cpjust

Does anyone know which (x86) instructions those operators boil down to?
All you'd need to do is see how many clock cycles each of those instructions takes and compare their speed, right?

For Integers, It should boil down to CMP R2,R1 (or however registers are names) followed by either JE or JGE. JE and JGE both just check the control flags, and are therefore trivial operations. For floating point it would use FCOM, instead of CMP.

So for primitives there is no difference.

cpjust

x86 does as King Mir states - cmp is the generic call to perform a comparison - it is very much like a subtraction. In x86, subtractions and cmp set flags in the CPU, indicating things like sign, zero flag, overflow - various technical results. After that, a conditional jump instruction is what makes the decision as to truth or falsehood of a particular comparison like <, !=, etc. All of these have the same cycle count - so the answer you've received is the best you can get - they are basically the same. There is no point in asking which is faster.

What makes this a little more complicated is the various CPU's ability to predict branches, cache reaction to branches, hyperthreading, speed of RAM, alignment in RAM, whether or not the cmp is applied to a register or memory location (I forget if/when that was or was not possible in x86)....

In other words, you're focused on such a microscopic level of performance that you probably can't get the results you're hoping for without deciding to code in assembler - and even that isn't likely to be all that productive in this case.

Each model CPU and combination of hardware could make some difference.

For the processor (all the common ones at least) they are surely absolutely equal.
For a bignum class the < would be slightly slower because it involves two comparisons in the loop (excluding the loop condition) rather than just one:

Code:

{
    if (a.data[i] < b.data[i]) return true;
    if (a.data[i] > b.data[i]) return false;
    // else continue iterating.
}

// vs

{
    if (a.data[i] != b.data[i]) return false;
}

iMalc:iMalc - good point, but we could do that in a different way:

Code:

   int cmp;
   for(...)
   {
      if ((cmp = a.data[i] - b.data[i]));
      {
         return (cmp > 0)?true:false; 
      }
   }

This assumes that the common case is similar numbers. But I don't think it's much worse for the case with immediately different numbers - and that is the fast case in either variant, anyways.

--
Mats

Originally Posted by matsp

iMalc:iMalc - good point, but we could do that in a different way:

Code:

   int cmp;
   for(...)
   {
      if ((cmp = a.data[i] - b.data[i]));
      {
         return (cmp > 0)?true:false; 
      }
   }

This assumes that the common case is similar numbers. But I don't think it's much worse for the case with immediately different numbers - and that is the fast case in either variant, anyways.

--
Mats

That at first seemed like a great idea, and would work for people who have implemented something where each decimal digit is stored in an int or something wasteful like that, but it wont work for a "wasteless" implementation where the bigint is an array of unsigned longs. The reason being that the result of the subtraction would have to range from 0xFFFFFFFFU - 0 to 0 - 0xFFFFFFFFU. So that's -0xFFFFFFFF to +0xFFFFFFFF, requring an extra bit, as well as casting to a signed datatype. Of course it will work if you cast both to a larger datatype first, however I imagine the efficiency will then come out about the same as the original way I posted. Well, maybe still a little ahead if you're lucky.