[gclist] Re: finding object prefix from infix pointer

[Hans Boehm]

On Jul 9,  9:41pm, marc.shapiro@inria.fr wrote:
> Subject: Re: [gclist] Re: finding object prefix from infix pointer
>  || From: boehm@hoh.engr.sgi.com (Hans Boehm)
>  || Subject: Re: [gclist] Re: finding object prefix from infix pointer
>  || Date: Fri, 9 Jul 1999 09:28:06 -0700
>  ||
>  || Each block (roughly page) of the heap contains objects of a fixed
>  || size.
>
> Isn't that very bad for locality?  I.e. you group objects by size rather
> than putting together those that are accessed together.
>
I doubt it, but real measurements would be welcome.  In fact, I would
conjecture that segregation is a slight win over pure allocation order on
average.  My intuition is that access paths generally go through objects of a
small number of distinct size classes.  Assume that capital letters refer to
one and lower case letters to another.  An access path through consecutively
allocated objects might be

aBcDeFgH

Whether these are arranged in the above order, or distributed over two pages as

aceg

BDFH

really doesn't affect locality very much.  You need the same size cache to hold
the path either way (associativity issues aside).  You will touch 2 pages
instead of 1, but that difference disappears once the access path covers more
than a page.

There are also cases where segregation actually helps.  If you allocate a
search tree, it may be good to segregate the interior nodes from the leaves,
since the interior nodes will probably be far more frequently accessed.

In reality, a nonmoving allocator won't quite give you allocation order within
a size class.  But it's usually pretty close, and that problem exists whether
or not you segregate by size.

Hans

-- 
Hans-J. Boehm
boehm@sgi.com