Re: Duplicate hashcode for different Class objects

I partially disagree.  The mistake in Java was not in exposing the  
hash codes; they're important enough to the construction of some user- 
defined data structures that they deserve runtime support.  The  
mistake was making them a property of any object; something like  
"implements Hashable" would have been the right compromise.

Java also made the same mistake with monitors.  Ugh.

david


On Dec 14, 2008, at 2:17 PM, Hudson, Rick wrote:

> Hashcode is one of the Java warts that we would be better off  
> without. At least one language, Common Lisp, never exposes the  
> actual hash code to the application. Instead it provides higher  
> level structures like hash tables. This 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 randomizing objects and the way Cheney scan  
> naturally orders objects.
>
> I hope that in the next language (whatever it is) we can avoid  
> exposing hash codes.
>
> - Rick
>
>
>
> -----Original Message-----
> From: [email protected] [mailto:owner- 
> [email protected]] On Behalf 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
> of hashcode give better or worse performance.  There are issues of
> both the number of "significant bits" and the quality of the hash
> (which of course gets traded off against the cost of object creation
> or the first hash).
>
> Grove, Fink, and I had a paper in ECOOP a few years ago about how to
> optimize hashing.  The basic idea is
>
> - assume most objects are never hashed, so don't bother generating a
> hashcode on creation and just have two hashcode flag bits which are
> initially 0 (also enables header compression).
>
> - if the object is hashed, use its address>>3 as the hashcode, and
> set a "hashed" bit in the object header.
>
> - if the object is moved by the collector, set a "hashed and moved"
> bit in the header and copy the old hash to the end of the copy of the
> object.
>
> This allows fast object creation and fairly high quality hash codes
> at the expense of complexity and a slightly more expensive hashCode()
> operation.  However, you have to be careful with a generational
> collector if the nursery is small.  One way around that would be to
> augment the hashcode with a generation number, at the expense of a
> couple of additional loads and adds in the hashCode() operation.
>
> We implemented this in Jikes RVM and it was a major driver in
> modularizing the object model.  I don't know whether any of the
> 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
>> collector.
>>
>> First, hashcodes are not guaranteed to be unique.
>>
>> Second, the memory address is not necessarily the hashcode.  If
>> nothing else, there are non-random bits in object locations (an 8-
>> byte alignment guarantees the three least significant bits are
>> zero). It is quite reasonable to apply an extra bit of hashing to
>> the object; either using something invariant like the address/
>> hashcode of the class, or storing a few extra bits in the header
>> word (say, the gc count, modulo 16) that get mixed into the
>> hashcode.  Or, the hashcode can be stored with the object itself.
>> That extra hashing can cause two different addresses to yield the
>> same hashcode.
>>
>> Third, in a copying collector, it is entirely likely that different
>> objects allocated at different times will get cycled through the
>> same youngspace, and the same address in the youngspace.  Thus,
>> their address would be the same.  If you can vary the size of the
>> youngspace, you might even be able to observe a change in the
>> frequency of these coincident hashcodes (if you did, that would
>> statistically confirm this hypothesis, if the frequency of
>> collision is somewhat inversely proportional to the size of the
>> youngspace).
>>
>> On 2008-12-13, at 5:11 AM, Unmesh joshi wrote:
>>
>>>
>>> Hi,
>>>
>>> We are facing a strange problem in our application. getClass
>>> ().hashCode() is returning same hashcode for two different
>>> classes. My understanding is that default JDK implementation
>>> returns Object's memory address as hashCode. Can this duplication
>>> happen because of any GC implementation chosen? (like copying
>>> collection?). Is there any such bug already known?
>>>
>>> This problem is intermitent on Mac OS X machines and also observed
>>> on a linux box.
>>>
>>>
>>> Thanks,
>>> Unmesh
>>> _________________________________________________________________
>>> Wish to Marry Now? Join MSN Matrimony FREE!
>>> http://in.msn.com/matrimony
>