Speed up printing of objectsize atoms by using the specialized function strbuf_add_uint() instead of the general-purpose function strbuf_addf():

Benchmark 1: ./git_main cat-file --batch-all-objects --batch-check='%(objectsize)'
  Time (mean ± σ):     751.7 ms ±   1.5 ms    [User: 733.5 ms, System: 17.1 ms]
  Range (min … max):   750.5 ms … 755.0 ms    10 runs

Benchmark 2: ./git cat-file --batch-all-objects --batch-check='%(objectsize)'
  Time (mean ± σ):     720.4 ms ±   0.4 ms    [User: 701.9 ms, System: 16.7 ms]
  Range (min … max):   719.7 ms … 721.2 ms    10 runs

Summary
  ./git cat-file --batch-all-objects --batch-check='%(objectsize)' ran
    1.04 ± 0.00 times faster than ./git_main cat-file --batch-all-objects --batch-check='%(objectsize)'

Benchmark 1: ./git_main cat-file --batch-all-objects --batch-check='%(objectsize:disk)'
  Time (mean ± σ):     404.6 ms ±   0.9 ms    [User: 397.8 ms, System: 5.7 ms]
  Range (min … max):   403.3 ms … 405.9 ms    10 runs

Benchmark 2: ./git cat-file --batch-all-objects --batch-check='%(objectsize:disk)'
  Time (mean ± σ):     378.3 ms ±   0.9 ms    [User: 371.2 ms, System: 5.9 ms]
  Range (min … max):   376.8 ms … 380.2 ms    10 runs

Summary
  ./git cat-file --batch-all-objects --batch-check='%(objectsize:disk)' ran
    1.07 ± 0.00 times faster than ./git_main cat-file --batch-all-objects --batch-check='%(objectsize:disk)'

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/cat-file.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

strbuf_addf() calls vsnprintf(3) underneath, which supports a plethora of formatting options. We can avoid its overhead in basic cases by providing specialized functions like strbuf_addstr() for strings. Add another one, strbuf_add_uint(), for unsigned integers.

Prepare the number string in a temporary buffer. Make it big enough for any unsigned integer value: A decimal digit can represent ln(10)/ln(2) ≈ 3.32 bits; dividing the number of bits of uintmax_t by 3.3 and rounding up gives a sufficiently close conservative size estimate.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 strbuf.c | 12 ++++++++++++
 strbuf.h |  6 ++++++
 2 files changed, 18 insertions(+)

Speed up printing of objectsize values by using the specialized function strbuf_add_uint() as well as strbuf_insert() for padding instead of the general-purpose function strbuf_addf(). Here are the numbers I get when listing objects in the Linux kernel repo:

Benchmark 1: ./git_main -C ../linux ls-tree -r --format='%(objectsize)' HEAD
  Time (mean ± σ):     294.4 ms ±   0.4 ms    [User: 231.5 ms, System: 59.4 ms]
  Range (min … max):   293.9 ms … 295.0 ms    10 runs

Benchmark 2: ./git -C ../linux ls-tree -r --format='%(objectsize)' HEAD
  Time (mean ± σ):     291.2 ms ±   0.4 ms    [User: 227.9 ms, System: 62.1 ms]
  Range (min … max):   290.6 ms … 292.0 ms    10 runs

Benchmark 3: ./git_main -C ../linux ls-tree -r --format='%(objectsize:padded)' HEAD
  Time (mean ± σ):     295.3 ms ±   0.6 ms    [User: 232.0 ms, System: 59.6 ms]
  Range (min … max):   294.3 ms … 296.3 ms    10 runs

Benchmark 4: ./git -C ../linux ls-tree -r --format='%(objectsize:padded)' HEAD
  Time (mean ± σ):     291.9 ms ±   0.4 ms    [User: 228.5 ms, System: 61.5 ms]
  Range (min … max):   291.2 ms … 292.3 ms    10 runs

Summary
  ./git -C ../linux ls-tree -r --format='%(objectsize)' HEAD ran
    1.00 ± 0.00 times faster than ./git -C ../linux ls-tree -r --format='%(objectsize:padded)' HEAD
    1.01 ± 0.00 times faster than ./git_main -C ../linux ls-tree -r --format='%(objectsize)' HEAD
    1.01 ± 0.00 times faster than ./git_main -C ../linux ls-tree -r --format='%(objectsize:padded)' HEAD

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/ls-tree.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

Speed up printing of objectsize values by using the specialized function strbuf_add_uint() as well as strbuf_insert() for padding instead of the general-purpose function strbuf_addf(). Here are the numbers I get when listing files in the Linux kernel repo:

Benchmark 1: ./git_main -C ../linux ls-files --format='%(objectsize)'
  Time (mean ± σ):     257.3 ms ±   0.4 ms    [User: 197.4 ms, System: 56.7 ms]
  Range (min … max):   256.7 ms … 258.1 ms    11 runs

Benchmark 2: ./git -C ../linux ls-files --format='%(objectsize)'
  Time (mean ± σ):     253.4 ms ±   0.3 ms    [User: 193.6 ms, System: 56.6 ms]
  Range (min … max):   253.0 ms … 253.8 ms    11 runs

Benchmark 3: ./git_main -C ../linux ls-files --format='%(objectsize:padded)'
  Time (mean ± σ):     257.9 ms ±   0.3 ms    [User: 198.0 ms, System: 56.6 ms]
  Range (min … max):   257.3 ms … 258.5 ms    11 runs

Benchmark 4: ./git -C ../linux ls-files --format='%(objectsize:padded)'
  Time (mean ± σ):     254.6 ms ±   1.0 ms    [User: 194.6 ms, System: 56.7 ms]
  Range (min … max):   253.7 ms … 256.8 ms    11 runs

Summary
  ./git -C ../linux ls-files --format='%(objectsize)' ran
    1.00 ± 0.00 times faster than ./git -C ../linux ls-files --format='%(objectsize:padded)'
    1.02 ± 0.00 times faster than ./git_main -C ../linux ls-files --format='%(objectsize)'
    1.02 ± 0.00 times faster than ./git_main -C ../linux ls-files --format='%(objectsize:padded)'

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/ls-files.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

Add a function that does the same as strbuf_addf(sb, "%"PRIuMAX, value), only faster, and use it to speed up bulk reporting of size values a bit.

  strbuf: add strbuf_add_uint()
  cat-file: use strbuf_add_uint()
  ls-files: use strbuf_add_uint()
  ls-tree: use strbuf_add_uint()

 builtin/cat-file.c |  4 ++--
 builtin/ls-files.c | 15 +++++++++------
 builtin/ls-tree.c  | 15 +++++++++------
 strbuf.c           | 12 ++++++++++++
 strbuf.h           |  6 ++++++
 5 files changed, 38 insertions(+), 14 deletions(-)

On Tue, May 12, 2026 at 01:56:00PM +0200, René Scharfe wrote:

Cute. The naive obvious question here is: why not just grow the strbuf and format it there directly?

And the answer is that it's much easier to format numbers right-to-left, and then you know how many digits you need. ;)

You can compute the number of digits needed up front, of course, but it's log-10. You might be able to do it quickly based on the size of the leading bit, but there are a lot of off-by-one gotchas.

So probably the extra memcpy() is not that big a deal.

-Peff

On Tue, May 12, 2026 at 01:56:01PM +0200, René Scharfe wrote:

Neat. It is sad that sprintf is so slow that this makes a difference. ;)

But it seems like an easy win, and I would argue the resulting code is more readable here.

-Peff

On Tue, May 12, 2026 at 01:56:02PM +0200, René Scharfe wrote:

OK, so here the improvement is less impressive than the previous commit. And the code is...

...also less nice. We are formatting into the strbuf, and then maybe memmove()-ing the result to accommodate padding. I wonder how much that affects the timing. It's extra shuffling, but memmove() etc is often surprisingly fast.

I wonder how bad it would be to handle the padding ahead of time. Obviously strbuf_add_uint() knows the size of the result right before it calls memcpy(), and it could insert the padding then. But adding a padding length parameter (let alone the space vs "0" decision) to that function feels kind of gross.

In the earlier patch I raised the notion of pre-computing the output length. If we had a helper to do that, it would be pretty easy to do:

  /* noop if third parameter is negative */
  strbuf_pad(line, ' ', 7 - decimal_digits(size));
  strbuf_add_uint(line, size);

You could also imagine a world where we had some stateful formatting system, and you could say:

  strbuf_pad_next(line, ' ', 7);
  strbuf_add_uint(line, size);

but somebody has to store that state between the calls, and I don't love the idea of bloating strbuf with it. So probably you have some "formatter" struct, and it operates on a strbuf. And now we have all of the OO boilerplate hassles like initializing and tearing down our formatter object. ;) So probably not worth it for this triviality. Having it all in one string ("%7d") is nice and concise.

I have often wondered how hard it would be to implement our own vsnprintf(), and whether we could do better than the libc ones. It would be nice to be able to add shorthands for common types (instead of the unreadable PRIuMAX mess), as well as custom ones (e.g., hex oids).

Probably also not worth the headache. ;)

-Peff

On 5/12/26 8:42 PM, Jeff King wrote:

Right. Using the strbuf to format the number at the right end and memmove()ing it in place is a valid approach. I expected it to be faster than using a buffer on the stack because there's a chance that only one cache line needs to be touched.

That's the simplest approach and I expected the few necessary extra divisions to be faster than using a buffer and having to copy the result.

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).

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. :)

René

On 5/12/26 9:01 PM, Jeff King wrote:

I gave my objectsize and objectsize:padded numbers; the difference was 1.2 ms, albeit with 1.0 ms noise in padded case.

I started with a struct numbuf for holding a number string and its length, which helped avoid the memmove(3) call. It's simple and doesn't require a lot of code, but introducing that concept felt a bit much for just two users.

Terrifying!

Yes, except the original code includes the 7 twice (again for the "-" fallback).

C99 has %ju for uintmax_t and %zu for size_t. Hmm, do we actually still need to avoid them? CodingGuidelines says "the C library used by MinGW does not" support it. 82c36fa0a9 (submodule: hash the submodule name for the gitdir path, 2026-01-12) just added a %zu, and there are lots of them in compat/mimalloc/ in Git for Windows.

An extensible printf-like formatter would be nice indeed. I wondered about how something like that could be used to write structured output like tar and zip archive entries in a terse way. The thought faded, I guess, when I found no compelling reason for that compactness that would justify the required complexity of the mechanism.

René

On Tue, May 12, 2026 at 09:32:09PM +0200, René Scharfe wrote:

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!

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

On Tue, May 12, 2026 at 10:44:21PM +0200, René Scharfe wrote:

Ah, right, that makes sense.

Applying the fast decimal-width from my earlier message, I came up with:

On Wed, May 13, 2026 at 12:22:32PM -0400, Jeff King wrote:

This last line should be "sb->buf + sb->len + digits", of course. Naturally that was the part I wrote by hand. ;)

It doesn't matter for the cat-file test, since we're always formatting into an empty buffer, but it does for the ls-files padding one.

-Peff

On Wed, May 13, 2026 at 12:22:32PM -0400, Jeff King wrote:

And btw, one final thing to look at if you are interested in micro-optimizing strbufs: using intrinsics for overflow detection.

Right now we use unsigned_add_overflows(), and then do the actual add. Using __builtin_add_overflow() might be faster.

-Peff

On 5/13/26 6:22 PM, Jeff King wrote:

Did them before I sent the series.

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

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

René

On 5/13/26 6:49 PM, Jeff King wrote:

Curious. Clang and GCC emit the same instructions for our unsigned_add_overflows() vs. __builtin_add_overflow() on x64, but clang on ARM64 fails to elide the comparison: https://godbolt.org/z/91d35KofM

Which explains why this patch:

--- 8< ---

René Scharfe <l.s.r@web.de> writes:

Interesting. A few percent is indeed impressive in such a micro optimization, and it is satisfying to see that the compilers can see what our unsigned_add_overflows() plus the actual add does and makes your above patch a no-op.

On Thu, May 14, 2026 at 01:09:24PM +0200, René Scharfe wrote:

Ah, neat. I always assumed there was low-hanging fruit to pick here, but it sounds like the compiler is (usually) more clever than I expected.

-Peff