dinsdag 16 augustus 2011

Compiler optimization with the shift operator

The other day I came across a peculiar operator in .NET called the shift operator.  I’ve seen it before in theory but I’ve never encountered a practical use for them.
For anyone who doesn’t know what the shift operator is, here is an explanation stolen from MSDN:

The right-shift operator (>>) shifts its first operand right by the number of bits specified by its second operand.
The left-shift operator (<<) shifts its first operand left by the number of bits specified by its second operand.

So simply put, when you have an integer that looks like this binary: 001000100 and you apply the right shift operator on it by 2 then you get 000010001.  For what could this be useful besides bit operations?
Well whenever you do a multiple or divide with a power-of-two number then you can use the shift operation to make this go faster.  Here is a small code sample to illustrate:

int nr;
int result;
var stopwatch = new Stopwatch();

nr = 5;

result = nr * 4;

Console.WriteLine("{0} ms ellapsed", stopwatch.Elapsed);

result = nr << 2;

Console.WriteLine("{0} ms ellapsed", stopwatch.Elapsed);

So when we run this we get the following output:

As you can see the shift operator is almost an order of magnitude faster than the multiply operator yet they do exactly the same thing.  I saw allot of threads on stackoverflow (1, 2, ...)  telling people that you don’t have to worry about this kind of stuff because the compiler will optimize this for you, but a real life code sample demonstrates that this is not true.  Flipping the optimization flag doesn’t change the way the IL is generated nor does it change the way the JIT compiles the IL.  This is based on the results of this example.

Should you use the bit operator for code optimization?  I would recommend you not to do so unless you have to do very long and heavy calculations.  The reason for this is that it makes you code unreadable.  There are many programmers (even seasoned ones) out there that haven’t even heard of the bit shift operator.  When they’ll see your code they won’t be able to make head or tails out of it.  In most cases the advantage of optimizing your code in this way will be nullified by the decrease of readability of your code.   Of course when you’re doing bitwise operations you should use it when necessary.

Till next time

2 opmerkingen:

  1. Doesn't this method allow for overflows and loss of information? Otherwise this would be usefull to optimize my bussiness logic
    Or are overflows (in case of left-shift) and loss of information (right shift) being corrected?

    Otherwise great post

  2. C# only contains a bit shift operator that doesn't overflow. If I'm not mistaken java has both a bit shift operator and a circular bit shift operator for overflows.

    So when you do a right shift with an overflow you have to use some other mechanism. see this post on stackoverflow for more info: http://stackoverflow.com/questions/35167/is-there-a-way-to-perform-a-circular-bit-shift-in-c