Performance difference in accessing an item in an array vs pointer reference?

Question

I'm fresh to C - used to scripting languages like, PHP, JS, Ruby etc. Got a query in regard to performance. I know one should not micro optimize too early - however, I'm writing a Ruby C Extension for Google SketchUp where I'm doing lots of 3D calculations so performance is a concern. (And this question is also for learning how C works.)

Often many iterations is done to process all the 3D data so I'm trying to work out what might be faster.

I'm wondering if accessing an array entry many times is faster if I make a pointer reference to that array entry? What would common practice be?

struct FooBar arr[10];
int i;
for ( i = 0; i < 10; i++ ) {
  arr[i].foo = 10;
  arr[i].bar = 20;
  arr[i].biz = 30;
  arr[i].baz = 40;
}

Would this be faster or slower? Why?

struct FooBar arr[10], *item;
int i;
for ( i = 0; i < 10; i++ ) {
  item = &arr[i];
  item->foo = 10;
  item->bar = 20;
  item->biz = 30;
  item->baz = 40;
}

I looked around and found discussions about variables vs pointers - where it was generally said that pointers required extra steps since it had to look up the address, then the value - but in general there wasn't a bit hit.

But what I was wondering was if accessing an array entry in C has much of a performance hit? In Ruby it is faster to make a reference to the entry if you need to access it many time - but that's Ruby...

In theory there is no difference (as long your array fits into cache). Problem will appear once it does not fit into cache. — Tomas Pruzina
– Tomas Pruzina, Commented Mar 12, 2012 at 12:22
You can try both alternatives, and then look at the generated assembly code. My guess is that the compiler will optimize both to the same code anyway. — Some programmer dude
– Some programmer dude, Commented Mar 12, 2012 at 12:23
"I know one should not micro optimize too early", but you're going to do so anyway — David Heffernan
– David Heffernan, Commented Mar 12, 2012 at 12:28
@AoeAoe Why? My view is that good compilers will emit identical code. — David Heffernan
– David Heffernan, Commented Mar 12, 2012 at 12:28
'"I know one should not micro optimize too early", but you're going to do so anyway' - In Ruby there is such a big difference that when you run many iterations it's quickly significant so I use it all the time. Wondered if it was of any concern at all in C or if I would just ignore it. — thomthom
– thomthom, Commented Mar 12, 2012 at 12:38

Steve Jessop · Accepted Answer · 2012-03-12 12:57:29Z

6

There's unlikely to be a significant difference. Possibly the emitted code will be identical. This is assuming a vaguely competent compiler, with optimization enabled. You might like to look at the disassembled code, just to get a feel for some of the things a C optimizer gets up to. You may well conclude, "my code is mangled beyond all recognition, there's no point worrying about this kind of thing at this stage", which is a good instinct.

Conceivably the first code could even be faster, if introducing the item pointer were to somehow interfere with any loop unrolling or other optimization that your compiler performs on the first. Or it could be that the optimizer can figure out that arr[i].foo is equal to stack_pointer + sizeof(FooBar) * i, but fail to figure that out once you use the pointer, and end up using an extra register, spilling something else, with performance implications. But I'm speculating wildly on that point: there is usually little to no difference between accessing an array by pointer or by index, my point is just that any difference there is can come for surprising reasons.

edited Mar 12, 2012 at 12:57

answered Mar 12, 2012 at 12:42

Steve Jessop

281k40 gold badges473 silver badges709 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

thomthom Over a year ago

So accessing a value in an array is the same as accessing a "flat" variable? foo = bar[4] has no penalty over biz = baz? Would it be different if the array is dynamically allocated?

Steve Jessop Over a year ago

@thomthom: I make no promises, but when you access an automatic array by name, the compiler knows where it is on the stack and can optimize accordingly. So bar[4] could be calculated at compile time to be at the offset from the stack pointer equal to the offset of bar, plus 4 times the size of each element, and there would be no calculation needed at runtime involving the number 4. Using a pointer to the first element of the array instead of a name, the compiler might still be able to figure out what value was assigned to that pointer and do the same optimization, or it might not.

Steve Jessop Over a year ago

... it depends where the pointer came from. Your example is a fairly good candidate for the compiler to notice what's going on, if it does unroll the loop.

unwind · Accepted Answer · 2012-03-12 12:52:08Z

2

If were worried, and felt like micro-optimizing it (or just were in a pointer-oriented mood), I'd skip the integer index and just use pointers all over:

struct FooBar arr[10], *item, *end = arr + sizeof arr / sizeof *arr;
for (item = arr; item < end; item++)
  item->foo = 10;
  item->bar = 20;
  item->biz = 30;
  item->baz = 40;
}

But please note: I haven't compiled this (or your code) and counted the instructions, which is what you'd need to do. As well as running it and measuring of course, since some combinations of multiple instructions might be faster than shorter sequences of other instructions, and so on.

answered Mar 12, 2012 at 12:52

unwind

402k64 gold badges492 silver badges620 bronze badges

3 Comments

Steve Jessop Over a year ago

And in any case measurement is difficult. If you write a simple benchmark loop, it may or may not reflect real use of the array (how hot the cache is and so on). The optimizer might detect that your benchmark does nothing and apply optimizations that wouldn't be valid in real use. So the only truly sound test of performance is real application code: that is, profile a real app rather than counting instructions or benchmarking small snippets in isolation.

thomthom Over a year ago

I understand - there's no obvious advantage. One has to check where the bottleneck is if there is any. That's what I wanted to find out. In Ruby there are so many bottlenecks in regard to looking up values so I'm chronically worried about it and I've learned what patterns are faster than others. The patterns in C appear to be very different. (Not surprisingly.)

Christian Rau Over a year ago

@thomthom Well, it's quite reasonable, considering what range-checking or polymorphism rubbish Ruby might do for a simple array access.

Collectives™ on Stack Overflow

Performance difference in accessing an item in an array vs pointer reference?

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related