#### Archived

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

# Circular Arrays / Ring Buffers - this the best way?

This topic is 5218 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
If your array size is a power of two, you can convert a % operation to an &

##### 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."

Measure, measure, measure!

##### 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 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 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]

1. 1
2. 2
Rutin
25
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 22
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631765
• Total Posts
3002213
×