[PATCH 0/4] strbuf: add and use strbuf_add_uint()

[PATCH 0/4] strbuf: add and use strbuf_add_uint()

[René Scharfe]

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

-- 
2.54.0

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

[René Scharfe]

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(+)

diff --git a/strbuf.c b/strbuf.c
index 3e04addc22..9731ecdc1f 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -361,6 +361,18 @@ void strbuf_addf(struct strbuf *sb, const char *fmt, ...)
 	va_end(ap);
 }
 
+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;
+
+	do
+		*--p = "0123456789"[value % 10];
+	while (value /= 10);
+	strbuf_add(sb, p, end - p);
+}
+
 static void add_lines(struct strbuf *out,
 			const char *prefix,
 			const char *buf, size_t size,
diff --git a/strbuf.h b/strbuf.h
index 06e284f9cc..1089ae687b 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -410,6 +410,12 @@ void strbuf_humanise_rate(struct strbuf *buf, off_t bytes);
 __attribute__((format (printf,2,3)))
 void strbuf_addf(struct strbuf *sb, const char *fmt, ...);
 
+
+/**
+ * Add an unsigned decimal number.
+ */
+void strbuf_add_uint(struct strbuf *sb, uintmax_t value);
+
 /**
  * Add a formatted string prepended by a comment character and a
  * blank to the buffer.
-- 
2.54.0

[PATCH 2/4] cat-file: use strbuf_add_uint()

[René Scharfe]

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

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index d9fbad5358..62160ca9d4 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -330,12 +330,12 @@ static int expand_atom(struct strbuf *sb, const char *atom, int len,
 		if (data->mark_query)
 			data->info.sizep = &data->size;
 		else
-			strbuf_addf(sb, "%"PRIuMAX , (uintmax_t)data->size);
+			strbuf_add_uint(sb, data->size);
 	} else if (is_atom("objectsize:disk", atom, len)) {
 		if (data->mark_query)
 			data->info.disk_sizep = &data->disk_size;
 		else
-			strbuf_addf(sb, "%"PRIuMAX, (uintmax_t)data->disk_size);
+			strbuf_add_uint(sb, data->disk_size);
 	} else if (is_atom("rest", atom, len)) {
 		if (data->mark_query)
 			data->split_on_whitespace = 1;
-- 
2.54.0

[PATCH 3/4] ls-files: use strbuf_add_uint()

[René Scharfe]

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

diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index b148607f7a..c142ad4156 100644
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c
@@ -250,20 +250,23 @@ static void expand_objectsize(struct repository *repo, struct strbuf *line,
 			      const struct object_id *oid,
 			      const enum object_type type, unsigned int padded)
 {
+	static const char padding[] = "       ";
+	size_t min_len = padded ? strlen(padding) : 0;
+	size_t orig_len = line->len;
+	size_t len;
+
 	if (type == OBJ_BLOB) {
 		unsigned long size;
 		if (odb_read_object_info(repo->objects, oid, &size) < 0)
 			die(_("could not get object info about '%s'"),
 			    oid_to_hex(oid));
-		if (padded)
-			strbuf_addf(line, "%7"PRIuMAX, (uintmax_t)size);
-		else
-			strbuf_addf(line, "%"PRIuMAX, (uintmax_t)size);
-	} else if (padded) {
-		strbuf_addf(line, "%7s", "-");
+		strbuf_add_uint(line, size);
 	} else {
 		strbuf_addstr(line, "-");
 	}
+	len = line->len - orig_len;
+	if (len < min_len)
+		strbuf_insert(line, orig_len, padding, min_len - len);
 }
 
 static void show_ce_fmt(struct repository *repo, const struct cache_entry *ce,
-- 
2.54.0

[PATCH 4/4] ls-tree: use strbuf_add_uint()

[René Scharfe]

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

diff --git a/builtin/ls-tree.c b/builtin/ls-tree.c
index 113e4a960d..57846911ce 100644
--- a/builtin/ls-tree.c
+++ b/builtin/ls-tree.c
@@ -26,20 +26,23 @@ static const char * const ls_tree_usage[] = {
 static void expand_objectsize(struct strbuf *line, const struct object_id *oid,
 			      const enum object_type type, unsigned int padded)
 {
+	static const char padding[] = "       ";
+	size_t min_len = padded ? strlen(padding) : 0;
+	size_t orig_len = line->len;
+	size_t len;
+
 	if (type == OBJ_BLOB) {
 		unsigned long size;
 		if (odb_read_object_info(the_repository->objects, oid, &size) < 0)
 			die(_("could not get object info about '%s'"),
 			    oid_to_hex(oid));
-		if (padded)
-			strbuf_addf(line, "%7"PRIuMAX, (uintmax_t)size);
-		else
-			strbuf_addf(line, "%"PRIuMAX, (uintmax_t)size);
-	} else if (padded) {
-		strbuf_addf(line, "%7s", "-");
+		strbuf_add_uint(line, size);
 	} else {
 		strbuf_addstr(line, "-");
 	}
+	len = line->len - orig_len;
+	if (len < min_len)
+		strbuf_insert(line, orig_len, padding, min_len - len);
 }
 
 struct ls_tree_options {
-- 
2.54.0

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

[Jeff King]

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

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

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

Re: [PATCH 2/4] cat-file: use strbuf_add_uint()

[Jeff King]

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

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

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

Re: [PATCH 3/4] ls-files: use strbuf_add_uint()

[Jeff King]

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

> 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

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

>  {
> +	static const char padding[] = "       ";
> +	size_t min_len = padded ? strlen(padding) : 0;
> +	size_t orig_len = line->len;
> +	size_t len;
> +
>  	if (type == OBJ_BLOB) {
>  		unsigned long size;
>  		if (odb_read_object_info(repo->objects, oid, &size) < 0)
>  			die(_("could not get object info about '%s'"),
>  			    oid_to_hex(oid));
> -		if (padded)
> -			strbuf_addf(line, "%7"PRIuMAX, (uintmax_t)size);
> -		else
> -			strbuf_addf(line, "%"PRIuMAX, (uintmax_t)size);
> -	} else if (padded) {
> -		strbuf_addf(line, "%7s", "-");
> +		strbuf_add_uint(line, size);
>  	} else {
>  		strbuf_addstr(line, "-");
>  	}
> +	len = line->len - orig_len;
> +	if (len < min_len)
> +		strbuf_insert(line, orig_len, padding, min_len - len);
>  }

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

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

[René Scharfe]

On 5/12/26 8:42 PM, Jeff King wrote:
> On Tue, May 12, 2026 at 01:56:00PM +0200, René Scharfe wrote:
> 
>> 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.
> 
> 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. ;)

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.

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

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é

Re: [PATCH 3/4] ls-files: use strbuf_add_uint()

[René Scharfe]

On 5/12/26 9:01 PM, Jeff King wrote:
> On Tue, May 12, 2026 at 01:56:02PM +0200, René Scharfe wrote:
> 
>> 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
> 
> OK, so here the improvement is less impressive than the previous commit.
> And the code is...
> 
>>  {
>> +	static const char padding[] = "       ";
>> +	size_t min_len = padded ? strlen(padding) : 0;
>> +	size_t orig_len = line->len;
>> +	size_t len;
>> +
>>  	if (type == OBJ_BLOB) {
>>  		unsigned long size;
>>  		if (odb_read_object_info(repo->objects, oid, &size) < 0)
>>  			die(_("could not get object info about '%s'"),
>>  			    oid_to_hex(oid));
>> -		if (padded)
>> -			strbuf_addf(line, "%7"PRIuMAX, (uintmax_t)size);
>> -		else
>> -			strbuf_addf(line, "%"PRIuMAX, (uintmax_t)size);
>> -	} else if (padded) {
>> -		strbuf_addf(line, "%7s", "-");
>> +		strbuf_add_uint(line, size);
>>  	} else {
>>  		strbuf_addstr(line, "-");
>>  	}
>> +	len = line->len - orig_len;
>> +	if (len < min_len)
>> +		strbuf_insert(line, orig_len, padding, min_len - len);
>>  }
> 
> ...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 gave my objectsize and objectsize:padded numbers; the difference was
1.2 ms, albeit with 1.0 ms noise in padded case.

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

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.

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

Terrifying!

> Having it all in one string ("%7d") is nice and concise.

Yes, except the original code includes the 7 twice (again for the
"-" fallback).
> 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).

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é

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

[Jeff King]

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,

Re: [PATCH 3/4] ls-files: use strbuf_add_uint()

[Jeff King]

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

> > ...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 gave my objectsize and objectsize:padded numbers; the difference was
> 1.2 ms, albeit with 1.0 ms noise in padded case.

Ah, right, that makes sense.

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

diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index c142ad4156..e17e3517ff 100644
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c
@@ -251,22 +251,24 @@ static void expand_objectsize(struct repository *repo, struct strbuf *line,
 			      const enum object_type type, unsigned int padded)
 {
 	static const char padding[] = "       ";
-	size_t min_len = padded ? strlen(padding) : 0;
-	size_t orig_len = line->len;
-	size_t len;
+	static const unsigned padding_len = ARRAY_SIZE(padding) - 1;
 
 	if (type == OBJ_BLOB) {
 		unsigned long size;
 		if (odb_read_object_info(repo->objects, oid, &size) < 0)
 			die(_("could not get object info about '%s'"),
 			    oid_to_hex(oid));
+		if (padded) {
+			unsigned digits = decimal_length_u64(size);
+			if (digits < padding_len)
+				strbuf_add(line, padding, padding_len - digits);
+		}
 		strbuf_add_uint(line, size);
 	} else {
+		if (padded)
+			strbuf_add(line, padding, padding_len - 1);
 		strbuf_addstr(line, "-");
 	}
-	len = line->len - orig_len;
-	if (len < min_len)
-		strbuf_insert(line, orig_len, padding, min_len - len);
 }
 
 static void show_ce_fmt(struct repository *repo, const struct cache_entry *ce,

but it was not meaningfully faster than your version.

> > 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).
> 
> 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 accidental test-balloon, I guess. It's in v2.54.0, so maybe we will
see some reports, or maybe we can eventually use it as evidence that we
can relax a bit.

-Peff

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

[Jeff King]

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

>  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;

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

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

[Jeff King]

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

> 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!

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

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

[René Scharfe]

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é

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

[René Scharfe]

On 5/13/26 6:49 PM, Jeff King wrote:
> On Wed, May 13, 2026 at 12:22:32PM -0400, Jeff King wrote:
> 
>> 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!
> 
> 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.
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< ---
diff --git a/strbuf.c b/strbuf.c
index 3e04addc22..4c2bd1e66f 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -106,12 +106,13 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)
 void strbuf_grow(struct strbuf *sb, size_t extra)
 {
 	int new_buf = !sb->alloc;
-	if (unsigned_add_overflows(extra, 1) ||
-	    unsigned_add_overflows(sb->len, extra + 1))
+	size_t len;
+	if (__builtin_add_overflow(extra, 1, &len) ||
+	    __builtin_add_overflow(sb->len, len, &len))
 		die("you want to use way too much memory");
 	if (new_buf)
 		sb->buf = NULL;
-	ALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);
+	ALLOC_GROW(sb->buf, len, sb->alloc);
 	if (new_buf)
 		sb->buf[0] = '\0';
 }
--- >8 ---

... gives a speedup on my Apple M1 with Apple's clang:

Benchmark 1: ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'
  Time (mean ± σ):     119.6 ms ±   0.2 ms    [User: 112.9 ms, System: 5.6 ms]
  Range (min … max):   119.3 ms … 120.1 ms    24 runs

Benchmark 2: ./git cat-file --batch-all-objects --batch-check='%(objectname)'
  Time (mean ± σ):     117.3 ms ±   0.2 ms    [User: 110.4 ms, System: 5.8 ms]
  Range (min … max):   117.1 ms … 117.6 ms    24 runs

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

... but has no effect with GCC 15.2.

René

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

[Junio C Hamano]

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

>> Right now we use unsigned_add_overflows(), and then do the actual add.
>> Using __builtin_add_overflow() might be faster.
> 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< ---
> diff --git a/strbuf.c b/strbuf.c
> index 3e04addc22..4c2bd1e66f 100644
> --- a/strbuf.c
> +++ b/strbuf.c
> @@ -106,12 +106,13 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)
>  void strbuf_grow(struct strbuf *sb, size_t extra)
>  {
>  	int new_buf = !sb->alloc;
> -	if (unsigned_add_overflows(extra, 1) ||
> -	    unsigned_add_overflows(sb->len, extra + 1))
> +	size_t len;
> +	if (__builtin_add_overflow(extra, 1, &len) ||
> +	    __builtin_add_overflow(sb->len, len, &len))
>  		die("you want to use way too much memory");
>  	if (new_buf)
>  		sb->buf = NULL;
> -	ALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);
> +	ALLOC_GROW(sb->buf, len, sb->alloc);
>  	if (new_buf)
>  		sb->buf[0] = '\0';
>  }
> --- >8 ---
>
> ... gives a speedup on my Apple M1 with Apple's clang:
>
> Benchmark 1: ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'
>   Time (mean ± σ):     119.6 ms ±   0.2 ms    [User: 112.9 ms, System: 5.6 ms]
>   Range (min … max):   119.3 ms … 120.1 ms    24 runs
>
> Benchmark 2: ./git cat-file --batch-all-objects --batch-check='%(objectname)'
>   Time (mean ± σ):     117.3 ms ±   0.2 ms    [User: 110.4 ms, System: 5.8 ms]
>   Range (min … max):   117.1 ms … 117.6 ms    24 runs
>
> Summary
>   ./git cat-file --batch-all-objects --batch-check='%(objectname)' ran
>     1.02 ± 0.00 times faster than ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'
>
> ... but has no effect with GCC 15.2.

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.

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

[Jeff King]

On Thu, May 14, 2026 at 01:09:24PM +0200, René Scharfe 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.
> 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

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