From: Martin Fick <mfick@codeaurora.org>
To: Michael Haggerty <mhagger@alum.mit.edu>
Cc: git discussion list <git@vger.kernel.org>,
Junio C Hamano <gitster@pobox.com>
Subject: Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)
Date: Mon, 21 May 2012 12:15:13 -0600 [thread overview]
Message-ID: <201205211215.14455.mfick@codeaurora.org> (raw)
In-Reply-To: <4FB9F92D.8000305@alum.mit.edu>
On Monday, May 21, 2012 02:13:33 am Michael Haggerty wrote:
> I just noticed that the remove_duplicates() function in
> builtin/fetch-pack.c is O(N^2) in the number of heads.
> Empirically, this function takes on the order of 25
> seconds to process 100k references.
>
> I know that 100k heads is kindof absurd. Perhaps
> handling this many heads is unrealistic for other
> reasons. But I vaguely recall numbers like this being
> mentioned on the mailing list.
Yes I have mentioned 100K several times, and I greatly
appreciate the many fixes already made to make git to better
handle large ref counts.
However, I would like to suggest that 100K not really be
viewed as absurd anymore. :) There are many users for whom
it is not absurd, certainly not if you are including tags.
But, I know that some of the tag uses have been brushed off
as abuses, so I will focus on feature branches, of which we
actually have more than tags in our larger repos, we have
around 60K in our kernel repo.
Of course, we use Gerrit, so features tend to be called
changes and each change may get many revisions (patchsets),
so all of these get refs, but I think that it might be wrong
to consider that out of the ordinary anymore. After all,
should a version control system such as git not support 100K
revisions of features developed independently on separate
branches (within Gerrit or not)? 100K is not really that
many when you consider a large project. Even without
Gerrit, if someone wanted to track that many features
(likely over a few years), they will probably use up tons of
refs.
It may be too easy to think that because git is distributed
that features will get developed in a distributed way and
therefor no one would ever want to track them all in one
place, but I suspect that this may be a bad assumption.
That being said, I believe that we are not even tracking
external features, and we have over 60K feature revisions
(gerrit patchsets) in one rep), so if someone were to track
all the changes for the kernel, I can only imagine that this
number would be in the millions.
I am sure that 1M refs is even within the sights of some
individuals already, I know users who actually have 250K. I
hope that 10M or even perhaps 100M refs will be considered
feasible to use long term with git.
Again, I really hope that this will no longer be seen as
absurd, but rather just normal for large projects. After
all the kernel was (still is?) the primary use case of git.
Our largest ref project is the kernel so I don't know that
we should be considered fringe, and I hope that we along
with other larger kernel contributors will be considered
normal to git, :)
-Martin
--
Employee of Qualcomm Innovation Center, Inc. which is a
member of Code Aurora Forum
next prev parent reply other threads:[~2012-05-21 18:15 UTC|newest]
Thread overview: 46+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-05-21 8:13 remove_duplicates() in builtin/fetch-pack.c is O(N^2) Michael Haggerty
2012-05-21 9:09 ` Junio C Hamano
2012-05-21 9:42 ` demerphq
2012-05-21 17:45 ` Jeff King
2012-05-21 22:14 ` Jeff King
2012-05-21 22:17 ` [PATCH 1/5] fetch-pack: sort incoming heads Jeff King
2012-05-22 20:08 ` Junio C Hamano
2012-05-22 20:23 ` Jeff King
2012-05-24 6:04 ` Jeff King
2012-05-21 22:17 ` [PATCH 2/5] fetch-pack: avoid quadratic behavior in remove_duplicates Jeff King
2012-05-21 22:19 ` [PATCH 3/5] add sorting infrastructure for list refs Jeff King
2012-05-21 22:19 ` [PATCH 4/5] fetch-pack: sort the list of incoming refs Jeff King
2012-05-21 22:23 ` [PATCH 5/5] fetch-pack: avoid quadratic loop in filter_refs Jeff King
2012-05-22 20:16 ` Junio C Hamano
2012-05-21 23:52 ` remove_duplicates() in builtin/fetch-pack.c is O(N^2) Jeff King
2012-05-22 0:07 ` Jeff King
2012-05-22 3:59 ` Michael Haggerty
2012-05-22 4:11 ` Jeff King
2012-05-22 7:15 ` Michael Haggerty
2012-05-22 7:37 ` Jeff King
2012-05-22 13:28 ` Michael Haggerty
2012-05-22 17:33 ` Jeff King
2012-05-24 12:05 ` Michael Haggerty
2012-05-25 0:17 ` Martin Fick
2012-05-25 0:39 ` Jeff King
2012-05-25 0:54 ` Martin Fick
2012-05-25 1:04 ` Jeff King
2012-05-25 1:32 ` Martin Fick
2012-05-25 6:50 ` Jeff King
2012-05-22 12:18 ` Nguyen Thai Ngoc Duy
2012-05-22 13:35 ` Michael Haggerty
2012-05-22 17:01 ` Jeff King
2012-05-22 17:35 ` Junio C Hamano
2012-05-22 17:46 ` Jeff King
2012-05-24 4:54 ` Michael Haggerty
2012-05-23 1:20 ` Nguyen Thai Ngoc Duy
2012-05-22 16:16 ` Junio C Hamano
2012-05-21 18:15 ` Martin Fick [this message]
2012-05-21 19:41 ` Jeff King
2012-05-21 22:08 ` Junio C Hamano
2012-05-21 22:24 ` Jeff King
2012-05-22 5:51 ` Martin Fick
2012-05-22 18:21 ` Jeff King
2012-05-22 22:19 ` Martin Fick
2012-05-22 23:23 ` Junio C Hamano
2012-05-23 0:46 ` Martin Fick
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=201205211215.14455.mfick@codeaurora.org \
--to=mfick@codeaurora.org \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=mhagger@alum.mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).