Alternatives to using % operator to wrap around the end of an array?

[Ernst Blofeld]

I'm trying to make sensible optimisations to a code base that does a lot of operations on elements in arrays that need to "wrap around", i.e. the operation on the last element needs to include the first element. These are mostly algorithms that need to visit every directed edge of a polygon, so the last edge is given by the last and first vertices. There are other examples, but it's mostly this.

Up till now, to make sure the last edge is (n - 1) to (0), I've been using the % operator. This effects performance because it's just a division in disguise.

So, how to fix? I've come up with three options, below, none of which really make me feel happy. I'm currently using Option A, but I can't live with code like that. Option B looks like it might be efficient, but doesn't feel nice. Option 3 feels like it might be efficient but adds complexity that I feel a simple problem like this doesn't warrant.

Are there any options I've overlooked?

My priorities are efficiency without complexity that hides the intent of the code, and sticking to what's available in C99.

Here are the options I've considered in code. The arrays elements are typically pointers to structures, but I think this gives the essence.

Original:
---------

for (int i = 0; i < n; i++) {
    int a = x[i];
    int b = x[(i + 1) % n];

    // do something with a and b
}

Option A: Copy and Paste
------------------------

for (int i = 0; i < n - 1; i++) {
    int a = x[i];
    int b = x[i + 1];

    // do something with a and b
} {
    int a = x[n - 1];
    int b = x[0];

    // do something with a and b
}

Option B: Repeat the First Element
----------------------------------

x[n] = x[0];

for (int i = 0; i < n; i++) {
    int a = x[i];
    int b = x[i + 1];

    // do something with a and b
}

Option 3: Some Pointers
-----------------------

int * p = &x[0];
int * q = &x[n - 1];
for (int i = 0; i < n; i++) {
    int a = *p;
    int b = *q;

    // do something with a and b

    q = p;
    p++;
}

[thomas]

If the size of the array is a power of two you could use the & operator instead of %.

int n = 1 << 8;
int mask = n - 1;

for (int i = 0; i < n; i++) {
    int a = x[i];
    int b = x[(i + 1) & mask];

    // do something with a and b
}

[Ernst Blofeld]

Originally Posted by thomas

If the size of the array is a power of two you could use the & operator instead of %.

It's not, it could be anything.

[jotd]

You cannot got much past the array. Only 1, which would wrap to 0 with the modulus. So you can simply access with a ternary expression:

x[i < (n-1) ? (i+1) : 0]

the expression yields i+1 if i < n-1 else it yields 0 (no need to do i-n+1 since the only case where it happens is when i == n-1)

[Thomas Richter]

Originally Posted by Ernst Blofeld

Up till now, to make sure the last edge is (n - 1) to (0), I've been using the % operator. This effects performance because it's just a division in disguise.

Before you optimize... are you sure you have a performance problem?


Repeating the first element is ok as long as you can ensure that you keep the data structure consistent. The problem here might be that you forget updating the elements accordingly. C has a penalty as well, namely one additional level of indirection. Depending on the processor, this may or may not be more costly than the division.



Does the order of elements matter? Are there at least 2 elements in the array? If not, then there is a nice solution with pointers rather than indices:

xp   = &x[0];
lp    = &x[n];
last  = lp[-1];
do {
 current = *xp; do(current,last);
 last = current;
 xp++;
} while(xp < lp);

Advantage is that there is only one indirection per loop, and no need for an index, and only a check at the end of the loop.

[Ernst Blofeld]

Originally Posted by Thomas Richter

Before you optimize... are you sure you have a performance problem?

Yes, because optimising it in any way gives a noticeable increase in frames per second. Like from 3fps to 6fps if I apply the pattern in 2 places.

Originally Posted by Thomas Richter

Does the order of elements matter? Are there at least 2 elements in the array? If not, then there is a nice solution with pointers rather than indices:

xp   = &x[0];
lp    = &x[n];
last  = lp[-1];
do {
 current = *xp; do(current,last);
 last = current;
 xp++;
} while(xp < lp);

Advantage is that there is only one indirection per loop, and no need for an index, and only a check at the end of the loop.

There will always be at least 3 elements in the array. I will spend some time working through your code. It looks like an improved version of my third option. But are negative array indexes

last  = lp[-1];

allowed?

Thanks.

[jotd]

lp[-1] is just *(lp-1) so it's pointer arithmetic and it's allowed.

[Ernst Blofeld]

Originally Posted by jotd

lp[-1] is just *(lp-1) so it's pointer arithmetic and it's allowed.

I can see that, but I'll probably rewrite just that line to use direct pointer maths instead.

[sparhawk]

Is the array index any value, or do you just want to wrap around?

If you just want to wrap around, you can use:

wrap = ARRAYSIZE - index

This works only as long as index is smaller than twice arraysize.

[Ernst Blofeld]

Originally Posted by sparhawk

Is the array index any value, or do you just want to wrap around?

If you just want to wrap around, you can use:

wrap = ARRAYSIZE - index

This works only as long as index is smaller than twice arraysize.

I need to iterate over the array, not access randomly, but always having pairs of elements, i.e. start and end vertices of edges of a polygon that's defined by its vertices.

I tried Mr Richter's solution but ended up settling on my original Option 3. His solution is definitely better, but I had to stop and think when reading my implementation of it.

[sparhawk]

I just noticed that my solution doesn't really work, because if index is outside the range, then you get a negative index.

[Ernst Blofeld]

Originally Posted by sparhawk

I just noticed that my solution doesn't really work, because if index is outside the range, then you get a negative index.

You can fix that by adding a %.

[sparhawk]

Originally Posted by Ernst Blofeld

You can fix that by adding a %.

But then you are back to Post #1.