From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:58
Jeff King [off-list ref] writes:
On Tue, Jul 02, 2013 at 12:41:51AM -0400, Jeff King wrote:
quoted
I replicated your test setup, and the problem is that we have many
common objects on both sides during the ref negotiation. So we end up in
rev_list_push for each one, which has the same O(n^2) behavior.
Switching it to just sort at the end is not trivial; we first insert all
of the objects, but then we actually walk the parents, pushing onto the
list as we go. So I think we'd want a better data structure (like a
priority queue).
Like the patch below, which is built on top of next (which has Junio's
prio_queue implementation), and has both the priority queue fix for
rev_list_push and the mark_complete sort-at-the-end fix.
Wow, I saw "160 lines" in my MUA which scared me a bit until I
opened it to realize 40% is discussion and most of the remaining
lines are context around single liners.
It just looks too easy/simple, but the result looks correct, at
least from a cursory read.
Good job ;-)
From: Jeff King <hidden> Date: 2016-06-15 22:57:58
On Mon, Jul 01, 2013 at 10:19:51PM -0700, Junio C Hamano wrote:
quoted
Like the patch below, which is built on top of next (which has Junio's
prio_queue implementation), and has both the priority queue fix for
rev_list_push and the mark_complete sort-at-the-end fix.
Wow, I saw "160 lines" in my MUA which scared me a bit until I
opened it to realize 40% is discussion and most of the remaining
lines are context around single liners.
It just looks too easy/simple, but the result looks correct, at
least from a cursory read.
Good job ;-)
Thanks. :)
I'm splitting it out into readable patches now. At first I was made a
bit nervous by the "popping" behavior I described as "oddity #2"
earlier. But the more I look at it, the more I am convinced it is
simply a bug that we can happen to fix along the way.
Patches in a few minutes.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:57:58
Here are my patches to deal with Martin's pathological case, split out
for easy reading. I took a few timings to show that the results of the
3rd patch are noticeable even with 50,000 unique refs (which is still a
lot, but something that I could conceive of a busy repo accumulating
over time).
[1/3]: fetch-pack: avoid quadratic list insertion in mark_complete
[2/3]: commit.c: make compare_commits_by_commit_date global
[3/3]: fetch-pack: avoid quadratic behavior in rev_list_push
And here's the diffstat to prove it is really not scary. :)
commit.c | 2 +-
commit.h | 2 ++
fetch-pack.c | 16 ++++++++--------
3 files changed, 11 insertions(+), 9 deletions(-)
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:57:58
We insert the commit pointed to by each ref one-by-one into
the "complete" commit_list using insert_by_date. Because
each insertion is O(n), we end up with O(n^2) behavior.
This typically doesn't matter, because the number of refs is
reasonably small. And even if there are a lot of refs, they
often point to a smaller set of objects (in which case the
optimization in commit ea5f220 keeps our "n" small).
However, in pathological repositories (hundreds of thousands
of refs, each pointing to a unique commit), this quadratic
behavior can make a difference. Since we do not care about
the list order until we have finished building it, we can
simply keep it unsorted during the insertion phase, then
sort it afterwards.
On a repository like the one described above, this dropped
the time to do a no-op fetch from 2.0s to 1.7s. On normal
repositories, it probably does not matter at all, but it
does not hurt to protect ourselves from pathological cases.
Signed-off-by: Jeff King <redacted>
---
A note on the timings. I measured the times above last year when I wrote
the same patch here:
http://article.gmane.org/gmane.comp.version-control.git/194939
And earlier tonight, I did a fetch that showed the same result. But when
I tried to replicate it while writing the commit message, I had trouble,
because either:
1. I was fetching actual commits, in which case the more serious
problem behavior in find_common kicked in, ruining the measurement.
2. It was a no-op fetch, in which case quickfetch() kicked in and we
did not call mark_complete at all.
So I'm rather confused how I managed to get timings earlier (both last
year, and earlier today). But I still think it's an obviously correct
thing to do, and does protect us in case (1) above (actually fetching a
commit) once we fix the problem in find_common.
fetch-pack.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
From: Jeff King <hidden> Date: 2016-06-15 22:57:58
This helper function was introduced as a prio_queue
comparator to help topological sorting. However, other users
of prio_queue who want to replace commit_list_insert_by_date
will want to use it, too. So let's make it public.
Signed-off-by: Jeff King <redacted>
---
There is also compare_commits_by_author_date, but I expect it to be less
generally useful (especially because it relies on a slab), so I didn't
bother publicizing it. I think this is sufficient for now, and any
later users can make the author version public if they need to.
Note also that we have a similar comparison function,
commit_list_compare_by_date, which gets fed to the linked-list mergesort
for commit_list_sort_by_date. I was tempted to unify them, but we can't,
because it takes an actual "struct commit_list *", not a "struct commit
*" (and the logic is not so complex that it is worth factoring out to a
shared helper).
commit.c | 2 +-
commit.h | 2 ++
2 files changed, 3 insertions(+), 1 deletion(-)
@@ -581,7 +581,7 @@ static int compare_commits_by_author_date(const void *a_, const void *b_,return0;}-staticintcompare_commits_by_commit_date(constvoid*a_,constvoid*b_,void*unused)+intcompare_commits_by_commit_date(constvoid*a_,constvoid*b_,void*unused){conststructcommit*a=a_,*b=b_;/* newer commits with larger date first */
From: Jeff King <hidden> Date: 2016-06-15 22:57:58
When we call find_common to start finding common ancestors
with the remote side of a fetch, the first thing we do is
insert the tip of each ref into our rev_list linked list. We
keep the list sorted the whole time with
commit_list_insert_by_date, which means our insertion ends
up doing O(n^2) timestamp comparisons.
We could teach rev_list_push to use an unsorted list, and
then sort it once after we have added each ref. However, in
get_rev, we process the list by popping commits off the
front and adding parents back in timestamp-sorted order. So
that procedure would still operate on the large list.
Instead, we can replace the linked list with a heap-based
priority queue, which can do O(log n) insertion, making the
whole insertion procedure O(n log n).
As a result of switching to the prio_queue struct, we fix
two minor bugs:
1. When we "pop" a commit in get_rev, and when we clear
the rev_list in find_common, we do not take care to
free the "struct commit_list", and just leak its
memory. With the prio_queue implementation, the memory
management is handled for us.
2. In get_rev, we look at the head commit of the list,
possibly push its parents onto the list, and then "pop"
the front of the list off, assuming it is the same
element that we just peeked at. This is typically going
to be the case, but would not be in the face of clock
skew: the parents are inserted by date, and could
potentailly be inserted at the head of the list if they
have a timestamp newer than their descendent. In this
case, we would accidentally pop the parent, and never
process it at all.
The new implementation pulls the commit off of the
queue as we examine it, and so does not suffer from
this problem.
With this patch, a fetch of a single commit into a
repository with 50,000 refs went from:
real 0m7.984s
user 0m7.852s
sys 0m0.120s
to:
real 0m2.017s
user 0m1.884s
sys 0m0.124s
Before this patch, a larger case with 370K refs still had
not completed after tens of minutes; with this patch, it
completes in about 12 seconds.
Signed-off-by: Jeff King <redacted>
---
Not that it really matters, but Martin, note that your "one million
refs" case is actually more like 370K, because that is how many commits
there are in the linux.git repo. The rest of the lines written to your
packed-refs file are just bogus.
fetch-pack.c | 13 ++++++-------
1 file changed, 6 insertions(+), 7 deletions(-)
From: Eric Sunshine <hidden> Date: 2016-06-15 22:57:58
On Tue, Jul 2, 2013 at 2:24 AM, Jeff King [off-list ref] wrote:
When we call find_common to start finding common ancestors
with the remote side of a fetch, the first thing we do is
insert the tip of each ref into our rev_list linked list. We
keep the list sorted the whole time with
commit_list_insert_by_date, which means our insertion ends
up doing O(n^2) timestamp comparisons.
We could teach rev_list_push to use an unsorted list, and
then sort it once after we have added each ref. However, in
get_rev, we process the list by popping commits off the
front and adding parents back in timestamp-sorted order. So
that procedure would still operate on the large list.
Instead, we can replace the linked list with a heap-based
priority queue, which can do O(log n) insertion, making the
whole insertion procedure O(n log n).
As a result of switching to the prio_queue struct, we fix
two minor bugs:
1. When we "pop" a commit in get_rev, and when we clear
the rev_list in find_common, we do not take care to
free the "struct commit_list", and just leak its
memory. With the prio_queue implementation, the memory
management is handled for us.
2. In get_rev, we look at the head commit of the list,
possibly push its parents onto the list, and then "pop"
the front of the list off, assuming it is the same
element that we just peeked at. This is typically going
to be the case, but would not be in the face of clock
skew: the parents are inserted by date, and could
potentailly be inserted at the head of the list if they
s/potentailly/potentially/
have a timestamp newer than their descendent. In this
case, we would accidentally pop the parent, and never
process it at all.
The new implementation pulls the commit off of the
queue as we examine it, and so does not suffer from
this problem.
With this patch, a fetch of a single commit into a
repository with 50,000 refs went from:
real 0m7.984s
user 0m7.852s
sys 0m0.120s
to:
real 0m2.017s
user 0m1.884s
sys 0m0.124s
Before this patch, a larger case with 370K refs still had
not completed after tens of minutes; with this patch, it
completes in about 12 seconds.
Signed-off-by: Jeff King <redacted>
From: Martin Fick <hidden> Date: 2016-06-15 22:57:58
On Tuesday, July 02, 2013 12:11:49 am Jeff King wrote:
Here are my patches to deal with Martin's pathological
case, split out for easy reading. I took a few timings
to show that the results of the 3rd patch are noticeable
even with 50,000 unique refs (which is still a lot, but
something that I could conceive of a busy repo
accumulating over time).
[1/3]: fetch-pack: avoid quadratic list insertion in
mark_complete [2/3]: commit.c: make
compare_commits_by_commit_date global [3/3]: fetch-pack:
avoid quadratic behavior in rev_list_push
And here's the diffstat to prove it is really not scary.
:)
commit.c | 2 +-
commit.h | 2 ++
fetch-pack.c | 16 ++++++++--------
3 files changed, 11 insertions(+), 9 deletions(-)
-Peff
I applied these 3 patches and it indeed improves things
dramatically. Thanks Peff, you are awesome!!!
The synthetic test case (but sorted), now comes in at around
15s. The more important real world case (for us), fetching
from my production server, which took around 12mins
previously, now takes around 30s (I think the extra time is
now spent on the Gerrit server, but I will investigate that
a bit more)! That is very significant and should make many
workflows much more efficient. +1 for merging this. :)
Again, thanks,
-Martin
Note, I tested git-next 1.8.3.2.883.g27cfd27 to be sure that
it is still problematic without this patch, it is (running
for 10mins now without completing).
--
The Qualcomm Innovation Center, Inc. is a member of Code
Aurora Forum, hosted by The Linux Foundation