Get the latest tech news
Cute trick for fetch-and-add-based queues
In a prototypical concurrent queue based on fetch-and-add (FAA), two concurrent enqueue operations will contend on two cache lines. First, they will contend on the queue head, and mediation will be required to determine who bumped it forward first.
(I’m going to assume a fairly typical configuration—64-byte cache lines, 8-byte queue elements—but the concepts are completely general; similarly, everything I say about producers applies equally well to consumers.) I’ve described this in terms of specific offsets in specific cache lines, assuming that the backing storage is aligned, but it is actually completely alignment-oblivious, and so works without modification even e.g. in cases where a garbage collector might change the alignment of the storage at runtime. The way I’ve presented this technique, we have to know the cache line size, but it’s worth noting that even if we slightly over- or under-estimate it, it is still helpful.
Or read this on Hacker News
