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.

2 files changed, 23 insertions, 1 deletions

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 @@ import (
 )
 
 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 @@ func (dw *deltaSelector) walk(objectsToPack []*ObjectToPack) error {
 			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 @@ func (s *DeltaSelectorSuite) TestObjectsToPack(c *C) {
 	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) {