4.1 - hashed collections still a problem

>
> If you interested in details, you can check it in Magma.
> Brief description:
> i using a linked list for storing associations which keys having same hash value
> so, in addition to key/value pair there is next ivar.
> And dictionary's array entries look like this:
> ...
> ...
> ...
> e1 -> e2 -> e3
> ...
> ...
>
> where e1,e2,e3 is associations , which having same hash value, but
> different keys.
> So, when it doing lookup for a key, say e3, initially by doing hash
> lookup it finds e1, and then since #= for e1 answers false, it looks
> for the next linked association, until e3 is found.
>
> If i remember, the last time i benched this implementation, it almost
> same in speed as an original implementation for small sizes, and
> outperforms on a large sizes, especially, when you got more than 4096
> elements.
>
> So, Chris, can you give us details how you compared the speed between
> LargeIdentitySet and my dictionaries?
> I don't think its correct to compare them, because dictionaries need
> to handle more data than sets, and we should expect some slowdown
> because of it.
> But sure, you can imitate the Set behavior with dicts, by simply
> ignoring the value field of association (set it to nil), and use only
> keys, i.e.
> set add: object
> is like:
> dict at: object put: nil.
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

> On Wed, 24 Mar 2010, Igor Stasenko wrote:
>
>> On a board's meeting, Chris mentioned my implementation, and he says
>> that it outperforms the LargeIdentitySet.
>> I'm not sure how Chris compared it, because i implemented this scheme
>> only for dictionaries , not sets.
>
> It's really hard to believe that a dictionary can be faster than
> LargeIdentitySet (I even doubt that a set could be faster), so I'm waiting
> for the numbers.
>
> As you pointed out it's unfair to compare sets to dictionaries, so I wrote
> LargeIdentityDictionary
> (http://leves.web.elte.hu/LargeIdentityDictionary/LargeIdentityDictionary.st
> ) which works just like LargeIdentitySet, but it also stores the values
> besides the keys. I modified Chris' benchmark just like you suggested: store
> nil as the value
> (http://leves.web.elte.hu/LargeIdentityDictionary/LargeIdentityDictionaryBenchmark.wst
> ). The benchmark compares LargeIdentityDictionary to IdentityDictionary. It
> uses two diffent lookup methods (#at: and #includesKey:). I ran the
> benchmarks and copied the results to a single file
> (http://leves.web.elte.hu/LargeIdentityDictionary/LargeIdentityDictionaryBenchmark.txt
> ), but I'm sure the nice charts are more interesting, so here they are:
> http://leves.web.elte.hu/LargeIdentityDictionary/LargeIdentityDictionary.png
> http://leves.web.elte.hu/LargeIdentityDictionary/LargeIdentityDictionary2.png
>
> The first chart shows that IdentityDictionary has a big spike at 970000,
> probably because of clustering (we need even better primes). So the second
> chart is the same as the first, but it only shows the 0-5000ms range. What
> we can see is #at: and #includesKey: have similar performance for
> IdentityDictionary (both use #scanFor:). LargeIdentityDictionary >> #at: is
> ~3.5-5x faster than IdentityDictionary >> #at:. And what's more interresing
> is that #includesKey: is so fast that it seems to be totally flat (though
> it's not). That's because #includesKey: can use the #pointsTo: primitive,
> but #at: can't, because it has to return the value for the key. So if a
> dictionary is faster than LargeIdentitySet, than it's graph has to be even
> flatter than #includesKey:'s graph (it's really hard to believe that such
> dictionary exists).
>

>
> Levente
>
> P.S. LargeIdentityDictionary is hardly tested and doesn't implement every
> "public" method that IdentityDictionary does.
>
>>
>> If you interested in details, you can check it in Magma.
>> Brief description:
>> i using a linked list for storing associations which keys having same hash
>> value
>> so, in addition to key/value pair there is next ivar.
>> And dictionary's array entries look like this:
>> ...
>> ...
>> ...
>> e1 -> e2 -> e3
>> ...
>> ...
>>
>> where e1,e2,e3 is associations , which having same hash value, but
>> different keys.
>> So, when it doing lookup for a key, say e3, initially by doing hash
>> lookup it finds e1, and then since #= for e1 answers false, it looks
>> for the next linked association, until e3 is found.
>>
>> If i remember, the last time i benched this implementation, it almost
>> same in speed as an original implementation for small sizes, and
>> outperforms on a large sizes, especially, when you got more than 4096
>> elements.
>>
>> So, Chris, can you give us details how you compared the speed between
>> LargeIdentitySet and my dictionaries?
>> I don't think its correct to compare them, because dictionaries need
>> to handle more data than sets, and we should expect some slowdown
>> because of it.
>> But sure, you can imitate the Set behavior with dicts, by simply
>> ignoring the value field of association (set it to nil), and use only
>> keys, i.e.
>> set add: object
>> is like:
>> dict at: object put: nil.
>>
>> --
>> Best regards,
>> Igor Stasenko AKA sig.
>>
>>
>
>

> On a board's meeting, Chris mentioned my implementation, and he says
> that it outperforms the LargeIdentitySet.
> I'm not sure how Chris compared it, because i implemented this scheme
> only for dictionaries , not sets.
>
> If you interested in details, you can check it in Magma.
> Brief description:
> i using a linked list for storing associations which keys having same hash value
> so, in addition to key/value pair there is next ivar.
> And dictionary's array entries look like this:
> ...
> ...
> ...
> e1 -> e2 -> e3
> ...
> ...
>
> where e1,e2,e3 is associations , which having same hash value, but
> different keys.
> So, when it doing lookup for a key, say e3, initially by doing hash
> lookup it finds e1, and then since #= for e1 answers false, it looks
> for the next linked association, until e3 is found.
>
> If i remember, the last time i benched this implementation, it almost
> same in speed as an original implementation for small sizes, and
> outperforms on a large sizes, especially, when you got more than 4096
> elements.
>
> So, Chris, can you give us details how you compared the speed between
> LargeIdentitySet and my dictionaries?
> I don't think its correct to compare them, because dictionaries need
> to handle more data than sets, and we should expect some slowdown
> because of it.
> But sure, you can imitate the Set behavior with dicts, by simply
> ignoring the value field of association (set it to nil), and use only
> keys, i.e.
> set add: object
> is like:
> dict at: object put: nil.
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

> On Thu, 25 Mar 2010, Igor Stasenko wrote:
>
>> i think that #pointsTo: is a cheat :), which you can use in Sets but
>> not dictionaries, because
>> it contains associations. Also, it works only for identity-based
>> collections.
>
> Dictionaries don't have to use associations (for example MethodDictionary
> doesn't use them), that's why #pointsTo: works (MethodDictionary also uses
> it).
>
>>
>>> I wonder how LargeIdentityDictionary compares to your dictionaries'.
>>>
>> me too.
>
> If you give me a pointer to the source code, I can run the benchmarks.
>
>
> Levente
>
>

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

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

> On a board's meeting, Chris mentioned my implementation, and he says
> that it outperforms the LargeIdentitySet.
> I'm not sure how Chris compared it, because i implemented this scheme
> only for dictionaries , not sets.
>
> If you interested in details, you can check it in Magma.
> Brief description:
> i using a linked list for storing associations which keys having same hash value
> so, in addition to key/value pair there is next ivar.
> And dictionary's array entries look like this:
> ...
> ...
> ...
> e1 ->  e2 ->  e3
> ...
> ...
>
> where e1,e2,e3 is associations , which having same hash value, but
> different keys.
> So, when it doing lookup for a key, say e3, initially by doing hash
> lookup it finds e1, and then since #= for e1 answers false, it looks
> for the next linked association, until e3 is found.
>
> If i remember, the last time i benched this implementation, it almost
> same in speed as an original implementation for small sizes, and
> outperforms on a large sizes, especially, when you got more than 4096
> elements.
>
> So, Chris, can you give us details how you compared the speed between
> LargeIdentitySet and my dictionaries?
> I don't think its correct to compare them, because dictionaries need
> to handle more data than sets, and we should expect some slowdown
> because of it.
> But sure, you can imitate the Set behavior with dicts, by simply
> ignoring the value field of association (set it to nil), and use only
> keys, i.e.
> set add: object
> is like:
> dict at: object put: nil.
>
>    

> On Thu, 25 Mar 2010, Igor Stasenko wrote:
>
>    
>> i think that #pointsTo: is a cheat :), which you can use in Sets but
>> not dictionaries, because
>> it contains associations. Also, it works only for identity-based collections.
>>      
> Dictionaries don't have to use associations (for example MethodDictionary
> doesn't use them), that's why #pointsTo: works (MethodDictionary also
> uses it).
>
>    
>>      
>>> I wonder how LargeIdentityDictionary compares to your dictionaries'.
>>>
>>>        
>> me too.
>>      
> If you give me a pointer to the source code, I can run the benchmarks.
>
>
> Levente
>
>
>    

> I don't have Squeak handy right now, I just meant to say that the code in the
> VisualWorks method will work correctly as long as isPrime is deterministic.
>
> On 3/23/10 18:58 , David T. Lewis wrote:
>> 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
>>
>>
>>
>
>

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

>
> On 3/25/10 1:27 , Levente Uzonyi wrote:
>> On Thu, 25 Mar 2010, Igor Stasenko wrote:
>>
>>
>>> i think that #pointsTo: is a cheat :), which you can use in Sets but
>>> not dictionaries, because
>>> it contains associations. Also, it works only for identity-based
>>> collections.
>>>
>> Dictionaries don't have to use associations (for example MethodDictionary
>> doesn't use them), that's why #pointsTo: works (MethodDictionary also
>> uses it).
>>
>>
>>>
>>>> I wonder how LargeIdentityDictionary compares to your dictionaries'.
>>>>
>>>>
>>> me too.
>>>
>> If you give me a pointer to the source code, I can run the benchmarks.
>>
>>
>> Levente
>>
>>
>>
>
>

> On Thu, 25 Mar 2010, Igor Stasenko wrote:
>
>> i think that #pointsTo: is a cheat :), which you can use in Sets but
>> not dictionaries, because
>> it contains associations. Also, it works only for identity-based
>> collections.
>
> Dictionaries don't have to use associations (for example MethodDictionary
> doesn't use them), that's why #pointsTo: works (MethodDictionary also uses
> it).
>

>>
>>> I wonder how LargeIdentityDictionary compares to your dictionaries'.
>>>
>> me too.
>
> If you give me a pointer to the source code, I can run the benchmarks.
>
>
> Levente
>
>

> On 25 March 2010 10:27, Levente Uzonyi <[hidden email]> wrote:
>> On Thu, 25 Mar 2010, Igor Stasenko wrote:
>>
>>> i think that #pointsTo: is a cheat :), which you can use in Sets but
>>> not dictionaries, because
>>> it contains associations. Also, it works only for identity-based
>>> collections.
>>
>> Dictionaries don't have to use associations (for example MethodDictionary
>> doesn't use them), that's why #pointsTo: works (MethodDictionary also uses
>> it).
>>
> But that means a linear scan of the whole collection, even if done primitively,
> this is not scalable.

>
>>>
>>>> I wonder how LargeIdentityDictionary compares to your dictionaries'.
>>>>
>>> me too.
>>
>> If you give me a pointer to the source code, I can run the benchmarks.
>>
>>
>> Levente
>>
>>
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

>>> Dictionaries don't have to use associations (for example MethodDictionary
>>> doesn't use them), that's why #pointsTo: works (MethodDictionary also uses
>>> it).
>>>
>> But that means a linear scan of the whole collection, even if done primitively,
>> this is not scalable.
>
> Not necessarily.  VisualAge had a LookupTable class that was identical
> to Dictionary except it used two parallel Array's (keys / values)
> rather than Association objects instaniated by its Dictionary.
> LookupTable was faster..
>
>

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