D2647: setdiscovery: make progress on most connected groups each roundtrip

[martinvonz (Martin von Zweigbergk)]

martinvonz added a comment.


  In https://phab.mercurial-scm.org/D2647#93258, @martinvonz wrote:
  
  > In https://phab.mercurial-scm.org/D2647#93256, @marmoute wrote:
  >
  > > I feel like I am missing something. Your commit message seems to be talking using at least as many item in the sameple than there is independant connected set. However your code seems to use "heads(undecided)" that is a quite different. Using independant connected set seems like a good trade off (but might be expensive to compute). Using all heads can significantly bloat the discovery without giving it a significant edge in many cases.
  >
  >
  > Good point. The case I can think of is when you have a tree of commits on the local side. Something like this:
  >
  >   o
  >   | o
  >   | | o
  >   | | | o
  >   | | |/
  >   | |/
  >   | o
  >   | |
  >   | o
  >   | |
  >   | o
  >   |/
  >   o
  >   ~
  >   
  >
  > If we have a long sequence of commits there and many heads, we would increase the sampling of the (mostly-)linear part unnecessarily. I'll see if there's an easy way to improve that.
  
  
  I think it was as easy as changing from using number of heads to using number of roots. Do you think there are still cases we'd handle poorly? I think there are things we can improve in the size-limited case too (it seems like it should be better to include certain points, like the mid-point, than to pick randomly), but that's a bigger task that I'm not willing to start working on now.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D2647

To: martinvonz, #hg-reviewers, indygreg, marmoute
Cc: indygreg, mercurial-devel