3 ms·

When I see you say “any brand of FIFO loses” in the same post as “what you need is a ring buffer”, it shows that there’s a terminology disconnect here: A “ring

When I see you say “any brand of FIFO loses” in the same post as “what you need is a ring buffer”, it shows that there’s a terminology disconnect here: A “ring buffer” used for streaming data is a brand of ”FIFO” :) Therefore, the implementation you’re suggesting is actually not all that different from my current solution, except for a few important details related to the particular problem I’m solving — e.g. handling many parallel streams which may momentarily drift out of sync (where those that are not delayed must still be processed without the state of other streams interfering to add latency), among other important details. Ultimately though, aside from this discussion on high performance designs (which though fun, would not work without you actually knowing the requirements of what I’m working on — e.g. it’s not HFT), I’m just glad we’re in agreement that there are applications where avoiding dynamic allocations is absolutely essential, and that it would be a huge mistake to add them to a high-performance language’s most fundamental integer types.

ncmncm 7y ago
That is an interesting problem. When I see it, the input streams tend to be ring buffers, and output is a priority queue of their heads, ordered by timestamp. Obviously a ring buffer is, literally, a first-in first-out medium. The essential difference between your typical FIFO and a ring buffer is the entire lack of interaction between writer and reader. More precisely, readers never have any effect on the writer. This allows any number of readers to be at random places along the sequence. The FIFO queues I find myself replacing tend to allocate a buffer, under a lock, and push it to a queue, under another lock (often these are hardware locks, what is often called "lock-free"), and readers pop a buffer under the same lock, use them for awhile, and then return them to a pool, under ther first lock. All this interaction generates overhead and cache pollution. The only coupling in a ring buffer is readers checking the current state of the head pointer, done under relaxed semantics. The head pointer lives at all times in the writer's cache. You probably understand all this, but remarkably many don't.

ncmncm 7y ago

That is an interesting problem. When I see it, the input streams tend to be ring buffers, and output is a priority queue of their heads, ordered by timestamp. Obviously a ring buffer is, literally, a first-in first-out medium. The essential difference between your typical FIFO and a ring buffer is the entire lack of interaction between writer and reader. More precisely, readers never have any effect on the writer. This allows any number of readers to be at random places along the sequence. The FIFO queues I find myself replacing tend to allocate a buffer, under a lock, and push it to a queue, under another lock (often these are hardware locks, what is often called "lock-free"), and readers pop a buffer under the same lock, use them for awhile, and then return them to a pool, under ther first lock. All this interaction generates overhead and cache pollution. The only coupling in a ring buffer is readers checking the current state of the head pointer, done under relaxed semantics. The head pointer lives at all times in the writer's cache. You probably understand all this, but remarkably many don't.