On Thu, 14 Oct 2010, Eliot Miranda wrote:
2010/10/14 jaayer <[email protected]>
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.
*No*. Stack and OrderedCollection differ *usefully*. Adding an item to a
Stack is always O(1). Adding an item to an OrderedCollection is O(N)
because when the array overflows a new one must be allocated and the old
objects copied to the new. Why not apply your speedups to
OrderedCollection, or is that not possible? If not possible, then come up
with a new name and add that. Please /don't/ change Stack.
I've never seen any code using Stack. People are more familiar with
OrderedCollection.
The O(1) worst case time for push is true in theory, but if we take into
account GCs and cache locality, then things are a lot worse.
GC pauses caused by the allocation of link objects are longer and happen
more often than the pause caused by array growing (though it may also
cause GC pauses). An array based implementation has much better cache
locality: related object pointers (push/pop) are next to each other and 4x
more pointers fit in same amount of cache.
There are no speedups that could be applied to OrderedCollection in the
code. The code implements a stack which is like an OrderedColelction with
a few extra constraints:
- firstIndex is always 1
- you can only add to the end
- you can only remove from the end
The implementation relies on these constraints. That's what makes it
faster than an OrderedCollection.
Levente
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).
_______________________________________________
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
