Mantis Bugtracker
  

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID Category Severity Reproducibility Date Submitted Last Update
0006976 [Squeak] Kernel minor N/A 03-10-08 22:38 04-18-10 22:04
Reporter nicolas cellier View Status public  
Assigned To nicolas cellier
Priority normal Resolution fixed  
Status closed   Product Version 3.10
Summary 0006976: [ENH] Speed-up SqNumberParser
Description 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.
Additional Information 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
Attached Files  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

- Relationships
related to 0007174closed nicolas cellier Make SqNumberParser parse LargeInteger faster 

- Notes
(0011913 - 925 - 1221 - 1221 - 1221 - 1221 - 1221)
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 - 387 - 443 - 443 - 443 - 443 - 443)
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 - 33 - 33 - 33 - 33 - 33 - 33)
KenCausey
05-25-08 22:38

Harvested by Edgar as update 7167
 
(0012170 - 15 - 15 - 15 - 15 - 15 - 15)
KenCausey
05-26-08 18:32

Fixed in 3.10.1
 
(0012555 - 1262 - 1416 - 1416 - 1416 - 1416 - 1416)
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 - 336 - 414 - 414 - 414 - 414 - 414)
nicolas cellier
08-31-08 01:38
edited on: 07-25-09 21:18

"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 - 212 - 224 - 224 - 331 - 331 - 331)
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 - 64 - 76 - 76 - 172 - 172 - 172)
nicolas cellier
08-31-08 21:17
edited on: 08-31-08 21:17

0007174 further enhances parsing LargeInteger as announced above

 
(0013280 - 59 - 59 - 209 - 209 - 209 - 209)
nicolas cellier
08-24-09 20:19

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

- Issue History
Date Modified Username Field Change
03-10-08 22:38 nicolas cellier New Issue
03-10-08 23:09 nicolas cellier File Added: ReadStream_nextFloat_M6976.1.cs
03-10-08 23:16 nicolas cellier File Added: SqNumberParser_speedUp_M6976_nice.1.cs
03-10-08 23:22 nicolas cellier Note Added: 0011913
05-20-08 10:08 edgardec Note Added: 0012124
05-25-08 22:38 KenCausey Status new => resolved
05-25-08 22:38 KenCausey Fixed in Version  => 3.10
05-25-08 22:38 KenCausey Resolution open => fixed
05-25-08 22:38 KenCausey Assigned To  => KenCausey
05-25-08 22:38 KenCausey Note Added: 0012167
05-26-08 18:32 KenCausey Status resolved => closed
05-26-08 18:32 KenCausey Note Added: 0012170
08-31-08 01:04 nicolas cellier Status closed => feedback
08-31-08 01:04 nicolas cellier Resolution fixed => reopened
08-31-08 01:04 nicolas cellier Note Added: 0012555
08-31-08 01:15 nicolas cellier File Added: SqNumberParser_speedUp_Patch_M6976_nice.1.cs
08-31-08 01:34 nicolas cellier File Added: SqNumberParser_speedUp_Test_M6976_nice.1.cs
08-31-08 01:38 nicolas cellier Note Added: 0012556
08-31-08 13:17 nicolas cellier Note Added: 0012558
08-31-08 21:17 nicolas cellier Note Added: 0012563
08-31-08 21:17 nicolas cellier Note Edited: 0012563
01-10-09 02:13 Keith_Hodges Status feedback => pending
07-25-09 21:10 nicolas cellier Note Edited: 0012556
07-25-09 21:18 nicolas cellier Note Edited: 0012556
08-24-09 20:19 nicolas cellier Note Added: 0013280
10-03-09 20:21 nicolas cellier Relationship added related to 0007174
10-03-09 20:22 nicolas cellier Status pending => resolved
10-03-09 20:22 nicolas cellier Fixed in Version 3.10 => trunk
10-03-09 20:22 nicolas cellier Resolution reopened => fixed
10-04-09 17:14 KenCausey Assigned To KenCausey => nicolas cellier
04-18-10 22:04 andreas Status resolved => closed


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