* [PATCH 0/2] builtin/repo: improve counting of objects
@ 2026-11-13 11:46 Patrick Steinhardt
2026-11-13 11:46 ` [PATCH 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt
` (2 more replies)
0 siblings, 3 replies; 15+ messages in thread
From: Patrick Steinhardt @ 2026-11-13 11:46 UTC (permalink / raw)
To: git
Hi,
I was recently using `git repo structure` in a very large repository and
was eventually greeted with an OOM. So I had a bit of a look and found a
way to improve the memory footprint and speed it up a bit.
The repository still doesn't produce results. As it turns out, walking
33 billion tree entries takes a while, and everything rev-list based
that walks trees is kinda broken in there. Oh, well, a problem for
another day.
Thanks!
Patrick
---
Patrick Steinhardt (2):
builtin/repo: only parse objects as needed
builtin/repo: don't fully parse trees
builtin/repo.c | 34 +++++++++++++++++++---------------
1 file changed, 19 insertions(+), 15 deletions(-)
---
base-commit: 1891de46f79dc444a47db1c87bd0c8c76b5463f2
change-id: 20261111-pks-repo-count-objects-speedup-528abf12ea23
^ permalink raw reply [flat|nested] 15+ messages in thread* [PATCH 1/2] builtin/repo: only parse objects as needed 2026-11-13 11:46 [PATCH 0/2] builtin/repo: improve counting of objects Patrick Steinhardt @ 2026-11-13 11:46 ` Patrick Steinhardt 2026-11-13 14:12 ` Kristofer Karlsson 2026-11-13 11:46 ` [PATCH 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2 siblings, 1 reply; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-13 11:46 UTC (permalink / raw) To: git To count objects we walk the repository's object graph. We then read the individual objects that we encounter so that we can learn about their metrics like their size. As part of this, we also unconditionally read the object's content and parse it. But this is quite unnecessary, as we only really need parsed commits and trees because we need their number of parents and tree entries, respectively. So the time we spend reading and parsing blobs and tags is ultimately pointless. Improve the status quo so that we only parse as needed. This allows us to do another small optimization: as we reach commits via the rev walk we know that they have already been parsed anyway. Consequently, we don't even need to read their data at all, and we can instead just look up the already-parsed commit. This speeds up `git repo structure` a bit. The following benchmark was executed in "git.git": Benchmark 1: ./git repo structure (commit = HEAD~) (10 runs) mean ± σ min … max Wall Time 10.891 s ± 0.113 s 10.779 s … 11.181 s Memory 3.5 GiB ± 0.0 GiB 3.5 GiB … 3.5 GiB Benchmark 2: ./git repo structure (commit = HEAD) (10 runs) mean ± σ min … max Wall Time 9.577 s ± 0.064 s 9.485 s … 9.673 s -12.1% Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB -4.1% Signed-off-by: Patrick Steinhardt <ps@pks.im> --- builtin/repo.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) diff --git a/builtin/repo.c b/builtin/repo.c index 0399c558719..98be90891ce 100644 --- a/builtin/repo.c +++ b/builtin/repo.c @@ -847,13 +847,14 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, size_t inflated_st = 0; struct commit *commit; struct object *obj; - void *content; + void *content = NULL; off_t disk; - int eaten; + int eaten = 0; oi.sizep = &inflated_st; oi.disk_sizep = &disk; - oi.contentp = &content; + if (type == OBJ_TREE) + oi.contentp = &content; if (odb_read_object_info_extended(data->odb, &oids->oid[i], &oi, OBJECT_INFO_SKIP_FETCH_OBJECT | @@ -861,9 +862,6 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, continue; inflated = cast_size_t_to_ulong(inflated_st); - obj = parse_object_buffer(the_repository, &oids->oid[i], type, - inflated, content, &eaten); - switch (type) { case OBJ_TAG: stats->type_counts.tags++; @@ -873,7 +871,15 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, inflated); break; case OBJ_COMMIT: - commit = object_as_type(obj, OBJ_COMMIT, 0); + /* + * Commits have already been parsed by the revision + * walk, so there is no need to read their contents + * again. + */ + commit = lookup_commit(data->odb->repo, &oids->oid[i]); + if (!commit || repo_parse_commit(data->odb->repo, commit)) + continue; + stats->type_counts.commits++; stats->inflated_sizes.commits += inflated; stats->disk_sizes.commits += disk; @@ -883,6 +889,9 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, commit_list_count(commit->parents)); break; case OBJ_TREE: + obj = parse_object_buffer(the_repository, &oids->oid[i], type, + inflated, content, &eaten); + stats->type_counts.trees++; stats->inflated_sizes.trees += inflated; stats->disk_sizes.trees += disk; -- 2.56.0.611.g1030f0b940.dirty ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH 1/2] builtin/repo: only parse objects as needed 2026-11-13 11:46 ` [PATCH 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt @ 2026-11-13 14:12 ` Kristofer Karlsson 2026-11-16 6:38 ` Patrick Steinhardt 0 siblings, 1 reply; 15+ messages in thread From: Kristofer Karlsson @ 2026-11-13 14:12 UTC (permalink / raw) To: Patrick Steinhardt; +Cc: git On Fri, 13 Nov 2026 at 13:50, Patrick Steinhardt <ps@pks.im> wrote: > > + /* > + * Commits have already been parsed by the revision > + * walk, so there is no need to read their contents > + * again. > + */ > + commit = lookup_commit(data->odb->repo, &oids->oid[i]); > + if (!commit || repo_parse_commit(data->odb->repo, commit)) > + continue; Tiny nit: I understood the comment as saying that the code depends on the commits being parsed already, but repo_parse_commit() handles the case where they are not. Since path-walk hands us commits from get_revision(), I assume that is only a failsafe? So this is just about the phrasing. How about: /* * Commits should already have been parsed by the * revision walk, so we do not need to read their * contents again. */ Otherwise this looks good to me. Only reading contents for trees avoids inflating every blob just to throw it away, which is a nice easy win. Thanks, Kristofer ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 1/2] builtin/repo: only parse objects as needed 2026-11-13 14:12 ` Kristofer Karlsson @ 2026-11-16 6:38 ` Patrick Steinhardt 2026-11-16 9:02 ` Kristofer Karlsson 0 siblings, 1 reply; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-16 6:38 UTC (permalink / raw) To: Kristofer Karlsson; +Cc: git On Fri, Nov 13, 2026 at 03:12:19PM +0100, Kristofer Karlsson wrote: > On Fri, 13 Nov 2026 at 13:50, Patrick Steinhardt <ps@pks.im> wrote: > > > > + /* > > + * Commits have already been parsed by the revision > > + * walk, so there is no need to read their contents > > + * again. > > + */ > > + commit = lookup_commit(data->odb->repo, &oids->oid[i]); > > + if (!commit || repo_parse_commit(data->odb->repo, commit)) > > + continue; > > Tiny nit: I understood the comment as saying that the code > depends on the commits being parsed already, but > repo_parse_commit() handles the case where they are not. > Since path-walk hands us commits from get_revision(), I > assume that is only a failsafe? So this is just about the > phrasing. How about: Yeah, it is. I was wondering whether I want to call `BUG()` here in the case where the commit cannot be parsed, as that case really shouldn't ever happen. But that felt a bit heavy-handed to me. > /* > * Commits should already have been parsed by the > * revision walk, so we do not need to read their > * contents again. > */ > > Otherwise this looks good to me. Only reading contents for > trees avoids inflating every blob just to throw it away, which > is a nice easy win. Yeah, that reads a bit better to me indeed. Will adapt, thanks! Patrick ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 1/2] builtin/repo: only parse objects as needed 2026-11-16 6:38 ` Patrick Steinhardt @ 2026-11-16 9:02 ` Kristofer Karlsson 0 siblings, 0 replies; 15+ messages in thread From: Kristofer Karlsson @ 2026-11-16 9:02 UTC (permalink / raw) To: Patrick Steinhardt; +Cc: git On Mon, 16 Nov 2026 at 07:38, Patrick Steinhardt <ps@pks.im> wrote: > > On Fri, Nov 13, 2026 at 03:12:19PM +0100, Kristofer Karlsson wrote: > > On Fri, 13 Nov 2026 at 13:50, Patrick Steinhardt <ps@pks.im> wrote: > > > Tiny nit: I understood the comment as saying that the code > > depends on the commits being parsed already, but > > repo_parse_commit() handles the case where they are not. > > Since path-walk hands us commits from get_revision(), I > > assume that is only a failsafe? So this is just about the > > phrasing. How about: > > Yeah, it is. I was wondering whether I want to call `BUG()` here in the > case where the commit cannot be parsed, as that case really shouldn't > ever happen. But that felt a bit heavy-handed to me. I think it would be a valid option, as long as their is enough test coverage. If there's ever a regression here that makes this function be called for commits that have not been loaded, the current implementation would mean surviving it, but at the cost of extra unintentional work, whereas a BUG() assert would make the regression more obvious. It's not something I have a strong opinion on though, and I think the updated comment will make future developers see what the intention is. Thanks, Kristofer ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 2/2] builtin/repo: don't fully parse trees 2026-11-13 11:46 [PATCH 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2026-11-13 11:46 ` [PATCH 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt @ 2026-11-13 11:46 ` Patrick Steinhardt 2026-11-13 14:15 ` Kristofer Karlsson 2026-11-16 13:43 ` Derrick Stolee 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2 siblings, 2 replies; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-13 11:46 UTC (permalink / raw) To: git When the rev walk hits a tree object we read its content and then parse it via `parse_object_buffer()`. This requires us to perform some extra bookkeeping that is ultimately unnecessary as we keep those trees in memory. The only thing that we need the tree object's content for is so that we can count its entries. But that can easily be done without having a parsed tree object, all we need is its content. Refactor the code accordingly, which gives us another significant speedup when executing `git repo structure` in "git.git": Benchmark 1: ./git repo structure (commit = HEAD~) (10 runs) mean ± σ min … max Wall Time 9.635 s ± 0.072 s 9.534 s … 9.799 s Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB Benchmark 2: ./git repo structure (commit = HEAD) (10 runs) mean ± σ min … max Wall Time 7.676 s ± 0.106 s 7.568 s … 7.823 s -20.3% Memory 0.7 GiB ± 0.0 GiB 0.7 GiB … 0.7 GiB -80.4% (5.1x less) But besides the speedup, the bigger win here is that we no longer keep these parsed trees in memory at all, which translates in a significant reduction in peak memory usage. Signed-off-by: Patrick Steinhardt <ps@pks.im> --- builtin/repo.c | 19 +++++++------------ 1 file changed, 7 insertions(+), 12 deletions(-) diff --git a/builtin/repo.c b/builtin/repo.c index 98be90891ce..64fb5e788d1 100644 --- a/builtin/repo.c +++ b/builtin/repo.c @@ -820,14 +820,14 @@ static void check_largest(struct object_data *data, struct object_id *oid, } } -static size_t count_tree_entries(struct object *obj) +static size_t count_tree_entries(const struct object_id *oid, + void *buffer, unsigned long size) { - struct tree *t = object_as_type(obj, OBJ_TREE, 0); struct name_entry entry; struct tree_desc desc; size_t count = 0; - init_tree_desc(&desc, &t->object.oid, t->buffer, t->size); + init_tree_desc(&desc, oid, buffer, size); while (tree_entry(&desc, &entry)) count++; @@ -846,10 +846,8 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, unsigned long inflated; size_t inflated_st = 0; struct commit *commit; - struct object *obj; void *content = NULL; off_t disk; - int eaten = 0; oi.sizep = &inflated_st; oi.disk_sizep = &disk; @@ -889,16 +887,16 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, commit_list_count(commit->parents)); break; case OBJ_TREE: - obj = parse_object_buffer(the_repository, &oids->oid[i], type, - inflated, content, &eaten); - stats->type_counts.trees++; stats->inflated_sizes.trees += inflated; stats->disk_sizes.trees += disk; check_largest(&stats->largest.tree_size, &oids->oid[i], inflated); check_largest(&stats->largest.tree_entries, &oids->oid[i], - count_tree_entries(obj)); + count_tree_entries(&oids->oid[i], content, + inflated)); + + free(content); break; case OBJ_BLOB: stats->type_counts.blobs++; @@ -910,9 +908,6 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, default: BUG("invalid object type"); } - - if (!eaten) - free(content); } object_count = get_total_object_values(&stats->type_counts); -- 2.56.0.611.g1030f0b940.dirty ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH 2/2] builtin/repo: don't fully parse trees 2026-11-13 11:46 ` [PATCH 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt @ 2026-11-13 14:15 ` Kristofer Karlsson 2026-11-16 6:39 ` Patrick Steinhardt 2026-11-16 13:43 ` Derrick Stolee 1 sibling, 1 reply; 15+ messages in thread From: Kristofer Karlsson @ 2026-11-13 14:15 UTC (permalink / raw) To: Patrick Steinhardt; +Cc: git On Fri, 13 Nov 2026 at 14:06, Patrick Steinhardt <ps@pks.im> wrote: > > Benchmark 1: ./git repo structure (commit = HEAD~) (10 runs) > mean ± σ min … max > Wall Time 9.635 s ± 0.072 s 9.534 s … 9.799 s > Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB > > Benchmark 2: ./git repo structure (commit = HEAD) (10 runs) > mean ± σ min … max > Wall Time 7.676 s ± 0.106 s 7.568 s … 7.823 s -20.3% > Memory 0.7 GiB ± 0.0 GiB 0.7 GiB … 0.7 GiB -80.4% (5.1x less) That's quite a nice memory reduction! > But besides the speedup, the bigger win here is that we no longer keep > these parsed trees in memory at all, which translates in a significant > reduction in peak memory usage. I took a look at this since it is very similar to what I recently did for the incremental connectivity check, where the tree verifier also reads raw tree buffers instead of going through parse_object_buffer(), for the same memory reasons (I only needed to track the oids, not the full objects). Both patches look good to me. Thanks, Kristofer ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 2/2] builtin/repo: don't fully parse trees 2026-11-13 14:15 ` Kristofer Karlsson @ 2026-11-16 6:39 ` Patrick Steinhardt 0 siblings, 0 replies; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-16 6:39 UTC (permalink / raw) To: Kristofer Karlsson; +Cc: git On Fri, Nov 13, 2026 at 03:15:16PM +0100, Kristofer Karlsson wrote: > On Fri, 13 Nov 2026 at 14:06, Patrick Steinhardt <ps@pks.im> wrote: > > > > Benchmark 1: ./git repo structure (commit = HEAD~) (10 runs) > > mean ± σ min … max > > Wall Time 9.635 s ± 0.072 s 9.534 s … 9.799 s > > Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB > > > > Benchmark 2: ./git repo structure (commit = HEAD) (10 runs) > > mean ± σ min … max > > Wall Time 7.676 s ± 0.106 s 7.568 s … 7.823 s -20.3% > > Memory 0.7 GiB ± 0.0 GiB 0.7 GiB … 0.7 GiB -80.4% (5.1x less) > > That's quite a nice memory reduction! > > > But besides the speedup, the bigger win here is that we no longer keep > > these parsed trees in memory at all, which translates in a significant > > reduction in peak memory usage. > > I took a look at this since it is very similar to what I > recently did for the incremental connectivity check, where > the tree verifier also reads raw tree buffers instead of > going through parse_object_buffer(), for the same memory > reasons (I only needed to track the oids, not the full objects). > > Both patches look good to me. Thanks for your review! Patrick ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 2/2] builtin/repo: don't fully parse trees 2026-11-13 11:46 ` [PATCH 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt 2026-11-13 14:15 ` Kristofer Karlsson @ 2026-11-16 13:43 ` Derrick Stolee 1 sibling, 0 replies; 15+ messages in thread From: Derrick Stolee @ 2026-11-16 13:43 UTC (permalink / raw) To: Patrick Steinhardt, git On 11/13/2026 6:46 AM, Patrick Steinhardt wrote: > When the rev walk hits a tree object we read its content and then parse > it via `parse_object_buffer()`. This requires us to perform some extra > bookkeeping that is ultimately unnecessary as we keep those trees in > memory. > > The only thing that we need the tree object's content for is so that we > can count its entries. But that can easily be done without having a > parsed tree object, all we need is its content. > > Refactor the code accordingly, which gives us another significant > speedup when executing `git repo structure` in "git.git": > Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB > Memory 0.7 GiB ± 0.0 GiB 0.7 GiB … 0.7 GiB -80.4% (5.1x less) This is an impressive memory reduction! Very nice. (I'd comment on v2, but my email host must have bounced those.0 Thanks, -Stolee ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH v2 0/2] builtin/repo: improve counting of objects 2026-11-13 11:46 [PATCH 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2026-11-13 11:46 ` [PATCH 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt 2026-11-13 11:46 ` [PATCH 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt @ 2026-11-16 8:01 ` Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt ` (3 more replies) 2 siblings, 4 replies; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-16 8:01 UTC (permalink / raw) To: git; +Cc: Kristofer Karlsson Hi, I was recently using `git repo structure` in a very large repository and was eventually greeted with an OOM. So I had a bit of a look and found a way to improve the memory footprint and speed it up a bit. The repository still doesn't produce results. As it turns out, walking 33 billion tree entries takes a while, and everything rev-list based that walks trees is kinda broken in there. Oh, well, a problem for another day. Changes in v2: - Reword a comment to point out that parsing the commit should in theory not be required. - Link to v1: https://patch.msgid.link/20261113-pks-repo-count-objects-speedup-v1-0-7ba4f29e74fb@pks.im Thanks! Patrick --- Patrick Steinhardt (2): builtin/repo: only parse objects as needed builtin/repo: don't fully parse trees builtin/repo.c | 34 +++++++++++++++++++--------------- 1 file changed, 19 insertions(+), 15 deletions(-) Range-diff versus v1: 1: a7a1c1a8041 ! 1: 2780e491ead builtin/repo: only parse objects as needed @@ builtin/repo.c: static int count_objects(const char *path UNUSED, struct oid_arr case OBJ_COMMIT: - commit = object_as_type(obj, OBJ_COMMIT, 0); + /* -+ * Commits have already been parsed by the revision -+ * walk, so there is no need to read their contents -+ * again. ++ * Commits should already have been parsed by the ++ * revision walk, so in theory we do not need to read ++ * their contents again. + */ + commit = lookup_commit(data->odb->repo, &oids->oid[i]); + if (!commit || repo_parse_commit(data->odb->repo, commit)) 2: d9fd2366b84 = 2: aa32dcb2961 builtin/repo: don't fully parse trees --- base-commit: 1891de46f79dc444a47db1c87bd0c8c76b5463f2 change-id: 20261111-pks-repo-count-objects-speedup-528abf12ea23 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH v2 1/2] builtin/repo: only parse objects as needed 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt @ 2026-11-16 8:01 ` Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt ` (2 subsequent siblings) 3 siblings, 0 replies; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-16 8:01 UTC (permalink / raw) To: git; +Cc: Kristofer Karlsson To count objects we walk the repository's object graph. We then read the individual objects that we encounter so that we can learn about their metrics like their size. As part of this, we also unconditionally read the object's content and parse it. But this is quite unnecessary, as we only really need parsed commits and trees because we need their number of parents and tree entries, respectively. So the time we spend reading and parsing blobs and tags is ultimately pointless. Improve the status quo so that we only parse as needed. This allows us to do another small optimization: as we reach commits via the rev walk we know that they have already been parsed anyway. Consequently, we don't even need to read their data at all, and we can instead just look up the already-parsed commit. This speeds up `git repo structure` a bit. The following benchmark was executed in "git.git": Benchmark 1: ./git repo structure (commit = HEAD~) (10 runs) mean ± σ min … max Wall Time 10.891 s ± 0.113 s 10.779 s … 11.181 s Memory 3.5 GiB ± 0.0 GiB 3.5 GiB … 3.5 GiB Benchmark 2: ./git repo structure (commit = HEAD) (10 runs) mean ± σ min … max Wall Time 9.577 s ± 0.064 s 9.485 s … 9.673 s -12.1% Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB -4.1% Signed-off-by: Patrick Steinhardt <ps@pks.im> --- builtin/repo.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) diff --git a/builtin/repo.c b/builtin/repo.c index 0399c558719..45ac005c2f7 100644 --- a/builtin/repo.c +++ b/builtin/repo.c @@ -847,13 +847,14 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, size_t inflated_st = 0; struct commit *commit; struct object *obj; - void *content; + void *content = NULL; off_t disk; - int eaten; + int eaten = 0; oi.sizep = &inflated_st; oi.disk_sizep = &disk; - oi.contentp = &content; + if (type == OBJ_TREE) + oi.contentp = &content; if (odb_read_object_info_extended(data->odb, &oids->oid[i], &oi, OBJECT_INFO_SKIP_FETCH_OBJECT | @@ -861,9 +862,6 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, continue; inflated = cast_size_t_to_ulong(inflated_st); - obj = parse_object_buffer(the_repository, &oids->oid[i], type, - inflated, content, &eaten); - switch (type) { case OBJ_TAG: stats->type_counts.tags++; @@ -873,7 +871,15 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, inflated); break; case OBJ_COMMIT: - commit = object_as_type(obj, OBJ_COMMIT, 0); + /* + * Commits should already have been parsed by the + * revision walk, so in theory we do not need to read + * their contents again. + */ + commit = lookup_commit(data->odb->repo, &oids->oid[i]); + if (!commit || repo_parse_commit(data->odb->repo, commit)) + continue; + stats->type_counts.commits++; stats->inflated_sizes.commits += inflated; stats->disk_sizes.commits += disk; @@ -883,6 +889,9 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, commit_list_count(commit->parents)); break; case OBJ_TREE: + obj = parse_object_buffer(the_repository, &oids->oid[i], type, + inflated, content, &eaten); + stats->type_counts.trees++; stats->inflated_sizes.trees += inflated; stats->disk_sizes.trees += disk; -- 2.56.1.763.g16177fe143.dirty ^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH v2 2/2] builtin/repo: don't fully parse trees 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt @ 2026-11-16 8:01 ` Patrick Steinhardt 2026-11-16 9:07 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Kristofer Karlsson 2026-11-16 16:02 ` Derrick Stolee 3 siblings, 0 replies; 15+ messages in thread From: Patrick Steinhardt @ 2026-11-16 8:01 UTC (permalink / raw) To: git; +Cc: Kristofer Karlsson When the rev walk hits a tree object we read its content and then parse it via `parse_object_buffer()`. This requires us to perform some extra bookkeeping that is ultimately unnecessary as we keep those trees in memory. The only thing that we need the tree object's content for is so that we can count its entries. But that can easily be done without having a parsed tree object, all we need is its content. Refactor the code accordingly, which gives us another significant speedup when executing `git repo structure` in "git.git": Benchmark 1: ./git repo structure (commit = HEAD~) (10 runs) mean ± σ min … max Wall Time 9.635 s ± 0.072 s 9.534 s … 9.799 s Memory 3.4 GiB ± 0.0 GiB 3.4 GiB … 3.4 GiB Benchmark 2: ./git repo structure (commit = HEAD) (10 runs) mean ± σ min … max Wall Time 7.676 s ± 0.106 s 7.568 s … 7.823 s -20.3% Memory 0.7 GiB ± 0.0 GiB 0.7 GiB … 0.7 GiB -80.4% (5.1x less) But besides the speedup, the bigger win here is that we no longer keep these parsed trees in memory at all, which translates in a significant reduction in peak memory usage. Signed-off-by: Patrick Steinhardt <ps@pks.im> --- builtin/repo.c | 19 +++++++------------ 1 file changed, 7 insertions(+), 12 deletions(-) diff --git a/builtin/repo.c b/builtin/repo.c index 45ac005c2f7..2c96a3ea577 100644 --- a/builtin/repo.c +++ b/builtin/repo.c @@ -820,14 +820,14 @@ static void check_largest(struct object_data *data, struct object_id *oid, } } -static size_t count_tree_entries(struct object *obj) +static size_t count_tree_entries(const struct object_id *oid, + void *buffer, unsigned long size) { - struct tree *t = object_as_type(obj, OBJ_TREE, 0); struct name_entry entry; struct tree_desc desc; size_t count = 0; - init_tree_desc(&desc, &t->object.oid, t->buffer, t->size); + init_tree_desc(&desc, oid, buffer, size); while (tree_entry(&desc, &entry)) count++; @@ -846,10 +846,8 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, unsigned long inflated; size_t inflated_st = 0; struct commit *commit; - struct object *obj; void *content = NULL; off_t disk; - int eaten = 0; oi.sizep = &inflated_st; oi.disk_sizep = &disk; @@ -889,16 +887,16 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, commit_list_count(commit->parents)); break; case OBJ_TREE: - obj = parse_object_buffer(the_repository, &oids->oid[i], type, - inflated, content, &eaten); - stats->type_counts.trees++; stats->inflated_sizes.trees += inflated; stats->disk_sizes.trees += disk; check_largest(&stats->largest.tree_size, &oids->oid[i], inflated); check_largest(&stats->largest.tree_entries, &oids->oid[i], - count_tree_entries(obj)); + count_tree_entries(&oids->oid[i], content, + inflated)); + + free(content); break; case OBJ_BLOB: stats->type_counts.blobs++; @@ -910,9 +908,6 @@ static int count_objects(const char *path UNUSED, struct oid_array *oids, default: BUG("invalid object type"); } - - if (!eaten) - free(content); } object_count = get_total_object_values(&stats->type_counts); -- 2.56.1.763.g16177fe143.dirty ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH v2 0/2] builtin/repo: improve counting of objects 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt @ 2026-11-16 9:07 ` Kristofer Karlsson 2026-11-16 16:02 ` Derrick Stolee 3 siblings, 0 replies; 15+ messages in thread From: Kristofer Karlsson @ 2026-11-16 9:07 UTC (permalink / raw) To: Patrick Steinhardt; +Cc: git On Mon, 16 Nov 2026 at 09:01, Patrick Steinhardt <ps@pks.im> wrote: > > Range-diff versus v1: > > 1: a7a1c1a8041 ! 1: 2780e491ead builtin/repo: only parse objects as needed > @@ builtin/repo.c: static int count_objects(const char *path UNUSED, struct oid_arr > case OBJ_COMMIT: > - commit = object_as_type(obj, OBJ_COMMIT, 0); > + /* > -+ * Commits have already been parsed by the revision > -+ * walk, so there is no need to read their contents > -+ * again. > ++ * Commits should already have been parsed by the > ++ * revision walk, so in theory we do not need to read > ++ * their contents again. > + */ > + commit = lookup_commit(data->odb->repo, &oids->oid[i]); > + if (!commit || repo_parse_commit(data->odb->repo, commit)) I think this range-diff addresses my only nit, so I am happy with this version! Thanks, Kristofer ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v2 0/2] builtin/repo: improve counting of objects 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt ` (2 preceding siblings ...) 2026-11-16 9:07 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Kristofer Karlsson @ 2026-11-16 16:02 ` Derrick Stolee 2026-11-16 17:32 ` Junio C Hamano 3 siblings, 1 reply; 15+ messages in thread From: Derrick Stolee @ 2026-11-16 16:02 UTC (permalink / raw) To: Patrick Steinhardt, git; +Cc: Kristofer Karlsson On 11/16/2026 3:01 AM, Patrick Steinhardt wrote: > I was recently using `git repo structure` in a very large repository and > was eventually greeted with an OOM. So I had a bit of a look and found a > way to improve the memory footprint and speed it up a bit. > > The repository still doesn't produce results. As it turns out, walking > 33 billion tree entries takes a while, and everything rev-list based > that walks trees is kinda broken in there. Oh, well, a problem for > another day. > > Changes in v2: > - Reword a comment to point out that parsing the commit should in > theory not be required. > - Link to v1: https://patch.msgid.link/20261113-pks-repo-count-objects-speedup- Thanks for these changes. I found your v2 patches in my inbox somehow disconnected from this cover letter. But I'm happy with v2. Thanks, -Stolee ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v2 0/2] builtin/repo: improve counting of objects 2026-11-16 16:02 ` Derrick Stolee @ 2026-11-16 17:32 ` Junio C Hamano 0 siblings, 0 replies; 15+ messages in thread From: Junio C Hamano @ 2026-11-16 17:32 UTC (permalink / raw) To: Derrick Stolee; +Cc: Patrick Steinhardt, git, Kristofer Karlsson Derrick Stolee <stolee@gmail.com> writes: > On 11/16/2026 3:01 AM, Patrick Steinhardt wrote: >> I was recently using `git repo structure` in a very large repository and >> was eventually greeted with an OOM. So I had a bit of a look and found a >> way to improve the memory footprint and speed it up a bit. >> >> The repository still doesn't produce results. As it turns out, walking >> 33 billion tree entries takes a while, and everything rev-list based >> that walks trees is kinda broken in there. Oh, well, a problem for >> another day. >> >> Changes in v2: >> - Reword a comment to point out that parsing the commit should in >> theory not be required. >> - Link to v1: https://patch.msgid.link/20261113-pks-repo-count-objects-speedup- > Thanks for these changes. I found your v2 patches in my inbox somehow > disconnected from this cover letter. But I'm happy with v2. Thanks for writing and reviewing. Let me mark the topic as ready for 'next'. ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2026-11-16 17:32 UTC | newest] Thread overview: 15+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2026-11-13 11:46 [PATCH 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2026-11-13 11:46 ` [PATCH 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt 2026-11-13 14:12 ` Kristofer Karlsson 2026-11-16 6:38 ` Patrick Steinhardt 2026-11-16 9:02 ` Kristofer Karlsson 2026-11-13 11:46 ` [PATCH 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt 2026-11-13 14:15 ` Kristofer Karlsson 2026-11-16 6:39 ` Patrick Steinhardt 2026-11-16 13:43 ` Derrick Stolee 2026-11-16 8:01 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 1/2] builtin/repo: only parse objects as needed Patrick Steinhardt 2026-11-16 8:01 ` [PATCH v2 2/2] builtin/repo: don't fully parse trees Patrick Steinhardt 2026-11-16 9:07 ` [PATCH v2 0/2] builtin/repo: improve counting of objects Kristofer Karlsson 2026-11-16 16:02 ` Derrick Stolee 2026-11-16 17:32 ` Junio C Hamano
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox