[Openmcl-devel] Quick HW question...

[Spires, Shannon V]

On Nov 16, 2010, at 1:10 PM, Jon Anthony wrote:

On Tue, 2010-11-16 at 11:30 -0700, Spires, Shannon V wrote:

But how do you even write clever cache-aware code in Lisp? Lisp is a pointer-following language with garbage collection; Lisp data is a dynamic graph where the nodes point all over the place and are constantly moving around. A C program is more like one big node: Its data is all in one place and it doesn't move around. Modern cache architectures were built with C-like programs in mind; they're hell for Lisp.

This sounds off to me on a few counts: Typical C programs have loads of
(manual) allocated ("pointer data") and the RTS managers for this are
not necessarily good and can lead to a lot of fragmentation.  Lisp (and
other expected GC languages) can and do bring all the live stuff
together in a smaller space (after collection).  Compacting collectors
(CCL) should typically be even better at this as "old" live things never
need to move.

Both larger C and Lisp (and for that matter more or less anything else)
will have memory not all in "one place" but scattered all over VM.
Again due to GC, I would think it more usual for manual allocation
programs to have more locality issues.

/Jon


Tim wrote:

I suspect things are much more complex than this.  Big C systems are typically doing some kind of semi-automated storage management which is either relocating things, reference counting (or perhaps some non-relocating GC), and hence chasing pointers all over the place.  Relocating garbage collectors can move things so they are close together and hence improve locality, unlike systems which don't relocate and often end up with hugely fragmented heaps.

And finally, there's another language which looks in many ways a bit like Lisp (it's garbage-collected, lots of things are pointers): Java.  There's a lot of Java out there, and the markets for it are such that I guess system-design people pay attention to performance issues.  What benefits java benefits Lisp to a great extent.

You're both right and you're both wrong. You're right in that C programs can do a lot of pointer chasing, and relocating GCs do compact memory in many Lisp systems.

You're wrong only because I was too vague in my initial comment: I'm biased toward programs that build large n-dimensional graph data structures and then grovel them, since I find those kind of problems interesting and that's what I'm paid to do. You can write those programs in any language, but I prefer Lisp. The point is that when n (the number of inherent dimensions of your data structure) is greater than 1, it's impossible to compact that data into a one-dimensional memory structure that localizes all the dimensions, no matter how smart your GC is. So for these kinds of programs, you're hosed with conventional architectures where caches are one-dimensional. Whether you're using C, Lisp, Cobol, or anything else.

Shannon Spires



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.clozure.com/pipermail/openmcl-devel/attachments/20101117/429c3f91/attachment.htm>