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

161–170 of 175 posts

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

#161

Post by nullc »

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.

You can also compute the optimization at runtime, same as the compiler does. Libtheora contains code for this, used for quantizing video data.

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

#162

Post by gpderetta »

smallnamespace wrote: post #153
jnordwick wrote: post #125

Earlier quoted context omitted.

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.

It does, but it may run out of non-dependent instructions to execute while waiting for the long pole of the cmov dependency chain to finish.

This used to be a problem on Pentium4 where cmov had high latency (4 cycles or more), but today, IIRC, a register-to-register cmov is only one cycle, so it is safe to use whenever a branch could have a non-trivial misprediction rate.

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

#163

Post by gpderetta »

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

Actually it might not really be mispredicted. Slightly older Intel CPUs had a dedicated loop predictor that would exactly predict quite complicated taken/non-taken sequences. If the RB is of fixed size the edge case would be always perfectly predicted.

More recent CPUs, IIRC, do away with the dedicated loop predictor as they have a much more sophisticated general predictor, which, although won't guarantee perfect prediction on this case, it might still get close enough.

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

#164

Post by NotThe1Pct »

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…

Me too, back in 2005 we were already doing all this. Also there is an easy hack that solves the overflow part.

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

#165

Post by pkolaczk »

__david__ wrote: post #73
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.)

I think it's so annoying because of the timing. I've never had one break when untying the knot or when just walking around. It's always while tying it which means I was just about to leave and now life has thrown a monkey wrench into my plans. Depending on how close I am cutting things, this may be an event that makes me late. Grrrrrr. Stupid shoelace!

Yes, this! And this happens particularly often, when you use standard cotton laces which make knots harder to accidentally undo. The synthetic ones last much longer, but are slippery and easy to untie.

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

#166

Post by amadvance »

tbirdz wrote: post #159
jnordwick wrote: post #125

Earlier quoted context omitted.

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

If you use __builtin_expect() the Intel compiler uses a branch. I mean this way:

if (__builtin_expect(index >= cap,0)) { ...

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

#167

Post by wccrawford »

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.

Yeah, it happens to shoes that are kept a long time.

However, I remain unconvinced that the wear pattern matters this much. It seems to me that an alternative would be to re-lace your shoes every year, flipping sides. Then the pattern would be more even, too. And probably still a waste of time and effort.

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

#168

Post by cksk »

pklausler wrote: post #74
dllthomas wrote: post #37

Earlier quoted context omitted.

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

Oh, come on, you don't need a branch to do a conditional subtraction. Reify the condition to 0/1 and use multiplication, or use AND with a two's complement of the condition.

OK, my bit twiddling knowledge is weak, my google skills are weaker still, and now I'm curious: what does "AND with a two's complement of the condition" mean, exactly?

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

#169

Post by pklausler »

cksk wrote: post #168
pklausler wrote: post #74

Earlier quoted context omitted.

Oh, come on, you don't need a branch to do a conditional subtraction. Reify the condition to 0/1 and use multiplication, or use AND with a two's complement of the condition.

OK, my bit twiddling knowledge is weak, my google skills are weaker still, and now I'm curious: what does "AND with a two's complement of the condition" mean, exactly?

x -= N & -(x >= N);

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

#170

Post by cksk »

pklausler wrote: post #169
cksk wrote: post #168

Earlier quoted context omitted.

OK, my bit twiddling knowledge is weak, my google skills are weaker still, and now I'm curious: what does "AND with a two's complement of the condition" mean, exactly?

x -= N & -(x >= N);

Ohh, nice, I get it now. Thanks a lot!
Post reply on HN