index-pack: retain child bases in delta cache

From: Arijit Banerjee <[email protected]>

When resolving a delta whose result has children of its own, index-pack adds the result to work_head, accounts its data in base_cache_used, and calls prune_base_data(). It then immediately frees that same data.

This bypasses the existing delta base cache policy and can force later descendants to reconstruct the queued base again. Let the existing delta_base_cache_limit pruning policy decide whether to keep or evict the data instead.

---
index-pack: retain child bases in delta cache

Speed up the local pack indexing phase of clone/fetch for large delta-compressed packs by keeping reconstructed delta bases available for reuse when they are queued for later delta resolution.

When index-pack reconstructs a child base and queues it for resolving descendant deltas, it currently frees that data immediately. This can force the same base to be reconstructed again. Instead, keep it in the existing delta base cache and let the existing delta_base_cache_limit policy decide whether to retain or evict it.

This does not add a new cache or increase the cache limit. The object data is already accounted in base_cache_used, and prune_base_data() is already called at this point.

Correctness:

* t/t5302-pack-index.sh passed all 36 tests.

Benchmarks on a quiet Ubuntu 24.04 VM, 16 vCPU, 32 GiB RAM, local SSD:

pack baseline patched wall-time change RSS change linux blobless 69.17s 57.98s 16.2% faster -0.0% linux full 280.72s 236.32s 15.8% faster +1.9%

Five-repeat public-repo medians also improved: git.git 13.1%, libgit2 14.0%, redis 13.5%, cpython 4.8%.

Perf on the linux blobless pack showed the same direction under
profiling: 76.64s baseline vs 61.09s patched, with similar RSS.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2131%2Farijit91%2Findex-pack-retain-child-base-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2131/arijit91/index-pack-retain-child-base-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2131

 builtin/index-pack.c | 1 -
 1 file changed, 1 deletion(-)

index cf0bd8280d..027c64b522 100644
@@ -1212,7 +1212,6 @@ static void *threaded_second_pass(void *data)
 			list_add(&child->list, &work_head);
 			base_cache_used += child->size;
 			prune_base_data(NULL);
-			free_base_data(child);
 		} else if (child) {
 			/*
 			 * This child does not have its own children. It may be

base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d

gitgitgadget

Is there any chance that you ran this also with SANITIZE=leak to make sure that we aren't introducing a memory leak? (It's hard to tell just from the patch context, though your description is convincing.)

Indeed, this PR has a passing linux-leaks build that exercises this test script. [1]

[1] https://github.com/gitgitgadget/git/actions/runs/26605615549/job/78399938323?pr=2131#step:9:1405

A lot of this information that is in your cover letter would be helpful to include in your commit message, for posterity.

Also, I prefer to see performance numbers for these repos reflected in results from our performance test suite. We have a test for this purpose, so you could try running this from t/perf/ for your local copies of these repos:

GIT_PERF_LARGE_REPO=<path> ./run HEAD~1 HEAD -- p5302-pack-index.sh

And this should result in a standard comparison table that will help present your results in a way that is familiar to Git contributors.

From: Arijit Banerjee <[email protected]>

When resolving a delta whose result has children of its own, index-pack adds the result to work_head, accounts its data in base_cache_used, and calls prune_base_data(). It then immediately frees that same data.

This bypasses the existing delta base cache policy and can force later descendants to reconstruct the queued base again. Let the existing delta_base_cache_limit pruning policy decide whether to keep or evict the data instead.

This does not add a new cache or increase the cache limit. The object data is already accounted in base_cache_used before prune_base_data() runs, and the existing pruning and base cleanup paths still release it.

On a quiet Ubuntu 24.04 VM with 16 vCPUs, 32 GiB RAM, and local SSD, direct index-pack timings on single-pack Linux fixtures improved as follows:

linux blobless: 69.17s -> 57.98s (16.2% faster), RSS flat
linux full: 280.72s -> 236.32s (15.8% faster), RSS +1.9%

Five-repeat medians on public repositories also improved:

git.git: 12.31s -> 10.70s (13.1% faster)

  libgit2:   3.35s ->  2.88s (14.0% faster)
  redis:     6.52s ->  5.64s (13.5% faster)

cpython: 33.02s -> 31.44s (4.8% faster)

The standard p5302 perf test on a smaller git.git fixture was neutral:

5302.9 index-pack default threads:

    11.21(38.07+1.33) -> 11.16(37.90+1.31), -0.4%

t/t5302-pack-index.sh passed, and GitGitGadget's linux-leaks CI also exercised that test under SANITIZE=leak.

---
index-pack: retain child bases in delta cache

Speed up the local pack indexing phase of clone/fetch for large delta-compressed packs by keeping reconstructed delta bases available for reuse when they are queued for later delta resolution.

When index-pack reconstructs a child base and queues it for resolving descendant deltas, it currently frees that data immediately. This can force the same base to be reconstructed again. Instead, keep it in the existing delta base cache and let the existing delta_base_cache_limit policy decide whether to retain or evict it.

This does not add a new cache or increase the cache limit. The object data is already accounted in base_cache_used, and prune_base_data() is already called at this point.

Correctness:

* t/t5302-pack-index.sh passed all 36 tests.

Benchmarks on a quiet Ubuntu 24.04 VM, 16 vCPU, 32 GiB RAM, local SSD:

pack baseline patched wall-time change RSS change linux blobless 69.17s 57.98s 16.2% faster -0.0% linux full 280.72s 236.32s 15.8% faster +1.9%

Five-repeat public-repo medians also improved: git.git 13.1%, libgit2 14.0%, redis 13.5%, cpython 4.8%.

Perf on the linux blobless pack showed the same direction under
profiling: 76.64s baseline vs 61.09s patched, with similar RSS.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2131%2Farijit91%2Findex-pack-retain-child-base-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2131/arijit91/index-pack-retain-child-base-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2131

Range-diff vs v1:

1: cafb1700be ! 1: 42eca38f51 index-pack: retain child bases in delta cache
@@ Commit message

When resolving a delta whose result has children of its own, index-pack adds the result to work_head, accounts its data in
- base_cache_used, and calls prune_base_data(). It then immediately
- frees that same data.
+ base_cache_used, and calls prune_base_data(). It then immediately frees
+ that same data.

This bypasses the existing delta base cache policy and can force later descendants to reconstruct the queued base again. Let the existing delta_base_cache_limit pruning policy decide whether to keep or evict the data instead.

+ This does not add a new cache or increase the cache limit. The object
+ data is already accounted in base_cache_used before prune_base_data()
+ runs, and the existing pruning and base cleanup paths still release it.
+
+ On a quiet Ubuntu 24.04 VM with 16 vCPUs, 32 GiB RAM, and local SSD,
+ direct index-pack timings on single-pack Linux fixtures improved as
+ follows:
+
+ linux blobless: 69.17s -> 57.98s (16.2% faster), RSS flat
+ linux full: 280.72s -> 236.32s (15.8% faster), RSS +1.9%
+
+ Five-repeat medians on public repositories also improved:
+
+ git.git: 12.31s -> 10.70s (13.1% faster)
+ libgit2: 3.35s -> 2.88s (14.0% faster)
+ redis: 6.52s -> 5.64s (13.5% faster)
+ cpython: 33.02s -> 31.44s (4.8% faster)
+
+ The standard p5302 perf test on a smaller git.git fixture was neutral:
+
+ 5302.9 index-pack default threads:
+ 11.21(38.07+1.33) -> 11.16(37.90+1.31), -0.4%
+
+ t/t5302-pack-index.sh passed, and GitGitGadget's linux-leaks CI also
+ exercised that test under SANITIZE=leak.
+

## builtin/index-pack.c ##

 builtin/index-pack.c | 1 -
 1 file changed, 1 deletion(-)

index cf0bd8280d..027c64b522 100644
@@ -1212,7 +1212,6 @@ static void *threaded_second_pass(void *data)
 			list_add(&child->list, &work_head);
 			base_cache_used += child->size;
 			prune_base_data(NULL);
-			free_base_data(child);
 		} else if (child) {
 			/*
 			 * This child does not have its own children. It may be

base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d

gitgitgadget

That explanation makes sense, but I'm left with one question/concern. Dropping the data for a base makes sense when we are "done" with it, because we know we won't need it anymore and it leaves more room in the cache for things we do care about.

The problem here is that the current notion of "done" is not correct. Imagine we have delta chains "A -> B -> C" and "A -> D -> F". We are totally done with A when we have resolved both B and D, but if I understand correctly, we currently throw it away after just resolving B.

Your patch never throws it away, and just waits for it to get evicted from the cache due to memory pressure. But could we realize the moment when B and D have both finished using it, and evict it then? That makes it more likely for us to keep something useful in the cache when there is pressure.

I'm not sure how hard that would be in practice, or how much it would help (the base cache works in list order, so I think it might naturally be a sort of LRU?).

-Peff

From: Arijit Banerjee <[email protected]>

When resolving a delta whose result has children of its own, index-pack adds the result to work_head, accounts its data in base_cache_used, and calls prune_base_data(). It then immediately frees that same data.

This bypasses the existing delta base cache policy and can force later descendants to reconstruct the queued base again. Let the existing delta_base_cache_limit pruning policy decide whether to keep or evict the data instead.

This does not add a new cache or increase the cache limit. The object data is already accounted in base_cache_used before prune_base_data() runs. Once all direct children of a base have been dispatched, and no thread is actively retaining that base for patch_delta(), release the cached bytes. The base_data struct itself remains alive until the existing children_remaining bookkeeping says the whole subtree is done.

On a quiet Ubuntu 24.04 VM with 16 vCPUs, 32 GiB RAM, and local SSD, standard p5302-pack-index.sh runs improved as follows:

  libgit2:  3.17(11.49+0.60)  ->   2.69(10.52+0.28), 15.1% faster
  redis:    5.84(15.56+0.63)  ->   4.95(14.05+0.32), 15.2% faster
  git.git: 11.17(38.04+1.29)  ->   9.67(35.29+0.60), 13.4% faster

cpython: 32.69(117.85+4.37) -> 28.60(109.25+1.91), 12.5% faster
linux: 279.22(797.69+40.86) -> 236.34(723.13+19.02), 15.4% faster

The linux p5302 number is from a single repeat; the others are from the default three repeats.

End-to-end local full-clone spot checks also improved:

  libgit2:  5.00s ->   4.54s, 9.2% faster
  redis:    8.75s ->   7.92s, 9.5% faster

git.git: 25.04s -> 23.71s, 5.3% faster
cpython: 56.72s -> 55.94s, 1.4% faster
linux: 556.17s -> 523.83s, 5.8% faster

t/t5302-pack-index.sh passed, and GitGitGadget's linux-leaks CI also exercised that test under SANITIZE=leak.

---
index-pack: retain child bases in delta cache

Speed up the local index-pack phase used by clone/fetch for large delta-compressed packs.

When index-pack reconstructs a child base and queues it for resolving descendant deltas, it currently frees that data immediately. This can force the same base to be reconstructed again. This patch keeps the data in the existing delta base cache instead of immediately freeing it.

This does not add a new cache or increase the cache limit. The object data is already accounted in base_cache_used, and prune_base_data() is already called at this point.

To keep the retained data lifetime precise, the patch also releases cached bytes once all direct children of a base have been dispatched and no thread is actively retaining that base for patch_delta(). The base_data struct itself still stays alive until the existing children_remaining bookkeeping says the whole subtree is done.

Changes since v2:

* Addressed Jeff King's review question by releasing cached base data after all direct children have been dispatched, while keeping the existing subtree bookkeeping intact.
* Re-ran t/t5302-pack-index.sh, p5302-pack-index.sh, and end-to-end full clone spot checks with the precise-release version.

Changes since v1:

* Added benchmark results and leak-safety context to the commit message.
* Included standard p5302-pack-index.sh perf-suite results.

Correctness:

* t/t5302-pack-index.sh passed.
* GitGitGadget's linux-leaks CI exercises t5302-pack-index.sh under SANITIZE=leak.

Benchmarks on a quiet Ubuntu 24.04 VM, 16 vCPU, 32 GiB RAM, local SSD:

Standard p5302-pack-index.sh perf-suite results using GIT_PERF_LARGE_REPO=<repo> ./run HEAD~1 HEAD -- p5302-pack-index.sh:

repo HEAD~1 HEAD wall-time change libgit2 3.17(11.49+0.60) 2.69(10.52+0.28) 15.1% faster redis 5.84(15.56+0.63) 4.95(14.05+0.32) 15.2% faster git.git 11.17(38.04+1.29) 9.67(35.29+0.60) 13.4% faster cpython 32.69(117.85+4.37) 28.60(109.25+1.91) 12.5% faster linux 279.22(797.69+40.86) 236.34(723.13+19.02) 15.4% faster

The linux p5302 row is from a single repeat; the others use the default three repeats. These timings isolate the index-pack phase affected by this patch.

End-to-end local full-clone spot checks also showed wins, though these timings include both server-side pack-objects and client-side index-pack running concurrently over a local file:// transport, so they are not isolated index-pack timings.

These runs used git clone --bare --no-local, dropped page cache before each clone, and used the matching build's bin-wrappers/git as the client plus the matching bin-wrappers/git-upload-pack via --upload-pack.

repo baseline patched wall-time change libgit2 5.00s 4.54s 9.2% faster redis 8.75s 7.92s 9.5% faster git.git 25.04s 23.71s 5.3% faster cpython 56.72s 55.94s 1.4% faster linux 556.17s 523.83s 5.8% faster

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2131%2Farijit91%2Findex-pack-retain-child-base-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2131/arijit91/index-pack-retain-child-base-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/2131

Range-diff vs v2:

1: 42eca38f51 ! 1: 51967f9edf index-pack: retain child bases in delta cache
@@ Commit message

This does not add a new cache or increase the cache limit. The object data is already accounted in base_cache_used before prune_base_data()
- runs, and the existing pruning and base cleanup paths still release it.
+ runs. Once all direct children of a base have been dispatched, and no
+ thread is actively retaining that base for patch_delta(), release the
+ cached bytes. The base_data struct itself remains alive until the
+ existing children_remaining bookkeeping says the whole subtree is done.

On a quiet Ubuntu 24.04 VM with 16 vCPUs, 32 GiB RAM, and local SSD,
- direct index-pack timings on single-pack Linux fixtures improved as
- follows:
+ standard p5302-pack-index.sh runs improved as follows:

- linux blobless: 69.17s -> 57.98s (16.2% faster), RSS flat
- linux full: 280.72s -> 236.32s (15.8% faster), RSS +1.9%
+ libgit2: 3.17(11.49+0.60) -> 2.69(10.52+0.28), 15.1% faster
+ redis: 5.84(15.56+0.63) -> 4.95(14.05+0.32), 15.2% faster
+ git.git: 11.17(38.04+1.29) -> 9.67(35.29+0.60), 13.4% faster
+ cpython: 32.69(117.85+4.37) -> 28.60(109.25+1.91), 12.5% faster
+ linux: 279.22(797.69+40.86) -> 236.34(723.13+19.02), 15.4% faster

- Five-repeat medians on public repositories also improved:
+ The linux p5302 number is from a single repeat; the others are from the
+ default three repeats.

- git.git: 12.31s -> 10.70s (13.1% faster)
- libgit2: 3.35s -> 2.88s (14.0% faster)
- redis: 6.52s -> 5.64s (13.5% faster)
- cpython: 33.02s -> 31.44s (4.8% faster)
+ End-to-end local full-clone spot checks also improved:

- The standard p5302 perf test on a smaller git.git fixture was neutral:
-
- 5302.9 index-pack default threads:
- 11.21(38.07+1.33) -> 11.16(37.90+1.31), -0.4%
+ libgit2: 5.00s -> 4.54s, 9.2% faster
+ redis: 8.75s -> 7.92s, 9.5% faster
+ git.git: 25.04s -> 23.71s, 5.3% faster
+ cpython: 56.72s -> 55.94s, 1.4% faster
+ linux: 556.17s -> 523.83s, 5.8% faster

t/t5302-pack-index.sh passed, and GitGitGadget's linux-leaks CI also exercised that test under SANITIZE=leak.
@@ Commit message

## builtin/index-pack.c ##
+@@ builtin/index-pack.c: static void free_base_data(struct base_data *c)
+ }
+ }
+
++static int base_data_has_remaining_direct_children(struct base_data *c) ++{
++ return c->ref_first <= c->ref_last ||
++ c->ofs_first <= c->ofs_last;
++}
++
+ static void prune_base_data(struct base_data *retain)
+ {
+ struct list_head *pos;
+@@ builtin/index-pack.c: static void *threaded_second_pass(void *data)
+ }
+
+ work_lock();
+- if (parent)
++ if (parent) {
+ parent->retain_data--;
++ if (!parent->retain_data &&
++ !base_data_has_remaining_direct_children(parent))
++ free_base_data(parent);
++ }
+
+ if (child && child->data) {
+ /*
@@ builtin/index-pack.c: static void *threaded_second_pass(void *data)
list_add(&child->list, &work_head); base_cache_used += child->size;

 builtin/index-pack.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

index cf0bd8280d..00b4dff419 100644
@@ -433,6 +433,12 @@ static void free_base_data(struct base_data *c)
 	}
 }
 
+static int base_data_has_remaining_direct_children(struct base_data *c)
+{
+	return c->ref_first <= c->ref_last ||
+	       c->ofs_first <= c->ofs_last;
+}
+
 static void prune_base_data(struct base_data *retain)
 {
 	struct list_head *pos;

@@ -1201,8 +1207,12 @@ static void *threaded_second_pass(void *data)
 		}
 
 		work_lock();
-		if (parent)
+		if (parent) {
 			parent->retain_data--;
+			if (!parent->retain_data &&
+			    !base_data_has_remaining_direct_children(parent))
+				free_base_data(parent);
+		}
 
 		if (child && child->data) {
 			/*

@@ -1212,7 +1222,6 @@ static void *threaded_second_pass(void *data)
 			list_add(&child->list, &work_head);
 			base_cache_used += child->size;
 			prune_base_data(NULL);
-			free_base_data(child);
 		} else if (child) {
 			/*
 			 * This child does not have its own children. It may be

base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d

gitgitgadget

...

Thanks for humoring me. I fully expected the answer to be "it is hard to do and doesn't show much improvement, so let's not bother". ;)

It was hard to see the difference between v2 and v3 performance (which I tried to dig out from the range-diff below), but it looks like it was basically none. I did my own run of p5302 between the two versions using both git.git and linux.git, and likewise didn't find anything.

I guess it would make a difference only if we were routinely expiring useful items out of the cache due to the limit. And even though linux.git is a "large" repo compared to git.git, cache locality here is mostly based on how wide the delta tree for a file gets (that is, how often we go down one chain, caching bases, while still finding it useful to keep earlier parts of the chain to go down a parallel path).

And that probably has less to do with overall repo size rather than with how we tend to pack things. Though I guess a repo with a lot of large files might see more cache pressure (just because each single entry "costs" more). We could simulate that by dropping the cache size in p5302, but I still couldn't find any effect even with a tiny cache.

(Actually, with a tiny cache it looked like things got ~1% slower; maybe noise, but maybe extra thread contention due to the release code?).

So I am happy with either v2 or v3.

-Peff

Apologies, my earlier replies were sent through GitHub's notification emails and appeared only as PR comments, so they did not reach the mailing list.

I also did not see a meaningful performance difference between v2 and v3. I am happy with either direction and defer to the maintainers on whether v3's more precise release is worth the added complexity.

I do not have strong RSS evidence. The spot checks showed no meaningful RSS change, and max RSS is not a good signal here because free_base_data() lowers Git's internal base_cache_used accounting but may not return pages to the OS or reduce the recorded peak.

The evidence for v3 is therefore structural: it releases the cached data once all direct children have been dispatched and retain_data reaches zero, rather than waiting for cache-pressure eviction.

Thanks,
Arijit

I have no strong preference either way.

Nor me. I'd probably go with v2 simply because it is shorter and less code. If there is an optimization whose effect we cannot measure, it is probably not worth even the few lines to have it. It could always be resurrected if somebody finds a case where it matters.

-Peff

Sounds like a good idea. I just resurrected v2 from my reflog ;-) Let's mark the topic for 'next'.

Thanks.