array index and pointer

[amit khan]

Hello friends:

p is an array and N is a large number. Which of the following two
loops is faster?

Case1:

for(i=0; i<N; i++){
p = i;

}

Case2:

for(i=0; i<N; i++){
*p = i;
p++;

}

It seems that Case 1 needs multiplication/shifting to calculate the
address/index and the second case needs only an ADD operation. But I
tested it, the speed is almost the same. Can anybody tell me why?
Thanks.

 

[Eric Sosman]

Hello friends:

p is an array and N is a large number. Which of the following two
loops is faster?

Case1:

for(i=0; i<N; i++){
p = i;

}

Case2:

for(i=0; i<N; i++){
*p = i;
p++;

}

The second is faster. Since it won't compile and hence won't
run, it takes zero execution time. (You might want to review
Question 6.2 in the comp.lang.c Frequently Asked Questions (FAQ)

It seems that Case 1 needs multiplication/shifting to calculate the
address/index and the second case needs only an ADD operation. But I
tested it, the speed is almost the same. Can anybody tell me why?

Compilers are good at a class of code transformations known as
"strength reduction," which try to replace expensive operations
with cheaper substitutes. In the case at hand, the compiler has
probably noticed that the apparent series of multiplications

T = X * 0
T = X * 1
T = X * 2
...
T = X * (N-1)

can be replaced by

T = 0
T += X
T += X
...
T += X

 

[amit khan]

I searched a little bit on the internet and it seems that nowadays
the
compiler is really smart that it can do many optimizations. So is it
still worth doing it by ourselfs? Or can we say that we should only
try to optimize the algorithm itself instead the code?

The other example is like this, which is very common in image
processing:
for(i=0;i<h;i++) for(j=0;j<w;j++)
p[i*w+j] = ...;

VS.
for(i=0; i<h; i++){
p_temp = p + i*w;
for(j=0; j<w; j++){
p_temp[j] = ...;
}
}

I tested those two cases, and the speed is almost the same...

Any ideas?

Hello friends:

p is an array and N is a large number. Which of the following two loops
is faster?

Case1:

for(i=0; i<N; i++){
p = i;

}

Case2:

for(i=0; i<N; i++){
*p = i;
p++;

}

The second is faster. Since it won't compile and hence won't
run, it takes zero execution time. (You might want to review Question
6.2 in the comp.lang.c Frequently Asked Questions (FAQ) page

It seems that Case 1 needs multiplication/shifting to calculate the
address/index and the second case needs only an ADD operation. But I
tested it, the speed is almost the same. Can anybody tell me why?

Compilers are good at a class of code transformations known as
"strength reduction," which try to replace expensive operations with
cheaper substitutes. In the case at hand, the compiler has probably
noticed that the apparent series of multiplications

T = X * 0
T = X * 1
T = X * 2
...
T = X * (N-1)

can be replaced by

T = 0
T += X
T += X
...
T += X

 

[Seebs]

Hello friends:

p is an array and N is a large number. Which of the following two
loops is faster?
Neither.

It seems that Case 1 needs multiplication/shifting to calculate the
address/index and the second case needs only an ADD operation. But I
tested it, the speed is almost the same. Can anybody tell me why?

Because you don't understand C.

There is no requirement that the actual operations performed be the ones
you think you have described; all that's required is that the output is
the same.

Compilers typically know most of the common loop idioms and express them
well.

Let me put it more directly: If you are wasting your time thinking about
whether or not one of these loops is "faster", you are unlikely to ever
become a good programmer. Turn back from that path of madness.

Write code that is clear, effective, and easy to understand. If you find
that it is not fast enough, start by profiling it to see where the time
is going. Look at the things that are taking the most time. See if there is
a way to change your algorithm to reduce their frequency; if you are
calling a comparison routine millions of times, a switch of sorting
algorithms can reduce that to tens of thousands, or a week's back-breaking
effort can reduce the cost of each call by 10%.

Don't try to figure out "what really happens", because that's not how C
works. What really happens is the compiler does something magical that
happens to result in the results that would have happened according to the
behavior of the abstract machine. Don't waste your time trying to guess
whether or not there are multiplies or something like that involved;
stick to the abstractions, and you'll have a better feel for what to expect.

-s

 

[Seebs]

I searched a little bit on the internet and it seems that nowadays
the
compiler is really smart that it can do many optimizations. So is it
still worth doing it by ourselfs?

At your level of experience: No.

For someone extremely experienced, ideally with compiler development
experience: No*.

[*] Someone at this level of experience will likely understand the exceptions.

Or can we say that we should only
try to optimize the algorithm itself instead the code?

In general, yes.

Any ideas?

Try paying attention to the part where people tell you you're wasting your
time, instead of coming up with more examples that you also don't understand.

-s

 

[bart.c]

Don't try to figure out "what really happens", because that's not how C
works. What really happens is the compiler does something magical that
happens to result in the results that would have happened according to the
behavior of the abstract machine. Don't waste your time trying to guess
whether or not there are multiplies or something like that involved;
stick to the abstractions, and you'll have a better feel for what to
expect.

If the array element size is an odd value, such as 7 bytes, then exactly how
the compiler accesses each element can be significant, especially where
there are no obvious optimisations.

So some knowledge about this can be useful; for example, padding the
elements to 8 bytes can be more efficient.

 

[Keith Thompson]

If the array element size is an odd value, such as 7 bytes, then exactly how
the compiler accesses each element can be significant, especially where
there are no obvious optimisations.

So some knowledge about this can be useful; for example, padding the
elements to 8 bytes can be more efficient.

Which is why compilers will typically do this for you.

 

[Eric Sosman]

I searched a little bit on the internet and it seems that nowadays
the
compiler is really smart that it can do many optimizations. So is it
still worth doing it by ourselfs? Or can we say that we should only
try to optimize the algorithm itself instead the code?
[...]

Have you ever been micro-managed? Had one of those compulsively
hands-on bosses who not only tells you what to do but hovers over you
and tells you exactly how to do it? "Don't click the toolbar to get a
menu; ALT-Shift-Q is quicker." "Use ptr[0] instead of *ptr." "Amit,
how many times must I tell you not to begin variable names with vowels?"

Ever had a boss like that? Did the micro-management improve the
quality of your work, or did it get in the way by distracting you from
what you should have been thinking about? Did it help you apply your
own ingenuity to solving problems, or did it stifle your creativity?

Don't micro-manage your compiler.

 

[Nick Keighley]

I searched a little bit on the internet and it seems that nowadays
the
compiler is really smart that it can do many optimizations.  So is it
still worth doing it by ourselfs?  Or can we say that we should only
try to optimize the algorithm itself instead the code?

first right your code as clearly as you can. Factorise it well (remove
repetitive code). Make sure you have a correct program before you
start to worry about speed or space.

Sometimes it is necessary to optimise code yourself but probably not
as often as you seem to think. Better algorithms often make a bigger
difference than code tweaks.

None of this is reason for writing bad code!

 

[John Bode]

I searched a little bit on the internet and it seems that nowadays
the
compiler is really smart that it can do many optimizations.  So is it
still worth doing it by ourselfs?  Or can we say that we should only
try to optimize the algorithm itself instead the code?

For most applications, focus on picking the right algorithms and data
structures, write your code in a straightforward, easy-to-understand
manner, and leave code-level optimization decisions to the compiler.
The more straigtforward your code is, the easier it will be for the
compiler to optimize (in general).

While speed does matter, it matters less than correctness, robustness,
and maintainability. It doesn't matter how fast your code is if it
gives you the wrong answer, or if it dies at the first hint of bad
input, or if you can't understand it six weeks after you wrote it.

There may be times when you will have a hard performance requirement
(e.g. the time allowed to perform a specific operation is limited to x
milliseconds), and you may have to resort to writing code in a certain
way to meet that requirement. However, this should only be done after
profiling the code to find the real bottlenecks, and if you to know
*exactly* how your compiler will translate code.