RingBuffer

[00:00:00]
>> I know you probably feel like you've had enough lists, but there's still one more list I do wanna cover. I think it's a very fantastic list, it's one of my favorite lists, I use it all the time. I tried to make a PR once to an open source library a while back, that wasn't using one.

[00:00:13]
And it would just cause terrible performance, and they didn't accept my PR, but I do think I was right on doing it, and of course, that is array buffers. I've created bajillions of these, I've created a bunch of them just this year. It's a very fancy word, but it's not actually all that confusing.

[00:00:27]
So let's go over an array buffer. I just love them, they're just the best. I believe these are used, if you're familiar with Rust, VecDeque or DequeVec, that's what they are as a double-ended ring buffer. So effectively, you can think the exact same thing as an ArrayList, right, where you have 0 to N.

[00:00:47]
And you have some sort of array-like storage. The only difference is that we're not using 0 as our head, and length as our tail. That's what's happening in ArrayList, you can kind of imagine it kind of a LinkedList. Instead, what we're gonna have is we can literally have index based head, and we can have index based tail.

[00:01:06]
And so they exist somewhere within the list. Or you could imagine everything this direction is null, everything this direction is null. And everything within the head and the tail are the items that you have. So if you wish to remove from the front, what do you do? You just +1 to the head.

[00:01:24]
And now, that item that was the head is no longer in there, we clean it up, return it out, and now we have a new one. So that is an O(1) operation, which is fantastic. Same thing with tail, if you wanted to add to the tail, what would you do?

[00:01:38]
Just add 1 to the tail, right? This is just tail + 1. Boom, and now we've updated it. So pushing, popping, shifting, unshifting, all are O(1) operations, which is fantastic. You guys are so astute, I can just see the astuteness. And you're saying, well, checkmate, instructor, what if you go off the edge?

[00:02:01]
Well, that's why they're called ring buffers, people, is that you can actually go, [SOUND] right, the modulo operator, right? So tail, this.tail modulo length gives you your index into the array, so you can ring around it. So your head can literally be on this side, and your tail can be over here, and you still have the same thing.

[00:02:23]
Now, if you need to resize, that's where things get a little bit confusing, right? By the way, is everyone familiar with the modulo operator? Modulo operator is the remainder operator, so 5 divided by 2, the answer should be 2. TypeScript rots your brain so much, you're like 2.5.

[00:02:40]
It's like, no, it's 2 remainder 1, right? So 5 modulo 2 is 1, right? That's the answer. Most languages don't convert from integers to floats without your permission. You need to say, hey, this is now officially a float, you can put a point in there. So anyways, this does the remainder afterwards.

[00:03:03]
So you can imagine if tail, let's say if you had an array, say size 10, and your tail was 12. 12 modulo 10, 2, your tail would be right here. And if your head was say 24, let's just say it's 24. Somehow it's bigger than your tail, don't ask questions, it's just somehow bigger than your tail.

[00:03:23]
24 modulo 10, of course, that's 4. So your head would be here at 4, your tail will be at 2, that means you're using from 4 until 2, right? So that makes sense, right? You can actually go around, it's a little ring around. The only problem happens is when your tail exceeds your head.

[00:03:39]
Once that happens, I mean, a, you're probably falling down some stairs. But b, what actually is happening is that you need to resize. And so this is where a little bit of the trickiness comes in. Because one thing that's inherent about ring buffers is they also maintain order.

[00:03:54]
So when you shift or unshift, you're not just getting any element, you're getting the element that was last added into the front or perhaps the first element added, right? So if you're only adding to the tail and removing from the front, you're just simply creating a queue, right?

[00:04:09]
That's all you're doing, a queue that runs around a ring. And so you do have to do a little bit of that, and you'll have to resize, and a resize is pretty straightforward. So if you did have this situation in which the tail is now where the head is at, and you're trying to insert.

[00:04:21]
Well, all you have to do is start at your head, go the length, and write that into a new larger capacity buffer. And there you go, you now have it rewritten in proper order, your tail or your head, or let's see. Now, no, your head will be at 0, your tail will be at length, and there you go.

[00:04:41]
Now, you can just add 1 cuz you have more capacity, everything is good to go. So ring buffers are really fantastic items. Hopefully, this is just an explanation point, we're not actually gonna implement them. But they are a really great list to know you have, cuz inevitably, what's gonna happen is you're gonna write something like, let's say a log batcher, right?

[00:04:59]
You have a service which needs the batch logs and then write logs. The problem is logs need to maintain order, and while you're writing logs, new logs can come in. So you can imagine something that doesn't wanna take too long writing logs, doesn't wanna do this. You could use something like a ring buffer in which every so long, every so timer, it flushes 50 logs, 100 logs, some amount of logs, all the logs.

[00:05:19]
You don't really care, you just flush it, and then you have something that can keep on running while it's doing it. And you don't even have to worry about putting, say a mutex around it. I know this is maybe a little too unsafe for all the rustaceans out there, because you don't write into memory that's being used until your tail or your head or your tail exceeds your head.

[00:05:39]
So you have this free space, you can do some really cool operations with it. You can make it super duper fast, where you don't have to worry about some of these read write operation problems. Big fan of it, I like it, it's great. Obviously, one of the problems is that you will have to do a little bit of mutexing around your tail index.

[00:05:55]
So you don't actually do something that's bad. We got one question.
>> Is it called a rain buffer?
>> A Ring Buffer, a Ring Buffer. They're a lot of fun, and you can use them quite a bit for performance object pooling if you really wanna use ring buffer for object pooling.

[00:06:16]
You can just use an ArrayList for object pooling, cuz they don't really care if they're created the last or added to the pool last. It's just like, I just need a new object to reuse again. And so you don't have to do that. For those that don't know what an object pool is, say you have a service that creates a user every single time a request comes in.

[00:06:34]
You're getting thousands upon thousands upon thousands of requests, why recreate this object over and over and over and over again? Just have an object, set new values on it, use it for the service, hand it back to a pool. So that way, your memory doesn't go like this, instead, it goes like that.

[00:06:50]
Just makes life a little bit easier. And often, you can run into situations where you don't get garbage collection destroying your service, blah blah blah blah. Pools, they're great, everyone loves pools, I love pools.