On Tue, May 21, 2019 at 1:24 PM Pierre-Yves David < 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>> 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>> 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>>> > > > 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>>> > > > # 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. > > Cheers, > > -- > Pierre-Yves David >
_______________________________________________ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel