(Sorry Pharo, meant to post this to squeak-dev).

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 Wed, Mar 17, 2010 at 5:07 PM, Nicolas Cellier
<nicolas.cellier.aka.nice at gmail.com> wrote:
> http://www.mail-archive.com/pharo-project@lists.gforge.inria.fr/msg15177.html
> http://lists.squeakfoundation.org/pipermail/squeak-dev/2009-November/141493.html
> etc...
>
> 2010/3/17 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
>> 2010/3/17 Chris Muller <asqueaker at 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 at 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 at lists.gforge.inria.fr
>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>
>>>>
>>>> _______________________________________________
>>>> Pharo-project mailing list
>>>> Pharo-project at lists.gforge.inria.fr
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>
>>>
>>> _______________________________________________
>>> Pharo-project mailing list
>>> Pharo-project at lists.gforge.inria.fr
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>
> _______________________________________________
> Pharo-project mailing list
> Pharo-project at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>