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?

Looks like a spinwait before a context switch. I.e. it checks for a condition 8 times before putting the thread to sleep. — vgru, Nov 15 '13 at 17:05
[Similar thread](http://stackoverflow.com/questions/508208/what-is-the-impact-of-thread-sleep1-in-c); Crux is to allow OS to schedule other task — Konstantin, Nov 15 '13 at 17:07

Hans Passant · Accepted Answer · 2013-11-15T21:40:20.837

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.

I thought `Sleep(0)` was recommended if you want just a yield. `Sleep(1)` is actually a sleep. — Ben Voigt, Nov 15 '13 at 22:36
Sleep(0) only yields if there's another thread ready to run with a higher priority. Not the intention here. — Hans Passant, Nov 15 '13 at 22:41
Only to threads of equal priority actually... which is what yield generally means. — Ben Voigt, Nov 15 '13 at 22:47
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. — Hans Passant, Nov 15 '13 at 22:54
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. — Ben Voigt, Nov 15 '13 at 22:57

score 7 · Answer 2 · answered Nov 15 '13 at 17:10

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.

David Seiler · Answer 3 · 2013-11-15T17:11:23.110

5

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.

edited Nov 15 '13 at 17:11

answered Nov 15 '13 at 17:04

David Seiler

9,557
2
31
39

3

No we don't. After `++num3`, `num3` will be 1. Or I seriously lack caffeine. – Maciej Stachowski Nov 15 '13 at 17:06
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. – dan04 Nov 15 '13 at 17:11
3

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. – Maciej Stachowski Nov 15 '13 at 17:12
And what has num4 to do with all this? – BlackBear Nov 15 '13 at 17:18
@BlackBear - 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. – Maciej Stachowski Nov 15 '13 at 17:27
@MaciejStachowski It sounds reasonable. I was not expecting a variable named version to be updated in such a way ;) – BlackBear Nov 15 '13 at 17:29
2

@BlackBear - 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 :) – Maciej Stachowski Nov 15 '13 at 17:31

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

3 Answers3