Why there is a Thread.Sleep(1) in .NET internal Hashtable?

Question

Recently I was reading implementation of .NET Hashtable and encountered piece of code that I don't understand. Part of the code is:

int num3 = 0;
int num4;
do
{
   num4 = this.version;
   bucket = bucketArray[index];
   if (++num3 % 8 == 0)
     Thread.Sleep(1);
}
while (this.isWriterInProgress || num4 != this.version);

The whole code is within public virtual object this[object key] of System.Collections.Hashtable (mscorlib Version=4.0.0.0).

The question is:

What is the reason of having Thread.Sleep(1) there?

Collado

Looks like a spinwait before a context switch. I.e. it checks for a condition 8 times before putting the thread to sleep. – Chacon

Similar thread; Crux is to allow OS to schedule other task – Probation

Answer 1

Sleep(1) is a documented way in Windows to yield the processor and allow other threads to run. You can find this code in the Reference Source with comments:

   // Our memory model guarantee if we pick up the change in bucket from another processor,
   // we will see the 'isWriterProgress' flag to be true or 'version' is changed in the reader.
   //
   int spinCount = 0;
   do {
       // this is violate read, following memory accesses can not be moved ahead of it.
       currentversion = version;
       b = lbuckets[bucketNumber];

       // The contention between reader and writer shouldn't happen frequently.
       // But just in case this will burn CPU, yield the control of CPU if we spinned a few times.
       // 8 is just a random number I pick.
       if( (++spinCount) % 8 == 0 ) {
           Thread.Sleep(1);   // 1 means we are yeilding control to all threads, including low-priority ones.
       }
   } while ( isWriterInProgress || (currentversion != version) );

The isWriterInProgress variable is a volatile bool. The author had some trouble with English "violate read" is "volatile read". The basic idea is try to avoid yielding, thread context switches are very expensive, with some hope that the writer gets done quickly. If that doesn't pan out then explicitly yield to avoid burning cpu. This would probably have been written with Spinlock today but Hashtable is very old. As are the assumptions about the memory model.

Darwen

I thought Sleep(0) was recommended if you want just a yield. Sleep(1) is actually a sleep. – Djambi

Sleep(0) only yields if there's another thread ready to run with a higher priority. Not the intention here. – Darwen

Only to threads of equal priority actually... which is what yield generally means. – Djambi

Equal or higher. Writes take very little time, implicit is that the writing thread must have been suspended if this doesn't work after 8 tries. This is not great code. – Darwen

If there were a higher priority thread ready to run, it would be running already. If your code is running, then all higher priority threads are either also running (on other cores) or blocked. So Sleep (0) only yields to equal priority. Considering dynamic priority of course. – Djambi

Answer 2

Without having access to the rest of the implementation code, I can only make an educated guess based on what you've posted.

That said, it looks like it's trying to update something in the Hashtable, either in memory or on disk, and doing an infinite loop while waiting for it to finish (as seen by checking the isWriterInProgress).

If it's a single-core processor, it can only run the one thread at a time. Going in a continuous loop like this could easily mean the other thread doesn't have a chance to run, but the Thread.Sleep(1) gives the processor a chance to give time to the writer. Without the wait, the writer thread may never get a chance to run, and never complete.

Intine

Answer 3

I haven't read the source, but it looks like a lockless concurrency thing. You're trying to read from the hashtable, but someone else might be writing to it, so you wait until isWriterInProgress is unset and the version that you've read hasn't changed.

This does not explain why e.g. we always wait at least once. EDIT: that's because we don't, thanks @Maciej for pointing that out. When there's no contention we proceed immediately. I don't know why 8 is the magic number instead of e.g. 4 or 16, though.

Contrariwise

No we don't. After ++num3, num3 will be 1. Or I seriously lack caffeine. – Mum

The sleep is only done after 8 consecutive iterations in which a writer is in progress or the version is wrong. Presumably, to give the writer thread a chance to do its work. – Bezonian

If we were calling Sleep(1) within each call to [] operator, that would be seriously bad for the performance. Remember that Thread.Sleep(1) doesn't actually make you sleep 1 ms - it's more like 15. – Mum

And what has num4 to do with all this? – Redheaded

@Redheaded - I assume that this.version will be updated by the writer thread, and as such can change between the assignment and the test. The second while() condition makes it so that the reader will repeat the reading if it sees a change. – Mum

@MaciejStachowski It sounds reasonable. I was not expecting a variable named version to be updated in such a way ;) – Redheaded

@Redheaded - it threw me off at first too, but when you realize version probably means version of the data in the hashtable (i.e. each write creates a new one), it does make sense :) – Mum