Lock-free ring buffer is my favorite data structure. I remember implementing it in C++ and then using a legitimate implementation in the form of boost:SPSC for prod. The idea is so simple. And then I started thinking about designing some programming language or framework around the concept, only to then stumble upon the idea of "message passing" for concurrency. Which of course led me to learn about Erlang.
And then I went down the Erlang rabbit hole. It might have been a mistake...I made more money doing C++.
Optimizing a lock-free ring buffer
71–80 of 100 posts
Re: Optimizing a lock-free ring buffer
#72Something to add to this; if you're focussing on these low-level optimizations, make sure the device this code runs on is actually tuned. A lot of people focus on the code and then assume the device in question is only there to run it. There's so much you can tweak. I don't always measure it, but last time I saw at least a 20% improvement in Network throughput just by tweaking a few things on the machine.
That reminds me of one of the easiest big wins I've had in my career. SystemD was causing issues, so I slapped in Gentoo with the real-time kernel patch. Peak latency (practically speaking, the only core metric we cared about -- some control loop doing a bunch of expensive math and interacting with real hardware) went down 5000x.
That specific advice isn't terribly transferable (you might choose to hack up SystemD or some other components instead, maybe even the problem definition itself), but the general idea of measuring and tuning the system running your code is solid.
Re: Optimizing a lock-free ring buffer
#73Earlier quoted context omitted.
For ultra low-power embedded, wouldn't a mutex approach work just fine? You're running on a single core anyway.
I'm not sure about the single-core scenario, but would love to learn if someone else wants to add something In reality multiple threads for single core doesn't make much sense right?
> In reality multiple threads for single core doesn't make much sense right?
Not necessarily, I think -- depends what you're doing.
Re: Optimizing a lock-free ring buffer
#74Is there a C library that I can get these data structures for free?
ConcurrencyKit ck_ring. The SPSC macros are the most similar to this article:
https://github.com/concurrencykit/ck/blob/master/include/ck_...
Re: Optimizing a lock-free ring buffer
#75It's lock-free because it uses ordered loads and stores, which is also how you implement locks. I find the semantic distinction unconvincing. The post is really about how slow the default STL mutex implementation is.
There are real practical implications of both the producer and consumer mutating the same cache line to take a lock that is fundamentally avoided by this "lock-free" design. It isn't meaningless.
Re: Optimizing a lock-free ring buffer
#76Earlier quoted context omitted.
If it's a power of two, you don't need the branch at all. Let the unsigned index wrap.
Interesting, I've never heard about anybody using this. Maybe a bit unreadable? But yeah, should work :)
I believe ConcurrencyKit's impl does this.
https://github.com/concurrencykit/ck/blob/master/include/ck_...
Re: Optimizing a lock-free ring buffer
#77Something to add to this; if you're focussing on these low-level optimizations, make sure the device this code runs on is actually tuned. A lot of people focus on the code and then assume the device in question is only there to run it. There's so much you can tweak. I don't always measure it, but last time I saw at least a 20% improvement in Network throughput just by tweaking a few things on the machine.
That reminds me of one of the easiest big wins I've had in my career. SystemD was causing issues, so I slapped in Gentoo with the real-time kernel patch. Peak latency (practically speaking, the only core metric we cared about -- some control loop doing a bunch of expensive math and interacting with real hardware) went down 5000x. That specific advice isn't terribly transferable (you might choose to hack up SystemD or…
What do you think is causing the issue? We are having the same kind of problem. Core isolation, no_hz, core pinning, but i am still getting interrupted by nmi interrupts
Re: Optimizing a lock-free ring buffer
#78It's lock-free because it uses ordered loads and stores, which is also how you implement locks. I find the semantic distinction unconvincing. The post is really about how slow the default STL mutex implementation is.
There are real practical implications of both the producer and consumer mutating the same cache line to take a lock that is fundamentally avoided by this "lock-free" design. It isn't meaningless.
That only explains the last stage. In order to steelman the mutex alternative, everything before "further optimization" should have used 2 critical sections. That would give a realistic baseline.
Re: Optimizing a lock-free ring buffer
#79Earlier quoted context omitted.
That reminds me of one of the easiest big wins I've had in my career. SystemD was causing issues, so I slapped in Gentoo with the real-time kernel patch. Peak latency (practically speaking, the only core metric we cared about -- some control loop doing a bunch of expensive math and interacting with real hardware) went down 5000x. That specific advice isn't terribly transferable (you might choose to hack up SystemD or…
What do you think is causing the issue? We are having the same kind of problem. Core isolation, no_hz, core pinning, but i am still getting interrupted by nmi interrupts
Details depend, but the root cause is basically the same every time: your hardware is designed to do something other than what you want it to do. It might be close enough that you want to give it a shot anyway (often works, often doesn't), but solutions can be outside of the realm of what's suitable for a "prod-ready" service.
If you're experiencing NMIs, the solution is simple if you don't care about the consequences; find them and remove them (ideally starting by finding what's generating them and verifying you don't need it). Disable the NMI watchdog, disable the PMU, disable PCIe Error Reporting (probably check dmesg and friends first to ensure your hardware is behaving correctly and fix that if not), disable anything related to NMIs at the BIOS/UEFI/IPMI/BMC layers, register a kernel module to swallow any you missed in your crusade, and patch the do_nmi() implementation with something sane for your use case in your custom kernel (there be dragons here, those NMIs obviously exist for a reason). It's probably easier to start from the ground up adding a minimal set of software for your system to run than to trim it back down, but either option is fine.
Are you experiencing NMIs though? You might want to take a peek at hwlatdetect and check for SMIs or other driver/firmware issues, fixing those as you find them.
It's probably also worth double-checking that you don't have any hard or soft IRQs being scheduled on your "isolated" core, that no RCU housekeeping is happening, etc. Make sure you pre-fault all the memory your software uses, no other core maps memory or changes page tables, power scaling is disabled (at least the deep C-states), you're not running workloads prone to thermal issues (1000W+ in a single chip is a lot of power, and it doesn't take much full-throttle AVX512 to heat it up), you don't have automatic updates of anything (especially not microcode or timekeeping), etc.
Also, generally speaking, your hardware can't actually multiplex most workloads without side effects. Abstractions letting you pretend otherwise are making compromises somewhere. Are devices you don't care about creating interrupts? That's a problem. Are programs you don't care about causing cache flushes? That's a problem. And so on. Strip the system back down to the bare minimum necessary to do whatever it is you want to do.
As to what SystemD is doing in particular? I dunno, probably something with timer updates, microcode updates, configuring thermals and power management some way I don't like, etc. I took the easy route and just installed something sufficiently minimalish and washed my hands of it. We went from major problems to zero problems instantly and never had to worry about DMA latency again.
Re: Optimizing a lock-free ring buffer
#80Earlier quoted context omitted.
There are real practical implications of both the producer and consumer mutating the same cache line to take a lock that is fundamentally avoided by this "lock-free" design. It isn't meaningless.
That only explains the last stage. In order to steelman the mutex alternative, everything before "further optimization" should have used 2 critical sections. That would give a realistic baseline.
I don’t understand what you’re getting at.