Good book

[Tinus1959]

At the moment I'm reading the first two parts of the series "write great code". This should be on the list of every programmer. After reading you understand what is going on IN the computer and why things get slowed down.

One example:
I want to fill a two dimentional array whit the product of the indeces. So I declare the array and start filling with a two level loop.

For n = 0 to 1023 do
For m = 0 to 1023 do
a[m,n] = m*n
next m
next n

Compare this to:

For n = 0 to 1023 do
For m = 0 to 1023 do
a[n,m] = m*n
next m
next n

It might be hard to believe, but one code is much faster than the other.

Why is this?
I'll give the explanation next week.

[dmarsh]

Multidimensional arrays are still constructed out of a large block of contiguous memory, ie in effect they are a one dimensional array, anyone who has programmed assembler, C or has used overlays in FORTRAN, or has reverse engineered code will know this.

To index into the second dimension you must offset by the size of the second dimension, effectively paging the array. For arrays of non trivial size linear access of the array will be faster because it will result in less paging of virtual memory.

One part of code will sweep memory in a linear fashion, the other will jump to the same position in each 'page', resulting is a vast amount of jumping around.

The multiplication despite the change in the operands will be a constant time operation for each iteration.
The two pieces of code are not equivalent as they will store the results in a different order in memory.

This is why people say you should learn assembler or C and why embedded and games programmers are respected more than other programmers. You need to understand the machine and the back end of your compiler or you JVM and your OS, all of it.

Programmers used to create whole worlds in 64k, assembly lang programmers would chose op codes to save one cpu cycle, you should at least understand the performance characteristics of you chosen algorithms and their implementation.

[Tinus1959]

Spot on! Very good.