From: René Scharfe Date: Wed, 13 May 2026 17:46:11 GMT Subject: Re: [PATCH 1/4] strbuf: add strbuf_add_uint() 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: > 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é