Krzysztof Koźmic's blog

I used to do quite a lot of con­cur­rent pro­gram­ming early in my career. Recently I've been work­ing again on opti­mis­ing a large piece of code to behave bet­ter when ran in con­cur­rent envi­ron­ment and I must share a secret with you — I had a great fun. It all started with a semi-serious chal­lenge from a friend, and ended up con­sum­ing big part of my Christmas-new year break.

One of the prob­lems I found, was that a group of objects that was being used on mul­ti­ple threads had to be ini­tialised in a thread safe man­ner — that is the ini­tial­i­sa­tion code had to be ran just once, atom­i­cally, on a sin­gle thread. How­ever after­wards it could be safely exe­cuted con­cur­rently on mul­ti­ple threads. This was being accom­plished by using code sim­i­lar to following:

public void Foo GetInitializedFoo()
{
   if(this.fooIsInitialized) return foo;
   lock(lockObject)
   {
      if(this.fooIsInitialized) return foo;

      InitializeFoo();
      return foo;
   }
}

As you can see the code usu­ally works lock-free, and only the first time when foo is not ini­tialised it has to lock to per­form the ini­tial­i­sa­tion algo­rithm. The rea­son that was sub­op­ti­mal is that in heav­ily multi-threaded sce­nar­ios it yielded sub­op­ti­mal per­for­mance when mul­ti­ple threads were try­ing to ini­tialise foo.

Imag­ine there are four threads. First of them suc­ceeds in obtain­ing the lock, and goes ahead to per­form the ini­tial­i­sa­tion, while the other two go into the wait­ing queue and sleep there wait­ing for the lock to be freed. The first thread fin­ishes the ini­tial­i­sa­tion pretty soon, but by the time the first thread wakes up already quite a lot of time is wasted. Then the sec­ond thread obtains the lock, but the remain­ing two, even though the vari­able is already ini­tialised and there­fore safe to be read con­cur­rently, still wait in the lock queue. The three remain­ing threads could exe­cute all at once now, yet they will be woken up and exe­cuted each in turn.

Mad sci­en­tist solution

The prob­lem was that using lock proved to be sub­op­ti­mal for the prob­lem at hand. To try to address this (and to make my inner geek happy) I decided to look at mak­ing this code per­form better.

While .NET frame­work library has lots of syn­chro­ni­sa­tion prim­i­tives none of them really seemed to be any bet­ter suited for the job then good old Mon­i­tor. I didn't want to put wait­ing threads to sleep imme­di­ately, as this is quite an expen­sive oper­a­tion (and so is wak­ing them up back again), and the ini­tial­i­sa­tion would usu­ally be per­formed quite quickly. I also wanted all the wait­ing threads to be able to exe­cute con­cur­rently with no syn­chro­ni­sa­tion after the first one of them fin­ished ini­tial­i­sa­tion. To accom­plish this I came up with the fol­low­ing solution:

public sealed class ThreadSafeInit
{
	// We are free to use negative values here, as ManagedTreadId is guaranteed to be always > 0
	// http://www.netframeworkdev.com/net-base-class-library/threadmanagedthreadid-18626.shtml
	// the ids can be recycled as mentioned, but that does not affect us since at any given point in time
	// there can be no two threads with the same managed id, and that's all we care about
	private const int Initialized = int.MinValue + 1;
	private const int NotInitialized = int.MinValue;
	private int state = NotInitialized;

	public void EndThreadSafeOnceSection()
	{
		if (state == Initialized)
		{
			return;
		}
		if (state == Thread.CurrentThread.ManagedThreadId)
		{
			state = Initialized;
		}
	}

	public bool ExecuteThreadSafeOnce()
	{
		if (state == Initialized)
		{
			return false;
		}
		var inProgressByThisThread = Thread.CurrentThread.ManagedThreadId;
		var preexistingState = Interlocked.CompareExchange(ref state, inProgressByThisThread, NotInitialized);
		if (preexistingState == NotInitialized)
		{
			return true;
		}
		if (preexistingState == Initialized || preexistingState == inProgressByThisThread)
		{
			return false;
		}

		var spinWait = new SpinWait();
		while (state != Initialized)
		{
			spinWait.SpinOnce();
		}
		return false;
	}
}

The Thread­SafeInit class man­ages lock-free access to part of code­base. It has a state int flag which starts off in a non-initialised state. Then as Exe­cuteThread­SafeOnce method, which marks the begin­ning of the ini­tial­i­sa­tion sec­tion is being called, it uses Interlocked.CompareExchange to set the flag in a lock-free thread safe manned to the id of cur­rent thread. The thread that suc­ceeds returns true and is free to go ahead and do the ini­tial­i­sa­tion. Any other thread waits for the first one to fin­ish, but instead of going imme­di­ately to sleep it spins for a while, effec­tively wast­ing cycles, and then once the first thread fin­ishes, and calls End­Thread­SafeOn­ce­Sec­tion method, all the other threads can pro­ceed in parallel.

Usage pat­tern looks some­thing like this:

public void Foo GetInitializedFoo()
{
   if(this.fooIsInitialized) return foo;
   var initialising = false;
   try
   {
      initializing = init.ExecuteThreadSafeOnce();
      if(this.fooIsInitialized) return foo;

      InitializeFoo();
      return foo;
   }
   finally
   {
      if(initialising)
      {
         init.EndThreadSafeOnceSection();
      }
   }
}

Using this code I was able to mea­sure over two-fold improve­ment over the old solu­tion in this part of code. Sure, it's a micro-optimisation and in 99.9% of cases lock would be just fine, but as I said, it was a chal­lenge, and I had a blast work­ing on this, and that's all I care about. Well, not all per­haps. If you see any flaws in this code, ways to improve it, or I just repli­cated some­thing that some­one else did much bet­ter long time ago, let me know.