[PATCH 0/1] vsprintf: optimize decimal conversion (again)

[Denys Vlasenko <vda.linux@googlemail.com>]

[-- Attachment #1: Type: text/plain, Size: 1842 bytes --]

Hi Andrew,

Can you take this patch into -mm?

Michal, Jones - can you review the code?

Sometime ago, Michal Nazarewicz <mina86@mina86.com> optimized our
(already fast) decimal-to-string conversion even further.
Somehow this effort did not reach the kernel.

Here is a new iteration of his code.

Optimizations and patch follow in next email.

Please find test programs attached.

32-bit test programs were built using gcc 4.6.2
64-bit test programs were built using gcc 4.2.1
Command line: gcc --static [-m32] -O2 -Wall test_{org,new}.c

Sizes:
org32.o: 2850 bytes
new32.o: 2858 bytes
org64.o: 2155 bytes
new64.o: 2283 bytes

Correctness: I tested first and last 40 billion values from [0, 2^64-1] range,
they all produced correct result.

Speed:
I measured how many thousands of conversions per second are done, for several values
(it takes different amount of time to convert, say, 123 and 2^64-1 to their
string representations).
Format of data below: VALUE:THOUSANDS_OF_CONVS_PER_SEC.

Intel Core i7 2.7GHz:
org32: 8:46852 123:39252 123456:23992 12345678:21992 123456789:21048 2^32-1:20424 2^64-1:10216
new32: 8:55300 123:43208 123456:34456 12345678:31272 123456789:23584 2^32-1:23568 2^64-1:16720

AMD Phenom II X4 2.4GHz:
org32: 8:29244 123:23988 123456:13792 12345678:12056 123456789:11368 2^32-1:10804 2^64-1:5224
new32: 8:38040 123:30356 123456:22832 12345678:20676 123456789:13556 2^32-1:13472 2^64-1:9228

org64: 8:38664 123:29256 123456:19188 12345678:16320 123456789:15380 2^32-1:14896 2^64-1:7864
new64: 8:42664 123:31660 123456:21632 12345678:19220 123456789:20880 2^32-1:17580 2^64-1:9596

Summary: in all cases new code is faster than old one, in many cases by 30%,
in few cases by more than 50% (for example, on x86-32, conversion of num=12345678).
Code growth is ~0 in 32-bit case and ~130 bytes in 64-bit case.

-- 
vda

[-- Attachment #2: test_dec_conversion.tar.gz --]
[-- Type: application/x-tgz, Size: 5949 bytes --]