Complexity of operations in Mercurial

[Martin Geisler]

Dirkjan Ochtman <dirkjan at ochtman.nl> writes:

> On Tue, Feb 7, 2012 at 10:14, Martin Geisler <mg at lazybytes.net> wrote:
>> This question was asked recently on Stack Overflow:
>>
>>  http://stackoverflow.com/q/9169598/110204
>>
>> It's about how closed branches affect the performance. Do we have a
>> wiki page (or some other reference) that details the complexity of
>> various operations like 'hg commit', 'hg tag', 'hg pull'?
>
> IIRC most of the issues here are solved by the branchheads cache that
> we've had for a while now.

Right, that should make it fast to find branch heads.

> The idea here is that, to find tags, you need to parse contents from
> the .hgtags for every head. Searching for all the heads used to be
> slow, but is probably okay now. Extracting .hgtags from the manifest
> and parsing it might still get slow on a really large scale.

I think this is something else? We also have a tagscache that prevents
us from looking up .hgtags files on every head. Greg should know much
more about this.

> For commit, I can't think of any issues relating to the number of
> heads or branches off the top of my head. For pull, deciding what
> changesets to transfer is probably harder in the face of lots of
> heads. The newish sampling has probably improved the worst-case
> scenario here?

I seem to recall that the heads are still exchanged in the first round.
I looked briefly at setdiscovery just now and see things like

  def findcommonheads(ui, local, remote,
                      initialsamplesize=100,
                      fullsamplesize=200,

which suggests that we only send up to 100 nodes in the first sample and
no more than 200 in later rounds. Is that correct? That would be great
since that avoids the direct dependency on the number of heads.


-- 
Martin Geisler

Mercurial links: http://mercurial.ch/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: <http://selenic.com/pipermail/mercurial-devel/attachments/20120207/c0312411/attachment.pgp>