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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

0 files changed, 0 insertions, 0 deletions