cmpute / dashu

A library set of arbitrary precision numbers implemented in Rust.
Apache License 2.0
76 stars 9 forks source link

Increase throughput of power-of-two formatting by 50% #3

Open lemmih opened 2 years ago

lemmih commented 2 years ago

大数你好,

This change cuts the formatting time by a lot for large numbers when using a power-of-two radix. It's kinda ugly, though, so I'll try to find a better solution (hence the draft PR).

Before changes (M1 laptop):

to_hex/10               time:   [33.275 ns 33.313 ns 33.352 ns]
to_hex/100              time:   [52.407 ns 52.420 ns 52.436 ns]
to_hex/1000             time:   [897.85 ns 898.29 ns 898.71 ns]
to_hex/10000            time:   [8.6174 µs 8.6212 µs 8.6251 µs]
to_hex/100000           time:   [87.335 µs 87.525 µs 87.734 µs]
to_hex/1000000          time:   [885.83 µs 888.31 µs 891.29 µs]

After changes (M1 laptop):

to_hex/10               time:   [34.188 ns 34.252 ns 34.327 ns]
to_hex/100              time:   [52.624 ns 52.712 ns 52.818 ns]
to_hex/1000             time:   [605.80 ns 606.76 ns 607.62 ns]
to_hex/10000            time:   [5.6921 µs 5.7106 µs 5.7276 µs]
to_hex/100000           time:   [56.945 µs 56.957 µs 56.972 µs]
to_hex/1000000          time:   [599.15 µs 600.49 µs 601.99 µs]

Before changes (AMD desktop):

to_hex/10               time:   [44.258 ns 44.499 ns 44.770 ns]
to_hex/100              time:   [84.682 ns 85.002 ns 85.384 ns]
to_hex/1000             time:   [1.1311 µs 1.1357 µs 1.1410 µs]
to_hex/10000            time:   [10.785 µs 10.801 µs 10.819 µs]
to_hex/100000           time:   [106.89 µs 107.40 µs 107.84 µs]
to_hex/1000000          time:   [1.0991 ms 1.1015 ms 1.1035 ms]

After changes (AMD desktop):

to_hex/10               time:   [44.228 ns 44.281 ns 44.341 ns]
to_hex/100              time:   [91.382 ns 91.680 ns 91.848 ns]
to_hex/1000             time:   [374.47 ns 379.29 ns 384.40 ns]
to_hex/10000            time:   [3.8300 µs 3.9665 µs 4.1346 µs]
to_hex/100000           time:   [40.404 µs 42.612 µs 44.522 µs]
to_hex/1000000          time:   [392.89 µs 419.29 µs 449.91 µs]
cmpute commented 2 years ago

wow, thanks for putting effort into this so quickly! Glad to see this!