From: Jeff King Date: Wed, 13 May 2026 16:22:32 GMT Subject: Re: [PATCH 1/4] strbuf: add strbuf_add_uint() Message-ID: <20260513162232.GB103037@coredump.intra.peff.net> In-Reply-To: <60b1ef2a-3b12-449e-be0b-cb206425c80c@web.de> 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. ;) I guess it is not too surprising that they all come pretty close in whole-process benchmarks. These are all micro-optimizations of a relatively small portion of the total work the process is doing. Even the strbuf_grow() checks are probably slower! > 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. 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]); +} + void strbuf_add_uint(struct strbuf *sb, uintmax_t value) { - char buf[DIV_ROUND_UP(bitsizeof(value) * 10, 33)]; - char *end = buf + sizeof(buf); - char *p = end; + unsigned digits = decimal_length_u64(value); + char *p; + strbuf_grow(sb, digits); + p = sb->buf + digits; do *--p = "0123456789"[value % 10]; while (value /= 10); - strbuf_add(sb, p, end - p); + strbuf_setlen(sb, sb->len + digits); } static void add_lines(struct strbuf *out,