4 ms·

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

by klabb3 4y 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 4y 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 4y ago
  The nasty part of concurrency bugs is that normally you can expect the code is almost correct and needs some tweaks to fix oversights, but concurrency bugs in incompletely thought-out code more often requires throwing out the design to build it right. Additionally, concurrency issues usually arise from multiple components interacting in nonlocal ways, requiring a global knowledge of the system to diagnose and fix. And finding the presence of a bug or reproducing it is usually probabilistic, making concurrency heisenbugs hard to discover, locate, and prove they're fixed. It can be made somewhat tractable to experienced concurrency wizards; I think Rust's "cross-thread shared ^ mutable" rule is a good starting point, but have less experience with Go, JS, or Erlang-style approaches.
  - gautamdivgi 4y ago
    Aren’t there formal analysis techniques that can help ferret those out? My MSCS had a course called “science of programming”. The focus used to be proofs for correctness of programs, which included concurrent programs.
    - rerdavies 4y ago
      I've certainly heard of such things. If there's a tool to prove that my 135,000 lines of C++ are formally correct, I'm up for it. :-)
- myrmidon 4y ago
  From my point of view, the issues with concurrency (specifically the shared memory "threadlike"-kind) are absolutely NOT overblown, because misuse of that mechanism can completely RUIN a codebase in a way that few other things can; "goto" abuse would be a good analogy, or massive amounts of partly redundant global state. My perception is that other comparably dangerous mechanisms are taught with appropriate caveats-- you WILL typically be admonished to keep variables as local as possible, learn how to encapsulate state, and probably be instructed to ALWAYS use proper loops, conditionals and function calls instead of wild gotos-- it does not even matter if you learn programming in university or on your own. But with threading this is not the case, you'll typically get handed threading primitives without much prejudice, with predictable results.
nyanpasu64 4y ago
In addition to lock-free queues, I think another important lock-free primitive is a cell where writing a value drops previous values, even if they haven't been read, used for eg. time of day, volume levels passed from an audio thread to a GUI VU meter, and the like. Implementations include word-sized relaxed atomics (bigger tears), SPSC triple buffers (doesn't generalize to >2 threads), or other days structures I don't understand as well, like RCU or hazard pointers.
- klabb3 4y ago
  Yes! I’ve used atomics for metric counters (MPMC) with reasonable success. But for anything larger than an atomic uint64, you’d need good library support. Fortunately this can be solved without OS support in an optimistic fashion (atomic retry loop), right?
  - nyanpasu64 4y ago
    By an atomic retry loop, do you mean reading a generation, reading a set of values, then checking the generation is consistent? These kinds of seqlocks have interesting codegen challenges with the C++11 threading memory model (https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf).
- cryptonector 4y ago
  > another important lock-free primitive is a cell where writing a value drops previous values, even if they haven't been read More importantly, if you've read a value then that value should stay alive (not be destructed/collected) until you explicitly release it or re-read that "cell". Then what you do is publish immutable data to the "cell". Unlike rw locks there's neither the risk of readers blocking behind writers nor writers being starved, and it's highly concurrent. Clojure has a `ref` for this. Linux has RCU, which is a bit like this. I've implemented just that in a lockless way twice (see elsewhere in this thread) with this C API: typedef struct thread_safe_var *thread_safe_var; /* TSV */ typedef void (*thread_safe_var_dtor_f)(void *); /* Value destructor */ /* Initialize a TSV with a given value destructor */ int thread_safe_var_init(thread_safe_var *, thread_safe_var_dtor_f); /* Destroy a TSV */ void thread_safe_var_destroy(thread_safe_var); /* Get the current value of the TSV and a version number for it */ int thread_safe_var_get(thread_safe_var, void **, uint64_t *); /* Release the reference to the last value read by this thread from the TSV */ void thread_safe_var_release(thread_safe_var); /* Wait for a value to be set on the TSV */ int thread_safe_var_wait(thread_safe_var); /* Set a new value on the TSV (outputs the new version) */ int thread_safe_var_set(thread_safe_var, void *, uint64_t *);

by klabb3 4y ago

gpderetta 4y 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 4y ago
The nasty part of concurrency bugs is that normally you can expect the code is almost correct and needs some tweaks to fix oversights, but concurrency bugs in incompletely thought-out code more often requires throwing out the design to build it right. Additionally, concurrency issues usually arise from multiple components interacting in nonlocal ways, requiring a global knowledge of the system to diagnose and fix. And finding the presence of a bug or reproducing it is usually probabilistic, making concurrency heisenbugs hard to discover, locate, and prove they're fixed. It can be made somewhat tractable to experienced concurrency wizards; I think Rust's "cross-thread shared ^ mutable" rule is a good starting point, but have less experience with Go, JS, or Erlang-style approaches.
- gautamdivgi 4y ago
  Aren’t there formal analysis techniques that can help ferret those out? My MSCS had a course called “science of programming”. The focus used to be proofs for correctness of programs, which included concurrent programs.
  - rerdavies 4y ago
    I've certainly heard of such things. If there's a tool to prove that my 135,000 lines of C++ are formally correct, I'm up for it. :-)
myrmidon 4y ago
From my point of view, the issues with concurrency (specifically the shared memory "threadlike"-kind) are absolutely NOT overblown, because misuse of that mechanism can completely RUIN a codebase in a way that few other things can; "goto" abuse would be a good analogy, or massive amounts of partly redundant global state. My perception is that other comparably dangerous mechanisms are taught with appropriate caveats-- you WILL typically be admonished to keep variables as local as possible, learn how to encapsulate state, and probably be instructed to ALWAYS use proper loops, conditionals and function calls instead of wild gotos-- it does not even matter if you learn programming in university or on your own. But with threading this is not the case, you'll typically get handed threading primitives without much prejudice, with predictable results.

nyanpasu64 4y ago

In addition to lock-free queues, I think another important lock-free primitive is a cell where writing a value drops previous values, even if they haven't been read, used for eg. time of day, volume levels passed from an audio thread to a GUI VU meter, and the like. Implementations include word-sized relaxed atomics (bigger tears), SPSC triple buffers (doesn't generalize to >2 threads), or other days structures I don't understand as well, like RCU or hazard pointers.

klabb3 4y ago
Yes! I’ve used atomics for metric counters (MPMC) with reasonable success. But for anything larger than an atomic uint64, you’d need good library support. Fortunately this can be solved without OS support in an optimistic fashion (atomic retry loop), right?
- nyanpasu64 4y ago
  By an atomic retry loop, do you mean reading a generation, reading a set of values, then checking the generation is consistent? These kinds of seqlocks have interesting codegen challenges with the C++11 threading memory model (https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf).
cryptonector 4y ago
> another important lock-free primitive is a cell where writing a value drops previous values, even if they haven't been read More importantly, if you've read a value then that value should stay alive (not be destructed/collected) until you explicitly release it or re-read that "cell". Then what you do is publish immutable data to the "cell". Unlike rw locks there's neither the risk of readers blocking behind writers nor writers being starved, and it's highly concurrent. Clojure has a `ref` for this. Linux has RCU, which is a bit like this. I've implemented just that in a lockless way twice (see elsewhere in this thread) with this C API: typedef struct thread_safe_var *thread_safe_var; /* TSV */ typedef void (*thread_safe_var_dtor_f)(void *); /* Value destructor */ /* Initialize a TSV with a given value destructor */ int thread_safe_var_init(thread_safe_var *, thread_safe_var_dtor_f); /* Destroy a TSV */ void thread_safe_var_destroy(thread_safe_var); /* Get the current value of the TSV and a version number for it */ int thread_safe_var_get(thread_safe_var, void **, uint64_t *); /* Release the reference to the last value read by this thread from the TSV */ void thread_safe_var_release(thread_safe_var); /* Wait for a value to be set on the TSV */ int thread_safe_var_wait(thread_safe_var); /* Set a new value on the TSV (outputs the new version) */ int thread_safe_var_set(thread_safe_var, void *, uint64_t *);