On Mon, 26 Jan 2015, Eliot Miranda wrote:

> 
> 
> 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.

This benchmark shows that it takes O(n) time to remove a single element 
using random access, while it takes O(1) time with the linked implementation.

For #removeAll, if we want to go to the direction where we allocate new 
arrays (instead of replacing all the elements with nil - as it is done 
now), then I think assigning them to the instance variables will always be 
faster than #become:.

0.018ms sounds great for #become:.

Levente

>
>       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
> 
>