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