From d68f45f8aaca461167907c07e8c161be14e87157 Mon Sep 17 00:00:00 2001 From: Jeremy Stribling Date: Fri, 25 Aug 2017 13:52:07 -0700 Subject: plumbing: use `seen` map in tree walker This helps avoids iterating down the same trees for every commit. For a big-ish repo with 35K objects (17K commits), this reduced the time for calling `revlist.Objects` during a push (with 0 hashes to ignore) from more than ten minutes to less than a minute. --- plumbing/object/tree.go | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'plumbing/object/tree.go') diff --git a/plumbing/object/tree.go b/plumbing/object/tree.go index 512db9f..44ac720 100644 --- a/plumbing/object/tree.go +++ b/plumbing/object/tree.go @@ -297,9 +297,10 @@ func (iter *treeEntryIter) Next() (TreeEntry, error) { // TreeWalker provides a means of walking through all of the entries in a Tree. type TreeWalker struct { - stack []treeEntryIter + stack []*treeEntryIter base string recursive bool + seen map[plumbing.Hash]bool s storer.EncodedObjectStorer t *Tree @@ -309,13 +310,14 @@ type TreeWalker struct { // // It is the caller's responsibility to call Close() when finished with the // tree walker. -func NewTreeWalker(t *Tree, recursive bool) *TreeWalker { - stack := make([]treeEntryIter, 0, startingStackSize) - stack = append(stack, treeEntryIter{t, 0}) +func NewTreeWalker(t *Tree, recursive bool, seen map[plumbing.Hash]bool) *TreeWalker { + stack := make([]*treeEntryIter, 0, startingStackSize) + stack = append(stack, &treeEntryIter{t, 0}) return &TreeWalker{ stack: stack, recursive: recursive, + seen: seen, s: t.s, t: t, @@ -358,6 +360,10 @@ func (w *TreeWalker) Next() (name string, entry TreeEntry, err error) { return } + if w.seen[entry.Hash] { + continue + } + if entry.Mode == filemode.Dir { obj, err = GetTree(w.s, entry.Hash) } @@ -377,7 +383,7 @@ func (w *TreeWalker) Next() (name string, entry TreeEntry, err error) { } if t, ok := obj.(*Tree); ok { - w.stack = append(w.stack, treeEntryIter{t, 0}) + w.stack = append(w.stack, &treeEntryIter{t, 0}) w.base = path.Join(w.base, entry.Name) } -- cgit