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

login
register
mail settings
Submitter Pierre-Yves David
Date May 23, 2017, 8:02 p.m.
Message ID <e72ddd1a53c4c6321e7e.1495569750@nodosa.octopoid.net>
Download mbox | patch
Permalink /patch/20866/
State Changes Requested
Headers show

Comments

Pierre-Yves David - May 23, 2017, 8:02 p.m.
# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@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:

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.
Gregory Szorc - May 24, 2017, 2:10 a.m.
On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David <
pierre-yves.david@ens-lyon.org> wrote:

> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david@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:
>
> 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()?


> +            pfunc = cl.parentrevs
> +            mutablephases = (phases.draft, phases.secret)
> +            mutable = repo._phasecache.getrevset(repo, mutablephases)
> +            hidden = hidden - _domainancestors(pfunc, dynamic, mutable)
>      return hidden
>
>  def computeunserved(repo):
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
via Mercurial-devel - May 24, 2017, 4:04 a.m.
On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc@gmail.com> wrote:
> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
> <pierre-yves.david@ens-lyon.org> wrote:
>>
>> # HG changeset patch
>> # User Pierre-Yves David <pierre-yves.david@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)
>>      return hidden
>>
>>  def computeunserved(repo):
>> _______________________________________________
>> Mercurial-devel mailing list
>> Mercurial-devel@mercurial-scm.org
>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
>
>
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
via Mercurial-devel - May 24, 2017, 4:43 a.m.
On Tue, May 23, 2017 at 9:04 PM, Martin von Zweigbergk
<martinvonz@google.com> wrote:
> On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc@gmail.com> wrote:
>> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
>> <pierre-yves.david@ens-lyon.org> wrote:
>>>
>>> # HG changeset patch
>>> # User Pierre-Yves David <pierre-yves.david@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@mercurial-scm.org
>>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>
>>
>>
>> _______________________________________________
>> Mercurial-devel mailing list
>> Mercurial-devel@mercurial-scm.org
>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>
Pierre-Yves David - May 24, 2017, 12:39 p.m.
On 05/24/2017 04:10 AM, Gregory Szorc wrote:
> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
> <pierre-yves.david@ens-lyon.org <mailto:pierre-yves.david@ens-lyon.org>>
> wrote:
>
>     # HG changeset patch
>     # User Pierre-Yves David <pierre-yves.david@octobus.net
>     <mailto:pierre-yves.david@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/
>     <https://www.mercurial-scm.org/repo/users/marmoute/mercurial/>
>     #              hg pull
>     https://www.mercurial-scm.org/repo/users/marmoute/mercurial/
>     <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:
>
>     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.

Actually, this is not a list lookup. `cl.ancestors` returns a smart lazy 
ancestors[1]. The object use a set for membership testing[2] and walk 
the changelog on demands for it ('r in lazyancestors' stop walking once 
'r' has been passed).

[1] code for changelog.ancestors:
 
https://www.mercurial-scm.org/repo/hg/file/bdc4861ffe59/mercurial/revlog.py#l574
[2] lazy ancestors membership lookup:
 
https://www.mercurial-scm.org/repo/hg/file/bdc4861ffe59/mercurial/ancestor.py#l334

> Out of curiosity, how does the perf of "blocked
> = set(cl.ancestors(dynamic, inclusive=True))" compare to the new code
> using _domainancestors()?

Calling "set" on the lazy ancestors will force the object to iterate 
down to the bottom of the repository. That will not raise better result.

The speed up in this patch come from a drastically change the asymptotic 
complexity:
- from: O(len(repo) - O(rev(first(not public)))
- to:   O(len(mutable & visible))

[details below]


Complexity of the old code
==========================

the old code naively search ancestors without taking phases into 
account. This means we'll walk a large amount of public changesets to 
check if an old (non public) changeset is the ancestor or a recent revision.

Before this patch, we call:

     hiderablerevs in cl.ancestors(blockers)

We can reduced (complexity meaning "reduction) tp:

     min(hideablerevs) in ancestors(max(blockers)

Which can be reduced to:

     target = min(hideablerevs)
     current = max(blocker)
     while target < current:
         current = parent(current) # one parent to simplify

Complexity of the new code
==========================

The new could walk find blockers and walk from them. Stopping as soon as 
we reach public (non-mutable) changeset. So we do not walk more 
changeset that the one that will be visible.

A basic version of that new code is:

     # code is a bit wider for clarity
     actual_blockers = hideable & blockers
     revealed = set()
     for current in actual_blockers:
         while not public(current):
	    revealed.add(current)
             current = parent(current)
     hidden = hideable - revealed

Is the situation clearer to you now?

Cheers,
Pierre-Yves David - May 24, 2017, 12:42 p.m.
On 05/24/2017 06:04 AM, Martin von Zweigbergk wrote:
> On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc@gmail.com> wrote:
>> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
>> <pierre-yves.david@ens-lyon.org> wrote:
>>>
>>> # HG changeset patch
>>> # User Pierre-Yves David <pierre-yves.david@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?

Ha, good point. Using the perf extension:

   hg perfvolatileset obsolete visible

>>> 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.

(see my reply to Greg about why moving to set will hurt)

Cheers,
Pierre-Yves David - May 24, 2017, 12:52 p.m.
On 05/24/2017 06:43 AM, Martin von Zweigbergk wrote:
> On Tue, May 23, 2017 at 9:04 PM, Martin von Zweigbergk
> <martinvonz@google.com> wrote:
>> On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc@gmail.com> wrote:
>>> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
>>> <pierre-yves.david@ens-lyon.org> wrote:
>>>>
>>>> # HG changeset patch
>>>> # User Pierre-Yves David <pierre-yves.david@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?

There are quite similar but differs a bit.

In 'findmissingrevs':
   - heads: source of the iteration over parents,
   - common: iteration should stop when reaching "common",

In 'domainancestors':
   - revs: source of the iteration over parents,
   - domain: iteration should stop when exiting "domain",

The distinction is critical because in our case, it is simple and fast 
to compute "domain" while we do not have "common" accessible in any easy 
way.

(also, 'findcommonmissing' use a complex object to allow iterative 
computation while we know we will need the full set. [However, we could 
use the lazy object and turn it into C if more speed is necessary])

Cheers,
via Mercurial-devel - May 24, 2017, 5:08 p.m.
On Wed, May 24, 2017 at 5:42 AM, Pierre-Yves David
<pierre-yves.david@ens-lyon.org> wrote:
>
>
> On 05/24/2017 06:04 AM, Martin von Zweigbergk wrote:
>>
>> On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc@gmail.com>
>> wrote:
>>>
>>> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
>>> <pierre-yves.david@ens-lyon.org> wrote:
>>>>
>>>>
>>>> # HG changeset patch
>>>> # User Pierre-Yves David <pierre-yves.david@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?
>
>
> Ha, good point. Using the perf extension:
>
>   hg perfvolatileset obsolete visible

Do I just run "./hg perfvolatileset obsolete visible"? If I do that on
the hg core repo, I get these results:

Before:
! obsolete
! wall 0.004844 comb 0.010000 user 0.010000 sys 0.000000 (best of 547)
! visible
! wall 0.009090 comb 0.010000 user 0.010000 sys 0.000000 (best of 310)

After:
! obsolete
! wall 0.004720 comb 0.010000 user 0.010000 sys 0.000000 (best of 554)
! visible
! wall 0.009028 comb 0.000000 user 0.000000 sys 0.000000 (best of 304)


So there's practically no improvement at all on the hg core repo.
Where can I find the Mozilla repos to try it on?

>
>
>>>> 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.
>
>
> (see my reply to Greg about why moving to set will hurt)
>
> Cheers,
>
> --
> Pierre-Yves David
Pierre-Yves David - May 24, 2017, 6:43 p.m.
On 05/24/2017 07:08 PM, Martin von Zweigbergk via Mercurial-devel wrote:
> On Wed, May 24, 2017 at 5:42 AM, Pierre-Yves David
> <pierre-yves.david@ens-lyon.org> wrote:
>>
>>
>> On 05/24/2017 06:04 AM, Martin von Zweigbergk wrote:
>>>
>>> On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.szorc@gmail.com>
>>> wrote:
>>>>
>>>> On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
>>>> <pierre-yves.david@ens-lyon.org> wrote:
>>>>>
>>>>>
>>>>> # HG changeset patch
>>>>> # User Pierre-Yves David <pierre-yves.david@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?
>>
>>
>> Ha, good point. Using the perf extension:
>>
>>   hg perfvolatileset obsolete visible
>
> Do I just run "./hg perfvolatileset obsolete visible"? If I do that on
> the hg core repo, I get these results:
>
> Before:
> ! obsolete
> ! wall 0.004844 comb 0.010000 user 0.010000 sys 0.000000 (best of 547)
> ! visible
> ! wall 0.009090 comb 0.010000 user 0.010000 sys 0.000000 (best of 310)
>
> After:
> ! obsolete
> ! wall 0.004720 comb 0.010000 user 0.010000 sys 0.000000 (best of 554)
> ! visible
> ! wall 0.009028 comb 0.000000 user 0.000000 sys 0.000000 (best of 304)
>
>
> So there's practically no improvement at all on the hg core repo.
> Where can I find the Mozilla repos to try it on?

You need to have a least one dynamic-blocker for that code to quicks in.
(so either a bookmark or the working copy on an otherwise hidden 
changeset). You can use the following command for this purpose:

   hg up --hidden 'max(hidden())'

I use "max" because the higher the blocker is, the higher the impact of 
the old code was.

In my mercurial repository I get the following number:

Before
! obsolete
! wall 0.009808 comb 0.010000 user 0.010000 sys 0.000000 (best of 285)
! visible
! wall 0.019836 comb 0.020000 user 0.020000 sys 0.000000 (best of 149)

After
! obsolete
! wall 0.009582 comb 0.020000 user 0.020000 sys 0.000000 (best of 301)
! visible
! wall 0.012674 comb 0.010000 user 0.010000 sys 0.000000 (best of 230)

Adjusted time gives (10ms vs 3 ms) a 3x improvement
(for this specific changeset)

The running time of these algorithm is affected by multiple variable:
* how many obsolete changesets,
* how many mutable changesets in general,
* how early in the revlog is the first obsolete changeset.

So depending of the repository characteristic, timing will change a lot. 
The new algorithm is much less subject to variation on "abstract" thing 
like the early-ness of the first obsolete changeset.
(which is why I included some stats on the repository in my timing report).

For my mercurial core repository I've:
  * 38542 changeset total
  * 214 visible changesets
  * 5896 hidden changesets
  * oldest hidden changesets is rev 28845

The mozilla repository are two repos based on greg "devel" repository. 
on is build from pulling from him[1] every couple of months. The other 
one is a tarball of his local repository (so many more hidden 
changesets) that you can probably obtain from him directly.

Cheers,

Patch

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)
+            pfunc = cl.parentrevs
+            mutablephases = (phases.draft, phases.secret)
+            mutable = repo._phasecache.getrevset(repo, mutablephases)
+            hidden = hidden - _domainancestors(pfunc, dynamic, mutable)
     return hidden
 
 def computeunserved(repo):