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

151–160 of 175 posts

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

#151

Post by Pinckney »

chrisseaton wrote: post #29
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 don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.

If you pull the loops of a standard shoelace knot, you wind up with a square knot. Do the same with Ian's secure shoelace knot and you wind up with a surgeon's knot.

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

#152

Post by userbinator »

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

It doesn't require division, but how is that long sequence of instructions going to beat an AND?

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

#153

Post by smallnamespace »

jnordwick wrote: post #125
tbirdz wrote: post #100

Earlier quoted context omitted.

You could also do a predicated conditional move instead. Just do the subtraction every time, and use something like cmov to only do the write if you need to. I don't know if it would end up being faster, though.

Most likely (very very likely) the branch would be faster. It will almost always be predicted correctly (exceptions on the rollover) and cmov can be moderately expensive. The general rule is to only use cmov if your test condition is mostly random.

Can't the CPU just continue execute out-of-order while waiting on the cmov data dependency to finish though?

In which case cmov would be relatively cheap since it isn't blocking execution of other instructions.

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

#154

Post by jnordwick »

SamReidHughes wrote: post #124
kitsuac wrote: post #76

Earlier quoted context omitted.

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.

You don't need a conditional. You can set up a mask using sbb. ; precondition: 0 = N sbb y, 0 ; subtract 1 from y if carry flag set and x, y ; set x to zero if x == N

The cmov looks better than sbb, but both have data dependencies than a predicted branch wouldn't.

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

#155

Post by buzzybee »

phkahler wrote: post #138

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…

I believe it's very common to find little variations on algorithms or coding style like this that could produce a nice gain in efficiency or elegance. They aren't really the same problem as whole-system engineering, though, since most of your bottlenecks come from the algorithm that is completely unsuitable, not the one that is a little bit suboptimal.

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

#156

Post by mikekchar »

doktrin wrote: post #149
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

Probably just because it doesn't add to the discussion. Though, from a certain standpoint it shows one of the problems with our education system pretty clearly. This is truly a fundamental technique. I don't know how one gets out of school without knowing it. It doesn't say anything about you, but it says a lot about what we are teaching people. Embarrassingly, for a long time I thought I had invented this technique ;-)

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

#157

Post by SamReidHughes »

jnordwick wrote: post #154
SamReidHughes wrote: post #124

Earlier quoted context omitted.

You don't need a conditional. You can set up a mask using sbb. ; precondition: 0 = N sbb y, 0 ; subtract 1 from y if carry flag set and x, y ; set x to zero if x == N

The cmov looks better than sbb, but both have data dependencies than a predicted branch wouldn't.

Ahh! Serves me right for reading books from before the 486 :P

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

#158

Post by doktrin »

mikekchar wrote: post #156
doktrin wrote: post #149

Earlier quoted context omitted.

I honestly can't tell whether the downvotes are from elitist neckbeards or offended plebs pls explain I'd love to hear

Probably just because it doesn't add to the discussion. Though, from a certain standpoint it shows one of the problems with our education system pretty clearly. This is truly a fundamental technique. I don't know how one gets out of school without knowing it. It doesn't say anything about you, but it says a lot about what we are teaching people. Embarrassingly, for a long time I thought I had invented this technique…

I didn't attend college or graduate school (yeah ik ik I'm a pos), so that may well go a ways towards explaining my dumbassery

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

#159

Post by tbirdz »

jnordwick wrote: post #125
tbirdz wrote: post #100

Earlier quoted context omitted.

You could also do a predicated conditional move instead. Just do the subtraction every time, and use something like cmov to only do the write if you need to. I don't know if it would end up being faster, though.

Most likely (very very likely) the branch would be faster. It will almost always be predicted correctly (exceptions on the rollover) and cmov can be moderately expensive. The general rule is to only use cmov if your test condition is mostly random.

I don't think this is true. I tried the sample out, and gcc, clang, and intel's compiler all generate a cmov for the code instead of a branch with -O2. I don't think all these compilers would have used a cmov instead of a branch if the cmov was more expensive than a branch in this case.

https://godbolt.org/g/nyFLwp

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

#160

Post by emn13 »

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…

fastest would likely be to wrap at the greatest multiple of N that fits in your integer representation, since that (probably dramatically) reduces branch mispredicts.

However, you're still doing lots of modulos to then find the "real" array index from the "virtual" one, so this is still likely not a great option compared to the power-of-two buffers.

It might actually be faster (at least for mildly large buffers) to use 2 ifs and a range that's twice the capacity. One ifs checks whether your virtual index needs to subtract the capacity to become real, and another checks whether it's time to substract 2 times the capacity.

Post reply on HN