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

81–90 of 175 posts

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

#81

Post by schoen »

torrent-of-ions wrote: post #55
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.

More importantly, make sure your starting knot and main knot are correct with respect to each other. When I learnt the Ian knot, I later learnt that I'd been tying my shoes using a "granny knot": http://www.fieggen.com/shoelace/grannyknot.htm If you are doing this, the easiest thing to do is reverse your starting knot; relearning the main knot is going to be much harder. Since learning the Ian knot (and correct start…

Wow, after reading that page I realized that I did this all throughout elementary school and middle school, which explains why my shoelaces would come undone all the time.

I use the "Two Loop Shoelace Knot Bad Technique 1" from that page.

In recent years I've been wearing shoes with a different fastening mechanism, but I have to tie some dress shoes for a wedding tomorrow, so this is very timely knowledge!

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

#83

Post by CorvusCrypto »

pklausler wrote: post #78
RBerenguel wrote: post #51

Earlier quoted context omitted.

Also as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2

Modulus by a power of two is cheap. Modulus by a constant is a multiplication by reciprocal and a shift. And if your argument is in [0..2N], mod N is just a conditional subtraction that doesn't even require a branch.

cheap is relative right? I mean a multiplication can be spread over shift and add/sub instructions whereas a mask is just one instruction I think right?

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

#84

Post by coldtea »

kitsuac wrote: post #76
jgrahamc wrote: post #15

Earlier quoted context omitted.

You wouldn't use the modulus operation. You aren't adding some arbitrary number that's going to make you increase either index by more than the buffer length so you know that at worse you are going to need to subtract the length of the buffer. IIRC the way we made this really fast was the write the buffer backwards. That way you can detect wrapping around the buffer because DEC will underflow and set the sign flag. T…

You are still introducing a conditional by detecting the need to subtract, and iterating backward through memory is horrific for cache performance. If you need a specific, non power-of-2 sized buffer, then of course you make that design decision and pay the performance penalty. But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.

>But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.

Costs were very different in the pipelines (or lack thereof) of eighties/early nineties hardware.

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

#85

Post by coldtea »

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.

Yes. I've had lots of laces wear out, especially the plasticky end parts.

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

#86

Post by ambrop7 »

kazinator wrote: post #58
jgrahamc wrote: post #9

This is of course not a new invention. The earliest instance I could find with a bit of searching was from 2004, with Andrew Morton mentioning in it a code review so casually that it seems to have been a well established trick. But the vast majority of implementations I looked at do not do this. I was doing this in 1992 so it's at least 12 years older than the 2004 implementation. I suspect it was being done long bef…

> It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask. The cost of a mask can probably be entirely buried in the instruction pipeline, so that it's hardly any more expensive than whatever it costs just to move from one register to another. Modulo requires division. Division requires a hardware algorithm that iterates, consuming multiple cycles (pipeline stall).

You do not need modulo or division to implement non-power-of-2 ring buffers. Because you will only increment by one. So instead of "x = x % BufferSize" you can do "if (x >= BufferSize) x -= BufferSize;" or similar.

That's for "normal" ring buffers. I suspect that the design described in the article can be implemented for non power-of-two without division but I'll need to think about the details.

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

#87

Post by tveita »

The Linux kernel seems to leave one element free, which surprised me, but it does have this interesting note about it:

https://www.kernel.org/doc/Documentation/circular-buffers.tx...

  Note that wake_up() does not guarantee any sort of barrier unless something
  is actually awakened.  We therefore cannot rely on it for ordering.  However,
  there is always one element of the array left empty.  Therefore, the
  producer must produce two elements before it could possibly corrupt the
  element currently being read by the consumer.  Therefore, the unlock-lock
  pair between consecutive invocations of the consumer provides the necessary
  ordering between the read of the index indicating that the consumer has
  vacated a given element and the write by the producer to that same element.

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

#88

Post by geophile »

His favored solution introduces subtlety and complexity. Remember that 20-year old binary search bug in the JDK a few years ago? That is the sort of bug that could be lurking in this solution.

I understand not wanting to waste one slot. A third variable (first, last, count) isn't too bad. But if you really hate that third variable, why not just use first and count variables? You can then compute last from first and count, and the two boundary cases show up as count = 0 and count = capacity.

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

#89

Post by jsnell »

alanbernstein wrote: post #82
hzhou321 wrote: post #26

He keeps stating the case of one-element ring buffer. Is that a real concern ever?

It seemed like a sarcastic comment to me. Why would that ever be used?

It's indeed a ridiculous data structure, but I did actually need it.

It's a dynamically sized ring buffer with an optimization analogous to that of C++ strings; if the required capacity is small enough, the buffer is stored inline in the object rather than in a separate heap-allocated object. So something in the spirit of (but not exactly like):

  struct rb {
      union {
          Value* array;
          // Set N such that this array uses the same amount of space as the pointer.
          Value inline_array[N];
       };
      uint16_t read;
      uint16_t write;
      uint16_t capacity;
  }
You'd dynamically switch between the two internal representations, and choose whether to read from array or inline_array based on whether capacity is larger than N. In this setup it'd be pretty common for N to be 1. Having to add a special case to every single method would kind of suck, generic code that could handle any size seemed like a nice property to have.

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

#90

Post by fbonetti »

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.

That looks very similar to the handcuff knot
Post reply on HN