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

Eliot Miranda eliot.miranda at gmail.com
Fri Jan 16 15:36:56 UTC 2015


Hi Marcel,

On Jan 16, 2015, at 5:54 AM, Marcel Taeumel <marcel.taeumel at student.hpi.uni-potsdam.de> wrote:

> Ah, okay. I was curious about the performance of iterating over an array vs.
> the linked list:
> 
> a := Array new: 1000.
> l := LinkedList new.
> 
> 1000 timesRepeat: [l add: (StackLink with: nil)].
> 
> [a do: [:ea | 1 + 2]] bench. "'94,600 per second.'"
> 
> [l do: [:ea | 1 + 2]] bench. "'159,000 per second.'"
> 
> I expected the opposite! :-O Why is that so?

Look at the implementations of do:.

In the Array case we iterate over the indices using SmallIntegers (fast arithmetic with no allocation) and dereference each element using the Object>>at: primitive, which (apart from type and bounds checking) is simple indexed memory access. So one read per element.

In the LinkedList case each list element is fetched from the previous element and each value fetched from the element, so two reads per element.

> 
> Best,
> Marcel
> 
> 
> 
> --
> View this message in context: http://forum.world.st/The-Trunk-Collections-mt-593-mcz-tp4799750p4799893.html
> Sent from the Squeak - Dev mailing list archive at Nabble.com.
> 


More information about the Squeak-dev mailing list