Questions for using Lisp language to built the computeralgebra systems.
Subject: Questions for using Lisp language to built the computeralgebra systems.
From: Stavros Macrakis
Date: Tue, 18 Sep 2007 11:15:23 -0400
On 9/18/07, Richard Fateman <fateman at cs.berkeley.edu> wrote:
>
>
> Pointers do not point into random memory so much as point to the very next
> cell.
>
There was a very old paper (early 1970's) from BBN showing that even without
compacting GC and without any special effort to allocate nearby, most memory
references were quite local.
Compacting GCs make this happen quite often, so that linked lists are often
> on the same cache line. Papers on this subject have been written by Douglas
> Clarke (many years ago) and more recent papers by others (including me) show
> that pointers can be linearized, essentially. If you have any evidence that
> cdr-coding would make lisp faster on today's machines, you should publish
> these results.
>
> Basically, caches today are quite large relative to what is usually needed
> for lisp, even with pointers.
>
Cache misses and prefetching are one issue. A different issue is the
overhead of link-following. There's an extra memory/cache fetch (l = l.next)
which may or may not be pipelinable.
-s