Making it fast!

 

In the last post, I outlined a strategy to generate Guids in a strictly increasing order to address the issues outlined here.

While Guid.NewGuid() natively takes quite a bit of time to create a random Guid, it would be interesting to see if our implementation is slower, or faster – and to investigate ways to speed it up.

Our first run

Hmm.. that seems to be pretty good – but inspecting the code should point a steady finger at the Thread.Sleep(1) call. So how does one make the sequence increase, without the Sleep() call.

Enter Interlocked.Increment()

A strategy to ensure monotonically increasing numbers would be to initialize a counter with DateTime.Now.Ticks, and then in the generation method, to increment it in a thread-safe manner – thus:

private static long _counter;

public static Guid NewSequentialGuid()
{
    lock (LockObject)
    {
        Interlocked.CompareExchange(ref _counter, DateTime.Now.Ticks, 0);
        Interlocked.Increment(ref _counter);

        var rgb = BitConverter.GetBytes(_counter);
        Array.Reverse(rgb);

        return new Guid(_a, _b, _c, rgb);
    }
}

The tests continue to pass, assuring us that  the Guids are still unique. Measuring the performance, we get:

Much better – we’ve made things around  twice as fast. I would leave things as they are now – except I’m quite curious to see if I can extract some more performance out of it.

The importance of profiling

We have only five lines of code there – where do we start speeding things up?

The best way to find out would be to fire up the profiler in Visual Studio 2010 and run the program in there. That points us to:

Hmm… looks like we’re spending most of our time getting the Ticks count, even if we never use it more than once – definitely wasteful.

Why don’t we cache the Ticks count once, and just use the Interlocked.Increment call to make it unique?

private static long _counter = DateTime.Now.Ticks;

public static Guid NewSequentialGuid()
{
    lock (LockObject)
    {
        Interlocked.Increment(ref _counter);

        var rgb = BitConverter.GetBytes(_counter);
        Array.Reverse(rgb);

        return new Guid(_a, _b, _c, rgb);
    }
}

That results in

Pretty good. So let’s look at a sequence of Guids created 50ms apart.

The implication of this is that every time the OrderedGuid class is initialized, the _counter would get set, and thereafter it would be a simple incremented sequence – even though there was a time delay of 50ms between each Guid being created.

If we wanted the creation of the Guid to be more ‘random’ and be more closely tied to the Ticks count, we could keep the _counter refreshed every so often with a Timer.

private static readonly Timer Timer = new Timer(ResetCounter, null, 0, 100);

private static void ResetCounter(object arg = null)
{
    lock (LockObject)
    {
        _counter = DateTime.Now.Ticks;
    }
}

static OrderedGuid()
{
    lock (LockObject)
    {
        ResetCounter();
    }
}

This would keep the _counter up to date reasonably frequently.

As you can see, we have a good somewhat random distribution between Guids created 50ms apart.

We’ve done this without appreciably slowing things down – given the coarse granularity of the tick-counting approach to timing, all we can say is that we haven’t made things very much different by introducing the timer.

And now we have a viable, fast way of generating predictably-unique, ordered Guids.