4 ms·

What's in a ring buffer? And using them in Rust

19 points by todsacerdoti 2y ago

tialaramex 2y ago
I think I reach the opposite conclusion which is that I'd not take a library dependency to get the non-growable version. I would however like push_within_capacity (currently available on Vec in nightly) so that I can express the idea "I would prefer to push this into the ring buffer but I have some plan B if there's no room"
- saghm 2y ago
  Interesting, I hadn't seen `push_within_capacity` before! I'm a bit surprised to see that the implementation for it is using unsafe rather than just calling `push` after returning an error if it's at max capacity already. Given that my understanding is that it's safe if there's spare capacity, my instinct is that "a logic bug in the implementation will mistakenly cause an allocation" is strictly better than "a logic bug in the implementation will mistakenly cause UB", given that UB might _also_ end up allocating, or do any number of other things. Other than that, the only difference I can think of is that calling `push` would potentially introduce a function call that isn't inlined, but that seems like it could be solved by having a helper method (or function in the `vec` module) marked as `inline(always)`, and that seems preferable to me than using unsafe code just to avoid the extra definition. Unless I'm missing something, the implementation using `push` would also be possible to mimic via the current stable public API of `Vec`, it might take 50 lines of code[1] to define a wrapper type with this method, so I'm with that this isn't something that I'd pull in a dependency for. [1]: If anyone reading this wants one to steal, feel free to grab one I threw together here https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ed4d8f4af1cdeeb4c8df4665bed8530a https://play.rust-lang.org/?version=stable&mode=debug&editio...
Secretmapper 2y ago
In my work, we had to use a ring buffer to play audio data (we decode audio data to raw WAV and use a ring buffer for playback). Interestingly, while the core part of the audio process is in rust (through WASM), the ring buffer itself is written in JS land (shared array buffer so that the audio context can read from it).
the__alchemist 2y ago
I've used these in rust to record and play audio on embedded devices. The gist is, you set up a static mut array, set the DMA peripheral to write or read to it and circular mode. Use indexes to split the buffer in the middle; you do CPU IO on the half the DMA isn't accessing. Use a Half-Transfer interrupt to trigger these CPU reads/writes.
- aktau 2y ago
  That sounds like double-buffering. Or did I misunderstand? Is it actually a ring-buffer? Can you give more details? What is a Half-Transfer interrupt?
  - the__alchemist 2y ago
    Yea; it's double-buffering in a ring buffer? Or maybe I don't really understand ring buffers or the terminology; thought I did from the article, since it said they were called circular buffers, and you set up the DMA in "circular" mode for this, and it's using a buffer! Half-transfer means when 1/2 of the DMA transfer size is done, an interrupt fires. So, you can use this and full-transfer interrupts to manage the sequencing.
    - flohofwoe 2y ago
      In a regular ringbuffer the writer just continuously pushes data to the 'head' and the reader continuously pops data from the 'tail' (and the size of the buffer is used to compensate for any 'hickups' on either side).
stefs 2y ago
for some reason, i always had problems with the concept of ring buffers - because what happens if end wraps around and overtakes start? it always takes me a few seconds (well, more than a few actually) to work out that in that case, the buffer is just full (like every other buffer).
- bob1029 2y ago
  In all the implementations I use, a full buffer simply blocks the producers. Nothing bad actually happens.
  - stefs 2y ago
    well, that's the great thing - you even have options: block the producers or overwrite old values. just don't forget to increment the start pointer too when overwriting old values.
- flohofwoe 2y ago
  ...and if you don't care about the oldest items being discarded, you can just continue writing and 'push the tail forward', e.g. a ringbuffer is perfect when you need to record a continuous stream of values, but only ever need to access the last N values.
deleted 2y ago
[deleted]
aldanor 2y ago
Since we're talking about ring buffers, here's one awesome crate I've used quite a few times - https://github.com/hawkw/thingbuf https://github.com/hawkw/thingbuf (concurrent lock-free ring buffer)

19 points by todsacerdoti 2y ago

I think I reach the opposite conclusion which is that I'd not take a library dependency to get the non-growable version. I would however like push_within_capacity (currently available on Vec in nightly) so that I can express the idea "I would prefer to push this into the ring buffer but I have some plan B if there's no room"

saghm 2y ago
Interesting, I hadn't seen `push_within_capacity` before! I'm a bit surprised to see that the implementation for it is using unsafe rather than just calling `push` after returning an error if it's at max capacity already. Given that my understanding is that it's safe if there's spare capacity, my instinct is that "a logic bug in the implementation will mistakenly cause an allocation" is strictly better than "a logic bug in the implementation will mistakenly cause UB", given that UB might _also_ end up allocating, or do any number of other things. Other than that, the only difference I can think of is that calling `push` would potentially introduce a function call that isn't inlined, but that seems like it could be solved by having a helper method (or function in the `vec` module) marked as `inline(always)`, and that seems preferable to me than using unsafe code just to avoid the extra definition. Unless I'm missing something, the implementation using `push` would also be possible to mimic via the current stable public API of `Vec`, it might take 50 lines of code[1] to define a wrapper type with this method, so I'm with that this isn't something that I'd pull in a dependency for. [1]: If anyone reading this wants one to steal, feel free to grab one I threw together here https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ed4d8f4af1cdeeb4c8df4665bed8530a https://play.rust-lang.org/?version=stable&mode=debug&editio...

Secretmapper 2y ago

In my work, we had to use a ring buffer to play audio data (we decode audio data to raw WAV and use a ring buffer for playback). Interestingly, while the core part of the audio process is in rust (through WASM), the ring buffer itself is written in JS land (shared array buffer so that the audio context can read from it).

the__alchemist 2y ago

I've used these in rust to record and play audio on embedded devices. The gist is, you set up a static mut array, set the DMA peripheral to write or read to it and circular mode. Use indexes to split the buffer in the middle; you do CPU IO on the half the DMA isn't accessing. Use a Half-Transfer interrupt to trigger these CPU reads/writes.

aktau 2y ago
That sounds like double-buffering. Or did I misunderstand? Is it actually a ring-buffer? Can you give more details? What is a Half-Transfer interrupt?
- the__alchemist 2y ago
  Yea; it's double-buffering in a ring buffer? Or maybe I don't really understand ring buffers or the terminology; thought I did from the article, since it said they were called circular buffers, and you set up the DMA in "circular" mode for this, and it's using a buffer! Half-transfer means when 1/2 of the DMA transfer size is done, an interrupt fires. So, you can use this and full-transfer interrupts to manage the sequencing.
  - flohofwoe 2y ago
    In a regular ringbuffer the writer just continuously pushes data to the 'head' and the reader continuously pops data from the 'tail' (and the size of the buffer is used to compensate for any 'hickups' on either side).

stefs 2y ago

for some reason, i always had problems with the concept of ring buffers - because what happens if end wraps around and overtakes start? it always takes me a few seconds (well, more than a few actually) to work out that in that case, the buffer is just full (like every other buffer).

bob1029 2y ago
In all the implementations I use, a full buffer simply blocks the producers. Nothing bad actually happens.
- stefs 2y ago
  well, that's the great thing - you even have options: block the producers or overwrite old values. just don't forget to increment the start pointer too when overwriting old values.
flohofwoe 2y ago
...and if you don't care about the oldest items being discarded, you can just continue writing and 'push the tail forward', e.g. a ringbuffer is perfect when you need to record a continuous stream of values, but only ever need to access the last N values.

deleted 2y ago

[deleted]

aldanor 2y ago

Since we're talking about ring buffers, here's one awesome crate I've used quite a few times - https://github.com/hawkw/thingbuf https://github.com/hawkw/thingbuf (concurrent lock-free ring buffer)