On Mon, Jan 26, 2015 at 11:12 PM, Levente Uzonyi <leves at elte.hu> wrote:

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

Of course, that's much better.  Simply replace the linked list with an
empty one.


>
> 0.018ms sounds great for #become:.


It's a key part of the design of Spur.

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


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