plumbing: use sliding window in delta calculations, like git CL
This sets a default sliding window of 10 for the delta calculation,
just like git CL:
https://git-scm.com/docs/git-pack-objects#git-pack-objects---windowltngt
For a big-ish repo with 35K objects (17K commits), this reduced the
time for calling `deltaSelection.walk` during a push from more than 14
minutes to about a minute.
diff --git a/plumbing/format/packfile/delta_selector.go b/plumbing/format/packfile/delta_selector.go
index efcbd53..cc0ae0f 100644
--- a/plumbing/format/packfile/delta_selector.go
+++ b/plumbing/format/packfile/delta_selector.go
@@ -8,6 +8,9 @@
)
const (
+ // How far back in the sorted list to search for deltas. 10 is
+ // the default in command line git.
+ deltaWindowSize = 10
// deltas based on deltas, how many steps we can do.
// 50 is the default value used in JGit
maxDepth = int64(50)
@@ -184,7 +187,7 @@
continue
}
- for j := i - 1; j >= 0; j-- {
+ for j := i - 1; j >= 0 && i-j < deltaWindowSize; j-- {
base := objectsToPack[j]
// Objects must use only the same type as their delta base.
// Since objectsToPack is sorted by type and size, once we find
diff --git a/plumbing/format/packfile/delta_selector_test.go b/plumbing/format/packfile/delta_selector_test.go
index cbbbc89..ca4a96b 100644
--- a/plumbing/format/packfile/delta_selector_test.go
+++ b/plumbing/format/packfile/delta_selector_test.go
@@ -196,6 +196,25 @@
c.Assert(otp[2].Original, Equals, s.store.Objects[s.hashes["o3"]])
c.Assert(otp[2].IsDelta(), Equals, true)
c.Assert(otp[2].Depth, Equals, 2)
+
+ // Check that objects outside of the sliding window don't produce
+ // a delta.
+ hashes = make([]plumbing.Hash, 0, deltaWindowSize+2)
+ hashes = append(hashes, s.hashes["base"])
+ for i := 0; i < deltaWindowSize; i++ {
+ hashes = append(hashes, s.hashes["smallTarget"])
+ }
+ hashes = append(hashes, s.hashes["target"])
+
+ // Don't sort so we can easily check the sliding window without
+ // creating a bunch of new objects.
+ otp, err = s.ds.objectsToPack(hashes)
+ c.Assert(err, IsNil)
+ err = s.ds.walk(otp)
+ c.Assert(err, IsNil)
+ c.Assert(len(otp), Equals, deltaWindowSize+2)
+ targetIdx := len(otp) - 1
+ c.Assert(otp[targetIdx].IsDelta(), Equals, false)
}
func (s *DeltaSelectorSuite) TestMaxDepth(c *C) {
