Re: [PATCH 1/4] strbuf: add strbuf_add_uint()
- From
René Scharfe <l.s.r@web.de>
- Date
- May 13, 2026, 17:46 UTC
- Message-ID
- <9e0b4f9f-ffcb-4dad-bd4f-295bbc011a1e@web.de>
- In-Reply-To
- <20260513162232.GB103037@coredump.intra.peff.net>
On 5/13/26 6:22 PM, Jeff King wrote:
Show 11 quoted lines
> 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.
Show 6 quoted lines
>> 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
Show 49 quoted lines
> 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é