Patchwork [RFC] cg1packer: use fastpath when changesets are not skipped or reordered

login
register
mail settings
Submitter Mike Hommey
Date April 12, 2015, 11:15 p.m.
Message ID <1428880529-25632-1-git-send-email-mh@glandium.org>
Download mbox | patch
Permalink /patch/8626/
State Changes Requested
Delegated to: Pierre-Yves David
Headers show

Comments

Mike Hommey - April 12, 2015, 11:15 p.m.
The current heuristic is that we can use the fast path when the repo is
not filtered and the requested heads match the topological heads. This
leaves out a lot of cases where the fast path would work just fine.

The most obvious one is when there is a race between a push and a http
pull, where the puller gets heads before the push, and does the getbundle
after, in which case the fast path is not taken because the pulled heads
are not topological heads anymore. A sibling case is when the puller
requests non-topological heads (such as branch heads that were subsequently
merged), or any changeset that appears in the history of another.

This changes the heuristic to use the fast path when all changesets in the
generated changegroup are in the same order as in the unfiltered repository,
and none are skipped.

This could be further improved by e.g. using the fast path for changeset up
until the first skipped or reordered one.

This partially addresses issue4595.

I'm not sure how this issue affects bundle2.

The effect of this patch can be seen on the mercurial repo:
$ hg log -l2 --template '{node|short}\n'
52ff737c63d2
553dc2b094d9

Before this patch:
$ time hg bundle --all -t none -r 52ff737c63d2 /tmp/hg.hg
24698 changesets found

real	0m4.361s
user	0m4.288s
sys	0m0.072s
$ time hg bundle --all -t none -r 553dc2b094d9 /tmp/hg.hg
24697 changesets found

real	0m7.201s
user	0m7.028s
sys	0m0.176s

After this patch:
$ time hg bundle --all -t none -r 553dc2b094d9 /tmp/hg.hg
24697 changesets found

real	0m4.330s
user	0m4.260s
sys	0m0.076s

Pulling with skipped changesets still triggers the slow path:
$ time hg bundle --all -t none -r 85219d6ece67 /tmp/hg.hg
24581 changesets found

real	0m7.264s
user	0m7.120s
sys	0m0.148s

(This kind of case would benefit from the proposed further improvement)

On mozilla-central, the slow path is 20+ minutes, compared to 2:20 for the
fast path, so it is critical to avoid the slow path as much as possible.
Mike Hommey - April 12, 2015, 11:40 p.m.
On Mon, Apr 13, 2015 at 08:15:29AM +0900, Mike Hommey wrote:
> The current heuristic is that we can use the fast path when the repo is
> not filtered and the requested heads match the topological heads. This
> leaves out a lot of cases where the fast path would work just fine.
> 
> The most obvious one is when there is a race between a push and a http
> pull, where the puller gets heads before the push, and does the getbundle
> after, in which case the fast path is not taken because the pulled heads
> are not topological heads anymore. A sibling case is when the puller
> requests non-topological heads (such as branch heads that were subsequently
> merged), or any changeset that appears in the history of another.

Another legitimate case, which is not covered by this patch:
- consider a changelog like the following:

@  2
|
| o  1
|/
o  0

- local clone has 0:1.
- pulling 2 uses the slow path because `heads` in getsubsetraw only
  contains the nodeid for rev 2, while repo.heads contains 1 and 2.

Mike
Mike Hommey - April 12, 2015, 11:59 p.m.
On Mon, Apr 13, 2015 at 08:40:26AM +0900, Mike Hommey wrote:
> On Mon, Apr 13, 2015 at 08:15:29AM +0900, Mike Hommey wrote:
> > The current heuristic is that we can use the fast path when the repo is
> > not filtered and the requested heads match the topological heads. This
> > leaves out a lot of cases where the fast path would work just fine.
> > 
> > The most obvious one is when there is a race between a push and a http
> > pull, where the puller gets heads before the push, and does the getbundle
> > after, in which case the fast path is not taken because the pulled heads
> > are not topological heads anymore. A sibling case is when the puller
> > requests non-topological heads (such as branch heads that were subsequently
> > merged), or any changeset that appears in the history of another.
> 
> Another legitimate case, which is not covered by this patch:
> - consider a changelog like the following:
> 
> @  2
> |
> | o  1
> |/
> o  0
> 
> - local clone has 0:1.
> - pulling 2 uses the slow path because `heads` in getsubsetraw only
>   contains the nodeid for rev 2, while repo.heads contains 1 and 2.

In fact, the reason why this case is not covered by this patch also
makes this patch regress the case where the local clone has 0 and we
pull 1 and 2, which does use the fast path before the patch but not
after.

Mike
Pierre-Yves David - April 14, 2015, 8:36 p.m.
On 04/12/2015 07:59 PM, Mike Hommey wrote:
> On Mon, Apr 13, 2015 at 08:40:26AM +0900, Mike Hommey wrote:
>> On Mon, Apr 13, 2015 at 08:15:29AM +0900, Mike Hommey wrote:
>>> The current heuristic is that we can use the fast path when the repo is
>>> not filtered and the requested heads match the topological heads. This
>>> leaves out a lot of cases where the fast path would work just fine.
>>>
>>> The most obvious one is when there is a race between a push and a http
>>> pull, where the puller gets heads before the push, and does the getbundle
>>> after, in which case the fast path is not taken because the pulled heads
>>> are not topological heads anymore. A sibling case is when the puller
>>> requests non-topological heads (such as branch heads that were subsequently
>>> merged), or any changeset that appears in the history of another.
>>
>> Another legitimate case, which is not covered by this patch:
>> - consider a changelog like the following:
>>
>> @  2
>> |
>> | o  1
>> |/
>> o  0
>>
>> - local clone has 0:1.
>> - pulling 2 uses the slow path because `heads` in getsubsetraw only
>>    contains the nodeid for rev 2, while repo.heads contains 1 and 2.
>
> In fact, the reason why this case is not covered by this patch also
> makes this patch regress the case where the local clone has 0 and we
> pull 1 and 2, which does use the fast path before the patch but not
> after.

I've confused. Why do we not use the fast path after that.

the second question is: What is the performance impact of computing this 
"fast-passable" thing?

Could we do some lazy approach that use the fast path as long as 
possible and just fallback to the slow old (in the middle of the bundle 
generation) whenever something is skipped?

Why is this patch RFC only (what do you think needs to be 
improved/discussed/clarify before moving forward).
Mike Hommey - April 14, 2015, 9:42 p.m.
On Tue, Apr 14, 2015 at 04:36:33PM -0400, Pierre-Yves David wrote:
> 
> 
> On 04/12/2015 07:59 PM, Mike Hommey wrote:
> >On Mon, Apr 13, 2015 at 08:40:26AM +0900, Mike Hommey wrote:
> >>On Mon, Apr 13, 2015 at 08:15:29AM +0900, Mike Hommey wrote:
> >>>The current heuristic is that we can use the fast path when the repo is
> >>>not filtered and the requested heads match the topological heads. This
> >>>leaves out a lot of cases where the fast path would work just fine.
> >>>
> >>>The most obvious one is when there is a race between a push and a http
> >>>pull, where the puller gets heads before the push, and does the getbundle
> >>>after, in which case the fast path is not taken because the pulled heads
> >>>are not topological heads anymore. A sibling case is when the puller
> >>>requests non-topological heads (such as branch heads that were subsequently
> >>>merged), or any changeset that appears in the history of another.
> >>
> >>Another legitimate case, which is not covered by this patch:
> >>- consider a changelog like the following:
> >>
> >>@  2
> >>|
> >>| o  1
> >>|/
> >>o  0
> >>
> >>- local clone has 0:1.
> >>- pulling 2 uses the slow path because `heads` in getsubsetraw only
> >>   contains the nodeid for rev 2, while repo.heads contains 1 and 2.
> >
> >In fact, the reason why this case is not covered by this patch also
> >makes this patch regress the case where the local clone has 0 and we
> >pull 1 and 2, which does use the fast path before the patch but not
> >after.
> 
> I've confused. Why do we not use the fast path after that.

Because the revision numbers don't start at 0, and that makes the
heuristic in the patch fail.

> the second question is: What is the performance impact of computing this
> "fast-passable" thing?

Negligible. I haven't seen a notable difference between before and
after.

> Could we do some lazy approach that use the fast path as long as possible
> and just fallback to the slow old (in the middle of the bundle generation)
> whenever something is skipped?

That was kind of what I was suggesting as a future improvement.

> Why is this patch RFC only (what do you think needs to be
> improved/discussed/clarify before moving forward).

Because I wasn't sure the approach was right, and sure enough, 2
messages later I figured it introduced a regression. And maybe we'd be
better off with a more aggressive approach, trying to minimize the slow
path even more.

Mike

PS: the funny thing is that the slow path is based on data that may not
be accurate (as the mozilla-central history demonstrates), but
fortunately, /shouldn't/ indicate new files that aren't new. That's
funny because if it was happening, then the slow path would need to be
even slower.
Pierre-Yves David - May 12, 2015, 8:10 p.m.
On 04/14/2015 02:42 PM, Mike Hommey wrote:
> On Tue, Apr 14, 2015 at 04:36:33PM -0400, Pierre-Yves David wrote:
>>
>>
>> On 04/12/2015 07:59 PM, Mike Hommey wrote:
>>> On Mon, Apr 13, 2015 at 08:40:26AM +0900, Mike Hommey wrote:
>>>> On Mon, Apr 13, 2015 at 08:15:29AM +0900, Mike Hommey wrote:
>>>>> The current heuristic is that we can use the fast path when the repo is
>>>>> not filtered and the requested heads match the topological heads. This
>>>>> leaves out a lot of cases where the fast path would work just fine.
>>>>>
>>>>> The most obvious one is when there is a race between a push and a http
>>>>> pull, where the puller gets heads before the push, and does the getbundle
>>>>> after, in which case the fast path is not taken because the pulled heads
>>>>> are not topological heads anymore. A sibling case is when the puller
>>>>> requests non-topological heads (such as branch heads that were subsequently
>>>>> merged), or any changeset that appears in the history of another.
>>>>
>>>> Another legitimate case, which is not covered by this patch:
>>>> - consider a changelog like the following:
>>>>
>>>> @  2
>>>> |
>>>> | o  1
>>>> |/
>>>> o  0
>>>>
>>>> - local clone has 0:1.
>>>> - pulling 2 uses the slow path because `heads` in getsubsetraw only
>>>>    contains the nodeid for rev 2, while repo.heads contains 1 and 2.
>>>
>>> In fact, the reason why this case is not covered by this patch also
>>> makes this patch regress the case where the local clone has 0 and we
>>> pull 1 and 2, which does use the fast path before the patch but not
>>> after.
>>
>> I've confused. Why do we not use the fast path after that.
>
> Because the revision numbers don't start at 0, and that makes the
> heuristic in the patch fail.
>
>> the second question is: What is the performance impact of computing this
>> "fast-passable" thing?
>
> Negligible. I haven't seen a notable difference between before and
> after.
>
>> Could we do some lazy approach that use the fast path as long as possible
>> and just fallback to the slow old (in the middle of the bundle generation)
>> whenever something is skipped?
>
> That was kind of what I was suggesting as a future improvement.
>
>> Why is this patch RFC only (what do you think needs to be
>> improved/discussed/clarify before moving forward).
>
> Because I wasn't sure the approach was right, and sure enough, 2
> messages later I figured it introduced a regression. And maybe we'd be
> better off with a more aggressive approach, trying to minimize the slow
> path even more.
>
> Mike
>
> PS: the funny thing is that the slow path is based on data that may not
> be accurate (as the mozilla-central history demonstrates), but
> fortunately, /shouldn't/ indicate new files that aren't new. That's
> funny because if it was happening, then the slow path would need to be
> even slower.

I think martin did some work in this area recently. And your patch does 
not apply anymore.

Can you have a look at what martin did and wrote about it and come back 
with a V2 and new data?
Mike Hommey - May 14, 2015, 4:21 a.m.
On Tue, May 12, 2015 at 01:10:25PM -0700, Pierre-Yves David wrote:
> >Because I wasn't sure the approach was right, and sure enough, 2
> >messages later I figured it introduced a regression. And maybe we'd be
> >better off with a more aggressive approach, trying to minimize the slow
> >path even more.
> >
> >Mike
> >
> >PS: the funny thing is that the slow path is based on data that may not
> >be accurate (as the mozilla-central history demonstrates), but
> >fortunately, /shouldn't/ indicate new files that aren't new. That's
> >funny because if it was happening, then the slow path would need to be
> >even slower.
> 
> I think martin did some work in this area recently. And your patch does not
> apply anymore.
> 
> Can you have a look at what martin did and wrote about it and come back with
> a V2 and new data?

AIUI, the changes he did made the slow path be used in more cases than
before, so there is no change wrt the original issue. Running the same
commands as in the original patch message still lead to the same
timings. OTOH the original patch was also buggy, so /that/ would need to
be addressed. At this point, I'd rather someone who actually know this
code took a look.

Mike
Martin von Zweigbergk - May 14, 2015, 4:32 a.m.
On Wed, May 13, 2015 at 9:21 PM Mike Hommey <mh@glandium.org> wrote:

> On Tue, May 12, 2015 at 01:10:25PM -0700, Pierre-Yves David wrote:
> > >Because I wasn't sure the approach was right, and sure enough, 2
> > >messages later I figured it introduced a regression. And maybe we'd be
> > >better off with a more aggressive approach, trying to minimize the slow
> > >path even more.
> > >
> > >Mike
> > >
> > >PS: the funny thing is that the slow path is based on data that may not
> > >be accurate (as the mozilla-central history demonstrates), but
> > >fortunately, /shouldn't/ indicate new files that aren't new. That's
> > >funny because if it was happening, then the slow path would need to be
> > >even slower.
> >
> > I think martin did some work in this area recently. And your patch does
> not
> > apply anymore.
> >
> > Can you have a look at what martin did and wrote about it and come back
> with
> > a V2 and new data?
>
> AIUI, the changes he did made the slow path be used in more cases than
> before,


I'm currently away from work with limited time to check, but I think I only
refactored and documented the behavior. I don't remember intentionally
changing it.


> so there is no change wrt the original issue. Running the same
> commands as in the original patch message still lead to the same
> timings. OTOH the original patch was also buggy, so /that/ would need to
> be addressed. At this point, I'd rather someone who actually know this
> code took a look.
>

I'll set a reminder for myself to look into this some time after I get back
to work.


>
> Mike
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
>

Patch

diff --git a/mercurial/changegroup.py b/mercurial/changegroup.py
index 82481ec..8c32f16 100644
--- a/mercurial/changegroup.py
+++ b/mercurial/changegroup.py
@@ -283,7 +283,7 @@  class cg1packer(object):
         if bundlecaps is None:
             bundlecaps = set()
         self._bundlecaps = bundlecaps
-        self._changelog = repo.changelog
+        self._changelog = repo.unfiltered().changelog
         self._manifest = repo.manifest
         reorder = repo.ui.config('bundle', 'reorder', 'auto')
         if reorder == 'auto':
@@ -387,6 +387,10 @@  class cg1packer(object):
                                 reorder=reorder):
             size += len(chunk)
             yield chunk
+
+        fastpathlinkrev = (fastpathlinkrev or
+            all(n == cl.rev(x) for x, n in clrevorder.iteritems()))
+
         self._verbosenote(_('%8.i (changelog)\n') % size)
         progress(msgbundling, None)
 
@@ -550,12 +554,10 @@  def getsubsetraw(repo, outgoing, bundler, source, fastpath=False):
     # heads have been requested (since we then know there all linkrevs will
     # be pulled by the client).
     heads.sort()
-    fastpathlinkrev = fastpath or (
-            repo.filtername is None and heads == sorted(repo.heads()))
 
     repo.hook('preoutgoing', throw=True, source=source)
     _changegroupinfo(repo, csets, source)
-    return bundler.generate(commonrevs, csets, fastpathlinkrev, source)
+    return bundler.generate(commonrevs, csets, fastpath, source)
 
 def getsubset(repo, outgoing, bundler, source, fastpath=False, version='01'):
     gengroup = getsubsetraw(repo, outgoing, bundler, source, fastpath)