Faster Sets and Pharo 1.1?

> When I released my FasterSets package it was too late
> for consideration for Pharo 1.0 so it was stated that it would be reconsidered
> for  Pharo  1.1.
>
> Of course, since my release, Levente has rewritten my version of FasterSets
> from scratch and also made many other changes to Sets.
>
> So I am wondering what the status of FasterSets is with respect to Pharo 1.1:
>
>   a) FasterSets is not wanted in Pharo.
>   b)  You will use my version of FasterSets in Pharo 1.1.
>   c)   You will use Levente's version of FasterSets and perhaps his many other
>        changes to Sets/Dictionaries in Pharo  1.1.
>
> Regards,
>
> Ralph Boland
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

> Thanks Ralph
>
> Levente, nicolas, henrik can you help us to take a good decision.
> I'm not precise enough on that topic and its implications.
> What I would love it to have Faster Set
> Levente is it dependent on hash changes that martin is working on?
>
> Stef
>
> On Mar 17, 2010, at 6:39 PM, Ralph Boland wrote:
>
>> When I released my FasterSets package it was too late
>> for consideration for Pharo 1.0 so it was stated that it would be reconsidered
>> for  Pharo  1.1.
>>
>> Of course, since my release, Levente has rewritten my version of FasterSets
>> from scratch and also made many other changes to Sets.
>>
>> So I am wondering what the status of FasterSets is with respect to Pharo 1.1:
>>
>>   a) FasterSets is not wanted in Pharo.
>>   b)  You will use my version of FasterSets in Pharo 1.1.
>>   c)   You will use Levente's version of FasterSets and perhaps his many other
>>        changes to Sets/Dictionaries in Pharo  1.1.
>>
>> Regards,
>>
>> Ralph Boland
>>
>> _______________________________________________
>> 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
>

> Did Faster Sets get integrated into the trunk image?  I can't seem to
> find discussion or benchmark results on the list.  Any info is greatly
> appreciated.
>
>  - Chris
>
> On Wed, Mar 17, 2010 at 12:58 PM, Stéphane Ducasse
> <[hidden email]> wrote:
>> Thanks Ralph
>>
>> Levente, nicolas, henrik can you help us to take a good decision.
>> I'm not precise enough on that topic and its implications.
>> What I would love it to have Faster Set
>> Levente is it dependent on hash changes that martin is working on?
>>
>> Stef
>>
>> On Mar 17, 2010, at 6:39 PM, Ralph Boland wrote:
>>
>>> When I released my FasterSets package it was too late
>>> for consideration for Pharo 1.0 so it was stated that it would be reconsidered
>>> for  Pharo  1.1.
>>>
>>> Of course, since my release, Levente has rewritten my version of FasterSets
>>> from scratch and also made many other changes to Sets.
>>>
>>> So I am wondering what the status of FasterSets is with respect to Pharo 1.1:
>>>
>>>   a) FasterSets is not wanted in Pharo.
>>>   b)  You will use my version of FasterSets in Pharo 1.1.
>>>   c)   You will use Levente's version of FasterSets and perhaps his many other
>>>        changes to Sets/Dictionaries in Pharo  1.1.
>>>
>>> Regards,
>>>
>>> Ralph Boland
>>>
>>> _______________________________________________
>>> 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

> 2010/3/17 Chris Muller <[hidden email]>:
>> Wow, I'm really glad this topic has just come up right when I'm
>> researching the list, trying to figure out why a large IdentitySet
>> seems to have gotten incredibly slow in the trunk image, relative to
>> 3.9.
>>
>> I haven't had a chance to do any measurements yet, but I have an
>> IdentitySet with just a quarter-million objects, it *seems* to be much
>> slower to add than in 3.9.
>>
>
> Huh? That's interesting, it should be the opposite.
> I presume you IdentitySet has enough room allocated (beware, some
> basicSize can be slow, better be a prime).
> Since there were 4096 different identityHash only and all contiguous,
> adding time did turn in O(n) in 3.9, so O(n^2)/2 to addAll:.
> Now, there are still 4096 different hash, but scaled to be non
> contiguous. Your score should be around O((n/4096)^2).
> Unless you messed with #identityHash or used basicNew: ?
>
> Nicolas
>
> http://bugs.squeak.org/view.php?id=1876
> http://code.google.com/p/pharo/issues/detail?id=213
> http://code.google.com/p/pharo/issues/detail?id=1868
> Browse pharo list in 2009.
> Message from Andres Valloud and Martin McClure
> Also search scaledIdentityHash identityHash IdentitySet in squeak-dev
> in 2009 messages from Levente.
>
>> Did Faster Sets get integrated into the trunk image?  I can't seem to
>> find discussion or benchmark results on the list.  Any info is greatly
>> appreciated.
>>
>>  - Chris
>>
>> On Wed, Mar 17, 2010 at 12:58 PM, Stéphane Ducasse
>> <[hidden email]> wrote:
>>> Thanks Ralph
>>>
>>> Levente, nicolas, henrik can you help us to take a good decision.
>>> I'm not precise enough on that topic and its implications.
>>> What I would love it to have Faster Set
>>> Levente is it dependent on hash changes that martin is working on?
>>>
>>> Stef
>>>
>>> On Mar 17, 2010, at 6:39 PM, Ralph Boland wrote:
>>>
>>>> When I released my FasterSets package it was too late
>>>> for consideration for Pharo 1.0 so it was stated that it would be reconsidered
>>>> for  Pharo  1.1.
>>>>
>>>> Of course, since my release, Levente has rewritten my version of FasterSets
>>>> from scratch and also made many other changes to Sets.
>>>>
>>>> So I am wondering what the status of FasterSets is with respect to Pharo 1.1:
>>>>
>>>>   a) FasterSets is not wanted in Pharo.
>>>>   b)  You will use my version of FasterSets in Pharo 1.1.
>>>>   c)   You will use Levente's version of FasterSets and perhaps his many other
>>>>        changes to Sets/Dictionaries in Pharo  1.1.
>>>>
>>>> Regards,
>>>>
>>>> Ralph Boland
>>>>
>>>> _______________________________________________
>>>> 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
>

> 2010/3/17 Chris Muller <[hidden email]>:
>> Wow, I'm really glad this topic has just come up right when I'm
>> researching the list, trying to figure out why a large IdentitySet
>> seems to have gotten incredibly slow in the trunk image, relative to
>> 3.9.
>>
>> I haven't had a chance to do any measurements yet, but I have an
>> IdentitySet with just a quarter-million objects, it *seems* to be much
>> slower to add than in 3.9.
>>
>
> Huh? That's interesting, it should be the opposite.
> I presume you IdentitySet has enough room allocated (beware, some
> basicSize can be slow, better be a prime).
> Since there were 4096 different identityHash only and all contiguous,
> adding time did turn in O(n) in 3.9, so O(n^2)/2 to addAll:.
> Now, there are still 4096 different hash, but scaled to be non
> contiguous. Your score should be around O((n/4096)^2).
> Unless you messed with #identityHash or used basicNew: ?
>
> Nicolas
>
> http://bugs.squeak.org/view.php?id=1876
> http://code.google.com/p/pharo/issues/detail?id=213
> http://code.google.com/p/pharo/issues/detail?id=1868
> Browse pharo list in 2009.
> Message from Andres Valloud and Martin McClure
> Also search scaledIdentityHash identityHash IdentitySet in squeak-dev
> in 2009 messages from Levente.
>
>> Did Faster Sets get integrated into the trunk image?  I can't seem to
>> find discussion or benchmark results on the list.  Any info is greatly
>> appreciated.
>>
>>  - Chris
>>
>> On Wed, Mar 17, 2010 at 12:58 PM, Stéphane Ducasse
>> <[hidden email]> wrote:
>>> Thanks Ralph
>>>
>>> Levente, nicolas, henrik can you help us to take a good decision.
>>> I'm not precise enough on that topic and its implications.
>>> What I would love it to have Faster Set
>>> Levente is it dependent on hash changes that martin is working on?
>>>
>>> Stef
>>>
>>> On Mar 17, 2010, at 6:39 PM, Ralph Boland wrote:
>>>
>>>> When I released my FasterSets package it was too late
>>>> for consideration for Pharo 1.0 so it was stated that it would be reconsidered
>>>> for  Pharo  1.1.
>>>>
>>>> Of course, since my release, Levente has rewritten my version of FasterSets
>>>> from scratch and also made many other changes to Sets.
>>>>
>>>> So I am wondering what the status of FasterSets is with respect to Pharo 1.1:
>>>>
>>>>   a) FasterSets is not wanted in Pharo.
>>>>   b)  You will use my version of FasterSets in Pharo 1.1.
>>>>   c)   You will use Levente's version of FasterSets and perhaps his many other
>>>>        changes to Sets/Dictionaries in Pharo  1.1.
>>>>
>>>> Regards,
>>>>
>>>> Ralph Boland
>>>>
>>>> _______________________________________________
>>>> 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
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>

> Thank you very much for the links.  Ok, so if you take Lukas' test
> code from the first link, and try it in trunk.  Here it is, but
> tweaked for an IdentitySet and increased to simulate a modestly-sized
> real-world use-case, 250K elements:
>
> | test ord |
> test := IdentitySet new.
> [ test size>= 250000 ] whileFalse: [
>      ord := OrderedCollection new: 100.
>      1000 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 ]
>
> 3.9 can run this entire thing and be done with it in under one minute.
>   In trunk, all looks pretty fine until 136K elements, at which point
> it completely seizes up; worse by a factor of>  120X.
>
>    - Chris

>  On 18.03.2010 02:08, Chris Muller wrote:
>>
>> Thank you very much for the links.  Ok, so if you take Lukas' test
>> code from the first link, and try it in trunk.  Here it is, but
>> tweaked for an IdentitySet and increased to simulate a modestly-sized
>> real-world use-case, 250K elements:
>>
>> | test ord |
>> test := IdentitySet new.
>> [ test size>= 250000 ] whileFalse: [
>>     ord := OrderedCollection new: 100.
>>     1000 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 ]
>>
>> 3.9 can run this entire thing and be done with it in under one minute.
>>  In trunk, all looks pretty fine until 136K elements, at which point
>> it completely seizes up; worse by a factor of>  120X.
>>
>>   - Chris
>
> Simplistic fix:
> - remove 282311 from HashedCollection class>>goodPrimes.
>
> The table should probably be remade for squeak, keeping in mind the
> scaledIdentityHash implementation.
>
> Cheers,
> Henry
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>