decimal conversion: digits10 using bit-counting instructions on x86-64
Summary: To estimate length of a number's base-10 length in digits, use insn `bsrq` (Bit Scan Reverse) to count significant bits. From that, approximate base-10 length. Tries to avoid branchiness, expensive math, and loops.
Test Plan:
1) Tested correctness by comparing results with `snprintf` and ensuring same string lengths. Tested at each boundary condition (2^k)-1, 2^k, (2^k+1); and similar for base 10.
2) Benchmarked with gcc 4.9 and clang 3.5.
Before/after values are millions operations / sec
GCC 4.9 Clang 3.5
1 111.09 111.7 1.005 1 115.36 393.81 3.414
2 115.36 111.7 0.968 2 115.36 393.89 3.414
3 114.91 111.34 0.969 3 111.09 393.56 3.543
4 114.91 111.34 0.969 4 111.09 393.86 3.545
5 115.36 111.36 0.965 5 111.09 392.18 3.530
6 99.99 104.32 1.043 6 103.43 393.74 3.807
7 83.31 84.71 1.017 7 81.06 268.39 3.311
8 76.9 78.23 1.017 8 76.91 268.26 3.488
9 62.48 68.26 1.093 9 65.56 190 2.898
10 59.98 63.65 1.061 10 61.17 190.54 3.115
11 50.6 55.87 1.104 11 54.54 148.03 2.714
12 47.19 51.7 1.096 12 50.84 148.57 2.922
13 40.53 46.99 1.159 13 43.33 115.91 2.675
14 40.48 43.42 1.073 14 41.5 115.97 2.794
15 34.92 40.21 1.151 15 37.27 94.89 2.546
16 33.49 37.51 1.120 16 35.77 94.88 2.653
17 29.89 35.02 1.172 17 31.7 80.67 2.545
18 29.11 32.98 1.133 18 30.76 80.63 2.621
19 26.58 31.05 1.168 19 28.22 70.15 2.486
20 25.64 29.38 1.146 20 27.96 70.16 2.509
Reviewed By: ldbrandy@fb.com
Subscribers: dancol, trunkagent, marcelo, chalfant, maoy, folly-diffs@, yzhan, yfeldblum
FB internal diff:
D1934777
Signature: t1:
1934777:
1433523486:
3acbe7ed9c9560c44194f854754529041eaa289d
projects / folly.git / commit