<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jan 16, 2015 at 11:49 AM, Chris Muller <span dir="ltr"><<a href="mailto:asqueaker@gmail.com" target="_blank">asqueaker@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">> In general the locality of the links are worse. In the example they are<br>
> allocated almost next to each other.<br>
> A slightly better example would be this:<br>
><br>
> | buffer |<br>
> buffer := Array new: 1000. "This will hold the filler objects."<br>
> #(1024 2048 4096 8192 16384 32768 65536) collect: [ :fillerSize |<br>
> | list |<br>
> list := LinkedList new.<br>
> 1 to: 1000 do: [ :index |<br>
> list add: (StackLink with: nil).<br>
> buffer at: index put: (Array new: fillerSize) ].<br>
> Smalltalk garbageCollect.<br>
> fillerSize -> [ list do: [ :ea | 1 + 2 ] ] bench ]<br>
><br>
> { "gap between nodes (x4 bytes)" -> "runs"<br>
> 1024->'78,000 per second.'.<br>
> 2048->'78,600 per second.'.<br>
> 4096->'77,500 per second.'.<br>
> 8192->'73,300 per second.'.<br>
> 16384->'70,200 per second.'. 32768->'66,400 per second.'.<br>
> 65536->'56,400 per second.'}<br>
><br>
> (The result is '45,700 per second.' for Arrays)<br>
><br>
> The results depend on the CPU (and probably on the OS too), but the numbers<br>
> are still pretty good. Probably a longer list would cause more problem for<br>
> the caches.<br>
> The same for 10k elements in the list:<br>
><br>
> {<br>
> 1024->'3,770 per second.'.<br>
> 2048->'4,780 per second.'.<br>
> 4096->'4,220 per second.'.<br>
> 8192->'2,480 per second.'.<br>
> 16384->'2,110 per second.'}<br>
><br>
> (The result is '4,380 per second.' for Arrays)<br>
><br>
> So the speed of a list depends on the cache locality of its elements. The<br>
> performance is still comparable with arrays for practical cases, but may be<br>
> both faster and slower depending on the cache locality.<br>
<br>
</div></div>Geez you guys /seriously/ rock. I never thought down to that level of<br>
(CPU) cache locality.<br>
<br>
You've got me feeling like I should go back to some<br>
performance-critical code which is enumerating Array's and see about<br>
converting them to LinkedLists.. too bad I don't have time to do<br>
that!<br></blockquote><div><br></div><div>Please, folks, unless you're really pressed don't bother. We should have Sista deployed this year and that will take care of this nicely. </div></div>-- <br><div class="gmail_signature">best,<div>Eliot</div></div>
</div></div>