[PATCH] fetch: avoid repeated commits in mark_complete

We add every local ref to a list so that we can mark them and all of their ancestors back to a certain cutoff point. However, if some refs point to the same commit, we will end up adding them to the list many times.

Furthermore, since commit_lists are stored as linked lists, we must do an O(n) traversal of the list in order to find the right place to insert each commit. This makes building the list O(n^2) in the number of refs.

For normal repositories, this isn't a big deal. We have a few hundreds refs at most, and most of them are unique. But consider an "alternates" repo that serves as an object database for many other similar repos. For reachability, it needs to keep a copy of the refs in each child repo. This means it may have a large number of refs, many of which point to the same commits.

By noting commits we have already added to the list, we can shrink the size of "n" in such a repo to the number of unique commits, which is on the order of what a normal repo would contain (it's actually more than a normal repo, since child repos may have branches at different states, but in practice it tends to be much smaller than the list with duplicates).

Here are the results on one particular giant repo (containing objects for all Rails forks on GitHub):

  $ git for-each-ref | wc -l
  112514

  [before]
  $ git fetch --no-tags ../remote.git
  63.52user 0.12system 1:03.68elapsed 99%CPU (0avgtext+0avgdata 137648maxresident)k
  1856inputs+48outputs (11major+19603minor)pagefaults 0swaps

  $ git fetch --no-tags ../remote.git
  6.15user 0.08system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123856maxresident)k
  0inputs+40outputs (0major+18872minor)pagefaults 0swaps

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/fetch-pack.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)