The point is why insisting on using identityHash with == if identityHash 
is limited?  Clearly you can refine identityHash to answer something 
more appropriate if needed, because the rule is x == y => x identityHash 
= y identityHash.  Nothing requires identityHash to answer the 12 or 
whatever header bits.  Also, if you take this route, then you don't make 
the object headers grow for every single object regardless of whether 
they are sent the message identityHash or not (which will make the VM 
run slower because the CPU will perform more memory reads).  And note 
that a good optimization strategy for VMs is to leave the identityHash 
field uninitialized at allocation time betting that checking whether the 
field is set or not, and providing an identityHash value lazily, will be 
cheaper than providing identityHash values that will be left unused most 
of the time...

On 3/26/10 3:36 , Levente Uzonyi wrote:
> On Thu, 25 Mar 2010, Andres Valloud wrote:
>
>    
>> So the problem is that the objects are not implementing hash/identityHash
>> properly...
>>      
> There are only 12 bits for identityHash in Squeak. The hash function used
> by the identity-based collections is from your hash changes.
>
>
> Levente
>
>    
>> On 3/24/10 1:47 , Levente Uzonyi wrote:
>>      
>>> On Tue, 23 Mar 2010, Andres Valloud wrote:
>>>
>>>
>>>        
>>>> (with a good hash function, the primitive will almost always find the
>>>> required object in the first try, negating the benefits of the primitive)
>>>>
>>>>          
>>> With 4096 different hash values and 1000000 objects that won't happen.
>>>
>>>
>>> Levente
>>>
>>>
>>>        
>>>> On 3/23/10 18:20 , Andres Valloud wrote:
>>>>
>>>>          
>>>>> As soon as you get a JIT VM, you will be surprised at how expensive
>>>>> primitives that require calling a C function can be.  You might be
>>>>> better off without the primitive and with a more streamlined hashed
>>>>> collection instead.  Also, the presence of the primitive will allow
>>>>> little to no flexibility...
>>>>>
>>>>> On 3/23/10 16:47 , Levente Uzonyi wrote:
>>>>>
>>>>>
>>>>>            
>>>>>> On Wed, 24 Mar 2010, Bert Freudenberg wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>              
>>>>>>> On 23.03.2010, at 23:57, Levente Uzonyi wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>                
>>>>>>>> On Tue, 23 Mar 2010, Bert Freudenberg wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>                  
>>>>>>>>> On 23.03.2010, at 16:01, Lukas Renggli wrote:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>                    
>>>>>>>>>>
>>>>>>>>>>                      
>>>>>>>>>>>> Just an idea: we could get rid of compact classes, which would
>>>>>>>>>>>> give
>>>>>>>>>>>> us
>>>>>>>>>>>> additional 6 bits (5 bits from the compact class index plus 1 bit
>>>>>>>>>>>> from the
>>>>>>>>>>>> header type because there would only be 2 header types left). This
>>>>>>>>>>>> would
>>>>>>>>>>>> increase the identity hash values from 4096 to 262144. In a
>>>>>>>>>>>> PharoCore1.0
>>>>>>>>>>>> image there are 148589 instances of compact classes, hence this
>>>>>>>>>>>> would cost
>>>>>>>>>>>> 580k. Or, we could just add an additional word and use the spare
>>>>>>>>>>>> bits from
>>>>>>>>>>>> the old identity hash for other stuff, e.g., immutability ;)
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>                          
>>>>>>>>>>> I like the first idea, we could even have the 17 continuous bits
>>>>>>>>>>> for
>>>>>>>>>>> identity hash the 1 separate bit for immutability.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>                        
>>>>>>>>>> Yes please, I love it :-)
>>>>>>>>>>
>>>>>>>>>> Lukas
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>                      
>>>>>>>>> Well, someone should code it up, and then lets's see macro benchmarks
>>>>>>>>> :)
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>                    
>>>>>>>> That's a great idea, but I'm sure it'll take a while until that
>>>>>>>> happens.
>>>>>>>> Fortunately identityhash related benchmarks can be done without
>>>>>>>> changing
>>>>>>>> the vm. I rewrote a bit the benchmark from Chris, created three
>>>>>>>> classes
>>>>>>>> which have 17, 18 and 30 bits for #scaledIdentityHash. Ran the
>>>>>>>> benchmark
>>>>>>>> with these three classes + Object, collected the data and created some
>>>>>>>> diagrams. I'm sure most people don't care about the code/data[1], so
>>>>>>>> here are the diagrams:
>>>>>>>> http://leves.web.elte.hu/identityHashBits/identityHashBits.png
>>>>>>>> http://leves.web.elte.hu/identityHashBits/identityHashBits2.png
>>>>>>>> http://leves.web.elte.hu/identityHashBits/identityHashBits3.png
>>>>>>>>
>>>>>>>> The first one contains the four graphs. It clearly shows that 12 bits
>>>>>>>> (Object) are insufficient for #identityHash. Even 5 more bits gives
>>>>>>>> 8-9x
>>>>>>>> speedup and a dramatic change in behavior.
>>>>>>>>
>>>>>>>> The second is the same as the first, but it shows only the 17, 18 and
>>>>>>>> 30
>>>>>>>> bits case. Note that the primes (hashtable sizes) are now optimized
>>>>>>>> for
>>>>>>>> 12 bits. If they are optimized for 17/18 bits then the results can be
>>>>>>>> better for larger set sizes (130+/260+) where they show worse behavior
>>>>>>>> compared to the 18/30 bits case.
>>>>>>>>
>>>>>>>> The third graph shows how an optimized data structure
>>>>>>>> (LargeIdentitySet)
>>>>>>>> compares to the 17, 18 and 30 bits case using only 12 bits.
>>>>>>>>
>>>>>>>> [1] All the code/data that were used to generate these graphs can be
>>>>>>>> found here http://leves.web.elte.hu/identityHashBits
>>>>>>>>
>>>>>>>>
>>>>>>>> Levente
>>>>>>>>
>>>>>>>> P.S. I also created a 12 bit version of the 17-18-30 bit classes and
>>>>>>>> found that it's 1.2-2.0x slower than Object, so the values after the
>>>>>>>> vm
>>>>>>>> changes are expected to be even better than what these graphs show.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>                  
>>>>>>> So this seems to indicate your specialized data structure beats all VM
>>>>>>> hash bits extension?
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>                
>>>>>> For IdentitySet - probably yes, up to a few million elements, but
>>>>>> I expect the difference to be smaller with the vm support and optimal
>>>>>> table sizes. (note that a "normal" image contains less than 500000
>>>>>> objects).
>>>>>> For IdentityDictionary - probably not, because we don't have a fast
>>>>>> primitive that can be used for the lookups.
>>>>>>
>>>>>>
>>>>>> Levente
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>              
>>>>>>> Also, we don't know yet how getting rid of compact classes would affect
>>>>>>> performance.
>>>>>>>
>>>>>>> - Bert -
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>                
>>>>>> .
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>              
>>>>> .
>>>>>
>>>>>
>>>>>
>>>>>            
>>>>
>>>>          
>>> .
>>>
>>>
>>>        
>>
>>      
> .
>
>