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

This is incredibly helpful, thank you!

nice article. Please do more of these systems programming things.

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. 🙂

@BlackM3sh

Жыл бұрын

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.

This is great! 🙏

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

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

@vei_bean

Жыл бұрын

We can check if the item at write index is some, option solves this issue :3

@Jeanpierrec19

Жыл бұрын

@@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...)

@vei_bean

Жыл бұрын

@@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

I was hoping that you would make a ring linked list to show how not to drive the compiler nuts.

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

@spedcr

11 ай бұрын

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.

@timClicks

11 ай бұрын

From memory, Rust's VecDeque is implemented with a ring buffer internally

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.

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.

@timClicks

Жыл бұрын

Thanks for the close read/code review

@jonathanmarcelino3923

Жыл бұрын

@@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

I would use .take() in pull function so much easier

Would be nice with ASPIC programming 😍

Should the modulus be the capacity instead of len()?

@clintonbowen

Жыл бұрын

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!

@timClicks

Жыл бұрын

In this code, the length is more appropriate as that is what the user has control over

@vei_bean

Жыл бұрын

I would make capacity function, that returns length, would make it easier to understand when reading the code

@timClicks

Жыл бұрын

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!?

@timClicks

Жыл бұрын

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.

@learning_rust

Жыл бұрын

@@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...

@timClicks

Жыл бұрын

What is?