Mantis Bugtracker
  

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID Category Severity Reproducibility Date Submitted Last Update
0006887 [Squeak] Kernel minor N/A 02-05-08 01:55 04-18-10 22:05
Reporter nicolas cellier View Status public  
Assigned To nicolas cellier
Priority normal Resolution fixed  
Status closed   Product Version 3.10
Summary 0006887: Faster printString for LargeInteger
Description 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.
Additional Information 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:
Attached Files  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

- Relationships
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: 

- Notes
(0011742 - 54 - 54 - 54 - 171 - 171 - 171)
nicolas cellier
02-05-08 02:00

Sorry for the typo, reference was 0006512 not 0001512...
 
(0011743 - 142 - 166 - 166 - 166 - 166 - 166)
nicolas cellier
02-05-08 03:05

Ah, just tested small improvement:

halfPower := halfPower asSmallerPowerOfTwo.

This makes recursion deeper but raisedToInteger: cheaper.
 
(0011744 - 571 - 993 - 993 - 993 - 993 - 993)
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 - 37 - 61 - 61 - 61 - 61 - 61)
nicolas cellier
02-05-08 03:08
edited on: 02-05-08 03:09

Oh yes, awfull.

Uploaded a .2.cs

 
(0011746 - 165 - 171 - 171 - 171 - 171 - 171)
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 - 451 - 666 - 666 - 666 - 666 - 666)
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 - 186 - 210 - 210 - 444 - 444 - 444)
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 - 163 - 207 - 207 - 207 - 207 - 207)
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 - 231 - 255 - 255 - 255 - 255 - 255)
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 - 767 - 884 - 884 - 884 - 884 - 884)
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 - 214 - 286 - 286 - 286 - 286 - 286)
nicolas cellier
02-15-08 22:05
edited on: 04-06-08 17:59

"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 - 238 - 244 - 244 - 334 - 334 - 334)
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 - 855 - 956 - 956 - 956 - 956 - 956)
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 - 212 - 272 - 272 - 272 - 272 - 272)
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 - 76 - 76 - 76 - 76 - 76 - 76)
al
07-21-08 20:48

The existing two tests named #testEmptyTemplate fail after applying the fix.
 
(0012398 - 372 - 478 - 478 - 478 - 478 - 478)
nicolas cellier
07-21-08 22:15
edited on: 07-21-08 22:30

"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 - 543 - 664 - 664 - 664 - 664 - 664)
nicolas cellier
07-21-08 22:35
edited on: 07-21-08 23:27

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 - 59 - 59 - 209 - 209 - 209 - 209)
nicolas cellier
08-24-09 20:15

Fixed in http://source.squeak.org/trunk/Kernel-nice.200.mcz [^]
 

- Issue History
Date Modified Username Field Change
02-05-08 01:55 nicolas cellier New Issue
02-05-08 02:00 nicolas cellier Note Added: 0011742
02-05-08 02:01 nicolas cellier File Added: Integer-fastPrint-experimental-M6887-nice.1.cs
02-05-08 03:03 rootbeer Issue Monitored: rootbeer
02-05-08 03:05 nicolas cellier Note Added: 0011743
02-05-08 03:05 rootbeer Note Added: 0011744
02-05-08 03:08 nicolas cellier Note Added: 0011745
02-05-08 03:09 nicolas cellier File Added: Integer-fastPrint-experimental-M6887-nice.2.cs
02-05-08 03:09 nicolas cellier Note Edited: 0011745
02-05-08 23:01 nicolas cellier File Added: Integer-fastPrint-experimental-M6887-nice.3.cs
02-05-08 23:04 nicolas cellier Note Added: 0011746
02-12-08 18:38 rootbeer Note Added: 0011766
02-12-08 19:02 nicolas cellier Note Added: 0011767
02-12-08 19:39 rootbeer Note Added: 0011768
02-12-08 21:12 nicolas cellier Note Added: 0011769
02-12-08 21:13 nicolas cellier File Added: Integer-fastPrint-experimental-M6887-nice.4.cs
02-13-08 20:14 nicolas cellier Note Added: 0011773
02-15-08 22:01 nicolas cellier File Added: Integer-fastPrint-test-M6887-nice.1.cs
02-15-08 22:02 nicolas cellier File Added: Integer-fastPrint-M6887-nice.5.cs
02-15-08 22:05 nicolas cellier Note Added: 0011811
04-06-08 17:59 nicolas cellier Note Edited: 0011811
07-04-08 01:47 matthewf Relationship added related to 0006724
07-04-08 01:50 matthewf Relationship added related to 0006512
07-04-08 01:58 matthewf Relationship added related to 0007107
07-04-08 01:58 matthewf Relationship deleted related to 0006724
07-04-08 22:40 nicolas cellier Note Added: 0012342
07-05-08 22:30 nicolas cellier Note Added: 0012343
07-05-08 22:51 nicolas cellier File Added: Integer-fastPrint-M6887-nice.6.cs
07-05-08 22:51 nicolas cellier Note Added: 0012344
07-21-08 20:48 al Note Added: 0012397
07-21-08 20:51 al Issue Monitored: al
07-21-08 22:00 nicolas cellier File Added: Integer-fastPrint-M6887-nice.7.cs
07-21-08 22:15 nicolas cellier Note Added: 0012398
07-21-08 22:15 nicolas cellier File Added: Integer-fastPrint-M6887-nice.8.cs
07-21-08 22:30 nicolas cellier File Added: Integer-fastPrint-test-M6887-nice.2.cs
07-21-08 22:30 nicolas cellier Note Edited: 0012398
07-21-08 22:35 nicolas cellier Note Added: 0012399
07-21-08 23:17 nicolas cellier File Added: Integer-fastPrint-M6887-nice.9.cs
07-21-08 23:22 nicolas cellier Note Edited: 0012399
07-21-08 23:27 nicolas cellier Note Edited: 0012399
01-10-09 02:00 Keith_Hodges Status new => pending
08-24-09 20:15 nicolas cellier Note Added: 0013278
10-03-09 20:23 nicolas cellier Status pending => resolved
10-03-09 20:23 nicolas cellier Fixed in Version  => trunk
10-03-09 20:23 nicolas cellier Resolution open => fixed
10-03-09 20:23 nicolas cellier Assigned To  => nicolas cellier
04-18-10 22:05 andreas Status resolved => closed


Mantis 1.0.8[^]
Copyright © 2000 - 2007 Mantis Group
166 total queries executed.
75 unique queries executed.
Powered by Mantis Bugtracker