4.1 - hashed collections still a problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
58 messages Options
123
Reply | Threaded
Open this post in threaded view
|

4.1 - hashed collections still a problem

Chris Muller-3
4.1 hashed collections, across the board, small to large, are slower
by a factor of 2?!  I just don't think we can keep doing this; getting
slower and slower and slower, like molasses..  I'm sorry, but I really
care about this and I know you do too because speed was the whole
premise of putting these changes in.

What went wrong?  More importantly, how can we fix this?



IdentitySet.3.9.png (7K) Download Attachment
IdentitySet.4.1.png (6K) Download Attachment
IdentityDictionary.3.9.png (7K) Download Attachment
IdentityDictionary.4.1.png (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Bert Freudenberg
On 22.03.2010, at 22:40, Chris Muller wrote:
>
> 4.1 hashed collections, across the board, small to large, are slower
> by a factor of 2?!  I just don't think we can keep doing this; getting
> slower and slower and slower, like molasses..  I'm sorry, but I really
> care about this and I know you do too because speed was the whole
> premise of putting these changes in.
>
> What went wrong?  More importantly, how can we fix this?
> <IdentitySet.3.9.png><IdentitySet.4.1.png><IdentityDictionary.3.9.png><IdentityDictionary.4.1.png>

Neat graphs. But what exactly are you measuring?

- Bert -



Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Chris Muller-3
The output of the test script from the other day.

| test ord |
test := IdentitySet new.
[ test size >= 1000000 ] whileFalse: [
   ord := OrderedCollection new: 100.
   10000 timesRepeat: [
       test add: ( ord add: Object new ) ].
   Transcript
       show: test size asString;
       tab.
   Transcript show:
       [
           10 timesRepeat: [
               ord do: [ :each | test includes: each ] ]
       ] timeToRun asString.
   Transcript cr ]



On Mon, Mar 22, 2010 at 4:46 PM, Bert Freudenberg <[hidden email]> wrote:

> On 22.03.2010, at 22:40, Chris Muller wrote:
>>
>> 4.1 hashed collections, across the board, small to large, are slower
>> by a factor of 2?!  I just don't think we can keep doing this; getting
>> slower and slower and slower, like molasses..  I'm sorry, but I really
>> care about this and I know you do too because speed was the whole
>> premise of putting these changes in.
>>
>> What went wrong?  More importantly, how can we fix this?
>> <IdentitySet.3.9.png><IdentitySet.4.1.png><IdentityDictionary.3.9.png><IdentityDictionary.4.1.png>
>
> Neat graphs. But what exactly are you measuring?
>
> - Bert -
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
In reply to this post by Chris Muller-3
On Mon, 22 Mar 2010, Chris Muller wrote:

> 4.1 hashed collections, across the board, small to large, are slower
> by a factor of 2?!  I just don't think we can keep doing this; getting
> slower and slower and slower, like molasses..  I'm sorry, but I really
> care about this and I know you do too because speed was the whole
> premise of putting these changes in.
>
> What went wrong?  More importantly, how can we fix this?
>

What went wrong?

I think nothing. :) IdentitySet and IdentityDictionary wasn't ment to
support really large collections. The main reason is that there are only
4096 different hash values. So practically these collections are growing
4096 lists in a single array. In 3.9 and 3.10 these collections used a
hash expansion technique which distributed the elements uniformly. This
was changed when we integrated Andrés' hash changes. As you noticed some
of the primes didn't work well with #scaledIdentityHash, it's far better
now, though there may be even better primes. Finding such primes is a
computationally intensive task and the current ones (up to 10000000) are
pretty close to optimal.
Other than that there are two things that cause slowdown:
  +1 extra message send/scanning: #scaledIdentityHash (the new hash
expansion scheme, but we save one by not using #findElementOrNil:)
  +k (worst case) extra message send/scanning: #enclosedSetElement (OO nil
support, this only applies for IdentitySet)
Where k is the length of the list. Since there are only 4096 different
identity hash values for n = 250000 k will be ~61 (if the identity hashes
have a uniform distribution). For n = 1000000 it will be ~244. Note that
your benchmark exploits the worst case.
The long lists are bad, because HashedCollection is optimized for O(1)
list length. In this case the length of the list is not O(1), but
O(n) (with a very small constant).

How can we fix this?

I see two possible solutions for the problem:
1) use #largeHash instead of #identityHash, which is the identity hash of
the object mixed with the identity hash of its class. This helps if there
are objects from different classes in the set, but it doesn't help with
your benchmark. SystemTracer uses this method.
2) use differently implemented collections which are optimized for your
use case. For example I wrote LargeIdentitySet which probably has the best
performance you can have: http://leves.web.elte.hu/squeak/LargeIdentitySet.st
(note that it's hardly tested, probably contains bugs)


Levente

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Adrian Lienhard
Has it ever been considered to make the identity hash larger than 12 bits? Of course this is a trade off against space, but one that can be justified?!

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 ;)

Cheers,
Adrian

On Mar 23, 2010, at 11:36 , Levente Uzonyi wrote:

> How can we fix this?
>
> I see two possible solutions for the problem:
> 1) use #largeHash instead of #identityHash, which is the identity hash of the object mixed with the identity hash of its class. This helps if there are objects from different classes in the set, but it doesn't help with your benchmark. SystemTracer uses this method.
> 2) use differently implemented collections which are optimized for your use case. For example I wrote LargeIdentitySet which probably has the best performance you can have: http://leves.web.elte.hu/squeak/LargeIdentitySet.st
> (note that it's hardly tested, probably contains bugs)
>
>
> Levente


Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
On Tue, 23 Mar 2010, Adrian Lienhard wrote:

> Has it ever been considered to make the identity hash larger than 12 bits? Of course this is a trade off against space, but one that can be justified?!

Probably yes.

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


Levente

> Cheers,
> Adrian
>
> On Mar 23, 2010, at 11:36 , Levente Uzonyi wrote:
>
>> How can we fix this?
>>
>> I see two possible solutions for the problem:
>> 1) use #largeHash instead of #identityHash, which is the identity hash of the object mixed with the identity hash of its class. This helps if there are objects from different classes in the set, but it doesn't help with your benchmark. SystemTracer uses this method.
>> 2) use differently implemented collections which are optimized for your use case. For example I wrote LargeIdentitySet which probably has the best performance you can have: http://leves.web.elte.hu/squeak/LargeIdentitySet.st
>> (note that it's hardly tested, probably contains bugs)
>>
>>
>> Levente
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Lukas Renggli
>> 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

--
Lukas Renggli
http://www.lukas-renggli.ch

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Bert Freudenberg
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 :)

- Bert -



Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
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.

>
> - Bert -
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Bert Freudenberg
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?

Also, we don't know yet how getting rid of compact classes would affect performance.

- Bert -



Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Igor Stasenko
On 24 March 2010 01:22, Bert Freudenberg <[hidden email]> 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?
>
> Also, we don't know yet how getting rid of compact classes would affect performance.
>
i expect a slight speed increase, because of more uniform header handling :)

Concerning LargeIdentitySet - this is good argument to the point that
for large collections we should use different data structures.

> - Bert -
>

--
Best regards,
Igor Stasenko AKA sig.

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
In reply to this post by Bert Freudenberg
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 -
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Andres Valloud-4
In reply to this post by Levente Uzonyi-2
IMO, it's not worth the hassle for hashed collections to store nil.  
Finding good primes is not that expensive either, usually it takes no
more than a couple seconds.  You can look at the bottom of the prime
table in VisualWorks and see an expression that finds them from scratch
(but note that isPrime *MUST BE DETERMINISTIC*).

In the case examined, just refine #hash or #identityHash as needed for
your application, and everything should be just fine.  For more
information, get the hash book here: www.lulu.com/avSmalltalkBooks.

Andres.

On 3/23/10 3:36 , Levente Uzonyi wrote:

> On Mon, 22 Mar 2010, Chris Muller wrote:
>
>    
>> 4.1 hashed collections, across the board, small to large, are slower
>> by a factor of 2?!  I just don't think we can keep doing this; getting
>> slower and slower and slower, like molasses..  I'm sorry, but I really
>> care about this and I know you do too because speed was the whole
>> premise of putting these changes in.
>>
>> What went wrong?  More importantly, how can we fix this?
>>
>>      
> What went wrong?
>
> I think nothing. :) IdentitySet and IdentityDictionary wasn't ment to
> support really large collections. The main reason is that there are only
> 4096 different hash values. So practically these collections are growing
> 4096 lists in a single array. In 3.9 and 3.10 these collections used a
> hash expansion technique which distributed the elements uniformly. This
> was changed when we integrated Andrés' hash changes. As you noticed some
> of the primes didn't work well with #scaledIdentityHash, it's far better
> now, though there may be even better primes. Finding such primes is a
> computationally intensive task and the current ones (up to 10000000) are
> pretty close to optimal.
> Other than that there are two things that cause slowdown:
>    +1 extra message send/scanning: #scaledIdentityHash (the new hash
> expansion scheme, but we save one by not using #findElementOrNil:)
>    +k (worst case) extra message send/scanning: #enclosedSetElement (OO nil
> support, this only applies for IdentitySet)
> Where k is the length of the list. Since there are only 4096 different
> identity hash values for n = 250000 k will be ~61 (if the identity hashes
> have a uniform distribution). For n = 1000000 it will be ~244. Note that
> your benchmark exploits the worst case.
> The long lists are bad, because HashedCollection is optimized for O(1)
> list length. In this case the length of the list is not O(1), but
> O(n) (with a very small constant).
>
> How can we fix this?
>
> I see two possible solutions for the problem:
> 1) use #largeHash instead of #identityHash, which is the identity hash of
> the object mixed with the identity hash of its class. This helps if there
> are objects from different classes in the set, but it doesn't help with
> your benchmark. SystemTracer uses this method.
> 2) use differently implemented collections which are optimized for your
> use case. For example I wrote LargeIdentitySet which probably has the best
> performance you can have: http://leves.web.elte.hu/squeak/LargeIdentitySet.st
> (note that it's hardly tested, probably contains bugs)
>
>
> Levente

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Andres Valloud-4
In reply to this post by Levente Uzonyi-2
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 -
>>
>>
>>
>>
>>      
> .
>
>    

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Andres Valloud-4
In reply to this post by Igor Stasenko
Igor, keep in mind that the image will become larger... you may get a
counterbalancing performance hit because the CPU will have to do more
memory reads...

On 3/23/10 16:29 , Igor Stasenko wrote:

> On 24 March 2010 01:22, Bert Freudenberg<[hidden email]>  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?
>>
>> Also, we don't know yet how getting rid of compact classes would affect performance.
>>
>>      
> i expect a slight speed increase, because of more uniform header handling :)
>
> Concerning LargeIdentitySet - this is good argument to the point that
> for large collections we should use different data structures.
>
>    
>> - Bert -
>>
>>      
>    

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Andres Valloud-4
In reply to this post by Andres Valloud-4
(with a good hash function, the primitive will almost always find the
required object in the first try, negating the benefits of the primitive)

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

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

David T. Lewis
In reply to this post by Andres Valloud-4
On Tue, Mar 23, 2010 at 06:18:23PM -0700, Andres Valloud wrote:
> You can look at the bottom of the prime
> table in VisualWorks and see an expression that finds them from scratch
> (but note that isPrime *MUST BE DETERMINISTIC*).

Andres,

Is this a reference to the #isPrime in Squeak trunk, which calls
#isProbablyPrime for LargePositiveInteger? If so, can you say if
there is any difference in the actual results of computing a prime
table with a Squeak trunk image compared to the VisualWorks results?

If there is an difference in the results in Squeak versus VisualWorks,
this would be important to know.

Thanks,
Dave


Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
In reply to this post by Andres Valloud-4
On Tue, 23 Mar 2010, Andres Valloud wrote:

> IMO, it's not worth the hassle for hashed collections to store nil.  Finding
> good primes is not that expensive either, usually it takes no more than a
> couple seconds.  You can look at the bottom of the prime table in VisualWorks
> and see an expression that finds them from scratch (but note that isPrime
> *MUST BE DETERMINISTIC*).

I'm not a VW user, but if those primes are the same as the primes in
HashedCollection class >> #goodPrimes (and the method is the same as the
way #goodPrimes were generated), than those primes are not good enough for
#scaledIdentityHash. Details here:
http://lists.squeakfoundation.org/pipermail/squeak-dev/2010-March/147154.html


Levente

>
> In the case examined, just refine #hash or #identityHash as needed for your
> application, and everything should be just fine.  For more information, get
> the hash book here: www.lulu.com/avSmalltalkBooks.
>
> Andres.
>
> On 3/23/10 3:36 , Levente Uzonyi wrote:
>> On Mon, 22 Mar 2010, Chris Muller wrote:
>>
>>
>>> 4.1 hashed collections, across the board, small to large, are slower
>>> by a factor of 2?!  I just don't think we can keep doing this; getting
>>> slower and slower and slower, like molasses..  I'm sorry, but I really
>>> care about this and I know you do too because speed was the whole
>>> premise of putting these changes in.
>>>
>>> What went wrong?  More importantly, how can we fix this?
>>>
>>>
>> What went wrong?
>>
>> I think nothing. :) IdentitySet and IdentityDictionary wasn't ment to
>> support really large collections. The main reason is that there are only
>> 4096 different hash values. So practically these collections are growing
>> 4096 lists in a single array. In 3.9 and 3.10 these collections used a
>> hash expansion technique which distributed the elements uniformly. This
>> was changed when we integrated Andrés' hash changes. As you noticed some
>> of the primes didn't work well with #scaledIdentityHash, it's far better
>> now, though there may be even better primes. Finding such primes is a
>> computationally intensive task and the current ones (up to 10000000) are
>> pretty close to optimal.
>> Other than that there are two things that cause slowdown:
>>    +1 extra message send/scanning: #scaledIdentityHash (the new hash
>> expansion scheme, but we save one by not using #findElementOrNil:)
>>    +k (worst case) extra message send/scanning: #enclosedSetElement (OO nil
>> support, this only applies for IdentitySet)
>> Where k is the length of the list. Since there are only 4096 different
>> identity hash values for n = 250000 k will be ~61 (if the identity hashes
>> have a uniform distribution). For n = 1000000 it will be ~244. Note that
>> your benchmark exploits the worst case.
>> The long lists are bad, because HashedCollection is optimized for O(1)
>> list length. In this case the length of the list is not O(1), but
>> O(n) (with a very small constant).
>>
>> How can we fix this?
>>
>> I see two possible solutions for the problem:
>> 1) use #largeHash instead of #identityHash, which is the identity hash of
>> the object mixed with the identity hash of its class. This helps if there
>> are objects from different classes in the set, but it doesn't help with
>> your benchmark. SystemTracer uses this method.
>> 2) use differently implemented collections which are optimized for your
>> use case. For example I wrote LargeIdentitySet which probably has the best
>> performance you can have:
>> http://leves.web.elte.hu/squeak/LargeIdentitySet.st
>> (note that it's hardly tested, probably contains bugs)
>>
>>
>> Levente
>
>

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
In reply to this post by Andres Valloud-4
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 -
>>>
>>>
>>>
>>>
>>>
>> .
>>
>>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: 4.1 - hashed collections still a problem

Levente Uzonyi-2
In reply to this post by Andres Valloud-4
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 -
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>> .
>>>
>>>
>>>
>> .
>>
>>
>
>

123