Archived

This topic is now archived and is closed to further replies.

paulecoyote

Circular Arrays / Ring Buffers - this the best way?

Recommended Posts

Hi there, Implementing a circular array / ring buffer that loops around and can have any amount of steps negative or positive (but always whole steps) applied to it, so it wraps around. The maths I got (which works) is: For positive (right) steps newpos = ( currentPos + x ) % arraySize For negative (left) steps newpos = ( currentPos + ( arraySize - ( x * -1) ) ) % arraySize I know that the mod operator is quite expensive usually, so is there any better way? (Not using linked lists or any other structure, random and indexed access to the collection is paramount). Cheers, Paul

Share this post


Link to post
Share on other sites
"% is expensive"
This statement is false in isolation. Make sure that you know that this will be a bottleneck, or you''re going to waste your time "optimizing."

See my other post in the thread about c++ code tuning.

Measure, measure, measure!

Share this post


Link to post
Share on other sites
Cheers, it is a power of two!

Don''t worry, I''m not optimising for optimising sake - just wondered if there is a better that''s all ;-) All too easy to get caught up in the detail huh?

Share this post


Link to post
Share on other sites
Just to make sure you get it right: for x a power of 2, (a % x) becomes (a & x-1), not (a & x).

In cases where your "step size" is guaranteed to be within +/- the array size, you can instead use a conditional and subtraction/addition:

newpos += x;
if (newpos >= arraySize) newpos -= arraySize;
if (newpos < 0) newpos += arraySize;


[edited by - Zahlman on April 6, 2004 6:20:29 AM]

Share this post


Link to post
Share on other sites
or, if it is (like you said) a power of 2, you only need

pos += x;
pos &= size - 1;

x being either positive or negative

should compile down to 2 asm instructions
even though cpus are getting faster, and you should always profile before optimizing, there is no loss in implementing simple, self explanatory, and might I say, cleaner code that runs faster..
div (and mod, usual 1 instruction) is still the most expensive basic arithmetic instruction (excluding composite instructions such as sin/cos/ln etc) in any hardware implementation today

[edited by - BiTwhise on April 6, 2004 1:58:11 PM]

Share this post


Link to post
Share on other sites