4 ms·
The importance and value of lock-free programming is massively overrated. I routinely improve performance and also reliability of systems by deleting lock-free
by ncmncm 6y ago
The importance and value of lock-free programming is massively overrated.
I routinely improve performance and also reliability of systems by deleting lock-free queues. The secret to both is reduced coupling, which lock-free methods do nothing to help with. Atomic operations invoke hardware mechanisms that, at base, are hardly different from locks. While they won't deadlock by themselves, they are so hard to get right that failures equally as bad as deadlocking are hard to avoid.
So, replace threads with separate processes that communicate via ring buffers, and batch work to make interaction less frequent. With interaction infrequent enough, time spent synchronizing, when you actually do it, becomes negligible.
- KMag 6y ago> So, replace threads with separate processes that communicate via ring buffers ... but those ringbuffers you're using presumably have a lockfree fast path with a futex or pthread mutex slow path to prevent the consumer from busy-waiting, so you're still taking advantage of lockfree data structures.
- ncmncm 6y agoYou may presume so, but you would be wrong. They are technically (also) lock-free, so require atomic operations when announcing additions, but being written by only one process, ownership of cache lines never changes, so hardware locks are not engaged. Readers do poll, and sleep as long as the tolerated latency when nothing new is found. Writers batch additions, and announce new entries only just so frequently.
- KMag 6y agoInteresting, though the overhead of nanosleep vs. futex wait with non-NULL timeout should be dwarfed by the context switch. I can see where if you have extreme latency and/or throughput constraints on the writer side of the ring buffer, you couldn't afford the extra atomic read and occasional futex wake on the writer side to wake the consumer. > but being written by only one process, ownership of cache lines never changes, so hardware locks are not engaged. Which cache coherency protocol are you referring to where cache lines are "locked"? I'm aware that early multiprocessor systems locked the whole memory bus for atomic operations, but my understanding is that most modern processors use advanced variants on the MESI protocol[0]. In the MOESI variant, an atomic write (or any write, for that matter) would put the cache line in the O state in the writing core's cache. If we had to label cache line states as either "locked" or "unlocked", the M, O, and E states would be "locked", and S and I would be "unlocked". Your knowledge of cache coherency protocols is probably much better than mine, so I'm probably just misinterpreting your shorthand jargon for "locked" cache lines. By "hardware locks are not engaged" do you just mean that the O state doesn't ping-pong between cores? [0] http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2...
- ncmncm 6y ago> * .. .you just mean that the O state doesn't ping-pong between cores?* Correct. My terminology was sloppy, sorry. I have no experience of this "context switch" you speak of; my processes are pinned and don't do system calls or get interrupted. :-) The writing core retains ownership of the cache lines, so no expensive negotiation with other caches occurs. When the writer writes, corresponding cache lines for other cores get invalidated, and when a reader reads, that core's cache requests a current copy of the writer's cache line. The reader can poll its own cache line as frequently as it likes without generating bus congestion, because no invalidation comes in until a write happens. There is a newish Intel instruction that just sleeps waiting for a cache line to be invalidated, that doesn't compete for execution resources with the other hyperthread, or burn watts. Of course compilers don't know it. I don't know if AMD has adopted it, but would like to know; I don't recall its name.
- adwn 6y agoI agree with regards to lock-free not being faster than lock-based, but that: > replace threads with separate processes that communicate via ring buffers does not follow at all. Interprocess communication is always more work to set up and less efficient [1] than interthread communication. The only thing separate processes gain you is enforced memory protection. [1] Different processes need different TLB entries, while different threads in the same process do not.
- gpderetta 6y agoTLB is not necessarily an issue as presumably you would be running the processes on different cores. The primary problem is that separate address spaces requires messages to be serialized (although of course serialization can be trivial). With shared memory you can share (or transfer ownership of) data by simply sharing a pointer.
- ncmncm 6y agoTLB usage is an advantage as each process, pinned to a core, gets its own. TLB shootdowns vanish. Cache line ownership, similarly, does not pingpong. Sharing pointers causes fragility, as failure in one thread takes down the whole system. Transferring ownership would add coupling. But such objects can live in a shared-memory area. Pointers into shared regions do require some care. Ideally, only one process ever owns objects in each, most commonly just the ring buffer. With separate processes, they may come and go as needed. Yes, setting up shared memory for ring buffers is more work, but interactions establishing them are not fast-path. Decoupling via separate processes is a different architecture, but has real benefits to motivate it.
- gpderetta 6y agoOh, I agree, it is all tradeoffs. Losing the ability to cheaply share objects, including closures, is a big tradeoff though. BTW lock free queues and data structures are pretty much required for interprocess sharing, unless you really want to deal with robust mutexes (and you don't!)