On 5/21/19 10:40 PM, Martin von Zweigbergk wrote:
On Tue, May 21, 2019 at 1:24 PM Pierre-Yves David
<pierre-yves.da...@ens-lyon.org <mailto:pierre-yves.da...@ens-lyon.org>>
wrote:
On 5/21/19 10:00 PM, Martin von Zweigbergk wrote:
>
>
> On Tue, May 21, 2019 at 11:10 AM Martin von Zweigbergk
> <martinv...@google.com <mailto:martinv...@google.com>
<mailto:martinv...@google.com <mailto:martinv...@google.com>>> wrote:
>
>
>
> On Tue, May 21, 2019 at 10:09 AM Pierre-Yves David
> <pierre-yves.da...@ens-lyon.org
<mailto:pierre-yves.da...@ens-lyon.org>
> <mailto:pierre-yves.da...@ens-lyon.org
<mailto:pierre-yves.da...@ens-lyon.org>>> wrote:
>
>
>
> On 5/21/19 6:05 PM, Martin von Zweigbergk wrote:
> >
> >
> > On Tue, May 21, 2019 at 4:22 AM Pierre-Yves David
> > <pierre-yves.da...@ens-lyon.org
<mailto:pierre-yves.da...@ens-lyon.org>
> <mailto:pierre-yves.da...@ens-lyon.org
<mailto:pierre-yves.da...@ens-lyon.org>>
> <mailto:pierre-yves.da...@ens-lyon.org
<mailto:pierre-yves.da...@ens-lyon.org>
> <mailto:pierre-yves.da...@ens-lyon.org
<mailto:pierre-yves.da...@ens-lyon.org>>>>
> > wrote:
> >
> > # HG changeset patch
> > # User Pierre-Yves David
<pierre-yves.da...@octobus.net <mailto:pierre-yves.da...@octobus.net>
> <mailto:pierre-yves.da...@octobus.net
<mailto:pierre-yves.da...@octobus.net>>
> > <mailto:pierre-yves.da...@octobus.net
<mailto:pierre-yves.da...@octobus.net>
> <mailto:pierre-yves.da...@octobus.net
<mailto:pierre-yves.da...@octobus.net>>>>
> > # Date 1558436902 -7200
> > # Tue May 21 13:08:22 2019 +0200
> > # Node ID 123267b121ea268b3bc488c6dde68a8d93ee4f4c
> > # Parent 86f17fc31aa8a0c26c11db6a532293463ee6428a
> > # EXP-Topic discovery
> > # Available At
https://bitbucket.org/octobus/mercurial-devel/
> > # hg pull
> > https://bitbucket.org/octobus/mercurial-devel/ -r
123267b121ea
> > discovery: slowly increase sampling size
> >
> > Some pathological discovery runs can requires many
> roundtrip. When
> > this happens
> > things can get very slow.
> >
> > To make the algorithm more resilience again such
> pathological case.
> > We slowly
> > increase the sample size with each roundtrip
(+5%). This
> will have a
> > negligible
> > impact on "normal" discovery with few roundtrips,
but a large
> > positive impact of
> > case with many roundtrips. Asking more question per
> roundtrip helps
> > to reduce
> > the undecided set faster. Instead of reducing the
> undecided set a
> > linear speed
> > (in the worst case), we reduce it as a guaranteed
(small)
> > exponential rate. The
> > data below show this slow ramp up in sample size:
> >
> > round trip | 1 | 5 | 10 | 20 |
50 |
> 100 |
> > 130 |
> > sample size | 200 | 254 | 321 | 517 | 2
199 |
> 25 123 |
> > 108 549 |
> > covered nodes | 200 | 1 357 | 2 821 | 7 031 | 42
658 |
> 524 530 | 2
> > 276 755 |
> >
> > To be a bit more concrete, lets take a very
pathological
> case as an
> > example. We
> > are doing discovery from a copy of Mozilla-try to
a more
> recent
> > version of
> > mozilla-unified. Mozilla-unified heads are unknown
to the
> > mozilla-try repo and
> > there are over 1 million "missing" changesets. (the
> discovery is
> > "local" to
> > avoid network interference)
> >
> >
> > What makes it slow in that case? If the 1 million
changesets
> are mostly
> > linear, it should still be fast, right? So I assume
they're
> spread out
> > across branches. Is it slow because the remote side
has many
> branches
> > that the local side does not, or the other way around?
>
> The million changeset are on many different branches. (the
> discovery is
> run from mozilla-try (many changesets, tree like) toward
> mozilla-unified
> (mostly linear).
>
>
> I think that means that there are many local heads. Maybe
it's the
> case I tried to address with
https://phab.mercurial-scm.org/D2647. I
> just re-opened that. I'll see if can get timing numbers for the
> repos you mentioned here.
I had a look at this commit. The idea in your commit message is
interesting, but I see a different one implemented in the code. See my
comment for details.
> That's now done. I've added you as reviewer. I feel like that's a
better
> solution for this particular case. It results in significantly more
> bytes transferred (+25%), but it's also much faster.
As said before in the scope of this series, I am not interest in any
better solution any particular case. I am working on a general purpose
safety net that improves the upper bound round trip complexity for
every
pathological cases.
The good point of this safety net is that it is not mutually exclusive
with improving for particular cases. For example, you change and my
change could peacefully coexist.
Can we move forward with this patch before discussing more specific
change?
I'm not sure what other pathological cases remain after that one is
fixed, but sure, I'll queue this anyway.
The nice thing with this patch, is that it does not matters, whatever
other pathological cases lurk in the shadow got better ;-)
--
Pierre-Yves David
_______________________________________________
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel