Mantis - Squeak
Viewing Issue Advanced Details
6887 Kernel minor N/A 02-05-08 01:55 04-18-10 22:05
nicolas cellier  
nicolas cellier  
normal  
closed 3.10  
fixed  
none    
none trunk  
0006887: Faster printString for LargeInteger
Following 0001512 enhance printString speed for LargeInteger this time, and for each and every radix (also for SmallInteger).

I provide changes with all methods prefixed nice (my initials) so that you can test against current implementation. And so that you can load without breaking anything.

| x |
x := 100 factorial.
{Time millisecondsToRun: [100 timesRepeat: [x printString]].
Time millisecondsToRun: [100 timesRepeat: [x niceprintString]].}

roughly improves by a factor 4.
Most time is wasted in LargeInteger operations #quo: #- #* which also trigger the garbage collector more than necessary.

In order to fall back as soon as possible to fast SmallInteger arithmetic, the strategy is to split LargeIntegers in two halves head and tail, recursively.

With n digits, this reduces number of LargeInteger ops from n to (n log: 2).

A serie of (base raisedTo: n//2) however increases the cost (it is computed much too often).
SmallInteger implementation is based on goran's: allocating a (String new: nDigits) is less expensive than a (base raisedToInteger: nDigits) and nDigits additional #quo:
related to 0006512closed  Much faster printString (and thus also asString) for SmallIntegers 
related to 0007107closed nicolas cellier 1 printStringBase: 1 generates an infinite loop within Integer>>printStringBase: 
 Integer-fastPrint-experimental-M6887-nice.1.cs [^] (5,674 bytes) 02-05-08 02:01
 Integer-fastPrint-experimental-M6887-nice.2.cs [^] (5,717 bytes) 02-05-08 03:09
 Integer-fastPrint-experimental-M6887-nice.3.cs [^] (6,535 bytes) 02-05-08 23:01
 Integer-fastPrint-experimental-M6887-nice.4.cs [^] (6,547 bytes) 02-12-08 21:13
 Integer-fastPrint-test-M6887-nice.1.cs [^] (1,613 bytes) 02-15-08 22:01
 Integer-fastPrint-M6887-nice.5.cs [^] (6,043 bytes) 02-15-08 22:02
 Integer-fastPrint-M6887-nice.6.cs [^] (7,280 bytes) 07-05-08 22:51
 Integer-fastPrint-M6887-nice.7.cs [^] (7,396 bytes) 07-21-08 22:00
 Integer-fastPrint-M6887-nice.8.cs [^] (7,452 bytes) 07-21-08 22:15
 Integer-fastPrint-test-M6887-nice.2.cs [^] (2,587 bytes) 07-21-08 22:30
 Integer-fastPrint-M6887-nice.9.cs [^] (7,634 bytes) 07-21-08 23:17

Notes
(0011742)
nicolas cellier   
02-05-08 02:00   
Sorry for the typo, reference was 0006512 not 0001512...
(0011743)
nicolas cellier   
02-05-08 03:05   
Ah, just tested small improvement:

halfPower := halfPower asSmallerPowerOfTwo.

This makes recursion deeper but raisedToInteger: cheaper.
(0011744)
rootbeer   
02-05-08 03:05   
The attached change set (M6887-nice.1) seems buggy. For example, this method uses the constant base 10 instead of the parameter b:

SmallInteger>>niceprintStringBase: b nDigits: n
    "Return a string representation of this number in base b with n digits (left padded with 0).
    should be invoked with: 0 <= self < (b raisedToInteger: n)"
    
    | integer next result |
    result := String new: n.
    integer := self.
    n to: 1 by: -1 do: [:i |
        next := integer // 10.
        result byteAt: i put: (Character digitValue: (integer - (next * 10))).
        integer := next].
    ^result
(0011745)
nicolas cellier   
02-05-08 03:08   
Oh yes, awfull.

Uploaded a .2.cs

(0011746)
nicolas cellier   
02-05-08 23:04   
Corrected one more bug in .3.cs when base isPowerOfTwo and added general utility Integer>>#numberOfDigitsInBase: that should perform fast with a few quo: operations.
(0011766)
rootbeer   
02-12-08 18:38   
This method, from the "nice.3" change set, sends the message #decimalDigitLength, which doesn't seem to be implemented anywhere.

SmallInteger>>numberOfDigitsInBase: b
    "Return how many digits are necessary to print this number in base b.
    Mostly same as super but an optimized version for base 10 case."
    
    b = 10 ifFalse: [^super numberOfDigitsInBase: b].
    self < 0 ifTrue: [^self negated numberOfDigitsInBase: b].
    ^self decimalDigitLength
(0011767)
nicolas cellier   
02-12-08 19:02   
Yes, you are right, it is available at 0006512 ...

And 0006512 is already loaded in latest 3.10 images.

I will add a prerequisite: instruction for Installer script when package tested.
(0011768)
rootbeer   
02-12-08 19:39   
I can't get this to work right yet. I get four leading zeroes here:

    (3 raisedTo: 28) niceprintStringBase: 3

It gives '000010000000000000000000000000000'.
(0011769)
nicolas cellier   
02-12-08 21:12   
Ah thank you very much for your interest.

The rough estimate used as halfPower was wrong. I picked the one from numberOfDigitsInBase: that works well (did a few tests on the latter, not the former).

So i upload version nice.4
(0011773)
nicolas cellier   
02-13-08 20:14   
I add a little explanation of rough under-estimate number of digits necessary to print a in base b:

a >= (2 raisedTo: a highBit - 1).
(2 raisedTo: b highBit) > b.
p1 := a highBit - 1 quo: b highBit.
p1 * b highBit <= a highBit - 1.
p2 := (a highBit quo: b hightBit) - 1.
p2 <= p1.

Thus:
a >= (2 raisedTo: a highBit - 1).
(2 raisedTo: a highBit - 1) >= (2 raisedTo: b highBit * p2).
(2 raisedTo: b highBit * p2) > (b raisedTo: p2).

Thus p2 provides an under-estimate of number of digits necessary to print a in base b.

Taking p2 asSmallerPowerOfTwo is more efficient than (p2 quo: 2) for splitting number of digits in two parts, because of (b raisedToInteger: p2) cost. Thus you get the explanation for the contents of halfPower temporary variable.
(0011811)
nicolas cellier   
02-15-08 22:05   
"fix begin"
Installer mantis ensureFix: 6512.
Installer mantis bug: 6887 fix:'Integer-fastPrint-M6887-nice.5.cs'.
"fix test"
Installer mantis bug: 6887 fix:'Integer-fastPrint-test-M6887-nice.1.cs'.
"fix end"

(0012342)
nicolas cellier   
07-04-08 22:40   
(100000000000 printStringBase: 123456789) will result in an infinite loop...
This would not happen with reasonable bases, but I would rather prefer it failing than looping! would trigger another MethodFinder infinite loop... (see 0006710 )
(0012343)
nicolas cellier   
07-05-08 22:30   
OK,i will upload new implementation.
I added tests on number of digits to avoid infinite loop in case of huge base.
I let Character digitValue: fail because i do not want to hardcode any arbitrary limit on base. I think today's limit is 36, but it could be extended.
I tested that preallocating stream space with exact numberOfDigitsInBase: did not speed up printString, even with exact power of two split trick.
So i let the simple one.
LargePositiveInteger>>printStringBase: base
    ^String streamContents: [:str | self printOn: str base: base]

It could be removed if Integer>>printStringBase: is removed, but i do not trust.

I programmed the split better to be the smaller power of two under half of number of digits under estimate, and gained a few % efficiency.
I think code is now more expressive with better temporary names and comments.
(0012344)
nicolas cellier   
07-05-08 22:51   
"fix begin"
Installer mantis ensureFix: 6512.
Installer mantis bug: 6887 fix:'Integer-fastPrint-M6887-nice.6.cs'.
"fix test"
Installer mantis bug: 6887 fix:'Integer-fastPrint-test-M6887-nice.1.cs'.
"fix end"
(0012397)
al   
07-21-08 20:48   
The existing two tests named #testEmptyTemplate fail after applying the fix.
(0012398)
nicolas cellier   
07-21-08 22:15   
"Thanks, I did not care of that feature.
.7.cs would pass the two tests, but would fail some crafted ones.
I upload a .8.cs to handle any weird case..."

"fix begin"
Installer mantis ensureFix: 6512.
Installer mantis bug: 6887 fix:'Integer-fastPrint-M6887-nice.8.cs'.
"fix test"
Installer mantis bug: 6887 fix:'Integer-fastPrint-test-M6887-nice.2.cs'.
"fix end"

(0012399)
nicolas cellier   
07-21-08 22:35   
Version .8.cs inlines test below, while 9.cs use a more expressive:
LargePositiveInteger>>isNormalized
    ^self digitLength > 0 and: [self lastDigit ~= 0]

Though it does not handle normalization to SmallInteger...

Note that the test will be called many times (self numberOfDigits log: 2). Could be optimized sending a self normalizedPrintOn:base: once asserted true...

While at it, check current implementation against:
    LargePositiveIntegerTest new testDenormalizedPrintString.
from 'Integer-fastPrint-test-M6887-nice.2.cs'

(0013278)
nicolas cellier   
08-24-09 20:15   
Fixed in http://source.squeak.org/trunk/Kernel-nice.200.mcz [^]