Array Index Wraparound
This page was last modified 2008-04-23 15:07:20 by Puchu.Net user Choco. (Show history)

I learned several years ago from school that modulus operations (% operator) is expensive. Never figured out how expensive it is, and I wondered if today's processors will magically speed up this process.

Very often I need to map a moving window to a data stream, and require a way to calculate the offset within that window using modulus operations. For example, the position in the stream modulo the size of the access window, when maintaining a FIFO/buffer as temporary storage.

Alternatives For This Experiment

Instead of calculating the offset every time using %, the offset is recalculated every time the window moves. For example:

buf[offset++] = data;
if (offset >= windowsize) offset = 0;

versus using modulus:

buf[offset++ % windowsize] = data

The difference is one requiring branching and the other modulus operation.

Experiment Results

With some test code, I am able to produce some timing data (in seconds) involving functions that use one of the two methods described earlier:

  1 2 3 4 5 ave.
branching 39.850 39.822 39.352 39.686 39.475 39.637
modulus 44.228 44.010 44.144 44.314 44.679 44.275

This is profiled on a quad-core computer over a 128MB data set, producing exactly the same output. The code path using modulus operation is taking about 12% more time to execute. Although more code is necessary to achieve the same results without using % operator, the return is significant. This is true especially if the branch prediction on your platform is very robust, and the likely result (as in this case) is very predictable.


Document is accessible from © 2002-2010 Sean Yang, Karen Yang, Don Yang and/or respective authors, all rights reserverd.

This material may contain (biased) opinions, inappropriate materials for numerous individuals, work of other authors from the internet, links that refer to other web documents and resources, or origial work that cannot be use for personal or commercial purposes. Please respect the work of original authors.

Creative Commons License
Powered By MediaWiki

© 2002-2010 Sean Yang, all rights reserved.