[Pharo-project] Stack should be reimplemented with Array
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).
2010/10/14 jaayer <jaayer@zoho.com>
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.
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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
---- On Thu, 14 Oct 2010 10:51:31 -0700 Eliot Miranda wrote ----
*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.
Yes, that point was made in the prior discussion regarding Stack and its superclass in defense of having such a class at all when OrderedCollection is already there. Further, you are correct that I am suggesting we trade guaranteed O(1) complexity when pushing/popping for worst-case O(n) complexity. However, asymptotic analysis does not the whole story tell, as it ignores the underlying constants, and in the real world, when n is small enough, the constants *do* matter. As it turns out, "small enough" in this case means a Stack created with the default initial capacity of 10 grown incrementally into one big enough to hold 500,000-1,000,000 elements. I ran the following benchmark with both versions, and the array-based Stack was ~60% faster when grown big enough to contain 100,000 elements, slightly faster for 500,000 elements, and two to three times slower for a million elements: s := nil. Smalltalk garbageCollect. [s := Stack new. 100000 timesRepeat: [s push: #foo]] timeToRun. s := nil. Smalltalk garbageCollect. [s := Stack new. 500000 timesRepeat: [s push: #foo]] timeToRun. s := nil. Smalltalk garbageCollect. [s := Stack new. 1000000 timesRepeat: [s push: #foo]] timeToRun. That means that even if you unknowingly create an enormous Stack without specifying the right size, you still come out ahead for at least the first 500,000 elements. Of course, the Array-based stack never deallocates any of its memory, which means a worst case of 2 * n memory complexity (where n is the largest number of elements a given Stack ever held). But as I said in my initial post, most Stacks are small, and when they aren't, you often have enough information to choose an appropriate size. If you really need constant time and memory complexity, which I argue is the exception, why not just use LinkedList directly with #addLast: and #removeLast to simulate a Stack as people did and still do with OrderedCollection? The rueful requirement that LinkList elements inherit from Link is gone. Stack, if it is to exist at all, should support *fast* push and pop operations. The current implementation does not. This one does, and should replace it.
On closer inspection, it appears the main reason why Stack is faster than OrderedCollection is that OrderedCollection will reallocate its Array even when #new: is supplied with what should be the correct size. To prevent reallocation, one must actually give it 1.5 times the size needed. This is because OrderedCollection keeps the first one-third of its Array empty so that #addFirst: operations will not require O(n) copying. This means that creating an OrderedCollection with new: 10 will require reallocation when the eighth element is added. If you create an OrderedCollection 50% bigger than what you expect to need, the performance gap closes to about ~7%, which isn't very significant: Smalltalk garbageCollect. r1 :=[100000 timesRepeat: [ s := Stack new: 100. 100 timesRepeat: [s push: #foo]]] timeToRun. Smalltalk garbageCollect. r2 := [100000 timesRepeat: [ oc := OrderedCollection new: 150. 100 timesRepeat: [oc addLast: #foo]]] timeToRun.
On Thu, 14 Oct 2010, Eliot Miranda wrote:
2010/10/14 jaayer <jaayer@zoho.com>
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
The original contains an error; it send min: where it should max:. This one contains the correction.
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
participants (3)
-
Eliot Miranda -
jaayer -
Levente Uzonyi