Array access taking O(1) time improvable?

Question

I've been reading a book assigned for class and it mentions that array access takes O(1) time. I realize that this is very fast (maybe as fast as possible), but if you have a loop that has to refer to this a few times, is there any advantage to assigning a temporary variable to have the value looked up in the array? Or would using the temporary variable still be O(1) to use as well?

I'm assuming this question is language independent. Also I realize that even if the answer is yes that the advantage is tiny, I'm just curious.

Answer 1

Note that O(1) doesn't mean "instantaneous." It just means "at most some constant." This means that both 1 and 10¹⁰⁰⁰ are both O(1), even though the second of these is bigger than the number of atoms in the universe.

If you are repeatedly accessing the same array element multiple times, it will take O(1) time for each access. Storing that array element in a local variable also gives O(1) lookup time, but the constants might not be the same. It might be better to pick one option over the other, but you'd really have to profile the program to be sure.

In practice, this sort of microoptimization is unlikely to have a measurable effect on program time unless the code you're running accounts for a huge fraction of the program's running time. I would be shocked to find an example where this change would make a noticeable impact in any real code.

Modern architectures probably might make this change a bit faster, but not dramatically so. If you keep accessing the same array element multiple times, the processor will probably keep that part of the array in cache, making lookups really fast. Also, a good optimizing compiler might already turn the non-local-copy code into the local copy code for you.

Hope this helps!

Answer 2

If I understand, you're asking if

for (int i=0; i<len; i++) {
   int temp = ar[i];
   foo += temp;
   bar -= temp;
}

is any better than:

for (int i=0; i<len; i++) {
   foo += ar[i];
   bar -= ar[i];
}

I wouldn't worry about it:

If the code in the body of your loop is going to access the same array entry, say ar[i] multiple times, any halfway decent compiler (at a nonzero optimization level) will keep that value in a register for quick re-use. In other words, the compiler will probably generate the exact same assembly given the either of the above code samples.

Note that either of these is still O(1) (accessing one thing one time). Don't confuse big-O notation of algorithms with instruction-level optimizations.

Edit

I just compiled a sample program with two functions, containing the above two samples, and at -O2 gcc 4.7.2 generated the exact same machine code; byte-for-byte.