6 ms·

"Lockless" sounds very positive, and it's tempting to think that everything should be made lockless. However, it's less great than it sounds. Mutexes are very

• corbet 3y ago
  Even an uncontended mutex can create a lot of cache-line bouncing, making it less cheap than it seems.
  • gsliepen 3y ago
    But a lockless algorithm would have the same amount of cache-line bouncing in the uncontended case. In the LWN series about lockless algorithms, there is a lot of detail about the atomic primitives used in them, but apart from ringbuffers, linked lists and RCU, I actually didn't see any mention of higher level lockless algorithms. For single-producer, single-consumer queues and for linked lists, lockless algorithms are known and performant, but many others are either not that performant, or they come with severe restrictions. For example, RCU sounds great, but you have to worry about grace periods, and you should only use it when you read much more often than you modify.
    • cryptonector 3y ago
      I've an RCU-like scheme that's performant and doesn't have anything like grace periods, and it works in user-land. https://github.com/cryptonector/ctp https://github.com/cryptonector/ctp
      • slaymaker1907 3y ago
        Just looking at this initially, thread_safe_var_init is not correct. There is no guarantee whatsoever that "*vpp = vp" actually does anything, the compiler is perfectly free to just never allocate vp and just use the memory at vpp (thus allowing partial initialization) and the situation is even worse on ARM. You need some sort of memory barrier between that last assignment and it should probably be a volatile/std::atomic pointer.
        • cryptonector 3y ago
          Hmmm, good point, the init function does need a memory barrier. Thanks for the review!
        • cryptonector 3y ago
          I fixed that. TSAN also found a pair of data races involving assert()s (oof). All three are fixed.
        • cryptonector 3y ago
          I've added use of Helgrind's `ANNOTATE_HAPPENS_BEFORE()` and `ANNOTATE_HAPPENS_AFTER()` macros to the functions in `atomics.c` and now this is Helgrind-clean as well as TSAN-clean. The only bugs found by TSAN (as noted in another reply) were the one you found and two assert()s that didn't use atomics. Those two asserts could be a big problem if one ran a non-NDEBUG build in production. So now this is TSAN- and Helgrind-clean. Thanks for prompting me to do this extra work!
      • nyanpasu64 3y ago
        > O(N log(N)) where N is the maximum number of live threads that have read the variable and M is the number of values that have been set and possibly released). If you reference N twice and M zero times, why did you define M? Did you make a typo in the O() or is this intentional? > Most threads only ever need to call thread_safe_var_get(). > reference count the data. Does getting a new value automatically release a reference to the old one (so it's no longer safe to read)?
• danbruc 3y ago
  Another problem with lockless is that you can't turn every algorithm into a lockless one, it's actually only a handful of them that are practical to implement locklessly. You can make every data structure lock-free, even wait-free, there are universal constructions [1]. The resulting performance may however be prohibitive. [1] https://www.researchgate.net/publication/221343511_Impossibility_and_Universality_Results_for_Wait-Free_Synchronization https://www.researchgate.net/publication/221343511_Impossibi...
  • cryptonector 3y ago
    Well, yes, but the appeal of lockless data structures is that they generally perform very well because they don't require sleeping, and sleeping is bad because context switching is expensive. A lockless data structure that doesn't perform or scale better than a traditional blocking data structure is just not worth using (though it might be worth talking about).
• spacechild1 3y ago
  You are totally right. Here's my rough personal guideline: prefer mutexes over lockfree code - unless you can't. For example, you cannot lock a mutex from the audio callback because it might put the thread to sleep and you would miss your deadline. (For anyone interested in this topic: http://www.rossbencina.com/code/real-time-audio-programming-101-time-waits-for-nothing http://www.rossbencina.com/code/real-time-audio-programming-...)
  • gpderetta 3y ago
    Similar issues with locking mutexes from signal handlers or from high priority threads (if you want to avoid prio-inversion).
  • oriolid 3y ago
    If putting the thread to sleep would be the problem, simple try_to_lock instead of blocking would be the solution. In practice, it looks like releasing the lock and potentially waking up threads that were blocking on it is another problem (https://timur.audio/using-locks-in-real-time-audio-processing-safely https://timur.audio/using-locks-in-real-time-audio-processin...) For what it's worth, on macOS profiling audio apps shows that the OS itself is using mutexes on audio thread and it doesn't seem to be a problem. The popular JUCE libraries add another set of mutexes.
    • gpderetta 3y ago
      try_lock fails. Then what?
      • deleted 3y ago
        [deleted]
      • oriolid 3y ago
        Citing TFA, > If you’re less lucky, you’ll have to switch your audio effect to bypass mode, or perhaps fade out, or some similar fallback strategy. It’s probably not ideal, but in many cases still better than a glitch.
• dist1ll 3y ago
  To add to this, the superset of these ideas is referred to as "non-blocking", and lock-freedom is one flavor. There is also obstruction-freedom, starvation-freedom, wait-freedom, etc.. All of which have their own trade-offs and complexities. If you're interested in some literature, McKenney's book[0] is considered a great practical introduction to these ideas. (also discussed before on HN [1][2]) In applications where you're willing to trade throughput for latency (like RTOS schedulers, drivers, audio processing), it can often make sense to go for a wait-free data structure. [0] https://arxiv.org/pdf/1701.00854.pdf https://arxiv.org/pdf/1701.00854.pdf [1] https://news.ycombinator.com/item?id=34859102 https://news.ycombinator.com/item?id=34859102 [2] https://news.ycombinator.com/item?id=26537298 https://news.ycombinator.com/item?id=26537298
• klabb3 3y ago
  > Mutexes are very cheap in the uncontended case It was a while ago I was deep into this mess so forgive any ignorance–but–iirc the thread-mutex dogma[1] has many pitfalls despite being so widely used. Primarily they’re easy to misuse (deadlocks, holding a lock across a suspend point), and have unpredictable performance because they span so far into compiler, OS and CPU territory (instruction reordering, cache line invalidation, mode switches etc). Also on Arm it’s unclear if mutices are as cheap because of the relaxed memory order(?). Finally code with mutices are hard to test exhaustively, and are prone to heisenbugs. Now, many if not most of the above apply to anything with atomics, so lock-free/wait-free won’t help either. There’s a reason why a lot of concurrency is ~phd level on the theoretical side, as well as deeply coupled with the gritty realities of hardware/compilers/os on the engineering side. That said, I still think there’s room for a slightly expanded concurrency toolbox for mortals. For instance, a well implemented concurrent queue can be a significant improvement for many workflows, perhaps even with native OS support (io_uring style)?. Another exciting example is concurrency permutation test frameworks[2] for atomics that reorder operations in order to synthetically trigger rare logical race conditions. I’ve also personally had great experience with the Golang race detector. I hope we see some convergence on some of this stuff within a few years. Concurrency is still incredibly hard to get right. [1]: I say this only because CS degrees has preached mutices to as the silver bullet for decades. [2]: https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom
  • gpderetta 3y ago
    I think the issues with concurrency are at this point greatly overblown. Is it hard? Maybe, so it are a lot of things in our field. Is it phd level? Not at all, unless you are literally breaking new ground; most problems have very well known solutions. Mutexes are a solution to the mutual exclusion problem, no more no less. Sometimes this problem can be solved by a queue, but that opens other large cans of worms like asynchronicity. I write more lock-less [1] code than most, but I will often fall back to a mutex as the right solution for a problem given a complexity and performance budget. [1] by that I mean code without standard use of mutexes, not necessarily non-blocking.
    • nyanpasu64 3y ago
• dataflow 3y ago
  > Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. You'll need to expand on this, since mutex acquisition also requires similar atomic read-modify-write operations. I think what you may be trying to say is that lockless algorithms require more of these operations as they scale to more processors?
  • gsliepen 3y ago
    Yes, only a few lockless algorithms require only a single atomic operation. And as soon as you need to do cmpxchg in a loop and there is contention, you can burn a lot of cycles while cache lines bounce between cores, potentially an unbounded number of cycles if it is not a wait-free algorithm. While a mutex would have to pay the price of a futex call in the contended case, it is at least bounded.
    • dataflow 3y ago
      Yeah. Now what about cases where the max contention is bounded (say, at most 2 threads waiting on a lock)? And what about factors other than running time? How does, say, fairness affect this picture?
      • gsliepen 3y ago
        If multiple cores are trying to do atomic operations on the same value, the hardware typically is not fair. For mutexes, it depends on whether the operating system wakes up waiters in a fair way. Often that is not fully fair either. If there are only two threads at most, you can sometimes use a different algorithm than if you have an arbitrary number of threads (for example, for single-producer, single-consumer queues, lockless is typically better than with a mutex). You should of course benchmark your particular problem to see what solution is actually faster.
• loeg 3y ago
  Mutexes are implemented with (among other) cmpxchg instructions under the hood. It’s sort of a false dichotomy to divide the world into locks and cmpxchgs. Also inconsistent to claim they are slow but uncontended mutexes are fast. It is certainly true that you can write slower and harder to understand algorithms using atomic primitives instead of mutexes.
  • slaymaker1907 3y ago
    This is a common misunderstanding but just because you use cmpxchgs and other similar instructions has nothing to do with being lockfree. Lockfree really means *dead*lock free since it guarantees that some thread always makes progress. This is far more difficult than it sounds since you can't assume that some particular thread (like the one holding a lock) is ever scheduled. Some models relax this a bit though and do assume a thread requesting to execute will eventually execute in which case systems with mutexes can be lockfree.
    • loeg 3y ago
      I was responding specifically to this claim in the original comment: > Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. Not interested in getting into a pedantic argument about the definition of "lockless" or "lockfree."
• mattpallissard 3y ago
  > You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. I'm with you. If you aren't benchmarking your datastructure changes, you probably shouldn't be messing around with lock-free code to begin with.
• themulticaster 3y ago
  I'd like to add some context as to why lockless algorithms are popular in the Linux kernel. Roughly speaking, there are two possible scenarios in which kernel code is executed: Either in context of a process (e.g. while handling a syscall) or while handling an interrupt [1]. Now, a mutex usually sets the current thread to sleep if it tries to lock a currently locked mutex. Even in kernel land, this is perfectly fine as long as the kernel is in process context. However, while handling an interrupt there is no current thread that can be put to sleep. Therefore you can't use a mutex for kernel data structures that will be accessed during interrupts, and that applies to a lot of data structures. This is why some common locking advice does not really apply to kernel code. Another example would be "avoid using spinlocks, prefer a mutex" - spinlocks are widely used in the kernel since they're the most straightforward alternative to mutexes. Not disagreeing with the parent post, just wanted to add some context why LWN likes to talk about lockless algorithms. [1] Actually, the kernel differentiates between hardirqs and softirqs, but that's not important here.
  • gsliepen 3y ago
    Indeed. Also, spinlocks are not that great in userlang where one thread can preempt another thread that is holding a spinlock, which means threads on other cores that also want that lock would spin for a whole timeslice and burn a huge amount of cycles. In the kernel, spinlocks are typically taken at the same time IRQs for the current core are disabled, which avoids this issue (and deadlocks of course).
    • afr0ck 3y ago
      You don't have to disable IRQs if the spinlock is never taken by an interrupt handler. Disabling preemption would be enough in such a case, and that reduces latency issues related to disabling IRQs.
  • cryptonector 3y ago
    You're describing the top-half and bottom-half driver model that's been part of Unix since forever. Indeed, bottom-half code can't sleep or block in any way, and that's a problem even in single-CPU systems like the ones Unix grew up on. There's ways to deal with this other than lockless data structures, though lockless data structures help, naturally. The reason lockless data structures are popular is performance and scalability, and they're popular in user-land as much as in kernel-land, and in the Linux kernel as much as in any other OS. The idea is to make sure that you don't block because context switches are expensive, but also not to spin for a long time either because that can be even worse than blocking. Along the way you want to make sure that contention is not a problem and that the algorithm scales to many CPUs and lots of racing, and that it's free of race condition bugs.
• dfox 3y ago
  The problem with typical OS-provided mutex is that it is almost always in some way distinctly non-cheap either because of the particular implementation or because of limitations imposed by ABI/API compatibility (and in some case both).
• bsder 3y ago
  > You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. I would, in fact, give precisely the reverse advice for one reason: Mutexs don't compose. Mutexs are really good at putting subtle bugs into your code that are ridiculously difficult to figure out. Lockless algorithms may be slower or cause performance issues, but they don't malfunction because you got the release order backwards.
  • cryptonector 3y ago
    > Mutexs don't compose. The don't compose because (as you hinted) lock taking/releasing order has to be the same for all callers, but if mutexes are being taken behind the scenes then API usage order becomes critical, and it is trivial to screw that up. > Lockless algorithms may be slower or cause performance issues, but they don't malfunction because you got the release order backwards. And they may scale better. Scalability is important. For me the classic case is rw locks vs. RCU-ish schemes. I think there's no case where rw locks are ever appropriate if you have an RCU-ish alternative. For example, OpenSSL uses only rw locks -- nuts!
  • gsliepen 3y ago
    I see your point, but as a counterpoint, consider that you have two or more distinct data structures, for example several separate linked lists. What if you need to update multiple lists in one atomic operation? With mutexes, you can do this rather easily: either you have one mutex that guards all lists, or you have one mutex for each list and you ensure you always take them in the same order. I would think that qualifies as composing. However, you can't easily compose a lockless algorithm that works on one list to make it work on multiple at the same time.
• cryptonector 3y ago
  You're too focused on "mutex". There are many more interesting constructs that one can build in a lockless manner: lists, hash tables, RCU, etc. Here's some of mine: https://github.com/cryptonector/ctp/ https://github.com/cryptonector/ctp/
• kerkeslager 3y ago
  > You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. This is true for all optimizations: optimizations should be chosen based on profiling, not based on reasoning about the programs. Reasoning can give you ideas of what to profile, but modern programs, including the environments in which they run, are complex enough that you can never really be sure that the assumptions you're basing your reasoning on are true. So I fully agree with this, but I have some questions about the rest of your post. > Mutexes are very cheap in the uncontended case, and in the contended case they have some nice properties. Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. My (very limited) experience in this area is mostly with optimistic lock-free algorithms, so maybe there's something that I'm missing. But my understanding of optimistic lock-free algorithms is that they make use of the idea that the uncontended case is the most common case, and try to optimize that case heavily. On Intel processors, a compare-and-exchange operation should literally be a single instruction (CMPXCHG[1]). So I'm wondering how the uncontested case using a mutex could be seen as a positive? > Another problem with lockless is that you can't turn every algorithm into a lockless one, it's actually only a handful of them that are practical to implement locklessly. How could "you can't turn every algorithm into a lockless one" could be true? It seems to me that you can "simulate" an atomic compare and swap using mutexes--although I can't find a reference easily, I believe this is what GCC's __sync_X_compare_and_swap does on architectures which don't have a compare-and-exchange instruction. Likewise you can implement a mutex fairly easily using a compare-and-swap operation. Whether this is practical would of course depend on the situation--implementing a mutex in terms of compare-and-exchange or vice-versa are likely not the optimal ways to implement either. But it seems to me that if compare-and-exchange and mutexes can be implemented in terms of each other, isn't that a trivial proof that any mutex algorithm can be implemented as a lock-free algorithm and vice-versa? [1] https://www.felixcloutier.com/x86/cmpxchg https://www.felixcloutier.com/x86/cmpxchg
  • BazookaMusic 3y ago
    What you're describing about writing a mutex with cmpxchg is a spinlock. If you just use that operation it's also a very inefficient spinlock. The point of a lock free algorithm is to avoid having a thread wait on a resource and not do any work. It may do useless work that needs to be reverted, but it's not sleeping or spinning until something happens. It's not guaranteed that you can do that for every algorithm in a way that makes sense performance wise. Here's a nice resource I used on my thesis for an adequate but not perfect spinlock with atomic instructions: https://rigtorp.se/spinlock/ https://rigtorp.se/spinlock/
• duped 3y ago
  I think even this muddies the waters - oftentimes people think of performance in terms of metrics (latency, bandwidth, memory, etc). Lock-free algorithms are about performance guarantees. Specifically, a lock-free algorithm is appropriate if it would be considered an error for one thread to stall and cause any other threads to stall. An example of this would be a concurrent garbage collector. These are used when you do not want garbage collection to stop a program from executing. The way that the GC thread communicates with the rest of the program therefore must be lock-free. That's not to say a stop-the-world GC could be faster: just that its lack of performance guarantees would be considered a bug.