David Kramer's high-entropy blog

Ring Buffers By Example

A ring buffer is a way of storing information from a continuous stream in a fixed-size container.  It’s called a ring buffer (or circular buffer) because conceptually, the two ends are joined.  There’s no beginning or end of the storage.  Imagine you hav a circular table.  There’s a pointer to where on the ring the next bit of data should be added by the data producer, and that pointer works its way around the ring.  But there’s also a pointer to where on the ring the next bit of data should be read by the data consumer, and that pointer works its way around the ring in the same direction, always consuming the oldest data and working its way to the newest data.  If the producer adds data and moves its pointer, and it hits the consumer’s pointer, you have a buffer overrun. The producer gets stressed out and forgetful. There’s data to store and nowhere to put it.  If the consumer reads data and moves its pointer, and it hits the producer’s pointer, you have a buffer underrun.  The consumer has read all the data there is and is starting to get bored and cranky.

In the world of computers, ring buffers are often used to hold data that comes in from an input device for a very short time until it can be processed.  It has the advantage of never needing to dynamically allocate or free memory, which is time-consuming.  The big disadvantage is that “full is full”.  You can’t easily make the ring larger without funky chaining and lookup tables, and then you’ve lost your performance advantage over keeping a pool of memory blocks around and reusing them.

Want to see how this relates to a really cool restaurant?

Why am I talking about this?  Because I saw a real-world ring buffer in action the other day, and it fascinated me.  We went to Fire and Ice, which is this funky restaurant where:

  1. You go up to the food bars with a big bowl and fill it with what you want to eat for dinner.  There’s gotta be about four dozen ingredients.
  2. You go up to the sauce bar and pick which sauces you want your food cooked with.
  3. You go up to this huge circular counter in the middle of the restaurant which has a huge circular cooking surface in the middle of it, and wait.
  4. A cook takes your food and spreads it it out in a line radiating from the outside of the cooking surface to the center, like petals of a flower.  Your line goes to the right of the food of the diner ahead of you (the producer pointer).
  5. As the food of the diners who have been there the longest is done, it is scooped up from the head of the line (the consumer pointer) and put on a clean plate.

Since new food is put on the right side of the previous diner’s food, and since the cooked food being taken off is from the left side of the the food put on after it, both the producer pointer and the consumer pointer generally work their way around the circle clockwise, assuming food is cooked at close to the rate people arrive in. All the while, each diner waiting for their food gets to watch the show as the cooks dance around the circle, adding food, turning food, and serving food.

This is cool!

  • This means that the grill surface gets evenly used.
  • New food is always put on the grill in the place that hasn’t been used in the longest time, so it’s hottest.
  • Everyone gets to see everyone else’s food being cooked.
  • Oh, and the food tastes fantastic!

Here are some crappy pictures of the grill taken with my camera phone:


August 21st, 2009 Posted by | One comment
Categories: Computers, Fun | Tags: , , ,

1 Comment »

  1. Totally dig Fire and Ice – haven’t been there in a couple of years. Nice analogy to ring buffers… it rings true (bad pun intended).

    Comment by John | August 24, 2009

Leave a comment

Site info