Using BitAnd() To Determine Odd / Even Rows (Thanks Tony Petruzzi)
I recently posted about how the MOD (modulus) operator could be used in ColdFusion to determine even and odd rows of an outputted query. Tony Petruzzi commented that this could also be done using bitwise manipulation and, in particular, the ColdFusion BitAnd() function.
For those of you who don't know how bits come into play when we are talking about numbers, the 10 second run down is that every number is represented by a combination of bits. Of these bits, 8 make up a byte. Each bit can be either 1 or 0 (zero). The order and toggling of these bits determines what numeric value the byte represents. Each bit in the byte represents a "place" in the number. Each place that is turned on (value of 1) is "summed" to get the resultant number.
There's a lot more to it, but anyway, the point here is that Tony Petruzzi raised a good point: using MOD actually requires the ColdFusion server to do a lot of division. Division is more expensive in terms of processing than Bitwise manipulation, which really doesn't require much calculation at all. He recommended performing:
BitAnd( QUERY_ROW, 1 )
This will Bit-AND the "ones" bit with the row number. Since only every other number (even vs. odd) has the ones place turned on, then Bit-ANDing it with one will result in TRUE for every other row. To test this, let's try this:
<!---
Loop over the index loop. This could just have
easily been a query loop where we were using
QUERY.CurrentRow instead of intI.
--->
<cfloop
index="intI"
from="1"
to="10"
step="1">
#intI# :
<cfif BitAnd( intI, 1 )>
Odd
<cfelse>
Even
</cfif>
</cfloop>
That gives us the following output:
1 : Odd
2 : Even
3 : Odd
4 : Even
5 : Odd
6 : Even
7 : Odd
8 : Even
9 : Odd
10 : Even
This is sneaky little trick. I like it. As he pointed out, you can read more about it over on the ColdFusion Cookbook. I am not sure how the bitwise manipulation happens under the hood, but hopefully it is something that is short-circuited so that the second negative it hits will result in an overall FALSE; if this were the case, it would only ever have to Bit-AND two bits (the "one" column of both numbers).
Want to use code from this post? Check out the license.
Reader Comments
"using MOD actually requires the ColdFusion server to do a lot of division. Division is more expensive in terms of processing than Bitwise manipulation, which really doesn't require much calculation at all. He recommended performing:"
Although I wonder if the compiler is smart enough to turn mod 2 into a check of the "rightmost" bit. I'd like to see some benchmarks, just for curiousity's sake.
@Sam,
That's a good point. I assume that the server has to do a lot of division for use with MOD because that is what I do in my head. I wonder how the server optimizes that stuff when it all compiles down. Very interesting.
I don't know about anyone else, but interpreting the bitwise operator is a lot less obvious to me compared with a simple MOD operation. When you're programming at the level (with respect to the CPU) of ColdFusion, shaving a few processor instructions is completely folly. First, the language is inherently slow to the point where a couple clock cycles won't mater, and second, the odds of the instructions you anticipate actually being executed as you anticipate are about zero because of all the translation layers that the code has to pass though.
This high up, readability is king, and it should require a pretty significant performance improvement to make a tradeoff that sacrifices readability for performance.
@Barney,
Most agreeably. I would still go with the MOD as I find it more readable. But, can't hurt to have more tools in the tool-box.
this post brought a tear to my eye ;)
@Sam
Extremely interesting indeed. I wonder if any CF developers at Adobe could tell us that.
@Barney
I agree with you hands down. Although the bitand method is really cool and it is good to have an understanding of bitwise logic under your belt, readability is everything.
@Ben
Now I guess I'm going to be having the same problem that you did. Someone just post a comment to my BASH Friday complaining about one the quotes on BASH :P
Barney - absolutely, readability is the main goal. But, that doesn't mean you couldn't create an isOdd() or isEven() method using that.
Surely its not obvious in the CF world, but bitwise operations are farily common idioms in other languanges (at least it seems to me that I've seen them at least as often as mod).
Ben - And even if CF sends the num mod 2 straight to Java, Java may compile it down to the operation on bits.
Agreed that it's good to remember that we have the ability to do Bitwise calculations in CF.
But, another reason for sticking with MOD: When your boss comes to you and says "Hey, I forgot to tell you. The client wants three different colours for the rows in this table" all you have to do is change the divisor, not your whole alternation method.
@Tom,
Quite true. The MOD stuff would be much easier to change.
I agree with you hands down. Although the bitand method is really cool and it is good to have an understanding of bitwise logic under your belt, readability is everything.
I did a comparison using GetTickCount() before and after loops over 30,000 rows and sometimes the difference would be 80ms, sometimes 5ms, and sometimes the BitAnd loop would take even longer. Even averaging 10 loops of each showed the same kind of results. I understand the logic of why BitAnd SHOULD take less time, but it really doesn't seem to have much of an effect (at least in my test). Is it possible, during compilation, maybe our MOD 2 statements are simplified into some sort of bit comparison? Anyone else do any tests like this?
Since MOD and bit operations are so low-level, the overhead of the loop is going to completely drown out any performance differences between the actual test subject.
Instead, I'd recommend manually copy and pasting your N iterations into a flat file. With compounding copy and paste, you can get a huge number of lines very quickly, and completely eliminate the loop overhead.
In any case, I think you've proven pretty convincingly that any performance different is pretty irrelevant. ;)
I guess I should note that this is a server running CF 7 on Windows 2003. I already deleted my test file, but the loops really didn't output anything, just did the even/odd calculation.
Fantastic