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. 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 <stephane.ducasse@inria.fr> 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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

http://www.mail-archive.com/pharo-project@lists.gforge.inria.fr/msg15177.htm... http://lists.squeakfoundation.org/pipermail/squeak-dev/2009-November/141493.... etc... 2010/3/17 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:

2010/3/17 Chris Muller <asqueaker@gmail.com>:

...

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 <stephane.ducasse@inria.fr> 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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

  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

On Wed, 17 Mar 2010, Chris Muller wrote:

Hmm, well, that only moves the goal posts to ~320K.

I just ran a bigger test in 3.9. Not only are the numbers comparable at the beginning of the test with a small IdentitySet, they only degrade to 10X slower at 1M elements. The trunk IdentitySet seems to have much more rapid degradation... Since there are only 4096 different keys, you're practically growing 4096 lists in an array. The cause of the problem is that the gap between the slots which are the head of the lists are less than the length of the list, so clustering will occur. Most primes above 100000 are affected by this issue in the #goodPrimes array. We can solve this issue by using: (1) different primes in general (2) different primes for identity hash based collections (3) a different method for #scaledIdentityHash calculation (4) a combination of the above I found 5918 primes between 5 and 1000000 which are expected to behave optimally (and 59115 which are close to optimal) with #scaledIdentityHash, so probably (1) or (2) is the ideal solution. Levente On Wed, Mar 17, 2010 at 9:40 PM, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote:

 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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project