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
