On Mon, Jan 19, 2015 at 11:32 AM, Levente Uzonyi <leves at elte.hu> wrote:

> I never said it was easy.
> Another way to do it is to compact eagerly on removal (as it's done in
> Pharo). This gives better mass removal performance, and some of the code
> becomes significantly simpler. This results in further performance boost.
>
> Removal still takes O(n) time, which means mass removal is in O(n^2), but
> with a significantly smaller constant (~1/10), which improves the
> usability of the collection quite a bit:
>
> | n random array |
> n := 10000.
> random := Random seed: 36rSQUEAK.
> array := Array new: n streamContents: [ :stream |
>         n timesRepeat: [ stream nextPut: (random nextInt: 1073741823) -> 1
> ] ].
> { OrderedDictionary. LinkedDictionary } collect: [ :class |
>     Smalltalk garbageCollect.
>     [
>         | instance |
>         instance := class new.
>         instance addAll: array.
>         array do: [ :each | instance removeKey: each key ] ] timeToRun ].
> "==> #(78 10)"
>
> (If n is 100k, then the result is still pretty bad: #(7055 136).)
>
> You can find these changes in the Inbox.
>

In Spur, self become: self copyEmpty should be cheap.  This takes about 18
usecs on my 2.2GHz i7.  So at some point the become will be cheaper for
removeAll.

Levente
>
> On Mon, 19 Jan 2015, Marcel Taeumel wrote:
>
>  Woah, managing such a lookup index between "array" and "order" is quite
>> complicated with the current implementation of Dictionary. :D
>>
>> Best,
>> Marcel
>>
>>
>>
>> --
>> View this message in context: http://forum.world.st/The-
>> Trunk-Collections-mt-599-mcz-tp4800299p4800317.html
>> Sent from the Squeak - Dev mailing list archive at Nabble.com.
>>
>>
>>
>


-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20150126/a1fe6433/attachment.htm