If you care about wait-free data structures (for reads) and about low latency software development, then I strongly recommend this talk.... but I'm totally biased ;)
Yes, that's me in the video... and no, your sound is not mutted, I just speak low, so you'll have to increase the volume :)
Presentation slides available on github
https://github.com/CppCon/CppCon2015/tree/master/Presentations/How%20to%20make%20your%20data%20structures%20wait-free%20for%20reads
PS: Big thanks to those of you who dropped by at the end of the talk to give some words of encouragement. Don't worry, Andreia and I are still cooking up new algorithms and data structures and will give more info soon ;)
First, GREAT talk about lock/wait-free data structures. Every time someone starts talking about some crazy no-lock-based algorithm I am afraid that it will make my head explode.
ReplyDeleteCould you answer, or point to a document that explains one thing: why does a writer need to wait for the readers of inactive index (this is the first thing that needs to be done after flipping the left-right switch)? It seems obvious for me that when a writer leaves the critical section it's guaranteed that there are no readers in the inactive index (as we waited for them) and all the new readers went to the currently active index.
Hi Bartosz,
DeleteI'm glad you enjoyed the talk :)
Here is the link to the Left-Right paper:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/left-right-2014.pdf
After flipping the leftRight switch, the Writer has to wait for Readers on the "inactive index" because there may
be some Readers that have arrived at the inactive index but are on the "active instance".
The leftRight and the versionIndex are two distinct variables (in this implementation) and because of that, there
is no way to make changes to both atomically, so one of tricks is that the Writer flips the leftRight first and then flip the versionIndex,
while the Readers read the versionIndex first and then read the leftRight. This means that we can have Readers on the
"inactive index" but on the "active instance", but never have Readers on the "active index" and on the "inactive instance".
Hello Bartosz,
DeleteI would like to add to Pedro explanation. One important thing is that the versionIndex where Readers arrive have no relation to what instance the leftRight is referring to. It is possible for a Reader to arrive to ReadIndicator with versionIndex 0 or 1, and will always go to the instance leftRight is referring to. The writer will have to always check both readIndicators.
It is necessary to start by checking the inactive versionIndex because afterwards we want to reuse that value of the versionIndex and guarantee that new Readers will read the newly set versionIndex. It is this mechanism that allows for Writers to wait only for older Readers. As soon as the Writer changes the versionIndex, it makes all new Readers arrive at that ReadIndicator, so the last ReadIndicator to be checked will only be used by older Readers where some of them can already be using the newly modified instance (or not), therefore the writer may be waiting unnecessarily for some Readers.
You can easily see that all combinations of leftRight and versionIndex are possible in the Readers diagram state machine.
Andreia