Potentially faster array access in C++?

Member
Posts: 161
Joined: 2005.07
Post: #1
Okay, this just popped into my head after my explanation of memory access for arrays in some other thread:

If I have a lot of loops that access arrays like this:
Code:
int m;
for (m = 0; m < array_size; m++)
  blah(array[m]);
Would it be beneficial to access the arrays like this?
Code:
int m, start = 0, size = sizeof(array[0]);
for (m = 0; m < array_size; m++) {
  blah(*(array+start));
  start += size;
}
The reason I ask is because if I'm accessing memory sequentially like that, it looks like I could potentially avoid a multipy instruction on each array access. However, does anyone know if the compiler already makes some optimizations there?

It isn't completely important since the current functions are nice and efficient, but making it even faster certainly doesn't hurt when making games.
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #2
Never mind, I forgot using pointer math also seems to multiply by the size of each item too. That means using *(b + 1) is the same as b[1].

Hmph.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #3
It will be faster to just have another pointer and increment it each time. (++arrayPtr) That way it only adds the size each time, instead of having to multiply as well.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #4
The compiler will perform strength reduction (reducing multiplication by the loop index to incremental addition) automatically, so whilst akb825 is technically correct that it'd be faster, the compiler will do that for you.

Array index notation A[i] in C is just syntactic sugar -- A[i] is exactly equivalent to *(A + i), which is exactly equivalent to *(i + A) (wtf?) which is exactly equivalent to i[A]... now go baffle your compsci professors Wink
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #5
akb825 Wrote:It will be faster to just have another pointer and increment it each time. (++arrayPtr) That way it only adds the size each time, instead of having to multiply as well.
Oh yeah, looks like I had a brain fart there. LOL

OneSadCookie Wrote:The compiler will perform strength reduction (reducing multiplication by the loop index to incremental addition) automatically, so whilst akb825 is technically correct that it'd be faster, the compiler will do that for you.
Excellent, thank you. I just ran a quick test, and using pointer addition took the exact same time as using A[i]. That's good to know, especially since using array indexes keeps the code more readable.
Quote this message in a reply
Member
Posts: 39
Joined: 2002.04
Post: #6
OneSadCookie Wrote:The compiler will perform strength reduction (reducing multiplication by the loop index to incremental addition) automatically, so whilst akb825 is technically correct that it'd be faster, the compiler will do that for you.

Array index notation A[i] in C is just syntactic sugar -- A[i] is exactly equivalent to *(A + i), which is exactly equivalent to *(i + A) (wtf?) which is exactly equivalent to i[A]... now go baffle your compsci professors Wink

One can also do things like A[-4], which may actualy be useful if A is a pointer into a element in another array e.g. A = &(B[10]).
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #7
We did that in one of my classes, where we made a stack using just an array, where we have the first 3 elements hold information about the stack, and the rest is the stack. After we created it, we would return the address of the first data element. (I believe it was index 3)
Quote this message in a reply
Moderator
Posts: 522
Joined: 2002.04
Post: #8
Check out loop nest optimization (called many things)

http://en.wikipedia.org/wiki/Loop_nest_optimization

It can really make performance skyrocket in some situations if done right. (+10 ambiguous)

So the thing to realize is that CPUs have many levels of cache and they try to predict what parts of memory will be used next, so if you access memory in the right order you won't get as many cache misses. (That's when what your code wants is not in so and so cache)

-Jon
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Subclass access warnings in Objective-C vectorscope 2 3,999 Sep 15, 2009 10:02 AM
Last Post: vectorscope
  speeding up IO and memory access Atomical 3 3,058 Oct 10, 2005 05:04 PM
Last Post: Atomical