Last year I was supposed to go give a talk at CppCon but one week earlier I was getting surgery so I couldn't go. This year I was able to attend, and give a talk not just about Left-Right, but also about Progress Conditions and how they affect Latency.
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 :)
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 ;)
Another presentation from CppCon, this time by Jeff Preshing who is a Technical Architect at Ubisoft Montreal
The talk is divided into two sections, and I found the first part nice to watch because there were some different patterns for concurrency that are particular to video games, and to see the approaches that are used for those situations was really interesting. Video games are cool application because they have strong time constraints (they have to push out a frame every 1/30 or 1/60 of a second), so they care about latency and scalability in multicore environments.
The second part is about C++11 atomics and it's not so interesting, better watch Herb Sutter talk on the subject. It is cool that they intend to use C++11 atomics because they develop for several different platforms (x86, PowerPC, ARM) which means that using these atomics makes their life easier in terms of writing portable code across these platforms.
In the middle of the talk there is a question also from Michael Wong about relaxed atomics and whether they (the Ubisoft guys) use it for lock-free data structures, to which he answers no. Well, as it so happens, Andreia and I have discovered a lock-free linked list that uses relaxed atomics as we talked about on a previous post, and as far as I know, this is the only lock-free linked list using relaxed atomics currently in existence. Unfortunately, we only published a Java version, and the C++11 version will have to wait because we need to polish it a bit more.
Btw, if you don't know what they do at Ubisoft, one example is Assassin's Creed.
One of the talks on CppCon 2014 was given by Tony Van Eerd on the subject of lock-free queues.
The title of the talk is a bit misleading because although the techniques he describes are the ones used on lock-free algorithms and data structures, the queue shown on the presentation is not actually lock-free for either pop() or push().
The interesting thing about his talk is that he focuses on the thought process needed to arrive at a lock-free queue. Most papers and talks just give us the "end result" with the algorithm as it should be, but they don't explain why it has to be the way it is. His talk goes into the common pitfalls of designing a lock-free queue, which makes it particularly instructive for people new to the field.
There was one statement that caught my attention, that lock-free algorithms need to maintain invariants at all times. This is sooooo true!
The main reason why designing lock-free (and wait-free) data structures is hard, is due to the fact that the invariants must hold at every step of the way, for every method of the data structure, and every shared (atomic) variable. The more methods you have on a lock-free data structure, the more complex the problem becomes. The more variables are shared among those methods, the greater the complexity and possible interleavings, and higher number of states, where each one must still uphold all the invariants.
Designing data structures with locks is much easier because, the code within a lock()/unlock() can temporarily break invariants without worry, as long as the invariants are restored before the call to unlock().
