How to write fast programs

[JuLieN]

I recently found this very interesting pdf document called "How to write fast programs). And although most of us yet knows a lot of the thing it tells, there's always something to learn for someone.

So here it is:
http://www.sysecol2.ethz.ch/Publication ... s/Lo28.pdf
(A bit old, january 1996, but still useful IMO)

[bob]

I recently found this very interesting pdf document called "How to write fast programs). And although most of us yet knows a lot of the thing it tells, there's always something to learn for someone.

So here it is:
http://www.sysecol2.ethz.ch/Publication ... s/Lo28.pdf
(A bit old, january 1996, but still useful IMO)

Not sure how much of that can be trusted. Disconnecting from the network increases speed by 30%. REALLY?

Some other things mentioned, any good compiler takes care of already.

[Kempelen]

I recently found this very interesting pdf document called "How to write fast programs). And although most of us yet knows a lot of the thing it tells, there's always something to learn for someone.

So here it is:
http://www.sysecol2.ethz.ch/Publication ... s/Lo28.pdf
(A bit old, january 1996, but still useful IMO)

I remember a good advice that explain that it is impossible to write fast programs, because the number of instruction per minute in a CPU is always fix, so the trick is not doing fast code, but code that do less. I always remember this when coding and it is the best advice I received.

[JuLieN]

@Grumpy Bob
Oh come one, lots of these ideas are still good to keep in mind when one is writing code!

@Fermin
Right, not a bad advice either!

[Edmund]

there's always something to learn for someone ...

Rule 8(7) Avoid recursions.

I bet there is only a handful of iterative search programs out there.

[Dave_N]

Rule 6(3) Minimise the cost of addressing/accessing if using multi-dimensional arrays.
In order to explain rule 6(3) we use an example written in pseudo code.
I1 = 2;
...
FOR I=1 TO NVAR DO ***** version 1 *****
DEY[1,I,I1] = Y
FOR J=1 TO K DO
YP = YP + (Y - DEY[J,I,I0]) * GKS[J]
DEY[J+1,I,I1] = YP
END
END
...
FOR I=1 TO NVAR DO ***** version 2 *****
DEY[I,1,I1] = Y
FOR J=1 TO K DO
YP = YP[I) + (Y - DEY[I,J,I0]) * GKS[J]
DEY[I,J+1,I1] = YP
END
END
Wild jumping in the physical addresses of a computer for storing values into an array slows
down an algorithm. It is better to address it consecutively within the multi-dimensional array
therefore reducing the time needed for physical addressing.
Version 1 is therefore the faster variant for languages storing multi-dimensional column oriented, whereas version 2 is faster for row oriented languages.

How does the example look in C/C++ ... obviously its the difference between

Code: Select all

int array2d[1024][1024];
int sum;

for&#40; unsigned int a = 0; a < 1024; a++ )
&#123;
    for&#40; unsigned int b = 0; b < 1024; b++ )
   &#123;
        sum += array2d&#91;a&#93;&#91;b&#93;;
   &#125;
&#125;

and 

for&#40; unsigned int b = 0; b < 1024; b++ )
&#123;
    for&#40; unsigned int a = 0; a < 1024; a++ )
   &#123;
        sum += array2d&#91;a&#93;&#91;b&#93;;
   &#125;
&#125;

I think the 2nd case is slower, not sure though.

[/code]

[lucasart]

IMO best advice to write efficient code is:
1/ understand what the compiler does with your code, and that goes a very long way... this also restricts the choice of programming languages: I only use C because I know what a C compiler does. I do not use C++ because a C++ compiler is infinitely more complex than a C compiler, and in many cases I don't know what the C++ compiler will do...
2/ do not listen to any advice, accept no rule from anyone, even from this paper. especially do not listen to anyone on talkchess (starting with me) and use a profiler and common sense (your common sense can only be useful if you understand 1/)

[JuLieN]

IMO best advice to write efficient code is:
1/ understand what the compiler does with your code, and that goes a very long way... this also restricts the choice of programming languages: I only use C because I know what a C compiler does. I do not use C++ because a C++ compiler is infinitely more complex than a C compiler, and in many cases I don't know what the C++ compiler will do...
2/ do not listen to any advice, accept no rule from anyone, even from this paper. especially do not listen to anyone on talkchess (starting with me) and use a profiler and common sense (your common sense can only be useful if you understand 1/)

I went into an infinite loop after reading your point #2 and decided it was time to catch some sleep.

[Dave_N]

In fact the method of creation of 2D arrays with pointers more or less proves the alignment issue (i.e. from int **array2D)

interesting read thank you for sharing. I think some numbers for the amount of slowdown to expect from computing with double's would be interesting.