4.1 - hashed collections still a problem
Locked
123
123
4.1 - hashed collections still a problem
 
|
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 |
Re: 4.1 - hashed collections still a problem
|
|
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 - |
Re: 4.1 - hashed collections still a problem
|
|
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 - > > > > |
Re: 4.1 - hashed collections still a problem
|
|
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 |
Re: 4.1 - hashed collections still a problem
|
|
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 |
Re: 4.1 - hashed collections still a problem
|
|
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 > > > |
Re: 4.1 - hashed collections still a problem
|
|
>> 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 |
Re: 4.1 - hashed collections still a problem
|
|
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 - |
Re: 4.1 - hashed collections still a problem
|
|
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 - > > > > |
Re: 4.1 - hashed collections still a problem
|
|
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 - |
Re: 4.1 - hashed collections still a problem
|
|
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. > 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. |
Re: 4.1 - hashed collections still a problem
|
|
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 - > > > > |
Re: 4.1 - hashed collections still a problem
|
|
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 |
Re: 4.1 - hashed collections still a problem
|
|
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 - >> >> >> >> >> > . > > |
Re: 4.1 - hashed collections still a problem
|
|
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 - >> >> > |
Re: 4.1 - hashed collections still a problem
|
|
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 - >>> >>> >>> >>> >>> >>> >> . >> >> >> > . > > |
Re: 4.1 - hashed collections still a problem
|
|
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 |
Re: 4.1 - hashed collections still a problem
|
|
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 > > |
Re: 4.1 - hashed collections still a problem
|
|
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 - >>> >>> >>> >>> >>> >> . >> >> > > |
Re: 4.1 - hashed collections still a problem
|
|
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 - >>>> >>>> >>>> >>>> >>>> >>>> >>> . >>> >>> >>> >> . >> >> > > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |