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

141–150 of 175 posts

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

#141

Post by mark-r »

EvilTerran wrote: post #137
mark-r wrote: post #99

Earlier quoted context omitted.

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

Nice idea, if the color works for you.

Edit: I see it comes in clear, which would be perfect. I'll have to pick me up some of that.

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

#142

Post by dllthomas »

jnordwick wrote: post #127
dllthomas wrote: post #37

Earlier quoted context omitted.

Subtraction requires a branch, which could be worse (or not) depending on architecture.

The branch will be properly predicted every time except for when it wraps. This should be faster than any of the alternatives.

I fully believe that there are plenty of contexts where that's true - particularly in any throughput oriented system where the buffer is large. But if you care, measure.

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

#143

Post by Retric »

hangonhn wrote: post #97
Bognar wrote: post #19

Earlier quoted context omitted.

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 preach this knot to everyone I can. I'm a runner and a running coach. I've run literally thousands of miles (approaching 10,000 at this point) with this knot and it has NEVER come undone. The really nice thing about this knot is that it looks really nice too so you can use them on both running shoes and dress shoes. It makes no sense to teach the more common shoe tying knots.

Young children have poor finger dexterity making this knot untenable.

You can go even further with this knot: https://www.youtube.com/watch?v=Gm5ItoIJ4sg Which is a slow and poor knot but you can do it with even one finger on each hand.

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

#144

Post by jwatte »

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

The real problem with modulo is at the end of the integer range. Add one and overflow and suddenly jump to a totally different index in the array!

BTW: read and write pointers, power of two, did that in BeOS (1998) and many sound drivers did it earlier than that. To me, that seemed like the obvious way to do it when I needed it.

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

#145

Post by [deleted] »

jgrahamc wrote: post #36
dllthomas wrote: post #33

Earlier quoted context omitted.

No, it's not. A non-power-of-two will lead to incorrect behavior, implementing the data structure the way the author describes, for precisely the reason given by your parent comment. There are other implementations that don't suffer from this (described in the comments there), but it's not simply a matter of replacing bitwise-and with a more generic computation of the modulus. Imagine we had four bit integers and a t…

I never claimed you should use a modulus operation.

[deleted]

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

#147

Post by caf »

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

Earlier quoted context omitted.

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.

That is fairly easy to fix, though. Add N to the size value you get until its non-negative.

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

#148

Post by _ihaque »

lorenzhs wrote: post #136
caf wrote: post #122

Earlier quoted context omitted.

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.

libdivide (http://libdivide.com) implements similar logic at runtime

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

#149

Post by doktrin »

doktrin wrote: post #70

> So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. I didn't even know what a ring buffer was where do I dispose of my programmer membership card? edit : lol, what a hostile reaction...

I honestly can't tell whether the downvotes are from elitist neckbeards or offended plebs

pls explain I'd love to hear

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

#150

Post by alfalfasprout »

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 reasoning comes down to how you use it. I use ringbuffers for ultra low latency buffering of market data for instance. If my ringbuffer is so full that I'm worried about its length approaching its capacity then I'm doing something wrong and I should be willing to lose the data. 1 element isn't going to make the difference.

The real reason to stick with the first approach is that your static analysis tools won't freak out that you have intentional unsigned int overflow. Heck, some compilers will now scream at you for doing this. Then what happens when someone goes to port your code to a language with stricter overflow behavior? It won't work.

IMO even in realtime systems, I don't use this. Heck, the linux kernel even uses the original version.

Post reply on HN