I've been writing ring buffers wrong all these years • Hacker News Board

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

#171

Post by dllthomas » Thu, Dec 15, 2016, 11:35 PM UTC

emn13 wrote: post #160

simcop2387 wrote: post #93

Earlier quoted context omitted.

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 u…

With the conditional subtraction recommended elsewhere, you can do 2*N with no branch mispredictions and no modulo. Whether that's actually faster should be tested, if you're in an environment where you care about such things.

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

#172

Post by mikekchar » Fri, Dec 16, 2016, 3:48 AM UTC

doktrin wrote: post #158

mikekchar wrote: post #156

Earlier quoted context omitted.

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

Don't worry. Programming and computer science is one of those things that anyone can learn on their own. If you don't mind some advice, though, try not to be embarrassed by things that you don't know. I can imagine that it is difficult, especially if you don't feel confident about your previous education. Even if most other people already know it, it just means that you have the pleasure of discovering it (as a certain XKCD comic pointed out).

One thing I've said to many people starting out (especially those without an academic background in the area) is that there is a lot to learn. Sometimes at the beginning, you improve so quickly that it is easy to think, "I must be getting close to knowing it all". After several decades in the industry, though, I'm still learning brand new (to me!) , important things every single day. In many ways, the best programmers are the ones who can see how much they don't know, not how much they do know.

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

#173

Post by doktrin » Fri, Dec 16, 2016, 9:07 AM UTC

mikekchar wrote: post #172

doktrin wrote: post #158

Earlier quoted context omitted.

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

Don't worry. Programming and computer science is one of those things that anyone can learn on their own. If you don't mind some advice, though, try not to be embarrassed by things that you don't know. I can imagine that it is difficult, especially if you don't feel confident about your previous education. Even if most other people already know it, it just means that you have the pleasure of discovering it (as a certa…

I want you to know I genuinely appreciate you taking the time to write that. It's both helpful and uplifting. I've been going through a rough patch professionally and in life, and your comment lifted my spirits and brought me to tears (as absurd as I'm sure that must sound).

From one stranger on the internet to another : thank you.

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

#174

Post by jnordwick » Sun, Dec 18, 2016, 12:01 AM UTC

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

It might have something to do with the branch not being part of a loop so the best it can do is assume the branch is random (think something like modding a hash code when it would indeed be random).

Ad was pointed out in the thread, recent cpus have reduced the latency of cmov to a cycle. So your result could also depend on your architecture.

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

#175

Post by jnordwick » Sun, Dec 18, 2016, 12:21 AM UTC

gpderetta wrote: post #162

smallnamespace wrote: post #153

Earlier quoted context omitted.

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.

Just looked it up. Yes, from Broadwell forward a reg to reg cmov has latency 1. On Atom processors it is still 6.

If you decrement your array index you don't even need the cmp instruction. The compiler could probably gen so good code.