Re: GCC Optimisation status update

[<zoltan at bendor dot com dot au>]

> We are working on a patch which will improve decimal
> itoa by up to 10X.  It will take a while to finish it.

What's the method?

I have a function converting 32 bit unsigneds to decimal which costs one
32x32->64 multiply with a constant (a single constant, not a look-up
table) plus a max. 8-times loop involving a few 64-bit adds and shifts,
which can be unrolled for speed (there's very little in the loop body,
really). There's also an initial overhead of up to three 32-bit compare
and subtracts.

The 64 bit unsigned to decimal conversion costs two calls to the above
routine, three 32x32->64 multiplies and a few preparation steps, which
are simple 64-bit add/sub things.

The routines are used on 32-bit ARM chips where multiply is dirt cheap;
for chips with no 32x32->64 multiply they might not be feasible. The
routines are also quite simple. Would they be useful for you, they've been
released under the GPL (with an additional relaxational clause, but that's
irrelevant here). I don't know if the method is well-known already, casual
search on the Net did not find binary to decimal conversion using the
above technique at the time when I came up with it (couple of years ago),
so it may not be that widespread.

I also have routines to convert 32 and 64 bit numbers to arbitrary base
without using division but again, they are heavily reliant on the cheap
32x32->64 multiply and cheap 64-bit shifts.

Zoltan