[Pharo-project] Stack should be reimplemented with Array

Stéphane Ducasse stephane.ducasse at inria.fr
Mon Oct 18 16:02:51 EDT 2010


Eliot

> 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 would really like not having Stack inheriting from LinkedList (I hate subclassing). Now from a VM point of view 
is there a constraint that Stack as to be a subclass of LList?


>  
> 
> 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
> Pharo-project at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
> 
> _______________________________________________
> Pharo-project mailing list
> Pharo-project at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project





More information about the Pharo-dev mailing list