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

131–140 of 175 posts

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

#131

Post by barrkel »

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.

How do you take your shoes off without untying the knot?

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

#132

Post by lomnakkus »

planckscnst wrote: post #38

This is another interesting ring buffer implementation that uses mmap. https://github.com/willemt/cbuffer

I was waiting for someone to mention this -- it seemed much more interesting to me. It's a real classic in the "what the hell, you can do that?" category. (Bonus points if you've done it in a language that requires "extra data" for strings, like storing the length somewhere.)

I must admit that I never actually benchmarked my implementation properly -- it might be interesting to see if there are actual trade-offs between mmap vs. copying. (I'm guessing that nothing can beat MMU support, but I think the MMU also supports copy operations, so...?)

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

#133

Post by lomnakkus »

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?

Weirdly, I think Haskell has an equivalent: MVar. It has its (low-level) uses, but its quite hard to get any sort of non-trivial (non-rendezvous) synchronization protocol right. It's incredibly easy to deadlock. (But that may be mostly to do with the MVar's paucity of non-blocking primitives.)

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

#135

Post by lorenzhs »

amag wrote: post #128
ambrop7 wrote: post #86

Earlier quoted context omitted.

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.

Then you have to deal with branch mispredictions which may hurt performance pretty bad if the RB is heavily trafficked (which often is the use case for an RB).

Depends heavily on the size of the buffer. If it's only three elements large, then branch overhead will be measurable. But for larger buffers, it likely will always be predicted as not taken, and you only have a branch miss upon wraparound.

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

#136

Post by lorenzhs »

caf wrote: post #122
kazinator wrote: post #58

Earlier quoted context omitted.

> 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).

Modulo by a constant doesn't require a division, you can instead use multiplications, shifts, adds and subtracts. This transform is typical for compilers. For example, this is what gcc targetting x86_64 does to perform % 17 on the unsigned value in %edi: movl $-252645135, %edx movl %edi, %eax mull %edx movl %edx, %eax shrl $4, %eax movl %eax, %edx sall $4, %edx addl %edx, %eax subl %eax, %edi

That only works for compile time constants, though. With a power of two sized buffer you can just store the mask and decide how large you want your buffer to be at runtime.

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

#137

Post by EvilTerran »

mark-r wrote: post #99
to3m wrote: post #68

Earlier quoted context omitted.

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.)

If the plastic bit at the end falls off, just cut off the frayed part and dip the end into molten wax from a candle. I can't say I've tried it yet though, even that's so much trouble that I just live with the frayed end.

Heat-shrink tubing is perfect for replacing shoelace ends, if you happen to have some lying around (or have a friend who tinkers with electronics you can blag a bit off).

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

#138

Post by phkahler »

I find the headline very interesting. It's very inviting because of the way it expresses a sort of epiphany about doing it wrong on a mundane programming task. One is tempted to read it in order to see if there is some great insight to this problem. just maybe it's applicable outside this one problem. It begs the question: if he's been doing it wrong on a fairly mundane thing, maybe I am too. I need to see what this is about.

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

#140

Post by DonHopkins »

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.

I guess you're not a Perl programmer, otherwise you'd be using duct tape instead of shoe laces.
Post reply on HN