"{ Package: 'stx:goodies/regression/benchmarks' }"

Object subclass:#CollectionBenchmarks

	instanceVariableNames:''

	classVariableNames:''

	poolDictionaries:''

	category:'benchmarks-Collections'

!

!CollectionBenchmarks class methodsFor:'standalone run'!

main

    "to run from the commandline, type

	stx -I --load CollectionBenchmarks.st --run CollectionBenchmarks

    "

    self collectionTimings

! !

!CollectionBenchmarks class methodsFor:'sorted collections'!

collectionTimings

    |N randomNumbers|

    N := 100000.

    randomNumbers := (1 to:N) collect:[:i | Random nextInteger].

    ObjectMemory garbageCollect.

    #(SortedCollection AATree BinaryTree) do:[:className |

	|class doBench coll t seq|

	class := Smalltalk classNamed:className.

	doBench := [:class |

		|coll t|

		t := Time millisecondsToRun:[

		    coll := class new.

		    randomNumbers do:[:each | coll add:each]

		].

		Transcript show:'Time to insert random '; show:N; show:' individually into ',class name,': '; show:t; showCR:'ms'.

		coll

	    ].

	ObjectMemory garbageCollect.

	doBench value:class.

	ObjectMemory garbageCollect.

	doBench := [:class |

		|coll t|

		t := Time millisecondsToRun:[

		    coll := class new.

		    coll addAll:randomNumbers

		].

		Transcript show:'Time to insert random '; show:N; show:' en-bloque into ',class name,': '; show:t; showCR:'ms'.

		coll

	    ].

	ObjectMemory garbageCollect.

	doBench value:class.

	ObjectMemory garbageCollect.

	doBench := [:class |

		|coll t|

		t := Time millisecondsToRun:[

		    coll := class new.

		    (1 to:N) do:[:each | coll add:each].

		].

		Transcript show:'Time to insert in order '; show:N; show:' individually into ',class name,': '; show:t; showCR:'ms'.

		coll

	    ].

	ObjectMemory garbageCollect.

	doBench value:class.

	ObjectMemory garbageCollect.

	doBench := [:class |

		|coll t|

		t := Time millisecondsToRun:[

		    coll := class new.

		    coll addAll:(1 to:N).

		].

		Transcript show:'Time to insert in order '; show:N; show:' en-bloque into ',class name,': '; show:t; showCR:'ms'.

		coll

	    ].

	ObjectMemory garbageCollect.

	doBench value:class.

	ObjectMemory garbageCollect.

	doBench := [:class |

		|coll t|

		t := Time millisecondsToRun:[

		    coll := class new.

		    (N downTo:1) do:[:each | coll add:each].

		].

		Transcript show:'Time to insert in reverse order '; show:N; show:' individually into ',class name,': '; show:t; showCR:'ms'.

		coll

	    ].

	ObjectMemory garbageCollect.

	doBench value:class.

	ObjectMemory garbageCollect.

	doBench := [:class |

		|coll t|

		t := Time millisecondsToRun:[

		    coll := class new.

		    coll addAll:(N downTo:1).

		].

		Transcript show:'Time to insert in reverse order '; show:N; show:' en-bloque into ',class name,': '; show:t; showCR:'ms'.

		coll

	    ].

	ObjectMemory garbageCollect.

	doBench value:class.

	ObjectMemory garbageCollect.

	coll := class new.

	coll addAll:randomNumbers.

	t := Time millisecondsToRun:[

	    coll removeAll:randomNumbers.

	].

	Transcript show:'Time to remove in random order '; show:N; show:' from ',class name,': '; show:t; showCR:'ms'.

	self assert:(coll isEmpty).

	ObjectMemory garbageCollect.

	coll := class new.

	coll addAll:randomNumbers.

	seq := randomNumbers copy sort.

	t := Time millisecondsToRun:[

	    coll removeAll:seq.

	].

	Transcript show:'Time to remove in order '; show:N; show:' from ',class name,': '; show:t; showCR:'ms'.

	self assert:(coll isEmpty).

	ObjectMemory garbageCollect.

	coll := class new.

	coll addAll:randomNumbers.

	seq := randomNumbers copy sort reverse.

	t := Time millisecondsToRun:[

	    coll removeAll:seq.

	].

	Transcript show:'Time to remove in reverse order '; show:N; show:' from ',class name,': '; show:t; showCR:'ms'.

	self assert:(coll isEmpty).

	ObjectMemory garbageCollect.

	Transcript cr.

    ].

!

documentation

"

    Time to insert random 100000 individually into SortedCollection: 6037ms

    Time to insert random 100000 en-bloque into SortedCollection: 172ms

    Time to insert in order 100000 individually into SortedCollection: 31ms

    Time to insert in order 100000 en-bloque into SortedCollection: 125ms

    Time to insert in reverse order 100000 individually into SortedCollection: 93ms

    Time to insert in reverse order 100000 en-bloque into SortedCollection: 125ms

    Time to remove in random order 100000 from SortedCollection: 6380ms

    Time to remove in order 100000 from SortedCollection: 109ms

    Time to remove in reverse order 100000 from SortedCollection: 125ms

    Time to insert random 100000 individually into AATree: 281ms

    Time to insert random 100000 en-bloque into AATree: 265ms

    Time to insert in order 100000 individually into AATree: 281ms

    Time to insert in order 100000 en-bloque into AATree: 328ms

    Time to insert in reverse order 100000 individually into AATree: 203ms

    Time to insert in reverse order 100000 en-bloque into AATree: 218ms

    Time to remove in random order 100000 from AATree: 452ms

    Time to remove in order 100000 from AATree: 312ms

    Time to remove in reverse order 100000 from AATree: 499ms

    Time to insert random 100000 individually into BinaryTree: 156ms

    Time to insert random 100000 en-bloque into BinaryTree: 156ms

    Time to insert in order 100000 individually into BinaryTree: 195921ms

    Time to insert in order 100000 en-bloque into BinaryTree: 205266ms

    Time to insert in reverse order 100000 individually into BinaryTree: 202271ms

    Time to insert in reverse order 100000 en-bloque into BinaryTree: 197684ms

    Time to remove in random order 100000 from BinaryTree: 234ms

    Time to remove in order 100000 from BinaryTree: 78ms

    Time to remove in reverse order 100000 from BinaryTree: 78ms

  on a 2010 powerbook (2.1Ghz 86_64)

    Time to insert random 100000 individually into SortedCollection: 1390ms

    Time to insert random 100000 en-bloque into SortedCollection: 50ms

    Time to insert in order 100000 individually into SortedCollection: 20ms

    Time to insert in order 100000 en-bloque into SortedCollection: 20ms

    Time to insert in reverse order 100000 individually into SortedCollection: 40ms

    Time to insert in reverse order 100000 en-bloque into SortedCollection: 40ms

    Time to remove in random order 100000 from SortedCollection: 1370ms

    Time to remove in order 100000 from SortedCollection: 40ms

    Time to remove in reverse order 100000 from SortedCollection: 40ms

    Time to insert random 100000 individually into AATree: 170ms

    Time to insert random 100000 en-bloque into AATree: 170ms

    Time to insert in order 100000 individually into AATree: 170ms

    Time to insert in order 100000 en-bloque into AATree: 150ms

    Time to insert in reverse order 100000 individually into AATree: 130ms

    Time to insert in reverse order 100000 en-bloque into AATree: 120ms

    Time to remove in random order 100000 from AATree: 310ms

    Time to remove in order 100000 from AATree: 200ms

    Time to remove in reverse order 100000 from AATree: 260ms

    Time to insert random 100000 individually into BinaryTree: 110ms

    Time to insert random 100000 en-bloque into BinaryTree: 100ms

    Time to insert in order 100000 individually into BinaryTree: 77260ms

    Time to insert in order 100000 en-bloque into BinaryTree: 78420ms

    Time to insert in reverse order 100000 individually into BinaryTree: 78830ms

    Time to insert in reverse order 100000 en-bloque into BinaryTree: 79020ms

    Time to remove in random order 100000 from BinaryTree: 160ms

    Time to remove in order 100000 from BinaryTree: 50ms

    Time to remove in reverse order 100000 from BinaryTree: 40ms

"

!

test_Btree

    |coll sc randomNumbers|

    randomNumbers := (1 to:1000) collect:[:i |Random nextInteger].

    sc := SortedCollection new.

    sc addAll:randomNumbers.

    coll := BinaryTree new.

    coll addAll:randomNumbers.

    randomNumbers do:[:each |

"/        Transcript showCR:'-----------'.

"/        Transcript showCR:(coll instVarNamed:'treeRoot').

"/        Transcript showCR:each.

	coll remove:each.

	sc remove:each.

	self assert:(sc asOrderedCollection = coll asOrderedCollection).

    ].

! !

!CollectionBenchmarks class methodsFor:'documentation'!

version

    ^ '$Header$'

! !