dashu icon indicating copy to clipboard operation
dashu copied to clipboard

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

Open lemmih opened this issue 3 years ago • 1 comments

大数你好,

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]

lemmih avatar Sep 14 '22 15:09 lemmih

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

cmpute avatar Sep 14 '22 17:09 cmpute