Hacker News Reader

Comment by ncmncm | Hacker News Reader

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.

View on HN

> 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.

You 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.

Interesting, 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.2...

> * .. .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.

I 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.

TLB 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.

TLB 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.

Oh, 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!)

I do it. Without mutexes.

I don't count single-writer ring buffers among the ordinary lock-free queues, because there is no competition for access, and cache lines never change ownership. So, none of the overheads show up. And, they are very easy to get right, so pose none of the risk of subtle heisenbugs.

Being able to kill and add downstream clients at random is worth a lot of architectural rejiggery.

It follows in a weird way: Processes requires more effort to communicate so you are less likely to send things across processes and when you do it is because it is worth it. You are also likely to batch the communication and then go off and compute.

All of the above improve performance. Nothing about it requires processes though, you can get the same results with threads if you take just as much care.

However processes do add one more thing: you can scale to multiple physical computers in ways threads can't.

> However processes do add one more thing: you can scale to multiple physical computers in ways threads can't.

Although this is technically true, communication with another system has orders of magnitude higher latency and lower bandwidth compared to other cores in the same CPU. So in practice, you'll typically have to redesign your approach anyway.

Separate processes means no TLB shoot-downs.

If you put ring buffers in hugepages, the number of TLB entries involved is small, typically 1. And, pinning the processes to cores, each gets its own set.

Reply on news.ycombinator.com