Jump to content
  • Advertisement

Archived

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

paulecoyote

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.

If you intended to correct an error in the post then please contact us.

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
Advertisement
"% 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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!