Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I've been writing ring buffers wrong all these years

snellman.net

Post reply on HN
Print view View original

111–120 of 175 posts

Re: I've been writing ring buffers wrong all these years

#111

Post by dllthomas »

Bartweiss wrote: post #22
falcolas wrote: post #8

Usually when I'm writing a ring buffer, it's for tasks where the loss of an item is acceptable (even desirable - a destructive ring buffer for debugging messages is a fantastic tool). As such, I simply push the read indicator when I get to the r=1, w=1 case. Using the mask method is slick (I'd cache that mask with the array to reduce runtime calculations), but it's definitely going to add cognitive overhead and get m…

In general, this makes sense; certainly data you're putting into a ring buffer is data you're willing to lose. Doesn't it break the order invariant of the buffer, though? I can't see a way to do this without the risk of getting reads of newer data prior to older data. That's probably fine in many cases, but something like non-timestamped-debugging strikes me as a case where I'd want to know that the data arrived in t…

> certainly data you're putting into a ring buffer is data you're willing to lose.

When that's the case, a ring buffer is a great choice. It's not required, though - the writer could block when it detects a full buffer.

Re: I've been writing ring buffers wrong all these years

#112

Post by vaughngh »

phaemon wrote: post #4

> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.

Been using this for years, symmetric knots ftw!

Re: I've been writing ring buffers wrong all these years

#113

Post by dllthomas »

simcop2387 wrote: post #93
dllthomas wrote: post #52

Earlier quoted context omitted.

Yes, any choice. Yes, that's not the case if you change the implementation in other ways in tandem - but then you are describing a different implementation. To mask where he does, any choice of mask will exhibit this problem (or other problems), mathematically. I can produce a proof if you need it. > He only ever calls mask() after an increment. I think you misunderstand what he's talking about. He calls mask at inse…

That said, one of the comments on the blog actually had a great suggestion for dealing with this. Wrap the value yourself at 2*capacity, you'll still get the same benefits from the algorithm and it's trivial to prevent the overflow then. You can then avoid the modulo operation (subtract the capacity if it's a larger index) and get better performing non-power of 2 capacities. That said I'd mostly be using this kind of…

Yeah, that's a great option!

Conceptually it's roughly what's going on anyway - something must wrap at some point if we're going to store our offsets in limited space - just that we get the wrapping for free from overflow if it's 2^n.

The confusion above stemmed, I think, from the fact that in the "original" implementation the mask is used for that wrapping and then we have a noop projection from offset to index. In this implementation, overflow is used for that wrapping and the mask is to project from offset to index. In the implementation you discuss, we pick still other functions for both.

Re: I've been writing ring buffers wrong all these years

#114

Post by Guvante »

mark-r wrote: post #96
heisenbit wrote: post #60

Earlier quoted context omitted.

As far as I can tell that int wrap around could be avoided by - subtracting buffer size from both pointers once the read pointer has wrapped. - choosing a longer int for the math operation where possible That seems a small price for the freedom to be able to choose an appropriate buffer size.

One of the benefits of the original algorithm is the independence of the read and write indexes, they can be updated from different threads (or different processors!) without any atomic operations beyond writing or reading a value. Subtracting from both pointers requires an additional atomic read/modify/write operation.

You could also just restrict the pointers in the normal way but to two times the size of the buffer. So instead of wrapping at N you wrap at 2*N.

You are only encoding 1 bit of data (first or second) so adding more data than that by allowing unsigned integer overflow is just an optimization, not fundamentally necessary.

Re: I've been writing ring buffers wrong all these years

#116

Post by lacampbell »

chrisseaton wrote: post #65
wccrawford wrote: post #34

Earlier quoted context omitted.

From the site: "The finished "Ian Knot" is identical to either the Standard Shoelace Knot or the Two Loop Shoelace Knot. Because it was tied much more quickly and symmetrically, the laces suffer less wear and tear and thus last longer."

Do people's laces wear out? That's not a problem I've ever experienced.

Yeap - a bit of my shoe lace broke just after tying them once on a work morning. I had to run to catch a bus, but instead I stood on my shoe lace mid stride, fell and slid across a petrol station driveway. Spent the bus ride trying not to bleed on the seats and had to apply disinfectant and remove stones from the flesh wound at work.

Anyway it was embarrassing but it taught me a valuable lesson - shoe laces can wear out and break.

Re: I've been writing ring buffers wrong all these years

#117

Post by tbirdz »

Bognar wrote: post #19
phaemon wrote: post #4

> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.

The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.

I've been using this knot for 8 years, and it hasn't come untied on me once! I'd highly recommend it.

Re: I've been writing ring buffers wrong all these years

#119

Post by cannam »

I love the way this discussion has divided neatly into thirds: history of ringbuffers; digression on shoelaces; fragmentary, widely ignored, replies about everything else (this one included, I'm sure).

I like this kind of article and enjoyed this particular one, but the long discussion above about the "right" way to do it goes some way to justifying why so many people are happy to do it the "wrong" way.

I've implemented and used ring buffers the "wrong" way many times (with the modulus operator as well!) and the limitations of this method have never been a problem or bottleneck for me, while its simplicity means that it's easier to write and understand than almost any other data structure.

In most practical applications, it's memory barriers that you really have to worry about.

Re: I've been writing ring buffers wrong all these years

#120

Post by mark-r »

Guvante wrote: post #114
mark-r wrote: post #96

Earlier quoted context omitted.

One of the benefits of the original algorithm is the independence of the read and write indexes, they can be updated from different threads (or different processors!) without any atomic operations beyond writing or reading a value. Subtracting from both pointers requires an additional atomic read/modify/write operation.

You could also just restrict the pointers in the normal way but to two times the size of the buffer. So instead of wrapping at N you wrap at 2*N. You are only encoding 1 bit of data (first or second) so adding more data than that by allowing unsigned integer overflow is just an optimization, not fundamentally necessary.

If you do that then the size() function becomes a problem. The original implementation relies on unsigned integer wrap-around to give the proper result when write < read.
Post reply on HN