OrderedDictionary (was: Re: [squeak-dev] Re: The Trunk: Collections-mt.593.mcz)

Eliot Miranda eliot.miranda at gmail.com
Fri Jan 16 20:06:35 UTC 2015


On Fri, Jan 16, 2015 at 11:49 AM, Chris Muller <asqueaker at gmail.com> wrote:

> > In general the locality of the links are worse. In the example they are
> > allocated almost next to each other.
> > A slightly better example would be this:
> >
> > | buffer |
> > buffer := Array new: 1000. "This will hold the filler objects."
> > #(1024 2048 4096 8192 16384 32768 65536) collect: [ :fillerSize |
> >         | list |
> >         list := LinkedList new.
> >         1 to: 1000 do: [ :index |
> >                 list add: (StackLink with: nil).
> >                 buffer at: index put: (Array new: fillerSize) ].
> >         Smalltalk garbageCollect.
> >         fillerSize -> [ list do: [ :ea | 1 + 2 ] ] bench ]
> >
> > { "gap between nodes (x4 bytes)" -> "runs"
> > 1024->'78,000 per second.'.
> > 2048->'78,600 per second.'.
> > 4096->'77,500 per second.'.
> > 8192->'73,300 per second.'.
> > 16384->'70,200 per second.'. 32768->'66,400 per second.'.
> > 65536->'56,400 per second.'}
> >
> > (The result is '45,700 per second.' for Arrays)
> >
> > The results depend on the CPU (and probably on the OS too), but the
> numbers
> > are still pretty good. Probably a longer list would cause more problem
> for
> > the caches.
> > The same for 10k elements in the list:
> >
> > {
> > 1024->'3,770 per second.'.
> > 2048->'4,780 per second.'.
> > 4096->'4,220 per second.'.
> > 8192->'2,480 per second.'.
> > 16384->'2,110 per second.'}
> >
> > (The result is '4,380 per second.' for Arrays)
> >
> > So the speed of a list depends on the cache locality of its elements. The
> > performance is still comparable with arrays for practical cases, but may
> be
> > both faster and slower depending on the cache locality.
>
> Geez you guys /seriously/ rock.  I never thought down to that level of
> (CPU) cache locality.
>
> You've got me feeling like I should go back to some
> performance-critical code which is enumerating Array's and see about
> converting them to LinkedLists..  too bad I don't have time to do
> that!
>

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.
-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20150116/fb07aaa1/attachment.htm


More information about the Squeak-dev mailing list