alt Hacker NewsWhy would you ever want a data structure that wraps around!? What a headache! Is it a memory constraint or optimization!? All I can think about is a physical knob where you want to know what position it is in.
Replies
aldonius • today at 12:43 PM
It's a somewhat different kind of ring buffer, because there's just one index, but I used it in my signal processing class for a finite-impulse-response filter.
Choose N to be a power of two >= the length of your filter.
Increment index i mod N, write the sample at buffer position x[i], output sum of x[i-k mod N] * a[k] where a[k] are your filter coefficients, repeat with next sample at next time step.
They are efficient FIFOs (queues). You‘ll find them in many places. I know them from multimedia / audio, where you often have unsynchronized readers and writers.
In the audio domain, the reader and weiter are usually allowed to trample over each other. If you‘ve ever gamed on a PC, you might have heard this. When a game freezes, sometimes you hear a short loop of audio playing until the game unfreezes. That‘s a ringbuffer whose writer has stopped, but the async reader is still reading the entire buffer.
Zig‘s “There are too many ring buffer implementations in the standard library“ might also be interesting:
https://github.com/ziglang/zig/issues/19231