Writing a Rust-based ring buffer
Vložit
- čas přidán 27. 08. 2024
- A handy data structure for buffering input, the ring buffer (also known as a circular buffer, among a few other names) is a fun data structure to implement. In this video, we use the Rust programming language.
If you're worried about the video's length, it's not because of the complexities of the implementation. It's because I spend a lot of time in this teaching Rust!
This implementation avoids the use of raw pointers and reveals some differences between Rust and other languages, such as Java and C, that can make porting code slightly complex.
📚 Resources:
- Code: gist.github.co...
- Java reference code: www.baeldung.c...
- C reference code: en.wikipedia.o...
🦀 Rust resources:
- Rust Documentation: doc.rust-lang....
- Rust Playground: play.rust-lang...
- Rust in Action (Tim's book!) mng.bz/4MlD
- How to Learn Rust (a course I'm offering!) learning.accel...
👋 Connect with Tim:
- Twitter: / timclicks
- GitHub: github.com/tim...
- Mastodon: mastodon.nz/@t...
- DEV: dev.to/timclicks/
- Patreon (extra learning materials) / timclicks
🔔 Subscribe to the channel and click the bell icon to stay updated with the latest videos and live streams from timClicks: www.youtube.co...
👍 Like this video if you found it helpful, and share it with your friends who are also interested in Rust programming.
It might have helped to explain the principle of a ringbuffer in the beginning. The idea would be if the index we are going to read is the current write index the buffer is empty. If the index we are going to write to next is the read index then we are full. This implicitly makes the capacity len()-1.
In the context of a vec [0, 1, 2, 3] if the read index is 0 and the write index is 0 we are empty. However if the read index is 3 and the write index is currently 2 we are full. We haven't written to 2 but to respect the invariants we cannot write to 2 otherwise it would be difficult to check whether we are full. Think of the case where read index is 0 and write index is 3. We cannot possibly check whether write is less than read because it isn't. However write +1 == read which means we are full.
The C implementation is correct.
Awesome channel, thanks for making this stuff! I've dabbled a bit in Rust but keep getting sidetracked because I don't have any concrete projects to build, so this stuff is great for inspiration
10:34 Something else you could have done is use `let vec = Vec::::with_capacity(capacity)` which would allow you to remove the Option wrapper and the restriction on T to be Clone. The length is zero however so indexing now would panic, but you can use `vec.set_len(capacity)` to fix that. This will allow you to index possible garbage data, but as long as you implement the ring buffer correctly it is safe to use. One last thing is that after you have allocated the underlying array you don't really need the Vec anymore since the array should now be fixed length, so lastly you can call `vec.into_boxed_slice()` to convert to a Box and use that as storage instead of Vec. 🙂
Another thing, the C implementation is not wrong. I would recommend renaming `read_index` and `write_index` to `start` and `end` in your code. This way it is easier to see that in new() you initialise start to be after end (start > end), which seems to be your main problem. Hopefully this also makes it more clear why we only update the write_idx (end) on push, since the read_idx (start) doesn't move.
nice article. Please do more of these systems programming things.
Determining full vs empty in ring buffer is a common issue. Whenever head == tail, the ring buffer can be either full or empty. You need extra logic to tell them apart. A simple approach is to use a bool flag to mean full (i.e. you see the flag to true whenever number of items == capacity) and make empty be head == tail && !full
We can check if the item at write index is some, option solves this issue :3
@@vei_bean This assumes that you have initialized the memory in the first place and that you actually set the value back to None after you have read from it. Neither is true. The simplist solution is to check whether the next index that would be written to is the read index.
In the case where you are resetting the value after each read you are leaving performance on the table since you are having to initialize the object at the index on every single operation. When you are using a ringbuffer you are generally worried about performance. You could always just be using a linked list which would be simpler to implement(well at least in most languages...)
@@Jeanpierrec19 when creating the ring buffer we fill it with None variant of Option, the memory is initialized it's just empty Options (None). checking the next index isn't necessarily the simplest solution, checking for Some is just .is_some(), seems pretty simple to me. I'm not too sure whether or not it is more or less intensive as some math and and comparison.
my logic on checking is_some is that once we get Some at the write index it would have to mean we have looped back to the starting write index if you dont reset the value and if you do reset the value would mean you write faster than you read, both of which i interpret as a full buffer. if you consider already read data empty when not reseting the value, well that would require more overhead. really just a tupple of (Option, bool) if you want that. again i dont really know how efficient option is but from what i understand about rust, they put alot of effort to make sure it is as efficient as possible in the standard lib.
I made my own ring buffer implementation if you want to look at that: codeberg.org/Vulpesx/ring_buffer
Rust itself has a ring buffer in std::collections::vec_deque, it's not perfect 1 to 1 with your implementation as it is not fixed size but I imagine it might be worthwhile to look at the source in that for a more idiomatic ring buffer if you cant make a vec_deque work for yourself or impl something on top of a vec_deque
was going to ask how is a vec_deque different from a ring buffer. I've had success with vec_deque in the past, very easy to use.
From memory, Rust's VecDeque is implemented with a ring buffer internally
I would use .take() in pull function so much easier
I was hoping that you would make a ring linked list to show how not to drive the compiler nuts.
To check if full just check if write index is some, could do this in java aswell since it has options too. Options solve the issue of checking capacity
Note: Pull fn needs to use readidx not writeidx.
For C implementation, the wiki says to add a counter. Also set readidx to 0 when using it in pull fn.
In the Java implementation, the write and read sequences continue to grow. Which is why you can use them as way to check if empty or full. So this would require the rust code to track the sequences and evaluate the index on pull/push.
I prefer the first option.
Thanks for the close read/code review
@@timClicks love you work. I couldn’t fall asleep so this was good exercise before bed.
I think Someone in comments had the idea to mark the read items as None. Is_full fn could then just check if next item is Some. I’m not sure how to check if_empty in option.
Edit: You can add a back_idx fn and check if idxs are same and back_idx(readidx) is none. Maybe I haven't tested that out yet
This is incredibly helpful, thank you!
Would be nice with ASPIC programming 😍
This is great! 🙏
Hai Tim. In the tutorial you had mentioned the push(write) operation is mutable and pull(read) is by reference or immutable. Is that the right way of doing?. We cant hold a mutable and immutable reference to a same thing same time. The underlying Data structure need to move the elements to new memory location in heap every time. This may cause a mismatch of element referenced in a memory location. Please correct me if I am wrong.
Should the modulus be the capacity instead of len()?
BTW I loved watching this as the ring buffer is a favorite data structure of mine and I've been keen to try implementing it in rust in various ways. Thanks for making this!
In this code, the length is more appropriate as that is what the user has control over
I would make capacity function, that returns length, would make it easier to understand when reading the code
That is a good idea!
I was following along but Clone at 14:50 has left me with head in hands!? Not your fault, just a quirk of Rust that I'm yet to begin to understand!?
It's not your fault either - the details are confusing. Using clone is a way to "cheat" the ownership system by creating a second owner.
@@timClicks Ah, thank you. Keep up the videos, I hope you get a big following on here, you deserve it!
It's kind of a shame again...
What is?