Thursday, January 9, 2014

Thoughts on Double Instance Locking

Some time ago, we talked about the "Double Instance Locking" which is a technique that using only reader-writer locks can provide lock-free read operations:

This technique is new, as far as we can tell, but it doesn't provide a particular performance improvement, at least when compared with the Left-Right technique.
Yet, the post on the Double Instance Locking is one of the highest read posts of this blog... I think the reason for its allure lies in its simplicity of understanding how it works, ease of implementation in any language, and perhaps even the ease of understanding why it works.
You see, one of the major problems with the Left-Right is that it is easy to understand the how it works because the algorithm is just a few lines of code, but understanding the why it works is waaayy trickier. We've had discussions with concurrency experts that are borderline absurd... it would go something like this:
Suppose you're showing a new machine that you invented to an acquaintance, and it's a "car". He looks at it for a while, checks under the hood, reads the specs and the mechanics diagrams and says something like this: "This is a very interesting idea! This device you call a car is capable if going extremely fast, it can transport people or merchandise, and it looks very cool. There's just one thing I don't understand: what is the purpose of these four round things? I believe you called them wheels?"

An now, where do you take it from here? What are you going to say to this guy? I don't know... start from the beginning I guess.

Some people seem to have the almost magical ability of transforming complex subjects into simple ideas, the best example I know is Richard Feynmann. He was able to make Relativity make sense, or even Quantum Mechanics (as impossible as it may seem). Some people just have a "knack" for distilling these complex ideas and presenting them in a clear and concise way. Another good example is Andreia, she has that capability, although not as good as Feynmann (sorry baby), she is orders of magnitude better at it than me  ;)
This kind of skill is obviously very valuable, and yes, it is partly a skill because you can get better at it with practice, but don't expect miraculous improvements.
Even more valuable, are the ideas that don't need to be distilled by these special people. Ideas that are so simple, that anyone can "get them" with a small amount of effort. These are the really powerful concepts, one can almost say "memes", due to their ease of replication, from brain to brain.

I would say that the Left-Right is, unfortunately, on the "complex spectrum". Andreia doesn't agree with me on this one, and I understand (you should see some of the other stuff she's been doing), but compared with the "Double Locking Instance", the Left-Right is much harder to understand. In fact, the Double Instance Locking is so easy to understand that pretty much anyone who understands the concept of a Reader-Writer Lock can understand how to use the Double Instance Lock, even if the explanation is given by me  :)
So I guess that is where the value of the Double Instance Locking comes from: it's ease of understanding... and the fact that you can implement it in any language, even those without a clearly defined memory model, or an atomics API, all you need is a reader-writer lock with try-readlock.

More on the Double Instance Locking here:

No comments:

Post a Comment