list locality (WAS: Parallelizing...)

cliffc@ami.sps.mot.com (Cliff Click) writes:


>In passing - I long ago gave up on linked lists except for cases that
>require dynamic insertion in the middle or huge/infrequent structures,
>and use arrays instead. When spinning down the list the locality of
>arrays beats pointer-chasing-cache-misses any day.


This brings up an interesting question that I previously hadn't thought
about. Garbage collecting allocators (even those that don't move
objects) often place consecutively allocated objects of the same
size in adjacent locations. Thus the main cause of a decrease in cache
performance is likely to be the space taken up by the pointers.


If I allocate object B after object A, and both are of the same size,
does it matter which one has the larger address? (My guess is yes,
for some cache architectures. It might be faster to step through
addresses in increasing order.)


If the answer is yes, then presumably for mostly functional languages
I should allocate A at a higher address than B, since B will usually be
accessed first. What's the right order for C/C++ programs?


Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...
--

Return to the comp.compilers page.
Search the comp.compilers archives again.