English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Language > Coders. C/C++

 
 
Thread Tools
Old 08 December 2020, 18:32   #1
Ernst Blofeld
<optimized out>

Ernst Blofeld's Avatar
 
Join Date: Sep 2020
Location: <optimized out>
Posts: 275
Alternatives to using % operator to wrap around the end of an array?

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.

Code:
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++;
}
Ernst Blofeld is offline  
Old 08 December 2020, 19:25   #2
thomas
Registered User
thomas's Avatar
 
Join Date: Jan 2002
Location: Germany
Posts: 6,191
If the size of the array is a power of two you could use the & operator instead of %.

Code:
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
}
thomas is offline  
Old 08 December 2020, 19:36   #3
Ernst Blofeld
<optimized out>

Ernst Blofeld's Avatar
 
Join Date: Sep 2020
Location: <optimized out>
Posts: 275
Quote:
Originally Posted by thomas View Post
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.
Ernst Blofeld is offline  
Old 08 December 2020, 19:38   #4
jotd
This cat is no more
jotd's Avatar
 
Join Date: Dec 2004
Location: FRANCE
Age: 49
Posts: 5,104
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:

Code:
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)

Last edited by jotd; 08 December 2020 at 19:45.
jotd is offline  
Old 08 December 2020, 19:46   #5
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 977
Quote:
Originally Posted by Ernst Blofeld View Post
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:
Code:
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.
Thomas Richter is offline  
Old 08 December 2020, 19:59   #6
Ernst Blofeld
<optimized out>

Ernst Blofeld's Avatar
 
Join Date: Sep 2020
Location: <optimized out>
Posts: 275
Quote:
Originally Posted by Thomas Richter View Post
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.

Quote:
Originally Posted by Thomas Richter View Post
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:
Code:
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.
Ernst Blofeld is offline  
Old 08 December 2020, 20:00   #7
jotd
This cat is no more
jotd's Avatar
 
Join Date: Dec 2004
Location: FRANCE
Age: 49
Posts: 5,104
lp[-1] is just *(lp-1) so it's pointer arithmetic and it's allowed.
jotd is offline  
Old 08 December 2020, 20:15   #8
Ernst Blofeld
<optimized out>

Ernst Blofeld's Avatar
 
Join Date: Sep 2020
Location: <optimized out>
Posts: 275
Quote:
Originally Posted by jotd View Post
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.
Ernst Blofeld is offline  
Old 15 December 2020, 16:37   #9
sparhawk
Registered User

sparhawk's Avatar
 
Join Date: Sep 2019
Location: Essen/Germany
Age: 52
Posts: 376
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.
sparhawk is offline  
Old 15 December 2020, 17:16   #10
Ernst Blofeld
<optimized out>

Ernst Blofeld's Avatar
 
Join Date: Sep 2020
Location: <optimized out>
Posts: 275
Quote:
Originally Posted by sparhawk View Post
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.
Ernst Blofeld is offline  
Old 15 December 2020, 17:51   #11
sparhawk
Registered User

sparhawk's Avatar
 
Join Date: Sep 2019
Location: Essen/Germany
Age: 52
Posts: 376
I just noticed that my solution doesn't really work, because if index is outside the range, then you get a negative index.
sparhawk is offline  
Old 15 December 2020, 18:19   #12
Ernst Blofeld
<optimized out>

Ernst Blofeld's Avatar
 
Join Date: Sep 2020
Location: <optimized out>
Posts: 275
Quote:
Originally Posted by sparhawk View Post
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 %.
Ernst Blofeld is offline  
Old 15 December 2020, 18:46   #13
sparhawk
Registered User

sparhawk's Avatar
 
Join Date: Sep 2019
Location: Essen/Germany
Age: 52
Posts: 376
Quote:
Originally Posted by Ernst Blofeld View Post
You can fix that by adding a %.

But then you are back to Post #1.
sparhawk is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Illegal Operator opt c-,ow, o+ W4r3DeV1L Coders. General 5 23 September 2019 21:45
Creating an array gives me a Guru Shatterhand Coders. Blitz Basic 14 13 August 2019 21:54
Illegal Operator on Include marduk_kurios Coders. Asm / Hardware 8 04 August 2017 21:09
Strange AsmOne operator phx Coders. Asm / Hardware 23 19 March 2015 00:13
In game screen grab & Wrap around Retro1234 request.Other 0 09 September 2011 20:08

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 09:49.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Page generated in 0.08647 seconds with 13 queries