Show HN: Revring, a circular buffer with zero memory waste

https://analog10.com/posts/circular_buffer.html

by codehero • 11 years ago

12 12 11 years ago

rhaps0dy2• 11 years ago

You still have a buffer or size X that may store X-Y items. I fail to see the "zero memory waste" (not that it's a good tradeoff).

mungoman2• 11 years ago

No, the author can use all entries in the buffer. The space cost is hidden in that one of the pointers need to hold X+1 values, ie for 256 entries it is not enough with 8-bit indices.

An unfortunate effect of this implementation is that both indices are modified by the consumer. It's not safe to write/read dats from different contexts, something that would be very useful in a driver.

rhaps0dy2• 11 years ago

Ah, thanks for explaining.

Now it makes sense.

codehero2• 11 years ago

Yeah your intuition is correct here. On an MSP430 (which is were I use it) the producer is in interrupt context but as a savvy redditor pointed out, I will need to enable/disable interrupts in the consumer function as well.

akkartik• 11 years ago

If I understand correctly he's storing X items in a buffer of size X, but using an invalid value in the head pointer to indicate that the buffer is full.

It's easier to understand without the decrementing. Initialize head and tail to 0, keep incrementing and cycling through the end as usual. When removing an element check if head and tail are equal before removing. When adding an element check if head and tail are equal after adding, and set the head to a sentinel value, say MAX_INT. Now you can check for the sentinel before attempting to add an element.

Neat trick!

cpr• 11 years ago

Gosh, all that to save one byte? ;-)

jonsen• 11 years ago

That byte will be needed elsewhere to make it multitasking safe.

codehero2• 11 years ago

I'm running it on a system with 512 bytes of RAM and multiple queues...saving 1 byte helps. I do not need extra space for synchronization; I can enable/disable interrupts without extra RAM required.

jhallenworld2• 11 years ago

Suppose you have only 4 entries (perhaps very large) in your ring. You might care about this.

dpc_pw• 11 years ago

This post is literally about saving one byte, at the cost of being slower and not producer-consumer friendly. Not very interesting.

The flag could have been hidden in any other field as a bit or something. Then it could be at least masked with simple AND operation which is usually faster than branching, especially on pipelined CPUs.

Update: Quick implementation: https://gist.github.com/dpc/a194b7784adfa150a450

This fix for concurrency issue is an ugly hack. I'm not sure if it's even correct in this particular scenario, and definitely not proper for anything that would aspire to be good reusable code. I'd advise this code to push atomicity requirement onto caller. Irqs should have been disabled by calling code.

"register" keyword is obsolete. There's no point in using it.

kstenerud• 11 years ago

I did something similar back in the DOS era for a serial port library: https://github.com/kstenerud/DOS-Serial-Library/blob/master/...

jhallenworld2• 11 years ago

A conceptually simpler way to do this is to assign one (or more) extra bits in the head an tail pointers. For example, for a 512 entry ring, use 16-bit indices. Whenever you index the ring, and the index with 511 before performing the index.

  Write to ring: ring[511&(head++)] = data

  Read from ring: data = ring[511&(tail++)]

  Ring is empty: head == tail

  Ring is full: tail + 512 == head

Show HN: Revring, a circular buffer with zero memory waste

Related Stories