3 ms·

I just finished writing a custom FIFO allocator for an extremely high bandwidth and low latency data processing (and UI) system written in C/C++ (even std::dequ

I just finished writing a custom FIFO allocator for an extremely high bandwidth and low latency data processing (and UI) system written in C/C++ (even std::deque was doing WAY too many heap allocations, not to mention the allocations within each object passing through the system, despite use of move semantics to minimize redundancy). Performance improved by 100x - 1000x. And it was already blazingly fast before, if measured against performance standards we’ve become accustomed to from JavaScript and other GC languages. In high performance systems (where the benefits of C/C++/etc. outweigh the downsides), dynamic allocations always come back to bite you. If you rely on them too heavily from the start (and don’t plan for custom allocation schemes in the future), you can even get into bad situations where it’s infeasible to refactor to custom memory management (without a total rewrite), when you later need the performance gain. Incorporating even the possibility of heap allocations into a language’s most fundamental data types will doom that language to being relegated to performance-insensitive and latency-insensitive tasks, if only because it requires that a heap exist (whereas C, Rust, etc can run on embedded real-time systems with no heap). And that’s okay! It’s good that we have languages for that. But C/C++/Rust/etc. are definitely not where you can tolerate such a thing in the core language.

ncmncm 7y ago
If you are doing high-throughput, and you ever allocate anything after startup, you are Doing It Wrong. Any brand of FIFO loses. What you need is a big-ass ring buffer, mmapped on a hugetlbfs, fed by a process on a NOHZ isolcpu core. Readers are separate processes.
- CoolGuySteve 7y ago
  No. Thread local/core-specific FIFO is more cache efficient than a ring buffer because the address about to be allocated is significantly more likely to be in a high level cache. With a ring buffer, you're constantly cycling out to L3 or worse and hoping the prefetcher figures out what you intend. It's basically a LIFO allocator. Even if you want to use a separate processing core, you get better latency using a FIFO allocator between 2 threads on the same core complex and the code is simpler, reducing instruction fetch overhead. Frankly, I see architectures like yours all the time from firms like Hudson River Trading and I think they suck. They incur tons of overhead, the process separation adds a useless layer of abstraction that's annoying to transcend, and you end up with this useless message protocol between cores that invokes tons of copies and breaks compiler inlining features.
  - ncmncm 7y ago
    Ring buffers have a strictly sequential access pattern, which prefetchers are specifically optimized for. Anybody using a "message protocol" with ring buffers, or doing copies out of them, is Doing It Wrong. I routinely get 10x performance by doing away with FIFOs and buffer allocation and freeing. Process separation means you can start and stop readers independently of any other activity.
- electrograv 7y ago
  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

If you are doing high-throughput, and you ever allocate anything after startup, you are Doing It Wrong. Any brand of FIFO loses. What you need is a big-ass ring buffer, mmapped on a hugetlbfs, fed by a process on a NOHZ isolcpu core. Readers are separate processes.

CoolGuySteve 7y ago
No. Thread local/core-specific FIFO is more cache efficient than a ring buffer because the address about to be allocated is significantly more likely to be in a high level cache. With a ring buffer, you're constantly cycling out to L3 or worse and hoping the prefetcher figures out what you intend. It's basically a LIFO allocator. Even if you want to use a separate processing core, you get better latency using a FIFO allocator between 2 threads on the same core complex and the code is simpler, reducing instruction fetch overhead. Frankly, I see architectures like yours all the time from firms like Hudson River Trading and I think they suck. They incur tons of overhead, the process separation adds a useless layer of abstraction that's annoying to transcend, and you end up with this useless message protocol between cores that invokes tons of copies and breaks compiler inlining features.
- ncmncm 7y ago
  Ring buffers have a strictly sequential access pattern, which prefetchers are specifically optimized for. Anybody using a "message protocol" with ring buffers, or doing copies out of them, is Doing It Wrong. I routinely get 10x performance by doing away with FIFOs and buffer allocation and freeing. Process separation means you can start and stop readers independently of any other activity.
electrograv 7y ago
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.