Improve digits_to() performance
authorEitan Frachtenberg <efrach@fb.com>
Wed, 13 Jun 2012 00:07:02 +0000 (17:07 -0700)
committerTudor Bosman <tudorb@fb.com>
Fri, 13 Jul 2012 23:28:16 +0000 (16:28 -0700)
commitb384b6bc5ca309c6dfb814ddfd62da745f667806
tree6fed346c063f47bb2904643583f15396db3f2f3b
parent2a4a4178b6b25d8633143361686fa283655a53f7
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
folly/Conv.h