Simplify your locking strategy — simpler is better


Well I didn’t mean to but it seems I’m writing a series of articles on locking. 


Based on my last posting I got several requests for a simple example of a case that could be improved with simpler locking.  Here’s something of that ilk that’s similar to something I encountered in The Real World.  The 2nd choice is based on what I recommended.


 

    class FreeThreaded1
{
private static volatile Dictionary dict = new Dictionary();

static void UpdateThreadProc() // one thread runs this
{
for (;;)
{
using (StreamReader sr = new StreamReader(“c:\\pickupdir\\dictionary.txt”))
{
lock (dict)
{
dict.Clear();

String line = null;

while (null != (line = sr.ReadLine()))
{
int iTab = line.IndexOf(‘\t’);

if (iTab < 1 || iTab > line.Length-2)
continue;

string key = line.Substring(0, iTab);
string val = line.Substring(iTab+1);

dict.Add(key, val);
}
}
}

System.Threading.Thread.Sleep(5000);
}
}

static string ReadEntry(string s) // this is called by many threads at random
{
lock (dict)
{
return dict[s];
}
}
}

class FreeThreaded2
{
private static volatile Dictionary dict = new Dictionary();

static void UpdateThreadProc() // one thread runs this
{
for (;;)
{
using (StreamReader sr = new StreamReader(“c:\\pickupdir\\dictionary.txt”))
{
Dictionary d = new Dictionary();
String line = null;

while (null != (line = sr.ReadLine()))
{
int iTab = line.IndexOf(‘\t’);

if (iTab < 1 || iTab > line.Length-2)
continue;

string key = line.Substring(0, iTab);
string val = line.Substring(iTab+1);

d.Add(key, val);
}
dict = d;
}

System.Threading.Thread.Sleep(5000);
}
}

static string ReadEntry(string s) // this is called by many threads at random
{
return dict[s];
}
}

Can you spot at least 3 reasons why I would like the 2nd one better? Not that it’s perfect…

Comments (18)

  1. Well…

    – Avoids locks (probably faster)

    – Atomic commits (don’t run into getting half an updated dictionary)

    – Less code (clearer and probably more bug-free, especially when there’s less concurrency-related code)

  2. Ayende Rahien says:

    It looks like the second version should be better memory wise since the dict instance will be collected as one instance, instead of it having to do the work for clear()

  3. Stan says:

    Obviously, in the second version the ReadEntry method is available 100% of time with no delays at all while in the first version it may become a significant (tens of seconds) bottleneck especially if the text file is huge.

    Secondly, there are a lot of string allocations inside the cycle. In the first example there is a high chance that the collection will happen inside the lock which would increase the wait time in ReadEntry even further.

    Lastly if the text file has  duplicate keys that would cause an exception in d.Add (in both versions) but in the first version that would leave the dictionary in a partially filled state.

  4. georgem says:

    The FreeThreaded2 is better, reasons:

    – less locking, especially when calling the ReadEntry – assuming this is called quite often = faster application run

    – the contention is not transferred to other threads (while filling the new dictionary the other threads are still served from the old one) *can be also disadvantage, depending on the situation.

    – I guess there is some advantage in allocating new dictionary over calling Clear.

    disadvantage – assumes that dict = d; is an atomic operation.

  5. manojv says:

    Does volatile keyword protect dict from processor reordering? Or is a call to System.Threading.Thread.WriteMemoryBarrier() required?

  6. manojv says:

    Also with the no lock approach, if a context switch happens while processing dict[s] and the value of dict changes, can the old dict be garbage collected?

  7. Thomas says:

    disadvantage – assumes that dict = d; is an atomic operation.

    Why wouldn’t it be? It’s only updating a reference.

  8. Eyal says:

    Is the following line guranteed to be atmoic?

    dict = d;

    Isn’t it possible that

    return dict[s];

    would get a corrupted reference?

    I’d use Interlocked.Exchange for that line.

  9. That’s the point of the volatile keyword. It makes sure that the line "dict = d;" is atomic.

  10. jrista says:

    The volatile keyword forces a full update of a reference all the way out to system memory whenver that variable changes on any thread, so "dict = d;" would indeed be an atomic operation.

  11. Alois Kraus says:

    I am also quite interested when an operation is atomic and when not. MemoryBarriers are a very interesting but I do not know by what means they can be replaced. I found them used in the BCL code:

    taken from System.Environment:

    private static void InitResourceHelper()

    {

         bool flag1 = false;

         bool flag2 = false;

         RuntimeHelpers.PrepareConstrainedRegions();

         try

         {

               RuntimeHelpers.PrepareConstrainedRegions();

               try

               {

               }

               finally

               {

                     Thread.BeginCriticalRegion();

                     flag1 = true;

                     Monitor.Enter(Environment.InternalSyncObject);

                     flag2 = true;

               }

               if (Environment.m_resHelper == null)

               {

                     Environment.ResourceHelper helper1 = new Environment.ResourceHelper();

                     Thread.MemoryBarrier();

                     Environment.m_resHelper = helper1;

               }

         }

         finally

         {

               if (flag2)

               {

                     Monitor.Exit(Environment.InternalSyncObject);

               }

               if (flag1)

               {

                     Thread.EndCriticalRegion();

               }

         }

    }

    I think it would be quite interesting to see why the code was this way written in terms of:

    – Concurrency

    – Exception Safety (Constrained Execution Regions)

    – Performance

    Yours,

     Alois Kraus

  12. georgem says:

    my docs says about volatile:

    The system always reads the current value of a volatile object at the point it is requested, even if the previous instruction asked for a value from the same object. Also, the value of the object is written immediately on assignment.

    Which says nothing about the write itself being actually atomic. That means if the write is say 2 non-atomic instructions, you can be interrupted in middle of the write and if you’ll read the memory meanwhile, you’ll get some semi-updated reference (say 1st 4bytes updated, 2nd not).

    Maybe I’m wrong on this, but I introduced a few locks just to be sure on this side.

  13. zahical says:

    georgem:

    If Iā€™m not mistaken, the atomicity of the assignment is guaranteed by the c# language. From the ECMA-334 (C# Specifications), 12.5 Atomicity of variable references: ‘Reads and writes of the following data types shall be atomic: bool, char, byte, sbyte, short, ushort,

    uint, int, float, and _reference types_. …’

  14. georgem says:

    Yes, better to read the specifications (although quite they are quite boring to read).

    It is specified in 12.6.6. of ECMA-335 (CLI):

    Object references shall be treated as though they are stored in the native word size.

    and

    All reads and writes of certain properly aligned data types are guaranteed to occur atomically.

    and

    A conforming CLI shall guarantee that read and write access to properly aligned memory locations no larger than the native word size (the size of type native int) is atomic (see §12.6.2) when all the write accesses to a location are the same size.

    you know, this is still flashbacks from the native world šŸ˜‰

  15. ricom says:

    As it happens the volatile is not even needed in this example.  I included it only to ensure that the reading threads would see the update as soon as possible.  But in this case it doesn’t actually matter if they see an old dictionary for a read or two — it will just appear to them that the update has not yet happened, which must necessarily be legal or the whole thing is doomed in the first place.

    As has been noted object writes are guaranteed atomic (so you see all of it or none of it) but they are not necessarily immediately visible unless volatile.

    I’m not going to dare to explain the complex environment example in just a few words… that one is in need of a 17 page article šŸ™‚

  16. Igor says:

    While the second sample has all the threading benefits mentioned above, the cost is double memory use during load. In the first example  dict is cleared before load, so all the entries can be garbage collected. In the second case, both fully-loaded dictionaries are in memory.

  17. ricom says:

    Igor makes a good point in his comment above.  The reality could be very interesting indeed.  

    For instance, in a perfect world, recycling the entire dictionary might be enough to keep it out of generation two at all times… thus making the memory much cheaper.

    Or the reverse could happen, freeing the entire dictionary might be a disaster because it lives just long enough to get into generation 2 and then dies… ergo it contributes to mid-life-crisis.

    Is either of these likely to be an issue?

    That’s a whole ‘nother article but feel free to comment.

  18. Maurits says:

    A further possibility for improvement… add another private variable to store the last-modification-time of the dictionary file.

    Have UpdateThreadProc parse the file the first time, then do a file stat to see if the file has changed since the last parse.

    If this is a real bottleneck, it becomes worthwhile to have a journal file that stores only changes.  UpdateThreadProc can integrate those changes into the shared dictionary while only reading the small journal file.  Another lazy thread can be run to integrate the journal file into the main file during periods of low activity.  This can be done in such a way that the journal file and the main file can both be accessed but for the time it takes to rename a file.