Feb 032013
 

Generating sequential integers is not hard – simple counter++ is enough. Generating sequential positive integers is as trivial if you can use unsigned type. If you must stay in signed world, wrapping everything in condition will do the trick:

if (counter == Int32.MaxValue) {
    counter = 0;
} else {
    counter++;
}

Things get a bit more interesting if you need to do same in thread-safe manner. Obvious (and simplest) solution would be to put code in lock block:

lock (syncRoot) {
    if (counter == Int32.MaxValue) {
        counter = 0;
    } else {
        counter++;
    }
}

That will make code thread safe but it will also make it a lot slower. Every time you take a full blown lock, you will pay a hefty penalty. This example (on my computer) ran more than 30 times slower compared to first solution.

Only if there was an instruction specialized for integer incrementing…

Well, actually there is one – Interlocked.Increment. Unfortunate feature of this function is that (in case of 32-bit integers) once it goes up to 2147483647 it will return -1 as next value. Simple condition is all it takes to make code work:

Interlocked.Increment(ref counter);
if (counter == int.MinValue) { counter = 0; }

Except that this code does not work.

Any condition that touches our variable without being wrapped in some thread-safe construct will make a mess of things. In this case everything will work properly until variable reaches int.MaxValue (2147483647). Step after that we have a race condition between resetting variable to 0 and incrementing it further. If you have it running in two threads maybe it will even work. If code is running in more than that there is high chance you will see number 0 multiple times. Depending on your luck you might even see negative numbers counting up.

Fortunately code can be fixed:

var currCounter = Interlocked.Increment(ref counter);
if (currCounter < 0) { currCounter = currCounter + Int32.MaxValue + 1; }

We leave counter to increment as it wishes. Once it overflows we let it be – it will loop back eventually. However, there is nothing preventing us from modifying returned value because this value is ours alone and no other thread can touch it. We can simply increase all negative value by 2147483648 and we will get nice sequence of [... 2147483646 2147483647 0 1 ...]. Exactly what we wanted. And variable is held “locked” for only one instruction (Interlocked.Increment) so wait between threads is only as long as it needs to be to insure thread-safe operation.

This code is still more about ten times slower than simple non thread-safe example. But it is three times faster than our first go at locking whole operation. Whether this is even needed highly depends on your code. If you increment number only few times, there is nothing really wrong with locking even whole function. Don’t optimize code before you need to.

Timing routines are available for download. Be sure to measure on release code without debugging (Ctrl+F5). Measuring performance on debugging code is worthless because you might detect bottleneck where there isn’t any.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>