[RFC] Faster implementation of Integer to string conversion.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[RFC] Faster implementation of Integer to string conversion.

Bertram Felgenhauer-2
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

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

jtos.patch (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [RFC] Faster implementation of Integer to string conversion.

Simon Marlow-5
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
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [RFC] Faster implementation of Integer to string conversion.

Bertram Felgenhauer-2
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

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

jtos.tar.gz (3K) Download Attachment