ReRe: performance (shellsort experiments)

[Kresten Krab Thorup]

Tom Tromey <tromey@cygnus.com> writes:

> Kresten> ... I think the most significant single
> Kresten> thing one could do right now would be to implement uniquing
> Kresten> for Utf8Const's, both in the linker and in the runtime
> Kresten> system.
> 
> I'm curious to know why you picked this.

It's a hunch of cause.  It turned out to be a big issue for Objective
C, and I spend a lot of time at NeXT doing exactly this.  But I think
it is the same for GCJ most of the way.

The primary problem is, that the strings take up a lot of space.
String's are mixed with other Utf8Const's, so if a single constant
String representation ends up on a page (or other cache unit) along
with a lot of meta data there is a lot of memory which will end up
being "hot".  The strategy I used for Objetive C was

1) Split all the meta-data into seperate sections.  One section for 
   each kind of meta data (and for each kind of string).

2) Sort these sections according to two criteria:  How "hot" it is,
   and if it is shared or not.  

3) Uniq all the strings.

It makes sense to split even the strings into seperate sections,
because it facilitates a better sorting for hot'ness.  For instance,
class names are more hot than method descriptors.  This provides for
significantly better caching/paging behavior.

Additionally, if the strings are uniqed, we can save time comparing
strings of cause.  NeXT's Objective C uses string compare for method
lookup, so the advantage here is clear.   

I've also noticed that there are strings occurring in some of the
header files, which are replicated into every module.  This of cause
adds to the waste.

-- Kresten

 Kresten Krab Thorup           "I like my eggs ploded"
 Department of Computer Science, University of Aarhus
 Aabogade 34, DK-8200 Aarhus N, Denmark
 +45 8942 5665 (office), +45 2343 4626 (mobile)