<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 26, 2015 at 11:12 PM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@elte.hu" target="_blank">leves@elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Mon, 26 Jan 2015, Eliot Miranda wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
On Mon, Jan 19, 2015 at 11:32 AM, Levente Uzonyi <<a href="mailto:leves@elte.hu" target="_blank">leves@elte.hu</a>> wrote:<br>
I never said it was easy.<br>
Another way to do it is to compact eagerly on removal (as it's done in<br>
Pharo). This gives better mass removal performance, and some of the code<br>
becomes significantly simpler. This results in further performance boost.<br>
<br>
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<br>
usability of the collection quite a bit:<br>
<br>
| n random array |<br>
n := 10000.<br>
random := Random seed: 36rSQUEAK.<br>
array := Array new: n streamContents: [ :stream |<br>
n timesRepeat: [ stream nextPut: (random nextInt: 1073741823) -> 1 ] ].<br>
{ OrderedDictionary. LinkedDictionary } collect: [ :class |<br>
Smalltalk garbageCollect.<br>
[<br>
| instance |<br>
instance := class new.<br>
instance addAll: array.<br>
array do: [ :each | instance removeKey: each key ] ] timeToRun ].<br>
"==> #(78 10)"<br>
<br>
(If n is 100k, then the result is still pretty bad: #(7055 136).)<br>
<br>
You can find these changes in the Inbox.<br>
<br>
<br>
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.<br>
</blockquote>
<br></span>
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.<br>
<br>
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:.<br></blockquote><div><br></div><div>Of course, that's much better. Simply replace the linked list with an empty one. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
0.018ms sounds great for #become:.</blockquote><div><br></div><div>It's a key part of the design of Spur.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="HOEnZb"><font color="#888888">Levente</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Levente<br>
<br>
On Mon, 19 Jan 2015, Marcel Taeumel wrote:<br>
<br>
Woah, managing such a lookup index between "array" and "order" is quite<br>
complicated with the current implementation of Dictionary. :D<br>
<br>
Best,<br>
Marcel<br>
<br>
<br>
<br>
--<br>
View this message in context: <a href="http://forum.world.st/The-Trunk-Collections-mt-599-mcz-tp4800299p4800317.html" target="_blank">http://forum.world.st/The-<u></u>Trunk-Collections-mt-599-mcz-<u></u>tp4800299p4800317.html</a><br>
Sent from the Squeak - Dev mailing list archive at Nabble.com.<br>
<br>
<br>
<br>
<br>
<br>
<br>
--<br>
best,Eliot<br>
<br>
</blockquote>
</div></div><br><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">best,<div>Eliot</div></div>
</div></div>