Re: [PATCH 1/4] strbuf: add strbuf_add_uint()

["René Scharfe" <l.s.r@web.de>]

On 5/13/26 6:22 PM, Jeff King wrote:
> On Tue, May 12, 2026 at 09:32:09PM +0200, René Scharfe wrote:
> 
>> The three variants were close in my tests, the no-copy variant slightly
>> winning on Apple silicon, but losing slightly more on an AMD Ryzen
>> laptop CPU.  So I went with the solid choice of using an on-stack
>> buffer, same as in printf(3) (at least on BSD).  Buffering at the end of
>> the strbuf was not really faster; perhaps memmove(3) is just that much
>> slower than memcpy(3).
> 
> I'm not sure if you did these tests initially, or if I nerd-sniped you
> into it. Either way, I am happy to be able to hear the results. ;)

Did them before I sent the series.

>> Perhaps an optimized decimal_width() could change the picture somewhat,
>> but I don't expect a big win.  On the other hand I just told you how
>> unreliable my expectations are, so there might be treasure after all. :)
> 
> I got identical times for cat-file's %(objectsize:disk) running your
> version against the one below.

Similar here (git_stack is this series, git_clz is your patch on top,
git_dec uses pager.c::decimal_width()):

Benchmark 1: ./git_stack cat-file --batch-all-objects --batch-check='%(objectsize:disk)'
  Time (mean ± σ):     383.5 ms ±   0.8 ms    [User: 374.7 ms, System: 7.6 ms]
  Range (min … max):   382.2 ms … 384.7 ms    10 runs

Benchmark 2: ./git_dec cat-file --batch-all-objects --batch-check='%(objectsize:disk)'
  Time (mean ± σ):     382.5 ms ±   1.0 ms    [User: 373.9 ms, System: 7.5 ms]
  Range (min … max):   381.2 ms … 384.7 ms    10 runs

Benchmark 3: ./git_clz cat-file --batch-all-objects --batch-check='%(objectsize:disk)'
  Time (mean ± σ):     382.5 ms ±   0.5 ms    [User: 373.7 ms, System: 7.7 ms]
  Range (min … max):   381.9 ms … 383.6 ms    10 runs

> Not wanting to figure out all of the
> off-by-one corner cases myself, I checked stack overflow for an easy
> recipe but couldn't find one. The version below was generated by
> chatgpt, which looks plausibly correct to me.
> 
> -Peff
> 
> diff --git a/strbuf.c b/strbuf.c
> index 9731ecdc1f..c26614a698 100644
> --- a/strbuf.c
> +++ b/strbuf.c
> @@ -361,16 +361,52 @@ void strbuf_addf(struct strbuf *sb, const char *fmt, ...)
>  	va_end(ap);
>  }
>  
> +static const uint64_t powers_of_10[] = {
> +    1ULL,
> +    10ULL,
> +    100ULL,
> +    1000ULL,
> +    10000ULL,
> +    100000ULL,
> +    1000000ULL,
> +    10000000ULL,
> +    100000000ULL,
> +    1000000000ULL,
> +    10000000000ULL,
> +    100000000000ULL,
> +    1000000000000ULL,
> +    10000000000000ULL,
> +    100000000000000ULL,
> +    1000000000000000ULL,
> +    10000000000000000ULL,
> +    100000000000000000ULL,
> +    1000000000000000000ULL,
> +    10000000000000000000ULL,
> +};
> +
> +unsigned decimal_length_u64(uint64_t n)
> +{
> +    if (n == 0)
> +        return 1;
> +
> +    unsigned b = 63 - __builtin_clzll(n);
> +    /* approximate floor(log10(n)) */
> +    unsigned t = (b * 1233) >> 12;
> +    /* correct if estimate was low */
> +    return t + 1 + (n >= powers_of_10[t + 1]);
> +}

Clever.  But it seems for smallish object size numbers at least dividing
by ten repeatedly is not causing a bottleneck.

René