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

61–70 of 175 posts

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

#61

Post by falcolas »

dllthomas wrote: post #44
falcolas wrote: post #43

Earlier quoted context omitted.

Array size of 5 produces a mask of 0100 Write index of 8 = 1000 Masking those together to create a write position 1000 & 0100 = 0 Doesn't work out correctly, got 0, would expect to get 2. In fact, you could never get a write position of 1, 2, or 3 with an array size of 5.

This is not the problem. You are assuming still using &, which is very obviously incorrect with a very obvious fix (%5) which is still wrong because of behavior at overflow.

I'm answering the specific problem posed by the OP, given his other comments in this thread.

[EDIT] Resolved internal concerns about size calculations.

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

#62

Post by falcolas »

mfukar wrote: post #47
falcolas wrote: post #41

My C is rusty, but won't this act... oddly... on integer overflow? size() { return write - read; } 0 - UINT_MAX -1 = ? [EDIT] Changed constant to reflect use of unsigned integers, which I forgot to specify initially.

In all examples, `read` and `write` are unsigned, and since they both are the same type, no integer conversions are performed, ergo no overflow. PS. No wrap-around either, for different reasons.

> No wrap-around either, for different reasons.

You'll have to explain that to me, since I can't assign `x = 2^32` without wraparound when x is an unsigned 32 bit integer.

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

#63

Post by falcolas »

crististm wrote: post #45
falcolas wrote: post #41

My C is rusty, but won't this act... oddly... on integer overflow? size() { return write - read; } 0 - UINT_MAX -1 = ? [EDIT] Changed constant to reflect use of unsigned integers, which I forgot to specify initially.

Actually, this method counts on it. What I find interesting are the trade-offs: machine vs explicit integer wrap-around and buffers with maximum ~size(int)/2 vs ~size(int).

Got it. Modular arithmetic was the term I was looking for to resolve this.

    (0 - (2^32 - 1)) % 2^32 = 1

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

#64

Post by blub »

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…

This is exactly what I was thinking.

When pushing D in their example they overwrite the value to be read and items are out of order now.

But maybe I'm missing something, I lost interest at all the bit-twiddling.

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

#65

Post by chrisseaton »

wccrawford wrote: post #34
chrisseaton wrote: post #29

Earlier quoted context omitted.

I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.

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.

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

#66

Post by kbenson »

hzhou321 wrote: post #25
ams6110 wrote: post #2

Why do people use the version that's inferior and more complicated? Because it's easier to understand at first glance, has no performance penalty, and for most busy programmers that often wins.

The first version always leaves a "clean" state, that is both indices points to actual array locations. A mentally "clean" state makes understanding easier. For the third version one has to keep in mind the wrap around behavior of computer specific integers throughout the comprehension process, so it is a bit more difficult (to understand).

The third version also allows for the write index to be a counter of total store operations, at least until overflow, which could be useful.

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

#67

Post by greenshackle2 »

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.

Laces on my boots wear out.

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

#68

Post by to3m »

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.

I've had a shoelaces break maybe 3-4 times on shoes I wore regularly for more than 2-3 years. It's annoying out of all proportion to the expense involved.

(The plastic bits at the end can also get frayed and fall off, which happens more quickly, but I'm not sure knot style has much to do with that.)

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

#69

Post by cardiffspaceman »

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.

As a kid I wore canvas sneakers most of the time. I laced them every day. The shoes would outlast the laces even though eventually I would outgrow the shoes. Since I didn't have a personal assistant to get me new laces, I often had to tie the shoes differently so that the laces would still work in some fashion. On high top sneakers, sometimes I'd lace them approximately as low top sneakers, but with a really economical knot. The main point of wear was the point where the lace went through the top eyelets.
Post reply on HN