lockless data structures?
lockless data structures?
Posted Jul 31, 2008 20:02 UTC (Thu) by shapr (subscriber, #9077)Parent article: The lockless page cache
Is there a good reason linux doesn't have lots of lockless data structures all over the place? That would dramatically increase multi-core performance, yeah?
Posted Jul 31, 2008 21:38 UTC (Thu)
by bronson (subscriber, #4806)
[Link]
Posted Aug 1, 2008 1:43 UTC (Fri)
by maney (subscriber, #12630)
[Link] (1 responses)
My personal opinion is that lock-free algorithms are not a good generic synchronization
technique, and are definitely very very complex and difficult to understand. However, in
certain specific cases, lock-free can be simple, elegant, and a huge performance advantage
over traditional approaches.
Posted Aug 1, 2008 15:42 UTC (Fri)
by PaulMcKenney (✭ supporter ✭, #9624)
[Link]
We are still learning how best to use RCU to obtain good performance and scalability while keeping things (again, relatively) simple. For that matter, we are also still learning when not to use RCU. RCU is quite specialized, so is not always the right tool for the job, much though I might wish it otherwise. ;-)
Posted Aug 1, 2008 14:01 UTC (Fri)
by pflugstad (subscriber, #224)
[Link]
lockless data structures?
Yes. Lockless is quite simple in theory but gets really difficult in the real world (say,
where ring buffers actually wrap). You thought threading was hard to prove correct, debug,
and maintain? Lockless is harder in every way.
I converted a small event-based networking app I wrote two years ago to use lockless lists.
It was fun but ultimately a waste of time... It didn't run much faster but now it contained
subtle boundary conditions that, when violated by an unwary programmer, resulted in occasional
corruptions under load. Good luck trying to debug that (don't bother stepping through it in
gdb)!
There are a few areas where lockless really is worth it, especially when you have a hot,
high-contention buffer or stack. But be prepared for some tough maintenance.
From one of Val's responses to a question asked about the KHB: Synthesis article:
lockless data structures?
Val's comment is directed at lock-free synchronization, which is a very different animal than lockless algorithms.
The RCU implementation described in this article is lockless, but not lock-free: although RCU has deterministic read-side primitives, its updates can block via call_rcu() and synchronize_rcu().
In some cases, the fact that RCU's updates do block keeps things (relatively) simple.
lockless data structures?
Linus on lockless data structures
Linus posts in a long thread over on RealWorldTech about lockless algorithms and SMP scaling:
http://www.realworldtech.com/forums/index.cfm?action=deta...