Re: Duplicate hashcode for different Class objects

Hashcode is one of the Java warts that we would be better off without. At l=
east one language, Common Lisp, never exposes the actual hash code to the a=
pplication. Instead it provides higher level structures like hash tables. T=
his allows the implementation to safely change an object's hash code. This =
in turn allows the hash code to be based on the address of the object. The =
cost is that the GC has to rehash if it moves a hashed object.

A "Back In The Day GC" (for lack of a better name) is careful to trace the =
hash tables last. This avoids the tension between the hash table's job of r=
andomizing objects and the way Cheney scan naturally orders objects.

I hope that in the next language (whatever it is) we can avoid exposing has=
h codes.

- Rick =20



-----Original Message-----
From: [email protected] [mailto:[email protected]] On B=
ehalf Of David F. Bacon
Sent: Saturday, December 13, 2008 10:21 AM
To: David Chase
Cc: Unmesh joshi; [email protected]
Subject: Re: [gclist] Duplicate hashcode for different Class objects

Yes, that's all correct.  That being said, different implementations =20
of hashcode give better or worse performance.  There are issues of =20
both the number of "significant bits" and the quality of the hash =20
(which of course gets traded off against the cost of object creation =20
or the first hash).

Grove, Fink, and I had a paper in ECOOP a few years ago about how to =20
optimize hashing.  The basic idea is

- assume most objects are never hashed, so don't bother generating a =20
hashcode on creation and just have two hashcode flag bits which are =20
initially 0 (also enables header compression).

- if the object is hashed, use its address>>3 as the hashcode, and =20
set a "hashed" bit in the object header.

- if the object is moved by the collector, set a "hashed and moved" =20
bit in the header and copy the old hash to the end of the copy of the =20
object.

This allows fast object creation and fairly high quality hash codes =20
at the expense of complexity and a slightly more expensive hashCode() =20
operation.  However, you have to be careful with a generational =20
collector if the nursery is small.  One way around that would be to =20
augment the hashcode with a generation number, at the expense of a =20
couple of additional loads and adds in the hashCode() operation.

We implemented this in Jikes RVM and it was a major driver in =20
modularizing the object model.  I don't know whether any of the =20
specific code is still in there.

david


On Dec 13, 2008, at 9:27 AM, David Chase wrote:

> This is completely possible, especially when you have a copying =20
> collector.
>
> First, hashcodes are not guaranteed to be unique.
>
> Second, the memory address is not necessarily the hashcode.  If =20
> nothing else, there are non-random bits in object locations (an 8-=20
> byte alignment guarantees the three least significant bits are =20
> zero). It is quite reasonable to apply an extra bit of hashing to =20
> the object; either using something invariant like the address/=20
> hashcode of the class, or storing a few extra bits in the header =20
> word (say, the gc count, modulo 16) that get mixed into the =20
> hashcode.  Or, the hashcode can be stored with the object itself.  =20
> That extra hashing can cause two different addresses to yield the =20
> same hashcode.
>
> Third, in a copying collector, it is entirely likely that different =20
> objects allocated at different times will get cycled through the =20
> same youngspace, and the same address in the youngspace.  Thus, =20
> their address would be the same.  If you can vary the size of the =20
> youngspace, you might even be able to observe a change in the =20
> frequency of these coincident hashcodes (if you did, that would =20
> statistically confirm this hypothesis, if the frequency of =20
> collision is somewhat inversely proportional to the size of the =20
> youngspace).
>
> On 2008-12-13, at 5:11 AM, Unmesh joshi wrote:
>
>>
>> Hi,
>>
>> We are facing a strange problem in our application. getClass=20
>> ().hashCode() is returning same hashcode for two different =20
>> classes. My understanding is that default JDK implementation =20
>> returns Object's memory address as hashCode. Can this duplication =20
>> happen because of any GC implementation chosen? (like copying =20
>> collection?). Is there any such bug already known?
>>
>> This problem is intermitent on Mac OS X machines and also observed =20
>> on a linux box.
>>
>>
>> Thanks,
>> Unmesh
>> _________________________________________________________________
>> Wish to Marry Now? Join MSN Matrimony FREE!
>> http://in.msn.com/matrimony