Re: String interning

[Tom Tromey <tromey at cygnus dot com>]

Bryce> Unfortunatly the DELETED_STRING (using weak references) thing
Bryce> didnt work out either. The problem is that the hashtable ends
Bryce> up being populated nearly entirely with DELETED_STRINGs after
Bryce> lots of strings have been interned and collected, this means
Bryce> that intern() ends up having to traverse anything up to the
Bryce> entire table looking for the first UNUSED_SLOT (~0) entry, so
Bryce> performance sucks.

What if we make each slot in the hash table a linked list of interned
strings instead?  Then when we delete a string it will always be safe
to simply reuse a deleted slot.  This is bad in its own way, which is
that the lists could get very long.

It is possible to solve that problem, too, though.  We could resize
the table by rearranging the links.  Then there'd be no more calls to
remove weak references.

Bryce> So, I thought about going back to using a finalizer for
Bryce> interned strings instead. But it is safe to have a
Bryce> synchronized{} block inside a finializer? Does the collector
Bryce> invoke finalizers while it is in the "world-stopped" state?
Bryce> What would happen if the garbage collector is invoked inside
Bryce> intern(), while it holds the lock on String.class?

It is safe to use synchronized inside a finalizer.  However, Java
doesn't make any guarantees about when a finalizer might be run.  I
think we should not be any more restrictive on our GC implementation
than Java itself is.  For instance, finalizers might be run in a
separate thread at the same time all the user threads are run.

Tom