[PATCH 2 of 6 V2] hidden: use _domainancestors to compute revs revealed by dynamic blocker

[Martin von Zweigbergk]

On Tue, May 23, 2017 at 9:04 PM, Martin von Zweigbergk
<martinvonz at google.com> wrote:
> On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc at gmail.com> wrote:
>> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
>> <pierre-yves.david at ens-lyon.org> wrote:
>>>
>>> # HG changeset patch
>>> # User Pierre-Yves David <pierre-yves.david at octobus.net>
>>> # Date 1495373721 -7200
>>> #      Sun May 21 15:35:21 2017 +0200
>>> # Node ID e72ddd1a53c4c6321e7ecd686cd24c2a8c8914bc
>>> # Parent  5f964af88a0fae242ce24b0478c676d2056e0dc6
>>> # EXP-Topic fast-compute-hidden
>>> # Available At
>>> https://www.mercurial-scm.org/repo/users/marmoute/mercurial/
>>> #              hg pull
>>> https://www.mercurial-scm.org/repo/users/marmoute/mercurial/ -r e72ddd1a53c4
>>> hidden: use _domainancestors to compute revs revealed by dynamic blocker
>>>
>>> The complexity of computing the revealed changesets is now 'O(revealed)'.
>>> This massively speeds up the computation on large repository. Moving it to
>>> the
>>> millisecond range.
>>>
>>> Below are timing from two Mozilla repositories with different contents:
>
> Timing of what? How can I run the test on hg core for comparison?
>
>>>
>>> 1) mozilla repository with:
>>>  * 400667 changesets
>>>  * 35 hidden changesets (first rev-268334)
>>>  * 288 visible drafts
>>>  * obsolete working copy (dynamicblockers),
>>>
>>> Before:
>>> ! visible
>>> ! wall 0.030247 comb 0.030000 user 0.030000 sys 0.000000 (best of 100)
>>>
>>> After:
>>> ! visible
>>> ! wall 0.000585 comb 0.000000 user 0.000000 sys 0.000000 (best of 4221)
>>>
>>> The timing above include the computation of obsolete changeset:
>>> ! obsolete
>>> ! wall 0.000396 comb 0.000000 user 0.000000 sys 0.000000 (best of 6816)
>>>
>>> So adjusted time give 30ms before versus 0.2ms after. A 150x speedup.
>>>
>>> 2) mozilla repository with:
>>>  * 405645 changesets
>>>  * 4312 hidden changesets (first rev-326004)
>>>  * 264 visible drafts
>>>  * obsolete working copy (dynamicblockers),
>>>
>>> Before:
>>> ! visible
>>> ! wall 0.168658 comb 0.170000 user 0.170000 sys 0.000000 (best of 48)
>>>
>>> After
>>> ! visible
>>> ! wall 0.008612 comb 0.010000 user 0.010000 sys 0.000000 (best of 325)
>>>
>>> The timing above include the computation of obsolete changeset:
>>> ! obsolete
>>> ! wall 0.006408 comb 0.010000 user 0.010000 sys 0.000000 (best of 404)
>>>
>>> So adjusted time give 160ms before versus 2ms after. A 75x speedup.
>>>
>>> diff --git a/mercurial/repoview.py b/mercurial/repoview.py
>>> --- a/mercurial/repoview.py
>>> +++ b/mercurial/repoview.py
>>> @@ -212,8 +212,10 @@ def computehidden(repo):
>>>          # changesets and remove those.
>>>          dynamic = hidden & revealedrevs(repo)
>>>          if dynamic:
>>> -            blocked = cl.ancestors(dynamic, inclusive=True)
>>> -            hidden = frozenset(r for r in hidden if r not in blocked)
>>
>>
>> An obvious problem with this old code is that the "r not in blocked" bit is
>> an O(n) list lookup. Out of curiosity, how does the perf of "blocked =
>> set(cl.ancestors(dynamic, inclusive=True))" compare to the new code using
>> _domainancestors()?
>
> Good point. If it does make a difference to switch to a set, I'd
> appreciate if we could get that in a separate patch.
>
>>
>>>
>>> +            pfunc = cl.parentrevs
>>> +            mutablephases = (phases.draft, phases.secret)
>>> +            mutable = repo._phasecache.getrevset(repo, mutablephases)
>>> +            hidden = hidden - _domainancestors(pfunc, dynamic, mutable)

The call to _domainancestors() looks similar to cl.findmissingrevs()
with "common" set to the parents of the mutable phase roots and
heads=dynamic. Would that work? Would it be slower?

>>>      return hidden
>>>
>>>  def computeunserved(repo):
>>> _______________________________________________
>>> Mercurial-devel mailing list
>>> Mercurial-devel at mercurial-scm.org
>>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>
>>
>>
>> _______________________________________________
>> Mercurial-devel mailing list
>> Mercurial-devel at mercurial-scm.org
>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>