Hashed collection changes, the performance graphs

> The test code, a variant of the test from the HashTable SqueakSource  
> wiki, is at the bottom of this message. Basically, it adds a bunch  
> of instances of Object to a Dictionary and sees how much time it  
> takes to look them up again.
>
> From the graphs in the previous message, you can see that  
> performance for sizes > 4000 is greatly improved. For size = 10000,  
> #at: is 1000 times faster, 2-3 microseconds vs. >2 milliseconds. At  
> size=10000, #at:put: is about 200 times faster, ~10 microseconds vs.  
> >2 milliseconds, and the large spikes for growing the collection are  
> 21 milliseconds vs. > 4 seconds, again a factor of about 200.
>
> Performance for dictionary sizes < 4000 is essentially the same as  
> before, so these collections can serve as general-purpose  
> collections over a wide range of sizes. I've attached the graphs for  
> sizes <4000 to this message so you can see that more clearly than on  
> the previous graphs.
>
> These results should hold for any object that inherits #hash from  
> Object, in other words uses its identity hash as its equality hash.  
> Other objects with better hashes did not have as serious a problem,  
> but will probably show increased performance as well due to using  
> prime table sizes.
>
> These changes are in Set, so should improve Set's subclasses as  
> well. IdentityDictionary, IdentitySet, and WeakIdentityKeyDictionary  
> did not have as serious a problem, but should see some improvement.  
> MethodDictionaries have been left alone on the assumption that the  
> VM depends on the hashing of those.

> Since there are still only 4K possible values of identity hash,  
> collisions are inevitable in large collections, and the number of  
> collisions will grow linearly with collection size. So how well does  
> the spread hash / prime table size do at even larger sizes? I ran  
> the same test at sizes of one million. As expected, access was quite  
> a bit slower than it had been at 10000. Time for #at: was ~250  
> microseconds, and #at:put: was about the same. Note, however, that  
> this is still ten times faster than Dictionary previously was at a  
> size of 10000; 100 times larger yet 10 times faster.
>
> I had a lot of fun doing this. This is better results than I  
> expected, for a fairly minor (though deep) code change.

> | test ord |
> Transcript cr.
> test := Dictionary new.
> [ test size >= 10000] whileFalse: [
> ord := OrderedCollection new: 100.
> Transcript show:
> [
> 100 timesRepeat: [
> test at: ( ord add: Object new ) put: nil ].
> ] timeToRun asString.
> Transcript tab;
> show: test size asString;
> tab.
> Transcript show:
> [
> 1000 timesRepeat: [
> ord do: [ :each | test at: each ] ]
> ] timeToRun asString.
> Transcript tab; show:
> [
> 1000 timesRepeat: [
> ord do: [ :each | ] ]
> ] timeToRun asString.
> Transcript cr ]
>
> <
> SmallDictPerformanceGraphs1
> .png>_______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

> Martin
>
> so what you are saying is that we can gain speed. And that these  
> changes are beneficial for simple default.
>
>
>  
>> The test code, a variant of the test from the HashTable SqueakSource  
>> wiki, is at the bottom of this message. Basically, it adds a bunch  
>> of instances of Object to a Dictionary and sees how much time it  
>> takes to look them up again.
>>
>> From the graphs in the previous message, you can see that  
>> performance for sizes > 4000 is greatly improved. For size = 10000,  
>> #at: is 1000 times faster, 2-3 microseconds vs. >2 milliseconds. At  
>> size=10000, #at:put: is about 200 times faster, ~10 microseconds vs.  
>>    
>>> 2 milliseconds, and the large spikes for growing the collection are  
>>>      
>> 21 milliseconds vs. > 4 seconds, again a factor of about 200.
>>
>> Performance for dictionary sizes < 4000 is essentially the same as  
>> before, so these collections can serve as general-purpose  
>> collections over a wide range of sizes. I've attached the graphs for  
>> sizes <4000 to this message so you can see that more clearly than on  
>> the previous graphs.
>>
>> These results should hold for any object that inherits #hash from  
>> Object, in other words uses its identity hash as its equality hash.  
>> Other objects with better hashes did not have as serious a problem,  
>> but will probably show increased performance as well due to using  
>> prime table sizes.
>>
>> These changes are in Set, so should improve Set's subclasses as  
>> well. IdentityDictionary, IdentitySet, and WeakIdentityKeyDictionary  
>> did not have as serious a problem, but should see some improvement.  
>> MethodDictionaries have been left alone on the assumption that the  
>> VM depends on the hashing of those.
>>    
>
> So where are these changes :)
> Should we integrate them?
> Andres and other hash freaks what are your point of view?
>
>  
>> Since there are still only 4K possible values of identity hash,  
>> collisions are inevitable in large collections, and the number of  
>> collisions will grow linearly with collection size. So how well does  
>> the spread hash / prime table size do at even larger sizes? I ran  
>> the same test at sizes of one million. As expected, access was quite  
>> a bit slower than it had been at 10000. Time for #at: was ~250  
>> microseconds, and #at:put: was about the same. Note, however, that  
>> this is still ten times faster than Dictionary previously was at a  
>> size of 10000; 100 times larger yet 10 times faster.
>>
>> I had a lot of fun doing this. This is better results than I  
>> expected, for a fairly minor (though deep) code change.
>>    
>
> So where are these changes :)
> Should we integrate them?
> Andres and other hash freaks what are your point of view?
>
>
>  
>> | test ord |
>> Transcript cr.
>> test := Dictionary new.
>> [ test size >= 10000] whileFalse: [
>> ord := OrderedCollection new: 100.
>> Transcript show:
>> [
>> 100 timesRepeat: [
>> test at: ( ord add: Object new ) put: nil ].
>> ] timeToRun asString.
>> Transcript tab;
>> show: test size asString;
>> tab.
>> Transcript show:
>> [
>> 1000 timesRepeat: [
>> ord do: [ :each | test at: each ] ]
>> ] timeToRun asString.
>> Transcript tab; show:
>> [
>> 1000 timesRepeat: [
>> ord do: [ :each | ] ]
>> ] timeToRun asString.
>> Transcript cr ]
>>
>> <
>> SmallDictPerformanceGraphs1
>> .png>_______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>    
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
> .
>
>  

>
>
> If, on the other hand, we provide a new scaledIdentityHash method, then
> all senders of identityHash keep behaving the same way as they do now.  
> Hashed collections, which currently send identityHash, would need to
> change so that they send scaledIdentityHash instead.  Furthermore, any
> implementor of hash such as
>
> SomeObject>>hash
>
>   ^self someInstanceVariable identityHash
>
>
> would need to be rewritten as
>
> SomeObject>>hash
>
>   ^self someInstanceVariable scaledIdentityHash

>> Clever hacks such as
>>
>> SomeObject>>hash
>>
>>   ^(self variableA identityHash bitShift: 12) + self variableB identityHash
>>
>>
>> would also remain undisturbed.  
>>    
>
> Yes, if #identityHash is changed it's the clever hacks that will have to
> change. This could be a disadvantage of this approach, but often, as in
> the case of IdentityDictionary, IdentitySet, and
> WeakIdentityKeyDictionary, the necessary change is simply to remove the
> clever hack, get simpler code, and enjoy better performance than you got
> with the clever hack, so making the change is IMO an improvement.
>  

>> Finally, I do not know of any Smalltalk
>> in which identityHash does not answer the actual object header bits for
>> the identity hash. If we change identityHash, then AFAIK Pharo would
>> become the only Smalltalk in which identityHash does not answer
>> consecutive values between 0 and (2^k)-1 (k=12 for Squeak/Pharo, k=14
>> for VisualWorks 32 bits, k=20 for VisualWorks 64 bits, IIRC k=15 for VA
>> and VisualSmalltalk).  
>>    
>
> GemStone is a Smalltalk that does not answer consecutive values for
> identityHash.

> Martin,
>
> One of the constituencies I thought of when I decided to leave
> identityHash alone was folks like you.  Now, as a representative, if  
> you
> are ok with dealing with broken identityHash senders (which I hope  
> will
> be few), then most of my motivation for leaving identityHash unchanged
> is gone.  Thus, I would not mind changing identityHash and  
> implementing
> primIdentityHash.
>
> What about others?  Would anybody mind if identityHash was changed?
>
> Some comments below...
>
>> I took a survey of the senders of #identityHash in the latest web  
>> image.
>> There aren't that many. The largest category is those that want the
>> printString of the identityHash.
>>
>
> These would probably need to be changed to get the printString of the
> primIdentityHash.
>
>> Of those that care about the value of the identityHash, there are
>> several that use it in #hash methods. The most common is this  
>> definition:
>>
>> hash
>>   ^self identityHash
>>
>> These are presumably overriding superclass behavior to restore Object
>> behavior.
>
> I'd like to take a look at these, I suspect there may be low hanging
> fruit waiting to be fixed.
>
>> If the authors knew about the limited range of #identityHash, that is
>> entirely possible. I tend to think it more likely that in most cases
>> these implementations are just the simplest way to follow the dictate
>> that 'a=b -> a hash = b hash', and that they didn't really think  
>> about
>> the impact on collection performance.
>>
>
> Or maybe they chose identityHash because they can assume uniqueness (=
> effectively being ==)...
>
>> 5 improved, 2 harmed. And one of the listed harmed is  
>> MethodDictionary,
>> whose performance would not be harmed, but I assume the VM would  
>> not be
>> happy if their hashing was changed (anybody know for sure whether  
>> that's
>> true?)
>>
>
> The VM probably knows a lot about identityHash values, and most likely
> uses the primIdentityHash values because then it doesn't have to shift
> on access.
>
>> They could, and I admit to having written this kind of code in the  
>> past,
>> but I doubt that I'm typical in doing so. Do you know of any Pharo  
>> code
>> that actually *does* this sort of thing? There isn't any in the
>> distributed web image, but I didn't look at every package that is  
>> meant
>> to be loadable in Pharo.
>>
>
> I might suspect that Magma does this kind of stuff... but that's  
> just a
> guess.  I didn't immediately see any code doing so.  As long as  
> package
> maintainers are fine with two quite different versions of Pharo with
> very different identityHash method behaviors, then I do not have a  
> problem.
>
>>> Clever hacks such as
>>>
>>> SomeObject>>hash
>>>
>>>  ^(self variableA identityHash bitShift: 12) + self variableB  
>>> identityHash
>>>
>>>
>>> would also remain undisturbed.
>>>
>>
>> Yes, if #identityHash is changed it's the clever hacks that will  
>> have to
>> change. This could be a disadvantage of this approach, but often,  
>> as in
>> the case of IdentityDictionary, IdentitySet, and
>> WeakIdentityKeyDictionary, the necessary change is simply to remove  
>> the
>> clever hack, get simpler code, and enjoy better performance than  
>> you got
>> with the clever hack, so making the change is IMO an improvement.
>>
>
> We agree, mod I wouldn't want to impose version maintenance homework  
> on
> maintainers of large packages.  For the sake of illustration only, and
> using Magma without knowing if it would be affected, I wouldn't want
> whoever is maintaining Magma to maintain two branches... one for Pharo
> 1.xyz, and one for Pharo 1.xyz++.
>
>>> Finally, I do not know of any Smalltalk
>>> in which identityHash does not answer the actual object header  
>>> bits for
>>> the identity hash. If we change identityHash, then AFAIK Pharo would
>>> become the only Smalltalk in which identityHash does not answer
>>> consecutive values between 0 and (2^k)-1 (k=12 for Squeak/Pharo,  
>>> k=14
>>> for VisualWorks 32 bits, k=20 for VisualWorks 64 bits, IIRC k=15  
>>> for VA
>>> and VisualSmalltalk).
>>>
>>
>> GemStone is a Smalltalk that does not answer consecutive values for
>> identityHash.
>
> Haha, I was thinking of "regular" image based Smalltalks...
>
>> In GemStone the identityHash is computed from the object's
>> OOP, and OOPs are not consecutive.
>
> Not necessarily, although I suspect identityHash values map to an
> integer interval along the lines of [0, 2^40-1].  So, if you look at
> hash(x) as a function, the image of hash(x) is a set of consecutive
> intervals.  Using bitShift: to scale identityHash values would make  
> the
> image of hash(x) sparse (with the exception of small integers,
> characters and, to some extent in VW 64 bit, small doubles).
>
>> And Smalltalk-80 basically used the
>> same scheme, though you could only have 32K objects, every one had a
>> different identityHash based on OOP.
>>
>
> These are also consecutive values... [0, 2^15-1], basically.
>
>> Also, most (all?) Smalltalks with limited ranges for identityHash do
>> have a larger range of identityHash for SmallIntegers (usually  
>> ^self),
>> so you can't use the clever hacks if you might have any  
>> SmallIntegers in
>> your collection. So any general-purpose collection must already deal
>> with the full SmallInteger range of identity hashes as keys, cannot  
>> use
>> the clever hacks, and so is likely to only be improved by changing
>> #identityHash. This is a key point that I forgot to bring up last  
>> night.
>>
>
> Well, more or less, because with scaledIdentityHash you'd need to
> implement it in SmallInteger as ^self... but yes, I think hashed
> collections shouldn't be put into a position where they judge what's a
> good hash value and what isn't (and  spend CPU time doing so at
> runtime!!!).  Java does this, and as far as I could see back when I
> studied Java's hashing implementation, IMO it's not a good idea.
>
> Andres.
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

> Stephane et al,
>
> Martin and I discussed this yesterday night at the PDX Smalltalk user
> group meeting.  Mostly we agree, with perhaps one small exception.  In
> order to make hashed collections simpler and identity hash handling  
> more
> straightforward, hashed collections should get a small integer range
> identity hash value.  Something between 0 and SmallInteger maxVal, for
> example.  The issue is how to get that.
>
> Martin's approach is to change identityHash itself, and provide
> primIdentityHash to access the existing identityHash implementation
> (primitive 75).  My approach is to leave identityHash as is, and  
> provide
> a new message called scaledIdentityHash.  Note that in both Martin's  
> and
> my implementation, the new identity hash values are identical.  In  
> other
> words, whereas Martin's changes implement
>
> identityHash
>
> ^self primIdentityHash bitShift: 18
>
>
> my changes implement
>
> scaledIdentityHash
>
> ^self identityHash bitShift: 18
>
>
> So, really, this is an issue of how to implement the *same* behavior,
> with the *same* goals.  Now, there are advantages and disadvantages  
> for
> both.  I'll try to explain.  Martin, please feel free to correct what
> follows if I miss something.
>
> There are two kinds of senders of identityHash.  Some (most) do not  
> care
> whether the answer is well distributed or not.  Typically, these are
> implementors of #hash, for example:
>
> SomeObject>>hash
>
> ^self someInstanceVariable identityHash
>
>
> If, on one hand, we change identityHash, then the behavior of these  
> hash
> methods improve because the values they answer would be distributed  
> more
> uniformly.  Nevertheless, precisely because they send identityHash, it
> could be argued that these hash methods were implemented assuming  
> there
> would be just a few of these objects in hashed collections.  If this
> turns out not to be the case, then performance could be much better by
> implementing a better hash method.
>
> Some (a few) other senders of identityHash assume that the answer  
> has a
> particular distribution (in Squeak's/Pharo's case, 0 through 4095).
> Consequently, the senders may do things like this:
>
> SomeObject>>hash
>
> ^(self variableA identityHash bitShift: 12) + self variableB  
> identityHash
>
>
> Also, there may be hashed collections which use identityHash to index
> hash buckets (e.g.: GemStone's own 32 bit object cache for  
> VisualWorks,
> which uses identityHash to access hash buckets).  So, if we change
> identityHash, these senders which required special care to write would
> break, requiring them to be written like this:
>
> SomeObject>>hash
>
> ^(self variableA primIdentityHash bitShift: 12) + self variableB
> primIdentityHash
>
>
> If, on the other hand, we provide a new scaledIdentityHash method,  
> then
> all senders of identityHash keep behaving the same way as they do now.
> Hashed collections, which currently send identityHash, would need to
> change so that they send scaledIdentityHash instead.  Furthermore, any
> implementor of hash such as
>
> SomeObject>>hash
>
> ^self someInstanceVariable identityHash
>
>
> would need to be rewritten as
>
> SomeObject>>hash
>
> ^self someInstanceVariable scaledIdentityHash
>
>
> if hashed collections are expected to contain numerous instances of
> SomeObject.  If these are not rewritten, then they would continue to
> have the same performance characteristics they have today (which may  
> be
> adequate to begin with).  Clever hacks such as
>
> SomeObject>>hash
>
> ^(self variableA identityHash bitShift: 12) + self variableB  
> identityHash
>
>
> would also remain undisturbed.  Finally, I do not know of any  
> Smalltalk
> in which identityHash does not answer the actual object header bits  
> for
> the identity hash.  If we change identityHash, then AFAIK Pharo would
> become the only Smalltalk in which identityHash does not answer
> consecutive values between 0 and (2^k)-1 (k=12 for Squeak/Pharo, k=14
> for VisualWorks 32 bits, k=20 for VisualWorks 64 bits, IIRC k=15 for  
> VA
> and VisualSmalltalk).  Moreover, AFAIK, identityHash has had this
> behavior for decades.  Is it a good idea to change it?  I am not so  
> sure
> on that one.  Also, I wouldn't want to break clever hacks that assume
> identityHash behaves the way it currently does, and I wouldn't want to
> make Pharo different gratuitously.
>
> So that's where we stand.  I think I understand where Martin is coming
> from, and I think Martin understands where I am coming from.  One  
> way or
> the other, we also agree that something should be done to make hashed
> collections faster in Pharo.
>
> Andres.
>
>
> Stéphane Ducasse wrote:
>> Martin
>>
>> so what you are saying is that we can gain speed. And that these
>> changes are beneficial for simple default.
>>
>>
>>
>>> The test code, a variant of the test from the HashTable SqueakSource
>>> wiki, is at the bottom of this message. Basically, it adds a bunch
>>> of instances of Object to a Dictionary and sees how much time it
>>> takes to look them up again.
>>>
>>> From the graphs in the previous message, you can see that
>>> performance for sizes > 4000 is greatly improved. For size = 10000,
>>> #at: is 1000 times faster, 2-3 microseconds vs. >2 milliseconds. At
>>> size=10000, #at:put: is about 200 times faster, ~10 microseconds vs.
>>>
>>>> 2 milliseconds, and the large spikes for growing the collection are
>>>>
>>> 21 milliseconds vs. > 4 seconds, again a factor of about 200.
>>>
>>> Performance for dictionary sizes < 4000 is essentially the same as
>>> before, so these collections can serve as general-purpose
>>> collections over a wide range of sizes. I've attached the graphs for
>>> sizes <4000 to this message so you can see that more clearly than on
>>> the previous graphs.
>>>
>>> These results should hold for any object that inherits #hash from
>>> Object, in other words uses its identity hash as its equality hash.
>>> Other objects with better hashes did not have as serious a problem,
>>> but will probably show increased performance as well due to using
>>> prime table sizes.
>>>
>>> These changes are in Set, so should improve Set's subclasses as
>>> well. IdentityDictionary, IdentitySet, and WeakIdentityKeyDictionary
>>> did not have as serious a problem, but should see some improvement.
>>> MethodDictionaries have been left alone on the assumption that the
>>> VM depends on the hashing of those.
>>>
>>
>> So where are these changes :)
>> Should we integrate them?
>> Andres and other hash freaks what are your point of view?
>>
>>
>>> Since there are still only 4K possible values of identity hash,
>>> collisions are inevitable in large collections, and the number of
>>> collisions will grow linearly with collection size. So how well does
>>> the spread hash / prime table size do at even larger sizes? I ran
>>> the same test at sizes of one million. As expected, access was quite
>>> a bit slower than it had been at 10000. Time for #at: was ~250
>>> microseconds, and #at:put: was about the same. Note, however, that
>>> this is still ten times faster than Dictionary previously was at a
>>> size of 10000; 100 times larger yet 10 times faster.
>>>
>>> I had a lot of fun doing this. This is better results than I
>>> expected, for a fairly minor (though deep) code change.
>>>
>>
>> So where are these changes :)
>> Should we integrate them?
>> Andres and other hash freaks what are your point of view?
>>
>>
>>
>>> | test ord |
>>> Transcript cr.
>>> test := Dictionary new.
>>> [ test size >= 10000] whileFalse: [
>>> ord := OrderedCollection new: 100.
>>> Transcript show:
>>> [
>>> 100 timesRepeat: [
>>> test at: ( ord add: Object new ) put: nil ].
>>> ] timeToRun asString.
>>> Transcript tab;
>>> show: test size asString;
>>> tab.
>>> Transcript show:
>>> [
>>> 1000 timesRepeat: [
>>> ord do: [ :each | test at: each ] ]
>>> ] timeToRun asString.
>>> Transcript tab; show:
>>> [
>>> 1000 timesRepeat: [
>>> ord do: [ :each | ] ]
>>> ] timeToRun asString.
>>> Transcript cr ]
>>>
>>> <
>>> SmallDictPerformanceGraphs1
>>> .png>_______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>
>>
>>
>> _______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>> .
>>
>>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project