Re: Speeding up method searches

[Per Bothner <per at bothner dot com>]

Tom Tromey <tromey@cygnus.com> writes:

> My guess is that interning would be more efficient.
> But that requires binutils work, which unfortunately lessens its
> chance of happening (based on history).

Not necessarily - it can be handled in one of the class load/init phases.

What about if in inappropriate data structures we replaced Utf8Const by
statically allocated String objects.? The init code can then intern the
strings.

Where the linker support would help is that we could in the best case
do the interning at link time (even create the hash table at link time!).
If not that, we could have the linker remove duplicate String objects
to the best of its ability.

However, even without linker support, it may make sense to remove or
reduce the use of Utf8Const.  Certainly, for String literals, it seems
a reasonable tradeoff to use pre-allocated String objects, and just
intern them, as opposed to at init time allocating a String (if not
already interned) and initializing it from a Utf8Const.  The tradeoff
is that a Utf8Const is more compact than a String, so if the String
never gets created (the class is not initialized) or is a duplicate,
it is more space efficient to use current implementation.  However, it
is not a very large saving, and in other cases it is more efficient to
use pre-allocated String.  Linker support just improves the tradeoff
because there are fewer duplicates.

The other advantage of Utf8Const is that the hash-value is pre-computed,
so interning is cheaper.  However, it may be plausible to always store
the hashCode with a String, as that would speed up a lot of String-handling.
(By clever use of a String's boffset field, we can add space for a hashCode
to some Strings, such as literals and other interned Strings, without
requiring four extra bytes for *all* Strings.)

Now if we agree that String literals should no longer use Utf8Const,
then we have the option to do the same thing for method and field
names.  For example, we can change the name field of a _Jv_Method to
be an interned string, with the interning happening sometime before
the class is initialized.  That speeds up searching for a match quite
a bit.  It also speeds up reflection in general, since the internal
name of the method is the same as the reflexive name.  If we go that
route, it becomes plausible to combine _Jv_Method and
java.lang.reflect.Method as the same type, similar to the way the
reflective Class is the same as the internal data structure.  Again,
there are tradeoffs:  Merging the types makes reflection faster,
and it makes the run-time code simpler, without noticably
complicating the compiler.  It saves space for the clases that use
reflection, but does use some more space (but not a lot) for classes
where reflection is not used.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/