3 ms·
If you enforce that the buffer size is a power of 2 you just use a mask to do the if (next_head == buffer.size()) next_head = 0; part
by secondcoming 6mo ago
If you enforce that the buffer size is a power of 2 you just use a mask to do the
if (next_head == buffer.size())
next_head = 0;
part
- JonChesterfield 6mo agoIf it's a power of two, you don't need the branch at all. Let the unsigned index wrap.
- dalvrosa 6mo agoInteresting, I've never heard about anybody using this. Maybe a bit unreadable? But yeah, should work :)
- mandarax8 6mo agoSee https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff... which takes it even further :)
- dalvrosa 6mo agoNice one!
- loeg 6mo agoI believe ConcurrencyKit's impl does this. https://github.com/concurrencykit/ck/blob/master/include/ck_ring.h#L124 https://github.com/concurrencykit/ck/blob/master/include/ck_...
- loeg 6mo agoYou ultimately need a mask to access the correct slot in the ring. But it's true that you can leave unmasked values in your reader/writer indices.
- dalvrosa 6mo agoIndeed that's true. That extra constraint enables further optimization It's mentioned in the post, but worth reiterating!
- foobar10000 6mo agoNice! Should be able to push it more if * we limit data shared to an atomic-writable size and have a sentinel - less mucking around with cached indexes - just spinning on (buffer_[rpos_]!=sentinel) (atomic style with proper sematics, etc..). * buffer size is compile-time - then mod becomes compile-time (and if a power of 2 - just a bitmask) - and so we can just use a 64-bit uint to just count increments, not position. No branch to wrap the index to 0. Also, I think there's a chunk of false sharing if the reader is 2 or 3 ahead of the writer - so performance will be best if reader and writer are cachline apart - but will slow down if they are sharing the same cacheline (and buffer_[12] and buffer_[13] very well may if the payload is small). Several solutions to this - disruptor patter or use a cycle from group theory - i.e. buffer[_wpos%9] for example (9 needs to be computed based on cache line size and size of payload). I've seen these be able to pushed to about clockspeed/3 for uint64 payload writes on modern AMD chips on same CCD.
- loeg 6mo agoThis was, in fact, mentioned in the article.