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