lkml.org 
[lkml]   [2015]   [Mar]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v1] lib/vsprintf.c: Even faster decimal conversion
On Wed, 11 Mar 2015 00:01:11 +0100 Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> The most expensive part of decimal conversion is the divisions by 10
> (albeit done using reciprocal multiplication with appropriately chosen
> constants). I decided to see if one could eliminate around half of
> these multiplications by emitting two digits at a time, at the cost of
> a 200 byte lookup table, and it does indeed seem like there is
> something to be gained, especially on 64 bits. Microbenchmarking shows
> improvements ranging from -50% (for numbers uniformly distributed in
> [0, 2^64-1]) to -25% (for numbers heavily biased toward the smaller
> end, a more realistic distribution).
>
> On a larger scale, perf shows that top, one of the big consumers of
> /proc data, uses 0.5-1.0% fewer cpu cycles.
>
> I had to jump through some hoops to get the 32 bit code to compile and
> run on my 64 bit machine, so I'm not sure how relevant these numbers
> are, but just for comparison the microbenchmark showed improvements
> between -30% and -10%.
>
> The bloat-o-meter costs are around 150 bytes (the generated code is a
> little smaller, so it's not the full 200 bytes) on both 32 and 64
> bit. I'm aware that extra cache misses won't show up in a
> microbenchmark as used above, but on the other hand decimal
> conversions often happen in bulk (for example in the case of top).
>
> I have of course tested that the new code generates the same output as
> the old, for both the first and last 1e10 numbers in [0,2^64-1] and
> 4e9 'random' numbers in-between.
>
> ...
>
> Test and verification code on github
> <https://github.com/Villemoes/dec>. It would be nice if someone could
> verify the code on architectures other than x86 - in particular, I
> believe it _should_ work on big-endian, but I have no way of testing
> that. Benchmark numbers would be nice too, of course.

That would be nice.

It would be best to make this as easy as possible for people. Create a
tarball, attach that to a request sent to linuxppc-dev@lists.ozlabs.org
along with simple instructions along the lines of

tar xfz tarball.tar.gz
cd ./dec
make
./whatever

and magic might happen!


\
 
 \ /
  Last update: 2015-03-11 23:01    [W:2.158 / U:0.004 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site