Mantis - Squeak
Viewing Issue Advanced Details
6976 Kernel minor N/A 03-10-08 22:38 04-18-10 22:04
nicolas cellier  
nicolas cellier  
normal  
closed 3.10  
fixed  
none    
none trunk  
0006976: [ENH] Speed-up SqNumberParser
Following Andreas Raab posting about Jabberwocky Qwaq improvments, I inquired ReadStream>>nextFloat which is claimed 10 times faster than Number>>readFrom:
https://lists.duke.edu/sympa/arc/croquet-dev/2007-05/msg00035.html [^]

This is true, as long as LargePositiveInteger don't mess in (in which case ).
So here is a little experiment to make SqNumberParser faster on Float crunching too.

Result is that ReadStream>>nextFloat is still 2 to 3 times faster.
But it does not answer the nearest floating point value.
Nor does it handle any odd radix printString.
It cannot be beaten, unless all SqNumberParser>>nextNumber is inlined, which is not desirable.

Thank you Andreas for doing the hard work.
Small improvments come in 4 acts:

1) inline digitValue when radix <= 10. This is the main gain.
2) Don't test 'NaN' and 'Infinity' in preamble.
   Test only in exceptional conditions (when no digit were found).
3) hack (aRadix raisedTo: exponent) with base 2 bitShift:
   and use timesTwoPower: a posteriori to avoid some LargePositiveInteger.
4) hack PositionableStream>>position:
   replace & condition by and: which is inlined by Compiler
related to 0007174closed nicolas cellier Make SqNumberParser parse LargeInteger faster 
 ReadStream_nextFloat_M6976.1.cs [^] (4,264 bytes) 03-10-08 23:09
 SqNumberParser_speedUp_M6976_nice.1.cs [^] (5,897 bytes) 03-10-08 23:16
 SqNumberParser_speedUp_Patch_M6976_nice.1.cs [^] (1,520 bytes) 08-31-08 01:15
 SqNumberParser_speedUp_Test_M6976_nice.1.cs [^] (1,420 bytes) 08-31-08 01:34

Notes
(0011913)
nicolas cellier   
03-10-08 23:22   
Unfinished sentence:
This is true, as long as LargePositiveInteger don't mess in (in which case imrpovment is masked by cost of LargeInteger arithmetic).

Some tests:

{Float pi printString.
'0.0'.
'0.0001'.
'1.2000000'.
'3.14159'.
'-3.14159'.
'314159.276'.
'3.14159e10'.
'3.14159e-10'.
'NaN'.
'-Infinity'.
} collect: [:e | e->
    {Time millisecondsToRun: [10000 timesRepeat: [e readStream nextFloat]].
    Time millisecondsToRun: [10000 timesRepeat: [SqNumberParser parse: e readStream]].
    Time millisecondsToRun: [10000 timesRepeat: [Number readFrom: e readStream]].}].

 {'3.141592653589793'->#(2388 5558 5246}.
'0.0'->#(187 476 1126}.
'0.0001'->#(228 813 1499}.
'1.2000000'->#(271 923 2129}.
'3.14159'->#(241 897 1621}.
'-3.14159'->#(242 911 1625}.
'314159.276'->#(274 962 1936}.
'3.14159e10'->#(423 911 2771}.
'3.14159e-10'->#(459 1799 4256}.
'NaN'->#(214 352 198}.
'-Infinity'->#(289 484 447)}
(0012124)
edgardec   
05-20-08 10:08   
In my Mac G5 PPC 1.6 GHz I got:
 {'3.141592653589793'->#(1275 1983 2221) . '0.0'->#(86 213 552) . '0.0001'->#(107 339 736) . '1.2000000'->#(117 368 955) . '3.14159'->#(103 380 846) . '-3.14159'->#(109 377 800) . '314159.276'->#(118 402 1120) . '3.14159e10'->#(202 454 1362) . '3.14159e-10'->#(212 783 1949) . 'NaN'->#(87 214 88) . '-Infinity'->#(122 216 192)}

I put on 3.10.1 updates
(0012167)
KenCausey   
05-25-08 22:38   
Harvested by Edgar as update 7167
(0012170)
KenCausey   
05-26-08 18:32   
Fixed in 3.10.1
(0012555)
nicolas cellier   
08-31-08 01:04   
Unfortunately, act 3) use timesTwoPower: trick didn't correctly handle gradual underflow (Ah tricky IEEE beast).

The result is that this breaks a test (SqNumberParserTest>>#testFloatPrintString): the SqNumberParser does not answer nearest Floating point value anymore but a Float one bit off for some gradual underflow Float.

self assert: (SqNumberParser readFrom: '10r1.569608368660598e-308') hex = '000B4964F562D3F1'.
Unoptimized version did it OK.
Uncorrected optimized version does answer '000B4964F562D3F2'...

I corrected SqNumberParser using,
    (m highBit - den highBit between: -1021 - (p*k) and: 1023)
instead of
    (m highBit - den highBit between: -1023 - (p*k) and: 1023)
for detecting underflow in #makeFloatFromMantissa:exponent:base:

I also refactored SqNumberParser to avoid some code duplication, and obtained more speed by using one more trick with LargeInteger arithmetic (same idea as divide and conquer for printing LargeInteger, but here it rather is compose and conquer).

This improves performance of (SqNumberParser parse: 500 factorial printString) by a factor 3, but also (SqNumberParser parse: Float pi printString) by a few percent.

I will publish, maybe in another report, that's too many changes at once.
(0012556)
nicolas cellier   
08-31-08 01:38   
"fix begin"
Installer mantis bug: 6976 fix:'ReadStream_nextFloat_M6976.1.cs'.
Installer mantis bug: 6976 fix:'SqNumberParser_speedUp_M6976_nice.1.cs'.
Installer mantis bug: 6976 fix:'SqNumberParser_speedUp_Patch_M6976_nice.1.cs'.
"fix test"
Installer mantis bug: 6976 fix:'SqNumberParser_speedUp_Test_M6976_nice.1.cs'.
"fix end"

(0012558)
nicolas cellier   
08-31-08 13:17   
The timing i reported here are not fair with Andreas' #nextFloat.

Using CharacterSetComplement instead of plain CharacterSet for noSeparatorMap did spoil efficiency of nextFloat. See 0007172 for updated timings.
(0012563)
nicolas cellier   
08-31-08 21:17   
0007174 further enhances parsing LargeInteger as announced above

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