I've been writing ring buffers wrong all these years

Re:I've been writing ring buffers wrong all these years by fla on Wednesday December 14, 2016 @10:02AM (#13176393)

Depending on the machine, a modulo can cost _alot_ .

Last time I checked, the operation cost was 26k cycles on my PIC.

Using a 2^n + mask made my queue perform 10 times faster (if not more).

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by jstimpfle on Wednesday December 14, 2016 @10:25AM (#13176597)

Don't use a modulo then. Use subtraction.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by dllthomas on Wednesday December 14, 2016 @10:57AM (#13176898)

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

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by pklausler on Wednesday December 14, 2016 @12:45PM (#13177951)

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.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by cksk on Thursday December 15, 2016 @11:44AM (#13185891)

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?

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by pklausler on Thursday December 15, 2016 @12:41PM (#13186424)

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

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by cksk on Thursday December 15, 2016 @01:20PM (#13186767)

Ohh, nice, I get it now. Thanks a lot!

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by avocad on Wednesday December 14, 2016 @03:42PM (#13179468)

Thanks! This AND trick is great. Actually makes me want to go back to assembly-level programming.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by dllthomas on Wednesday December 14, 2016 @02:30PM (#13178929)

Good point!

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by jnordwick on Wednesday December 14, 2016 @04:38PM (#13179894)

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

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by dllthomas on Wednesday December 14, 2016 @05:56PM (#13180500)

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.

[ Parent | on HN ]