So the problem is that the objects are not implementing 
hash/identityHash properly...

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 -
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>            
>>>> .
>>>>
>>>>
>>>>
>>>>          
>>> .
>>>
>>>
>>>        
>>
>>      
> .
>
>