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