Optimized lists

[Mats Cronqvist]

Richard A. O'Keefe wrote:

[..]
> (1) The Warren Abstract Machine stores list pairs in 2 words.  I don't
>     know what BEAM uses.  Probably 3 words.  The change would thus
>     add 33% to the size of every list.  This leads to
>     - less effective use of cache.  This has a bigger effect than
>       people commonly realise.  Here are some measurements from a 1GHz
>       G4 PowerPC running MacOS 10.3
>     
> 	 Level    Sequential access Random access 
> 	 L1 cache 1.7 GB/sec        2.1 GB/sec    
> 	 L2 cache 1.0 GB/sec        0.7 GB/sec    
> 	 main     0.4 GB/sec        0.05 GB/sec   
>                                           
>       And here are some measurements from a 500MHz SunBlade100 (UltraSparc II)
>       running Solaris 2.10:
>       
> 	 Level    Sequential access Random access 
> 	 L1 cache 2.8 GB/sec        1.6 GB/sec    
> 	 L2 cache 1.4 GB/sec        0.8 GB/sec    
> 	 main     0.3 GB/sec        0.04 GB/sec   

   in the AXD301 we have also found that cache is massively important. in one of 
our benchmarks a doubling of the cache size improved performance ~50% (not a 
typical value). indeed, we often see a loss of performance when we try 
hipe-compiling (our applications are not well-suited to hipe, and we lose on the 
cache).
   question; how did you make the measurements on memory access speeds?

[...]
> (3) There are plenty of list-processing functions which, to my understanding,
>     don't involve tail recursion at the moment, but with a slightly different
>     abstract machine *could* be tail recursions.  Here's one:
> 
> 	append([X|Xs], L) -> [X | append(Xs, L)];
> 	append([], L) -> L.
> 
>     Making this and similar functions tail recursive would be very good
>     news for memory use (using O(1) stack space instead of O(n)).  Such code
>     is _very_ common, much more common than length/1 is.  Switching to tail
>     recursion here would be IMPOSSIBLE if each list cell carried its length.


   what changes to the emulator would that be?

    mats