[m-rev.] for review: speed up uint32 to string conversion

[Zoltan Somogyi]

On Wed, 27 Oct 2021 19:53:11 +1100 (AEDT), Julien Fischer <jfischer at opturion.com> wrote:
> (Mind you, the main result of my original benchmarking is still
> perfectly valid: dont use sprintf()!)

I agree.

> >> +% XXX TODO: try table driven approaches.
> >
> > Alternatives 1 and 2 *are* table driven approaches,
> > though the table has only ten entries :-( But I presume
> > you mean approaches in which you index U into a table,
> > with or without having reduced its range.
> 
> No, that's not what I meant. I was principally referring to the
> technqiues for computing the number decimal digits, discussed in the
> following blog post
> 
> <https://lemire.me/blog/2021/05/28/computing-the-number-of-digits-of-an-integer-quickly/>

The methods discussed there look worth exploring.

> > I would also propose a3, which would be not a *sequence* of
> > if-then-elses, but a *tree* of if-then-else, that performs a
> > binary search on num_digits. There could be several versions
> > of this: one whose top level test is for num_digits being
> > above 5, one for below 4, one for below 3 etc. The latter
> > should perform better on workloads dominated by small
> > numbers.
> >
> > We can also extend a1 by indexing not into a ten-element
> > table of chars, but into a 100-element table of char pairs,
> > 1000-element table of char triples, etc. I don't think these
> > are likely to have any advantage over existing alternatives,
> > but if you want to be sure, you could try them.
> 
> ... both of those suggestions are mentioned in the post from
> Facebook engineering I linked to.  I intend to try them out

On all my machines, facebook.com and related domains are
all intentionally unreachable. I don't intend to undo the block
just to look at a blog post.
 
> That said, I think the immediate concern should be to replace calls to
> sprintf() where possible.

Agreed, but it should be done in two phases. First, find the best replacement,
and then, roll it out to all related conversion functions, not just
the one for uint32s. The best approach *may* differ between e.g.
uintN for different N, but probably not by much.

Zoltan.