On Sat, 12 Mar 2005, Eijiro Sumii wrote:

> 2. Some programs get much slower for larger heaps, even though they
>    don't seem to trigger any GC.  An example is such programs is given
>    below.  Why is this?  (There also exist programs that are not
>    affected at all, so this is not because of the initialization
>    overhead of the runtime system.)

Quite in general, Cache hierarchy may be an issue here. The CPU can only 
hold a small amount of data in its L1 cache, which is quite fast. Next, 
there are L2 and then L3 caches (should you have that), but if you have to 
do a lot of real memory access, that usually will kill you. Especially if 
your address space is so badly scrambled that the CPU constantly needs to 
re-load its address translation cache (called translation lookaside buffer 
for x86). Worst case situation on a 3-level MMU system is that you will
have to do four memory reads for one word of data.

So, as a quite general rule when doing computationally challenging 
algebraic stuff in a functional language: try hard to design your data 
representation in such a way that you minimize RAM access. If you can 
e.g. encode short lists of small integers into a fixnum-integer, then do 
so. A few shift and masking operations do not matter much for many 
pipelined processors, provided the code can be held in the cache. Memory 
access does. One can overdo it, though: if you need ten times more code to 
get rid of a simple memory access, you're on the wrong track. Code also 
has to be transported to the CPU core.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)