On Tue, 23 Mar 2010, 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...

We don't have a JIT and who knows if and when we will have one. Until then 
the following runtime rule applies most of the time:
primitives < code mostly bytecodes < code with sends.
And note that here I was talking abot #pointsTo: which when sent to an 
array tells if and object is in the array using ==. LargeIdentitySet uses 
this primitive to tell if the object is in the "list" of objects which 
have the same identity hash.


Levente

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