[RFC] Faster implementation of Integer to string conversion.
Hi, several people have noted that printing integers is slow. The attached patch implements a faster version of the jtos (read: positive integer to string) function in GHC's Num library. The algorithm is a divide and conquer algorithm, that converts numbers to base b by converting them to base b^2 first, and then splitting the digits. Notes: - I've tested the speed on my computer (which has an Athlon XP processor) and it seems to be of comparable speed as the original for small numbers and way faster for big numbers (read: a few hundred or thousand digits). - The changed conversion code is a much better list producer than the original one, which generates digits starting with the last. - There's similar code in Numeric.lhs, that deals with arbitrary bases. The current patch does not deal with this. (see questions below) - musabi on #haskell mentioned that there's interest in replacing GMP as the bignum implementation. This is independent of changing this string conversion, as far as I can see. Questions: - Is this really GHC specific? - Unfortunately I see no nice way to share code between the Numeric and Num modules. Does anyone have an idea how to do this without sacrificing performance for the common base 10 case? regards, Bertram
Bertram Felgenhauer wrote:
several people have noted that printing integers is slow. The attached patch implements a faster version of the jtos (read: positive integer to string) function in GHC's Num library. The algorithm is a divide and conquer algorithm, that converts numbers to base b by converting them to base b^2 first, and then splitting the digits.
Notes: - I've tested the speed on my computer (which has an Athlon XP processor) and it seems to be of comparable speed as the original for small numbers and way faster for big numbers (read: a few hundred or thousand digits). - The changed conversion code is a much better list producer than the original one, which generates digits starting with the last. - There's similar code in Numeric.lhs, that deals with arbitrary bases. The current patch does not deal with this. (see questions below) - musabi on #haskell mentioned that there's interest in replacing GMP as the bignum implementation. This is independent of changing this string conversion, as far as I can see.
I'm tempted to commit this patch, but I want to make sure it's not a performance regression for small integers. When you say "comparable" performance, what does that mean exactly? Printing small integers is by far the most common case. Perhaps we should special-case the small integers (i.e. the S# constructor)? Cheers, Simon
Simon Marlow wrote: [snip patch description]
I'm tempted to commit this patch, but I want to make sure it's not a performance regression for small integers. When you say "comparable" performance, what does that mean exactly? Printing small integers is by far the most common case. Perhaps we should special-case the small integers (i.e. the S# constructor)?
Thank you for the reply. Here are some numbers for Athlon XP; the new version is actually slightly faster even for small numbers because it deals with small numbers as Ints, not Integers, after just two comparisons. I'll attach a tar with the relevant files to play with. The test converts some numbers to strings. The output consists of the sum of the ascii codes of all digits, and the time taken. N.jtos is the new implementation of jtos; O.jtos is the old one. up to 2 48500000 --> (N.jtos) time=176011000000 48500000 --> (O.jtos) time=176011000000 up to 16 70125000 --> (N.jtos) time=216014000000 70125000 --> (O.jtos) time=260016000000 up to 256 132677310 --> (N.jtos) time=328021000000 132677310 --> (O.jtos) time=500031000000 up to 1024 76638408 --> (N.jtos) time=176010000000 76638408 --> (O.jtos) time=284018000000 down to -16 112312500 --> (N.jtos) time=348021000000 112312500 --> (O.jtos) time=388024000000 down to -256 177501495 --> (N.jtos) time=460030000000 177501495 --> (O.jtos) time=636039000000 down to -1024 99116403 --> (N.jtos) time=244015000000 99116403 --> (O.jtos) time=352022000000 1..6 digits 150916720 --> (N.jtos) time=280018000000 150916720 --> (O.jtos) time=556034000000 6..6 digits 156750000 --> (N.jtos) time=284018000000 156750000 --> (O.jtos) time=580036000000 8..8 digits 81600000 --> (N.jtos) time=144008000000 81600000 --> (O.jtos) time=308020000000 9..9 digits 91200000 --> (N.jtos) time=156009000000 91200000 --> (O.jtos) time=348023000000 10..10 digits 103115788 --> (N.jtos) time=212013000000 103115788 --> (O.jtos) time=384024000000 11..11 digits 56828940 --> (N.jtos) time=144009000000 56828940 --> (O.jtos) time=388024000000 16..16 digits 83650000 --> (N.jtos) time=180012000000 83650000 --> (O.jtos) time=608038000000 17..17 digits 88450000 --> (N.jtos) time=192012000000 88450000 --> (O.jtos) time=648040000000 18..18 digits 93250000 --> (N.jtos) time=192012000000 93250000 --> (O.jtos) time=688044000000 19..19 digits 98050000 --> (N.jtos) time=304019000000 98050000 --> (O.jtos) time=736045000000 24..24 digits 126050000 --> (N.jtos) time=344023000000 126050000 --> (O.jtos) time=968060000000 25..25 digits 132450000 --> (N.jtos) time=352022000000 132450000 --> (O.jtos) time=996063000000 50..50 digits 132300000 --> (N.jtos) time=376023000000 132300000 --> (O.jtos) time=1108070000000 150..150 digits 158530000 --> (N.jtos) time=468029000000 158530000 --> (O.jtos) time=1764111000000 I've not tested the code on other platforms. regards, Bertram
participants (2)
-
Bertram Felgenhauer -
Simon Marlow