thanks levente!
this is always nice to read such kind of post since they educate us and we need
that :)
I want to be taught a lot :)
Stef
On Oct 15, 2010, at 6:33 PM, Levente Uzonyi wrote:
> On Thu, 14 Oct 2010, jaayer wrote:
>
>> There was a post on this list back in August complaining about Stack
>> inheriting from LinkedList. There was some discussion, but apparently no
>> resolution, as Stack still inherits from LinkedList in the Pharo 1.2 Core
>> Image I just downloaded. Rather than reimplementing it to forward to a
>> contained LinkedList, I think it should use an Array internally like
>> OrderedCollection does. An Array-based implementation of Stack would be
>> faster than one based on LinkedList due to the basic stack operations (push,
>> pop and top) being able to rely more on primitives. This assumes that you
>> know roughly how a big a stack you need; if you don't, reallocating the
>> array and copying its contents over and over again will cost you, but this
>> is an exceptional case;-- most stacks are small and when they aren't, the
>> programmer usually has enough information to select a reasonable stack size.
>>
>> Enclosed is a fileout of an Array-based Stack implementation. It trounces
>> the LinkedList-based implementation easily, but more interestingly, it
>> performs better than an OrderedCollection when used like a stack:
>>
>> Pushing is roughly ~30% faster:
>> r1 :=[100000 timesRepeat: [
>> s := Stack new.
>> 10 timesRepeat: [s push: #foo]]] timeToRun.
>> r2 := [100000 timesRepeat: [
>> oc := OrderedCollection new.
>> 10 timesRepeat: [oc addLast: #foo]]] timeToRun.
>> 100 - ((r1 / r2) asFloat * 100).
>>
>> as is pushing + popping:
>> r3 := [100000 timesRepeat: [
>> s := Stack new.
>> 10 timesRepeat: [s push: #foo].
>> 10 timesRepeat: [s pop]]] timeToRun.
>> r4 := [100000 timesRepeat: [
>> oc := OrderedCollection new.
>> 10 timesRepeat: [oc addLast: #foo].
>> 10 timesRepeat: [oc removeLast]]] timeToRun.
>> 100 - ((r3 / r4) asFloat * 100).
>
> Please write more realistic benchmarks. Adding 10 elements to your Stack
> implementation won't make it's array grow. Also the benchmark measures a lot
> of other stuff besides the cost of push and pop. Something like this should
> do it:
>
> "The linked Stack implementation"
> (1 to: 5) collect: [ :run |
> | stack |
> Smalltalk garbageCollect.
> stack := Stack new.
> {
> [ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun.
> [ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ]
> #(#(167 88) #(169 91) #(169 88) #(166 87) #(166 88))
>
> "OrderedCollection"
> (1 to: 5) collect: [ :run |
> | stack |
> Smalltalk garbageCollect.
> stack := OrderedCollection new.
> {
> [ 1 to: 1000000 do: [ :each | stack addLast: each ] ] timeToRun.
> [ 1 to: 1000000 do: [ :each | stack removeLast ] ] timeToRun } ]
> #(#(87 98) #(87 100) #(87 98) #(88 97) #(87 99))
>
> "The new stack implementation"
> (1 to: 5) collect: [ :run |
> | stack |
> Smalltalk garbageCollect.
> stack := Stack new.
> {
> [ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun.
> [ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ]
> #(#(89 62) #(90 63) #(89 62) #(89 62) #(89 64))
>
> All benchmarks were run in the latest Squeak 4.2 alpha using the latest CogVM.
>
> Conclusion: OrderedCollection >> #removeLast uses #emptyCheck which is slow.
> Other than that the difference between OrderedCollection and an array-based
> stack implementation is neglible in Squeak using CogVM.
>
> Replacing
> self emptyCheck
> with
> lastIndex < firstIndex ifTrue: [ self errorEmptyCollection]
> in OrderedCollection >> #removeLast and running the benchmark again gives the
> following results:
> #(#(88 65) #(90 66) #(89 66) #(88 68) #(87 66))
>
>
> Also please send #postCopy to super if you implement #postCopy.
>
>
> Levente
>
> _______________________________________________
> Pharo-project mailing list
> [email protected]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
