Improve digits_to() performance
Summary:
This optimization eliminates about 75% of the multiplications and bounds
checking in the original code by using constant lookup tables to convert
from decical digit to (shifted) binary number, instead of arithmetic.
The total cost of the lookup tables is 2KB of static memory, but the
average throughput gain across the range from 1 to 19 characters is 27%.
The throughput distributes as follows: (in million iters/sec)
Bytes Orig New Speedup
1 101.31 110.12 109%
2 97.42 110.12 113%
3 97.42 105.53 108%
4 79.13 101.31 128%
5 74.48 97.42 131%
6 74.48 93.81 126%
7 70.35 93.81 133%
8 61.77 79.14 128%
9 58.9 72.35 123%
10 58.9 74.48 126%
11 56.28 74.48 132%
12 50.22 64.93 129%
13 48.52 60.3 124%
14 47.74 61.77 129%
15 46.88 61.77 132%
16 42.54 55.06 129%
17 41.51 51.69 125%
18 40.97 52.76 129%
19 39.57 52.76 133%
Test Plan: Passes all unit tests
Reviewed By: andrei.alexandrescu@fb.com
FB internal diff:
D493245