list locality (WAS: Parallelizing...) (Hans Boehm)
Wed, 22 Nov 1995 18:22:01 GMT

          From comp.compilers

Related articles
Re: Parallelizing (WAS: Death by pointers.) (1995-10-18)
Re: Parallelizing (WAS: Death by pointers.) (1995-10-28)
Re: Parallelizing (WAS: Death by pointers.) (1995-11-03)
list locality (WAS: Parallelizing...) (1995-11-22)
Re: list locality (WAS: Parallelizing...) (1995-11-28)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Hans Boehm)
Keywords: parallel, storage, GC
Organization: Xerox Palo Alto Research Center
References: 95-10-092 95-11-015 95-11-047
Date: Wed, 22 Nov 1995 18:22:01 GMT (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
Standard disclaimer ...

Post a followup to this message

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