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.
> 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 *);
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?
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).
