Busy-Wait Initialization

In response to my recent article on various kinds of initialization, GJ proposed another algorithm, which I will call here busy-wait initialization. This is the first time I’ve encountered this approach and I have no idea whether it is wide-known and has an “official” name.
The algorithm itself is very simple:

class function BusyWait<T>.Initialize(var storage: T; factory: TFactory): T;
begin
  if storage = nil then begin
    if InterlockedCompareExchangePointer(
         PPointer(@storage)^, PPointer(@factory)^, nil) = nil 
    then
      storage := factory()
  end;
  while PPointer(@storage)^ = PPointer(@factory)^ do
    Sleep(0);
end;

[This is not exactly the algorithm GJ proposed but my modified version, changed to work in a generic class.]

It uses a sentinel which prevents multiple simultaneous threads from creating the shared resource at the same time. In this respect it is similar to the pessimistic approach. It, however, doesn’t need an external lock and implements the locking through the interlocked instruction, just like the optimistic initialization does.
Let’s step through the code to see how it works:

• Firstly, a sentinel is stored in the global storage, but only if global storage itself is still uninitialized (nil).
• If the global storage is not yet initialized (Interlocked … returned nil), new shared resource is created and stored in the global storage.
• At the end, a busy loop waits until the storage does not contain a sentinel value anymore.

An address of the shared resource-creating factory is used as a sentinel as we can be sure that this value will never be returned from the factory itself.
Let’s walk through few scenarios.

Initialization in a single thread

• Interlocked… succeeds and returns nil. Storage now contains @factory.
• Factory method is called and result is stored in the storage. It does not contain @factory anymore.
• While loop tests the condition, which is not true, and exits.

Calling Initialize after the resource was initialized

• Let’s suppose that the outer if was executed before the storage was initialized and then the thread is paused and another thread initializes the resource.
• Interlocked… fails and returns non-nil value, therefore factory method is not called.
• While loop tests the condition, which is not true, and exits.

Two threads calling Initialize at the same time

• First thread calls Interlocked… which succeeds and returns nil. Storage now contains @factory.
• Second thread calls Interlocked… which fails.
• Second thread enters the while loop. Loop condition is true and second thread starts looping.
• First thread calls the factory, which initializes the resource.
• Both first and second thread now skip or exit out of the while loop as the storage is no longer equal to @factory.

Advantages and disadvantages

Advantages are obvious:

• Resource is created only once.
• No external (operating system) locking is used.

Disadvantages, however, may or not may be very important – depends on your application.

• Busy wait is used to wait on the resource.
• Execution is very dependent on the x86/x64 memory model and would probably fail on other architectures. For example, it assumes that read/writes from/to a shared DWORD/QWORD memory location are atomic.

Initialization mechanisms in practice

It looks like it’s the time to write a good stress/performance test of all three initialization approaches … I don’t, however, have a good idea how to write this test (yet).