Re: (topic change on) Teaching sorts

["Marcus H. Mendenhall" <mendenmh@nashville.net>]

Christian Bau wrote:
-> On a real computer (PowerMac, no virtual memory, no background 
processes,
-> nothing that would interfere with execution time), the _number of
-> instructions per second_ did reproducably vary by a factor up to 
_seven_
-> when going from n to n+1 (for example, case n = 128 took seven times
-> longer than cases n = 127 and n = 129). So for this computer, and 
this

Isn't cacheing fun?  I have observed many bizarre effects on the 
PowerMacs when one is doing work which involves thrashing memory (FFT's, 
matrix multiplies, etc.).

In effect, one can usually assume that the total number of cpu cycles 
actully used for floating point arithmetic in these cases is 0.  
Counting real memory hits due to cache reloads gives a much more 
accurate measure of time.

In the case of testing your matrix multiply, you could use a trick I did 
to investigate timing for FFT's: I took out all pointer increments from 
the loop, so that the algorithm proceeded as usual, but carried out all 
its operations on the same few bytes of memory.  It yields nonsense for 
the result, but gives an idea of how many cpu cycles are spent on 
everything except fetching. It is sometimes quite shocking (> factor of 
10) the speed increase.

In your case, with the problem at 128 elements, i suspect this was 
because of the way the PowerPC chips (some of them at least) choose 
which cache line to fill with new data, and the 1024 byte offset between 
successive data points probably meant that each fetch required a 
complete cache line reload.

Marcus Mendenhall