Hi Travis.

> > I have found this class incredibly useful for my number crunching.
> I played around with this for a while and didn't get the same results. 
> First of all baselined the 10 factorial send. I was getting values 
> (for 10000 iterations) of about 578 mills. Then I ran your code:

Ohhh... those are just examples of usage... the real benefit comes when
you want to find out the value of say 1000!... that's why I was
mentioning 3 * 2^1000 and 64! * 65. For instance, when calculating 100!,
here are the numbers I get...

i _ (1 to: 100) asArray.
Time millisecondsToRun: [CollectionProduct seqCollection: i] 15
Time millisecondsToRun: [t _ 1. i do: [:each | t _ t * each]] 46
Time millisecondsToRun: [t _ 1. 1 to: 100 do: [:each | t _ t * (i at:
each)]] 46

The results for 1000! are consistent with these figures:

i _ (1 to: 1000) asArray.
Time millisecondsToRun: [CollectionProduct seqCollection: i] 3735
Time millisecondsToRun: [t _ 1. i do: [:each | t _ t * each]] 11875
Time millisecondsToRun: [t _ 1. 1 to: 1000 do: [:each | t _ t * (i at:
each)]] 11312

> 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9

We should try with something that pushes us into the LargeIntegers.
CollectionProduct uses the argument that the multiplication function for
multiple precision integers is most efficient when squaring. If you then
assume that this function's complexity is somewhat "continuous", then
efficiency is high when multiplying numbers of similar bit size. As you
can see, it's roughly 3 times faster even for 100!. 

Where's the tie between those methods? We could try with lower
factorials such as 20!. But 20! is too fast for millisecondsToRun:. I
have built a profiler for these things. With the Profiler, we can see
what goes on throwing parenthesis:

Doing 1*2*3*...*20 takes 1ms 75mus 805ns. 

But (1*2)*(3*4)...(19*20) takes 629mus 394ns. 

And grouping those in pairs, ((1*2)*(3*4)) *... takes 407mus 226ns. 

Grouping again we obtain 385mus 253ns. 

The next and last grouping takes 411mus 926ns.

We have 3 methods. CollectionProduct, do:, and to:do: (see above).

factorial	CP		do:		  to:do:
20!		453mus 918ns	1ms 239mus 746ns  1ms 136mus 718ns 
30!		451mus 965ns	3ms 280mus 761ns  3ms 51mus 757ns 
40!		1ms 274mus 169ns 6ms 606mus 445ns 5ms 584mus 960ns 
50!		3ms 769mus 42ns 9ms 826mus 171ns  9ms 337mus 890ns 
60!		5ms 157mus 226ns 15ms 960mus 937ns 15ms 136mus 718ns 
etc...

If we replace the amount of the factorial by i size in the last one, add
more execution time. We could also make it faster by saying 1 to: n do:
[:each | t _ t * each], yet, the bulk of the execution time comes from
multiplications in the LargeIntegers.

What you have shown is that Integer>>factorial should have all
factorials cached up to somewhere. From then on, though, it should use
CollectionProduct.

Here are some numbers with low factorials:

i _ (1 to: 10) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 63mus 659ns 
Profiler measure: [t _ 1. i do: [:each | t _ t * each]] 46mus 134ns 
Profiler measure: [t _ 1. 1 to: 10 do: [:each | t _ t * each]] 19mus
248ns 

n _ 11. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 60mus 798ns 
Profiler measure: [t _ 1. i do: [:each | t _ t * each]] 53mus 520ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 21mus
816ns 

n _ 12. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 72mus 242ns 
Profiler measure: [t _ 1. i do: [:each | t _ t * each]] 60mus 554ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 23mus
662ns 

13! is in the LargeIntegers and it shows:

n _ 13. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 222mus 686ns 
Profiler measure: [t _ 1. i do: [:each | t _ t * each]] 196mus 472ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 143mus
35ns 

n _ 14. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 271mus 820ns 
Profiler measure: [t _ 1. i do: [:each | t _ t * each]] 336mus 669ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 256mus
500ns 

The second line is evidently slower than the 3rd and now it is losing
against CollectionProduct, so we drop it.

n _ 15. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 225mus 524ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 388mus
122ns 

A better grouping makes CollectionProduct start winning. Does this
happen for 16?

n _ 16. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 246mus 551ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 413mus
940ns 

n _ 17. i _ (1 to: n) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 314mus 697ns 
Profiler measure: [t _ 1. 1 to: n do: [:each | t _ t * each]] 671mus
386ns 

Ouch. It seems that from 15! and on, CollectionProduct is faster. This
is consistent with the figures we got before. The CollectionProduct
comments also includes a descendent power from 24 to 15. Let's examine
how much time does it take comparing CP and to:do:

i _ (15 to: 24) asArray.
Profiler measure: [CollectionProduct seqCollection: i] 316mus 650ns 
Profiler measure: [t _ 1. 15 to: 24 do: [:each | t _ t * each]] 401mus
550ns 

The comments also have a prime factorial like this:

i _ #(2 3 5 7 11 13 17 19 23 29).
Profiler measure: [CollectionProduct seqCollection: i] 193mus 145ns 
Profiler measure: [t _ 1. i do: [:each | t _ t * each]] 201mus 202ns 

Overall, CP is faster very soon after the result is in the
LargeIntegers.

Andres.
-------------- next part --------------
'From Squeak 2.3 of January 14, 1999 on 10 January 2000 at 10:32:42 pm'!
"Change Set:		Profiling
Date:			14 July 1999
Author:			Andres Valloud

A profiling tool. It provides nice
access to Time millisecondsToRun:
and other common practices.

It also includes a nice expression
profiler that will determine the
execution time of aBlock with
nanosecond precision.

The general usage is

	Profiler query: aBlock,

where the query is one of the
queries in the querying instance
method category in Profiler.

Enjoy!!
SqR!!
"!

Object subclass: #Profiler
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Others-Profiler'!
Profiler class
	instanceVariableNames: 'current '!

!Profiler reorganize!
('Printing' beautify:)
('Quering' evalsPerSecond: measure: msToRun: msToRun:times: quickMeasure: stopWatch: stopWatch:times: tallyBlock: tallyMeasure: tallyStopWatch:)
!


!Profiler methodsFor: 'Printing' stamp: 'SqR!!!! 7/14/1999 17:38'!
beautify: anInteger
	"Answer anInteger milliseconds in a readable fashion"

	| output add |

	anInteger < 0 ifTrue: [^('-', (self beautify: anInteger abs)) asSymbol].
	(add _ (anInteger // 86400000) printString) = '0' 
		ifTrue: [output _ String new] ifFalse: [output _ add, 'd '].
	(add _ (anInteger / 3600000 \\ 24) truncated printString) = '0' 
		ifFalse: [output _ output, add, 'h '].
	(add _ ((anInteger // 60000) \\ 60) truncated printString) = '0' 
		ifFalse: [output _ output, add, 'm '].
	(add _ (anInteger / 1000 \\ 60) truncated printString) = '0' 
		ifFalse: [output _ output, add, 's '].
	(add _ (anInteger \\ 1000) truncated printString) = '0' 
		ifFalse: [output _ output, add, 'ms '].
	(add _ (anInteger * 1000 \\ 1000) truncated printString) = '0' 
		ifFalse: [output _ output, add, 'mus '].
	(add _ (anInteger // (1 / 1000000) \\ 1000) printString) = '0' 
		ifFalse: [output _ output, add, 'ns '].
	output size == 0 ifFalse: [^output asSymbol] ifTrue: [^'0ms' asSymbol]! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!!!!!! 8/8/1998 22:22'!
evalsPerSecond: aBlock
	"Answer more or less the amount
	of evaluations of aBlock possible
	per second"

	| evals time |

	evals _ 1.
	[(time _ self msToRun: evals times: aBlock) > 1000]
		whileFalse: [evals _ evals * 2].
	^(1000 * evals / time roundTo: 0.001) asFloat! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!! 7/14/1999 17:39'!
measure: aBlock
	"Answer more or less the time required
	to evaluate aBlock"

	| evals time |

	evals _ 1.
	[(time _ self msToRun: evals times: aBlock) > 5000]
		whileFalse: [evals _ evals * 2].
	^self beautify: time / evals! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!!!!!! 8/8/1998 22:03'!
msToRun: aBlock
	"Answer how many milliseconds
	does it take to evaluate aBlock"

	^Time millisecondsToRun: aBlock! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!!!!!! 8/8/1998 22:48'!
msToRun: anInteger times: aBlock
	"Answer how many milliseconds	does it take 
	to evaluate aBlock anInteger times"

	^(Time millisecondsToRun: [1 to: anInteger do: [:each | aBlock value]]) -
		(Time millisecondsToRun: [1 to: anInteger do: [:each | ]]) max: 0! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!! 7/14/1999 17:40'!
quickMeasure: aBlock
	"Answer more or less the time required
	to evaluate aBlock. Method by Leandro 
	Caniglia"

	| eval time sum |

	eval _ 1.
	[(time _ self msToRun: eval times: aBlock) > 100] whileFalse: [eval _ eval * 2].
	sum _ time.
	sum _ (self msToRun: 2 * eval times: aBlock) + sum.
	sum _ (self msToRun: 3 * eval times: aBlock) + sum.
	^self beautify: sum * 6 / eval
! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!! 7/14/1999 17:40'!
stopWatch: aBlock
	"Answer how many milliseconds does it
	take to evaluate aBlock. Neat presentation"

	^self beautify: (self msToRun: aBlock)! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!! 7/14/1999 17:40'!
stopWatch: anInteger times: aBlock
	"Answer how many milliseconds does it take to evaluate 
	aBlock anInteger times. Neat presentation"

	^self beautify: (self msToRun: anInteger times: aBlock)! !

!Profiler methodsFor: 'Quering'!
tallyBlock: aBlock
	"Perform a message tally on aBlock"

	MessageTally spyOn: aBlock! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!! 2/26/1999 17:44'!
tallyMeasure: aBlock
	"Perform a message tally while measuring aBlock"

	| answer |

	MessageTally spyOn: [answer _ self measure: aBlock].
	^answer! !

!Profiler methodsFor: 'Quering' stamp: 'SqR!!!! 2/26/1999 22:19'!
tallyStopWatch: aBlock
	"Perform a message tally while stopWatching aBlock"

	| answer |

	MessageTally spyOn: [answer _ self stopWatch: aBlock].
	^answer! !


!Profiler class reorganize!
('Instance creation' new)
('Private' doesNotUnderstand:)
!


!Profiler class methodsFor: 'Instance creation' stamp: 'SqR!!!!!!!! 8/8/1998 22:12'!
new
	"Answer a new instance of the receiver"

	current isNil ifTrue: [current _ super new].
	^current! !

!Profiler class methodsFor: 'Private' stamp: 'SqR!!!!!!!! 8/16/1998 16:57'!
doesNotUnderstand: aMessage
	"Redirect the query? to the lone instance of the receiver"

	^self new perform: aMessage selector withArguments: aMessage arguments! !