Re: Git is not scalable with too many refs/*

quoted

quoted

Julian Phillips [off-list ref] wrote:

-- snip --

quoted

quoted

I've created a test repo with ~100k refs/changes/...
style refs, and ~40000 refs/heads/... style refs, and
checkout can walk the list of ~140k refs seven times
in 85ms user time including doing whatever other
processing is needed for checkout. The real time is
only 114ms - but then my test repo has no real data
in.

If I understand what you are saying, it sounds like you
do not have a very good test case. The amount of time
it takes for checkout depends on how long it takes to
find a ref with the sha1 that you are on. If that sha1
is so early in the list of refs that it only took you
7 traversals to find it, then that is not a very good
testcase. I think that you should probably try making
an orphaned ref (checkout a detached head, commit to
it), that is probably the worst testcase since it
should then have to search all 140K refs to eventually
give up.

Again, if I understand what you are saying, if it took
85ms for 7 traversals, then it takes approximately
10ms per traversal, that's only 100/s! If you have to
traverse it 140K times, that should work out to 1400s
~ 23mins.

Well, it's no more than 10ms per traversal - since the
rest of the work presumably takes some time too ...

However, I had forgotten to make the orphaned commit as
you suggest - and then _bang_ 7N^2, it tries seven
different variants of each ref (which is silly as they
are all fully qualified), and with packed refs it has to
search for them each time, all to turn names into hashes
that we already know to start with.

So, yes - it is that list traversal.

Does the following help?

diff --git a/builtin/checkout.c b/builtin/checkout.c
index 5e356a6..f0f4ca1 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c

@@ -605,7 +605,7 @@ static int

add_one_ref_to_rev_list_arg(const char *refname,
                                        int flags,
                                        void *cb_data)
  {
-       add_one_rev_list_arg(cb_data, refname);
+       add_one_rev_list_arg(cb_data,
strdup(sha1_to_hex(sha1))); return 0;
  }