Avoid accessing an array to speed up the code?

M

MBALOVER

Hi all,

My objective is to make my program written in C as fast as I can.

I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?

For example, is Version 2 faster than Version 1?

Version 1:

int A[10];
A[5]=10;

for (i=0;i<1000;++i)
{
if (A[5]>8)
printf("helllo");
}


Version 2:

int A[10];
A[5]=10;
B=A[5]; //<== Now I use variable B instead of the A[5]

for (i=0;i<1000;++i)
{
if B>8
printf("hello");
}

Thank you.
 
B

Barry Schwarz

Hi all,

My objective is to make my program written in C as fast as I can.

I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?

For example, is Version 2 faster than Version 1?

Version 1:

int A[10];
A[5]=10;

for (i=0;i<1000;++i)
{
if (A[5]>8)
printf("helllo");
}


Version 2:

int A[10];
A[5]=10;
B=A[5]; //<== Now I use variable B instead of the A[5]

for (i=0;i<1000;++i)
{
if B>8
printf("hello");
}

If the subscript is a constant, probably not. While not required to,
most compilers will perform the address calculations at compile time
and execution time to access the array element would be the same as
for a non-array object of the same type.

For a variable subscript, it depends on several factors including how
well the compiler recognizes repeated references with an unchanged
subscript, how often you reference the object, whether the sizeof the
object is a power of 2, etc.

This is more a quality of implementation issue rather than a language
issue.
 
J

Jens Thoms Toerring

MBALOVER said:
My objective is to make my program written in C as fast as I can.
I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?
For example, is Version 2 faster than Version 1?
Version 1:
int A[10];
A[5]=10;
for (i=0;i<1000;++i)
{
if (A[5]>8)
printf("helllo");
}
Version 2:
int A[10];
A[5]=10;
B=A[5]; //<== Now I use variable B instead of the A[5]
for (i=0;i<1000;++i)
{
if B>8
printf("hello");
}

There's no way to say for sure. You have two things: there's the
C language and then you have a compiler that converts a program
written in C into machine code (not to go into too much detail).
The C language doesn't state "doing something this way will be
faster than doing it some other way." How fast things are going
to be depends on how the the compiler converts the C program into
machine code.

There's a good chance that the compiler will notice that you
use A[5] over and over again in a tight loop in version 1, so
it may just emit code for you version 1 that is roughly equiva-
lent to that for your version 2 (with the value of A[5] stored
in a CPU register).

But if you look at the two versions of the program (disregarding
syntax errors;-) you immediately will see that there's an even
"faster" version

int A[ 10 ];
A[ 5 ] = 10;

if ( A[ 5 ] > 8 )
{
for ( i = 0; i < 1000; ++i )
printf( "hello" );
}

since with this version you don't do all the (redundant) checks
within the loop over and over again. The compiler may be able
to notice this and output machine code that is equivlent to code
generated from version 3, even for version 1 and 2 of your pro-
gram.

But the compiler may even notice that A[5] is always larger than
8, so the machine code you may end up with could very well be
just the equivaled of

int A[ 10 ];
A[ 5 ] = 10;

for ( i = 0; i < 1000; ++i )
printf( "hello" );

or even

int A[ 10 ];
A[ 5 ] = 10;
print( "hellohellohellohello/ repeat 995 times /hello");

So, you can't say "If I write something this way it will be
faster." The C language hasn't any built-in guarantees for
any of this. If something is faster or slower depends on how
good the compiler you use is at optimizing the C code you
pass to it for the machine it's going to be run on.

Getting compilers to create faster machine code is an on-going
effort. Compilers have gotten quite good at that and the usual
recommendation nowadays thus seems to be to write code that's
easy to understand and let the compiler take care of optimiza-
tions (writing too convoluted code may even throw off the com-
piler and result in slower execution). Only if there's a bottle-
neck you found by actually measuring how much time is spend at
certain parts of your program it makes sense to worry about re-
arranging the C code in order to help the compiler to emit
faster machine code (and then this will probably only work
with the compiler you did the measurements with and on that
architecture, using a different compiler or architecture the
same "improvements" may end up being contraproductive).

There's a lot of folklore to be found about "this will result
in faster code" but be wary of such claims - they may have been
correct 20 years ago when compilers weren't as good as they are
today. If you really need utmost speed (with a certain compiler
on a certain architecture) the only thing you should trust is
careful measurements and not believe in some "I read somewhere
that this is faster than that." statements.

If you are interested what happens mainly out of curiosity then
having a look at the assembler code generated by the compiler
might be enlightening. But just don't assume that the results
you get from one compiler will be the same as that fron another
one.
Regards, Jens
 
P

Phil Carmody

If you are interested what happens mainly out of curiosity then
having a look at the assembler code generated by the compiler
might be enlightening. But just don't assume that the results
you get from one compiler will be the same as that from another
one.

However, as an aside, GCC's often had as its objective the mimicking
of a chip vendor's own optimising compiler.

Phil
 
S

Seebs

My objective is to make my program written in C as fast as I can.

You should probably not be doing this.

Hand-tuning is an extremely difficult skill requiring a great deal of
knowledge. There are no rules for how to do it that don't have significant
exceptions.

If you have to ask the question, no answer to it will be good for you.
I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?
Maybe.

For example, is Version 2 faster than Version 1?

Sometimes yes, sometimes no.

Stop. You are doing the wrong thing. You are asking meaningless questions
because you don't have the right basic cognitive framework to approach this.

1. Compilers can do all sorts of crazy stuff. It is quite possible that
your two programs would, in fact, produce IDENTICAL code for many targets.
2. Even if they don't, that doesn't necessarily tell you *for sure* which
one will be faster. You could easily come up with a counterexample if you
tried hard enough.
3. If you don't start by already having detailed profiling information
showing where your program is spending it's time, all you're going to do is
make a program which isn't really noticably faster, but which is much buggier.

Start by writing a program that is clear and definitely correct. Understand
that program well. Then look to see where it is spending its time. Then
start thinking about ways to improve that. In most cases, the kinds of
trickery you're talking about will be COMPLETELY useless. I don't just mean
not useful enough to be worth the effort; I really do mean *COMPLETELY*
useless.

Learn more, slow down, and don't try to do something elaborate and complicated
without first understanding what you're doing.

-s
 
M

Michael Foukarakis

Hi all,

My objective is to make my program written in C as fast as I can.

I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?

For example, is Version 2 faster than Version 1?

Version 1:

int A[10];
A[5]=10;

for (i=0;i<1000;++i)
{
    if (A[5]>8)
      printf("helllo");

}

Version 2:

int A[10];
A[5]=10;
B=A[5]; //<== Now I use variable B instead of the A[5]

for (i=0;i<1000;++i)
{
  if B>8
  printf("hello");

}

Measure, measure, measure. Theoretically, they should be the same,
but...measure, measure, measure.
 
W

Willem

MBALOVER wrote:
) Hi all,
)
) My objective is to make my program written in C as fast as I can.

Use a good optimizing compiler.

) I read somewhere that I should avoid accessing an array too much
) because it takes processor's time. Is that true?

No, the optimizer will take care of that.

) For example, is Version 2 faster than Version 1?

No, they will be the same for any decent optimizing compiler.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
B

bartc

MBALOVER said:
Hi all,

My objective is to make my program written in C as fast as I can.

I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?

For example, is Version 2 faster than Version 1?

Version 1:
if (A[5]>8)
printf("helllo");
Version 2:
if B>8
printf("hello");
}

The difference, if any, will be negligible. Especially when A[5]>8, when the
time will be dominated by the printf() call (taking, on my machine, about
200000 times longer than the rest of the loop).
 
P

Pierre Asselin

MBALOVER said:
I read somewhere that I should avoid accessing an array too much
because it takes processor's time. Is that true?

Measure it. It probably won't matter in practice but you never know.

One reason to make a local copy is to avoid aliasing issues.
If you do

extern int A[10];
int i, j, *p;
/* ... */
i= A[5];
*p= 11;
j= A[5];

the compiler can't replace the last assignment by "j= i;" because
the assignment through *p may have overwritten A[5]. However if
you do

extern int A[10];
int i, *p, B;
/* ... */
B= A[5];
i= B;
*p= 11;
j= B;

with a local variable B whose address is never taken, the assignment
to *p can't overwrite B (in a conforming program) and the compiler
can do all sorts of caching, reordering and other optimizations.

Eliminating memory references is probably more important nowadays
than the exact machine instructions emitted. The "restrict" keyword
of C99 gives the compiler licence to optimize more aggressively in
this way. Whether compilers use that license is another matter.

In real life it gets more complicated than in the contrived examples
above. Always profile and measure your code before assuming that
something is a bottleneck. Learn what profiling tools are available
on your platform. If you don't, you will *always* optimize the
wrong thing!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top