[squeak-dev] SpeedingUp parsing of LargeInteger

nicolas cellier ncellier at ifrance.com
Sun Aug 31 03:35:20 UTC 2008


Here is the idea of the speed up:

Parsing 1234 digit after digit results in evaluating:
(((1 * 10) + 2 * 10) + 3 * 10) + 4

Of course, parentheses are not needed in Smalltalk:
1 * 10 + 2 * 10 + 3 * 10 + 4

Once number of digits is large, evaluating such expressions will involve 
some slow LargeInteger arithmetic at each and every digit.

The alternative algorithm is to recursively divide the number in 2 parts 
'12' and '34', then to recompose with:
12*100 + 34

Let us suppose that a number above 100 is large (in order to avoid a 
demonstration with numbers not fitting on the page).

With 12345678, you end up constructing the number with 6 large operations
((12*100)+24)*10000 + ((56*100)+78)

8 Small operations are performed for this:
12=1*10+2
34=3*10+4
56=5*10+6
78=7*10+8
Also 3 small + 1 large operations are performed for base powering:
100 = 10 squared
100 = 10 squared
10000 = (10 squared) squared.

Note that base powers are computed several times and could be cached to 
enhance speed further.

The total is 6+1=7 large operations.
plus 8+3 small operations.

The naive algorithm:
1 * 10 + 2 * 10 + 3 * 10 + 4 * 10 + 5 * 10 + 6 * 10 + 7 * 10 + 8
uses only 14 operations (no overhead for base powering), but only first 
2 are small, 12 last are large.

I implemented both forms, the naive is used while integers are small, 
the divide&conquer is used for decomposing/recomposing large integers.

This maximizes use of SmallInteger arithmetic.

There is an overhead due to the cost of recursive method invocation 
compared to an optimized byte code loop for naive one.

Without any base power cache, i get a x3 speed factor on parsing
	SqNumberParser readFrom: 500 factorial printString.
15ms to print, 5ms to read on my 1GHz 32bits athlon (printing involves 
divisions, hence more difficult).

This does even speed up a little
	SqNumberParser readFrom: Float pi printString.
(the fractionPart is large).

I will publish in mantis or elsewhere according to your advices (see my 
previous post)




More information about the Squeak-dev mailing list