Patchwork [evolve-ext] inhibit: improve transaction marker perf

login
register
mail settings
Submitter Durham Goode
Date Nov. 8, 2015, 1:20 a.m.
Message ID <7c680f209f7af35c7c47.1446945611@dev8060.prn1.facebook.com>
Download mbox | patch
Permalink /patch/11327/
State Rejected
Delegated to: Pierre-Yves David
Headers show

Comments

Durham Goode - Nov. 8, 2015, 1:20 a.m.
# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 1446945001 28800
#      Sat Nov 07 17:10:01 2015 -0800
# Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
# Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
inhibit: improve transaction marker perf

The old algorithm was a revset "::X and obsolete()". This was inefficient because
it requires walking all the way down the ancestor chain (since the revset did
not know it could stop walking at public nodes).

The new algorithm uses changelog.ancestors() directly and provides a function to
stop the iteration when we reach a public node. During a commit to a repo with
hundreds of thousands of commits, this change reduces the inhibitmarkers time
from 1.5 seconds to effectively 0 seconds.
Durham Goode - Nov. 8, 2015, 1:23 a.m.
On 11/7/15 5:20 PM, Durham Goode wrote:
> # HG changeset patch
> # User Durham Goode <durham@fb.com>
> # Date 1446945001 28800
> #      Sat Nov 07 17:10:01 2015 -0800
> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
> inhibit: improve transaction marker perf
>
> The old algorithm was a revset "::X and obsolete()". This was inefficient because
> it requires walking all the way down the ancestor chain (since the revset did
> not know it could stop walking at public nodes).
>
> The new algorithm uses changelog.ancestors() directly and provides a function to
> stop the iteration when we reach a public node. During a commit to a repo with
> hundreds of thousands of commits, this change reduces the inhibitmarkers time
> from 1.5 seconds to effectively 0 seconds.
>
This patch is dependent on the pending "ancestors: add stopfunc to 
revlog.ancestors" patch being accepted into core.
Martin von Zweigbergk - Nov. 8, 2015, 5:52 a.m.
On Sat, Nov 7, 2015 at 5:21 PM Durham Goode <durham@fb.com> wrote:

> # HG changeset patch
> # User Durham Goode <durham@fb.com>
> # Date 1446945001 28800
> #      Sat Nov 07 17:10:01 2015 -0800
> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
> inhibit: improve transaction marker perf
>
> The old algorithm was a revset "::X and obsolete()". This was inefficient
> because
> it requires walking all the way down the ancestor chain (since the revset
> did
> not know it could stop walking at public nodes).
>

I was hoping to reproduce the slowness on the Mozilla repo (270k
revisions), but "hg log -r '::tip and obsolete()'" runs in 180 ms. Do you
have a better command for me to try? How many obsmarkers in the repo you
tried it on?


> The new algorithm uses changelog.ancestors() directly and provides a
> function to
> stop the iteration when we reach a public node. During a commit to a repo
> with
> hundreds of thousands of commits, this change reduces the inhibitmarkers
> time
> from 1.5 seconds to effectively 0 seconds.
>
> diff --git a/hgext/inhibit.py b/hgext/inhibit.py
> --- a/hgext/inhibit.py
> +++ b/hgext/inhibit.py
> @@ -23,6 +23,7 @@ from mercurial import scmutil
>  from mercurial import commands
>  from mercurial import lock as lockmod
>  from mercurial import bookmarks
> +from mercurial import phases
>  from mercurial import util
>  from mercurial.i18n import _
>
> @@ -129,7 +130,15 @@ def _inhibitmarkers(repo, nodes):
>      if not _inhibitenabled(repo):
>          return
>
> -    newinhibit = repo.set('::%ln and obsolete()', nodes)
> +    newinhibit = set()
> +    revs = [repo[node].rev() for node in nodes]
> +    phase = repo._phasecache.phase
> +    obsoletes = obsolete.getrevs(repo, 'obsolete')
> +    for anc in repo.changelog.ancestors(revs, inclusive=True,
> +                stopfunc=lambda rev: phase(repo, rev) == phases.public):
> +        if anc in obsoletes:
> +            newinhibit.add(repo[anc])
> +
>      if newinhibit:
>          lock = tr = None
>          try:
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> https://selenic.com/mailman/listinfo/mercurial-devel
>
Durham Goode - Nov. 8, 2015, 6:15 a.m.
On 11/7/15 9:52 PM, Martin von Zweigbergk wrote:
>
>
> On Sat, Nov 7, 2015 at 5:21 PM Durham Goode <durham@fb.com 
> <mailto:durham@fb.com>> wrote:
>
>     # HG changeset patch
>     # User Durham Goode <durham@fb.com <mailto:durham@fb.com>>
>     # Date 1446945001 28800
>     #      Sat Nov 07 17:10:01 2015 -0800
>     # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>     # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>     inhibit: improve transaction marker perf
>
>     The old algorithm was a revset "::X and obsolete()". This was
>     inefficient because
>     it requires walking all the way down the ancestor chain (since the
>     revset did
>     not know it could stop walking at public nodes).
>
>
> I was hoping to reproduce the slowness on the Mozilla repo (270k 
> revisions), but "hg log -r '::tip and obsolete()'" runs in 180 ms. Do 
> you have a better command for me to try? How many obsmarkers in the 
> repo you tried it on?
You need to make sure you pass --hidden, otherwise the obsolete() revset 
resolves to an empty set and tests against it are cheap.

I have 1500 obs markers, if that affects things.
Martin von Zweigbergk - Nov. 8, 2015, 8:04 a.m.
On Sat, Nov 7, 2015 at 10:15 PM Durham Goode <durham@fb.com> wrote:

>
>
> On 11/7/15 9:52 PM, Martin von Zweigbergk wrote:
>
>
>
> On Sat, Nov 7, 2015 at 5:21 PM Durham Goode <durham@fb.com> wrote:
>
>> # HG changeset patch
>> # User Durham Goode <durham@fb.com>
>> # Date 1446945001 28800
>> #      Sat Nov 07 17:10:01 2015 -0800
>> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>> inhibit: improve transaction marker perf
>>
>> The old algorithm was a revset "::X and obsolete()". This was inefficient
>> because
>> it requires walking all the way down the ancestor chain (since the revset
>> did
>> not know it could stop walking at public nodes).
>>
>
> I was hoping to reproduce the slowness on the Mozilla repo (270k
> revisions), but "hg log -r '::tip and obsolete()'" runs in 180 ms. Do you
> have a better command for me to try? How many obsmarkers in the repo you
> tried it on?
>
> You need to make sure you pass --hidden, otherwise the obsolete() revset
> resolves to an empty set and tests against it are cheap.
>

I'm still not able to reproduce this :-( Some tests take ~800 ms, but most
of that time seems to be related to loading obsmarkers and not about
iterating over the revset.

I wanted to see if I could get the same results by playing with the revset
optimizer. I have never looked at that code before and I don't know if it's
a good idea. If it is, I'll have to let you do it yourself since I can't
even test it.


>
> I have 1500 obs markers, if that affects things.
>
Gregory Szorc - Nov. 8, 2015, 4:28 p.m.
On Sat, Nov 7, 2015 at 5:20 PM, Durham Goode <durham@fb.com> wrote:

> # HG changeset patch
> # User Durham Goode <durham@fb.com>
> # Date 1446945001 28800
> #      Sat Nov 07 17:10:01 2015 -0800
> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
> inhibit: improve transaction marker perf
>
> The old algorithm was a revset "::X and obsolete()". This was inefficient
> because
> it requires walking all the way down the ancestor chain (since the revset
> did
> not know it could stop walking at public nodes).
>
> The new algorithm uses changelog.ancestors() directly and provides a
> function to
> stop the iteration when we reach a public node. During a commit to a repo
> with
> hundreds of thousands of commits, this change reduces the inhibitmarkers
> time
> from 1.5 seconds to effectively 0 seconds.
>
> diff --git a/hgext/inhibit.py b/hgext/inhibit.py
> --- a/hgext/inhibit.py
> +++ b/hgext/inhibit.py
> @@ -23,6 +23,7 @@ from mercurial import scmutil
>  from mercurial import commands
>  from mercurial import lock as lockmod
>  from mercurial import bookmarks
> +from mercurial import phases
>  from mercurial import util
>  from mercurial.i18n import _
>
> @@ -129,7 +130,15 @@ def _inhibitmarkers(repo, nodes):
>      if not _inhibitenabled(repo):
>          return
>
> -    newinhibit = repo.set('::%ln and obsolete()', nodes)
> +    newinhibit = set()
> +    revs = [repo[node].rev() for node in nodes]
> +    phase = repo._phasecache.phase
> +    obsoletes = obsolete.getrevs(repo, 'obsolete')
> +    for anc in repo.changelog.ancestors(revs, inclusive=True,
> +                stopfunc=lambda rev: phase(repo, rev) == phases.public):
> +        if anc in obsoletes:
> +            newinhibit.add(repo[anc])
> +
>
>
I must be missing something obvious: why can't this be written as:

obsoletes = ...
for rev in repo.revs('::%ln and not public()'):
    if rev in obsoletes:
        ...

I don't understand why stopfunc is needed and why a revset can't do the
same thing.
Durham Goode - Nov. 8, 2015, 4:38 p.m.
On 11/8/15 8:28 AM, Gregory Szorc wrote:
> On Sat, Nov 7, 2015 at 5:20 PM, Durham Goode <durham@fb.com 
> <mailto:durham@fb.com>> wrote:
>
>     # HG changeset patch
>     # User Durham Goode <durham@fb.com <mailto:durham@fb.com>>
>     # Date 1446945001 28800
>     #      Sat Nov 07 17:10:01 2015 -0800
>     # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>     # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>     inhibit: improve transaction marker perf
>
>     The old algorithm was a revset "::X and obsolete()". This was
>     inefficient because
>     it requires walking all the way down the ancestor chain (since the
>     revset did
>     not know it could stop walking at public nodes).
>
>     The new algorithm uses changelog.ancestors() directly and provides
>     a function to
>     stop the iteration when we reach a public node. During a commit to
>     a repo with
>     hundreds of thousands of commits, this change reduces the
>     inhibitmarkers time
>     from 1.5 seconds to effectively 0 seconds.
>
>     diff --git a/hgext/inhibit.py b/hgext/inhibit.py
>     --- a/hgext/inhibit.py
>     +++ b/hgext/inhibit.py
>     @@ -23,6 +23,7 @@ from mercurial import scmutil
>      from mercurial import commands
>      from mercurial import lock as lockmod
>      from mercurial import bookmarks
>     +from mercurial import phases
>      from mercurial import util
>      from mercurial.i18n import _
>
>     @@ -129,7 +130,15 @@ def _inhibitmarkers(repo, nodes):
>          if not _inhibitenabled(repo):
>              return
>
>     -    newinhibit = repo.set('::%ln and obsolete()', nodes)
>     +    newinhibit = set()
>     +    revs = [repo[node].rev() for node in nodes]
>     +    phase = repo._phasecache.phase
>     +    obsoletes = obsolete.getrevs(repo, 'obsolete')
>     +    for anc in repo.changelog.ancestors(revs, inclusive=True,
>     +                stopfunc=lambda rev: phase(repo, rev) ==
>     phases.public):
>     +        if anc in obsoletes:
>     +            newinhibit.add(repo[anc])
>     +
>
>
> I must be missing something obvious: why can't this be written as:
>
> obsoletes = ...
> for rev in repo.revs('::%ln and not public()'):
>     if rev in obsoletes:
>         ...
>
> I don't understand why stopfunc is needed and why a revset can't do 
> the same thing.
The way "::X and not public()" works is it iterates down the ancestor 
line and checks each commit to see if it's not public. The iterator has 
no knowledge that finding something that is public means it can stop 
iterating, so it will iterate over all the commits.

In theory we could try to make revsets smarter (i.e. by allowing the 
ancestor revset to communicate to the public revset that it's doing a 
descendant traversal, and allowing the public revset to signal a stop), 
but that's rather complex, and the implementation would probably end up 
adding the stopfunc to lazyancestors anyway (since that's how you'd 
likely implement it).
Gregory Szorc - Nov. 8, 2015, 4:46 p.m.
On Sun, Nov 8, 2015 at 8:38 AM, Durham Goode <durham@fb.com> wrote:

>
>
> On 11/8/15 8:28 AM, Gregory Szorc wrote:
>
> On Sat, Nov 7, 2015 at 5:20 PM, Durham Goode <durham@fb.com> wrote:
>
>> # HG changeset patch
>> # User Durham Goode <durham@fb.com>
>> # Date 1446945001 28800
>> #      Sat Nov 07 17:10:01 2015 -0800
>> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>> inhibit: improve transaction marker perf
>>
>> The old algorithm was a revset "::X and obsolete()". This was inefficient
>> because
>> it requires walking all the way down the ancestor chain (since the revset
>> did
>> not know it could stop walking at public nodes).
>>
>> The new algorithm uses changelog.ancestors() directly and provides a
>> function to
>> stop the iteration when we reach a public node. During a commit to a repo
>> with
>> hundreds of thousands of commits, this change reduces the inhibitmarkers
>> time
>> from 1.5 seconds to effectively 0 seconds.
>>
>> diff --git a/hgext/inhibit.py b/hgext/inhibit.py
>> --- a/hgext/inhibit.py
>> +++ b/hgext/inhibit.py
>> @@ -23,6 +23,7 @@ from mercurial import scmutil
>>  from mercurial import commands
>>  from mercurial import lock as lockmod
>>  from mercurial import bookmarks
>> +from mercurial import phases
>>  from mercurial import util
>>  from mercurial.i18n import _
>>
>> @@ -129,7 +130,15 @@ def _inhibitmarkers(repo, nodes):
>>      if not _inhibitenabled(repo):
>>          return
>>
>> -    newinhibit = repo.set('::%ln and obsolete()', nodes)
>> +    newinhibit = set()
>> +    revs = [repo[node].rev() for node in nodes]
>> +    phase = repo._phasecache.phase
>> +    obsoletes = obsolete.getrevs(repo, 'obsolete')
>> +    for anc in repo.changelog.ancestors(revs, inclusive=True,
>> +                stopfunc=lambda rev: phase(repo, rev) == phases.public):
>> +        if anc in obsoletes:
>> +            newinhibit.add(repo[anc])
>> +
>>
>>
> I must be missing something obvious: why can't this be written as:
>
> obsoletes = ...
> for rev in repo.revs('::%ln and not public()'):
>     if rev in obsoletes:
>         ...
>
> I don't understand why stopfunc is needed and why a revset can't do the
> same thing.
>
> The way "::X and not public()" works is it iterates down the ancestor line
> and checks each commit to see if it's not public. The iterator has no
> knowledge that finding something that is public means it can stop
> iterating, so it will iterate over all the commits.
>
> In theory we could try to make revsets smarter (i.e. by allowing the
> ancestor revset to communicate to the public revset that it's doing a
> descendant traversal, and allowing the public revset to signal a stop), but
> that's rather complex, and the implementation would probably end up adding
> the stopfunc to lazyancestors anyway (since that's how you'd likely
> implement it).
>

I see. Thanks for explaining. And here I thought all that work in recent
releases to drastically speed up "not public()" implemented things like
this because it had to.
Durham Goode - Nov. 8, 2015, 4:52 p.m.
On 11/8/15 8:46 AM, Gregory Szorc wrote:
> On Sun, Nov 8, 2015 at 8:38 AM, Durham Goode <durham@fb.com 
> <mailto:durham@fb.com>> wrote:
>
>
>
>     On 11/8/15 8:28 AM, Gregory Szorc wrote:
>>     On Sat, Nov 7, 2015 at 5:20 PM, Durham Goode <durham@fb.com
>>     <mailto:durham@fb.com>> wrote:
>>
>>         # HG changeset patch
>>         # User Durham Goode <durham@fb.com <mailto:durham@fb.com>>
>>         # Date 1446945001 28800
>>         #      Sat Nov 07 17:10:01 2015 -0800
>>         # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>>         # Parent 48547b4c77defdd17c670b1eb0eb94272edf0207
>>         inhibit: improve transaction marker perf
>>
>>         The old algorithm was a revset "::X and obsolete()". This was
>>         inefficient because
>>         it requires walking all the way down the ancestor chain
>>         (since the revset did
>>         not know it could stop walking at public nodes).
>>
>>         The new algorithm uses changelog.ancestors() directly and
>>         provides a function to
>>         stop the iteration when we reach a public node. During a
>>         commit to a repo with
>>         hundreds of thousands of commits, this change reduces the
>>         inhibitmarkers time
>>         from 1.5 seconds to effectively 0 seconds.
>>
>>         diff --git a/hgext/inhibit.py b/hgext/inhibit.py
>>         --- a/hgext/inhibit.py
>>         +++ b/hgext/inhibit.py
>>         @@ -23,6 +23,7 @@ from mercurial import scmutil
>>          from mercurial import commands
>>          from mercurial import lock as lockmod
>>          from mercurial import bookmarks
>>         +from mercurial import phases
>>          from mercurial import util
>>          from mercurial.i18n import _
>>
>>         @@ -129,7 +130,15 @@ def _inhibitmarkers(repo, nodes):
>>              if not _inhibitenabled(repo):
>>                  return
>>
>>         -    newinhibit = repo.set('::%ln and obsolete()', nodes)
>>         +    newinhibit = set()
>>         +    revs = [repo[node].rev() for node in nodes]
>>         +    phase = repo._phasecache.phase
>>         +    obsoletes = obsolete.getrevs(repo, 'obsolete')
>>         +    for anc in repo.changelog.ancestors(revs, inclusive=True,
>>         +                stopfunc=lambda rev: phase(repo, rev) ==
>>         phases.public):
>>         +        if anc in obsoletes:
>>         +            newinhibit.add(repo[anc])
>>         +
>>
>>
>>     I must be missing something obvious: why can't this be written as:
>>
>>     obsoletes = ...
>>     for rev in repo.revs('::%ln and not public()'):
>>         if rev in obsoletes:
>>             ...
>>
>>     I don't understand why stopfunc is needed and why a revset can't
>>     do the same thing.
>     The way "::X and not public()" works is it iterates down the
>     ancestor line and checks each commit to see if it's not public.
>     The iterator has no knowledge that finding something that is
>     public means it can stop iterating, so it will iterate over all
>     the commits.
>
>     In theory we could try to make revsets smarter (i.e. by allowing
>     the ancestor revset to communicate to the public revset that it's
>     doing a descendant traversal, and allowing the public revset to
>     signal a stop), but that's rather complex, and the implementation
>     would probably end up adding the stopfunc to lazyancestors anyway
>     (since that's how you'd likely implement it).
>
>
> I see. Thanks for explaining. And here I thought all that work in 
> recent releases to drastically speed up "not public()" implemented 
> things like this because it had to.
"not public()" is optimized, so it's quick.  But testing a series of 
commits against it is still O(size of series). In theory we could 
optimize "::X and not public()" to iterate over the "not public()" set 
instead of the ancestors, then test against the ancestor set (which is 
cheaper), but that's still O(distance from first not-public commit), 
which is still too slow in this case.
Durham Goode - Nov. 8, 2015, 5:24 p.m.
On 11/8/15 12:04 AM, Martin von Zweigbergk wrote:
>
>
> On Sat, Nov 7, 2015 at 10:15 PM Durham Goode <durham@fb.com 
> <mailto:durham@fb.com>> wrote:
>
>
>
>     On 11/7/15 9:52 PM, Martin von Zweigbergk wrote:
>>
>>
>>     On Sat, Nov 7, 2015 at 5:21 PM Durham Goode <durham@fb.com
>>     <mailto:durham@fb.com>> wrote:
>>
>>         # HG changeset patch
>>         # User Durham Goode <durham@fb.com <mailto:durham@fb.com>>
>>         # Date 1446945001 28800
>>         #      Sat Nov 07 17:10:01 2015 -0800
>>         # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>>         # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>>         inhibit: improve transaction marker perf
>>
>>         The old algorithm was a revset "::X and obsolete()". This was
>>         inefficient because
>>         it requires walking all the way down the ancestor chain
>>         (since the revset did
>>         not know it could stop walking at public nodes).
>>
>>
>>     I was hoping to reproduce the slowness on the Mozilla repo (270k
>>     revisions), but "hg log -r '::tip and obsolete()'" runs in 180
>>     ms. Do you have a better command for me to try? How many
>>     obsmarkers in the repo you tried it on?
>     You need to make sure you pass --hidden, otherwise the obsolete()
>     revset resolves to an empty set and tests against it are cheap.
>
>
> I'm still not able to reproduce this :-( Some tests take ~800 ms, but 
> most of that time seems to be related to loading obsmarkers and not 
> about iterating over the revset.
>
> I wanted to see if I could get the same results by playing with the 
> revset optimizer. I have never looked at that code before and I don't 
> know if it's a good idea. If it is, I'll have to let you do it 
> yourself since I can't even test it.
I looked into this a bit more.  I think this performance is due to the 
nature of our largest repo.  We had three large repos which were then 
merged together, so there are three distinct branches in history.  The 
--profile of this revset is as follows:

~/foo> time hg log -r '::tip and obsolete()'  --hidden --profile
| 100.0%  cmdutil.py:     getlogrevs               line 4792:  revs, 
expr, filematcher = c...
  \ 93.3%  revset.py:      __nonzero__              line 2135:  if not revs:
    | 93.3%  revset.py:      _iterfilter            line 3110:  for r in it:
    | 93.3%  revset.py:      _desccontains          line 3084:  if cond(x):
    | 89.6%  revset.py:      _consumegen            line 3460:  for l in 
self._consumegen():
    | 82.2%  revset.py:      iterate                line 3508:  for item 
in self._gen:
    | 30.4%  changelog.py:   parentrevs             line 56:  for parent 
in cl.parentrevs...
    | 13.3%  revlog.py:      parentrevs             line 231:  return 
super(changelog, sel...

Most of the time is in iterate, which is where the heapq management 
goes. I think having the three branches in history cause more heap work 
than without (in fact, if I do "(A::tip | B::tip | C::tip) and 
obsolete()", where A B and C are roots of the three histories, it's way 
faster than just ::tip and the iterate disappears from the profile.

Either way, I think my fix still applies, since it fixes the O() entirely.
Martin von Zweigbergk - Nov. 9, 2015, 10:11 p.m.
On Sun, Nov 8, 2015 at 8:53 AM Durham Goode <durham@fb.com> wrote:

>
>
> On 11/8/15 8:46 AM, Gregory Szorc wrote:
>
> On Sun, Nov 8, 2015 at 8:38 AM, Durham Goode <durham@fb.com> wrote:
>
>>
>>
>> On 11/8/15 8:28 AM, Gregory Szorc wrote:
>>
>> On Sat, Nov 7, 2015 at 5:20 PM, Durham Goode < <durham@fb.com>
>> durham@fb.com> wrote:
>>
>>> # HG changeset patch
>>> # User Durham Goode < <durham@fb.com>durham@fb.com>
>>> # Date 1446945001 28800
>>> #      Sat Nov 07 17:10:01 2015 -0800
>>> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>>> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>>> inhibit: improve transaction marker perf
>>>
>>> The old algorithm was a revset "::X and obsolete()". This was
>>> inefficient because
>>> it requires walking all the way down the ancestor chain (since the
>>> revset did
>>> not know it could stop walking at public nodes).
>>>
>>> The new algorithm uses changelog.ancestors() directly and provides a
>>> function to
>>> stop the iteration when we reach a public node. During a commit to a
>>> repo with
>>> hundreds of thousands of commits, this change reduces the inhibitmarkers
>>> time
>>> from 1.5 seconds to effectively 0 seconds.
>>>
>>> diff --git a/hgext/inhibit.py b/hgext/inhibit.py
>>> --- a/hgext/inhibit.py
>>> +++ b/hgext/inhibit.py
>>> @@ -23,6 +23,7 @@ from mercurial import scmutil
>>>  from mercurial import commands
>>>  from mercurial import lock as lockmod
>>>  from mercurial import bookmarks
>>> +from mercurial import phases
>>>  from mercurial import util
>>>  from mercurial.i18n import _
>>>
>>> @@ -129,7 +130,15 @@ def _inhibitmarkers(repo, nodes):
>>>      if not _inhibitenabled(repo):
>>>          return
>>>
>>> -    newinhibit = repo.set('::%ln and obsolete()', nodes)
>>> +    newinhibit = set()
>>> +    revs = [repo[node].rev() for node in nodes]
>>> +    phase = repo._phasecache.phase
>>> +    obsoletes = obsolete.getrevs(repo, 'obsolete')
>>> +    for anc in repo.changelog.ancestors(revs, inclusive=True,
>>> +                stopfunc=lambda rev: phase(repo, rev) == phases.public):
>>> +        if anc in obsoletes:
>>> +            newinhibit.add(repo[anc])
>>> +
>>>
>>>
>> I must be missing something obvious: why can't this be written as:
>>
>> obsoletes = ...
>> for rev in repo.revs('::%ln and not public()'):
>>     if rev in obsoletes:
>>         ...
>>
>> I don't understand why stopfunc is needed and why a revset can't do the
>> same thing.
>>
>> The way "::X and not public()" works is it iterates down the ancestor
>> line and checks each commit to see if it's not public. The iterator has no
>> knowledge that finding something that is public means it can stop
>> iterating, so it will iterate over all the commits.
>>
>> In theory we could try to make revsets smarter (i.e. by allowing the
>> ancestor revset to communicate to the public revset that it's doing a
>> descendant traversal, and allowing the public revset to signal a stop), but
>> that's rather complex, and the implementation would probably end up adding
>> the stopfunc to lazyancestors anyway (since that's how you'd likely
>> implement it).
>>
>
> I see. Thanks for explaining. And here I thought all that work in recent
> releases to drastically speed up "not public()" implemented things like
> this because it had to.
>
> "not public()" is optimized, so it's quick.  But testing a series of
> commits against it is still O(size of series). In theory we could optimize
> "::X and not public()" to iterate over the "not public()" set instead of
> the ancestors, then test against the ancestor set (which is cheaper), but
> that's still O(distance from first not-public commit), which is still too
> slow in this case.
>

I think that's actually how it already works. Just time "hg log -T. -r ::@"
vs "hg log -T. -r '::@ and not public()'".

It seems like a good thing if "::X and obsolete()" could be optimized
rather than avoiding use of it, but that's of course much more work. Is it
likely enough that we will ever optimize that that we want to keep track of
it somehow (maybe "#  This works around '::%ln and obsolete()' which is not
yet optimized")? I don't know how we usually handle this kind of thing.


> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> https://selenic.com/mailman/listinfo/mercurial-devel
>
Pierre-Yves David - Nov. 18, 2015, 2:54 a.m.
On 11/08/2015 09:24 AM, Durham Goode wrote:
>
>
> On 11/8/15 12:04 AM, Martin von Zweigbergk wrote:
>>
>>
>> On Sat, Nov 7, 2015 at 10:15 PM Durham Goode <durham@fb.com
>> <mailto:durham@fb.com>> wrote:
>>
>>
>>
>>     On 11/7/15 9:52 PM, Martin von Zweigbergk wrote:
>>>
>>>
>>>     On Sat, Nov 7, 2015 at 5:21 PM Durham Goode <durham@fb.com
>>>     <mailto:durham@fb.com>> wrote:
>>>
>>>         # HG changeset patch
>>>         # User Durham Goode <durham@fb.com <mailto:durham@fb.com>>
>>>         # Date 1446945001 28800
>>>         #      Sat Nov 07 17:10:01 2015 -0800
>>>         # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
>>>         # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
>>>         inhibit: improve transaction marker perf
>>>
>>>         The old algorithm was a revset "::X and obsolete()". This was
>>>         inefficient because
>>>         it requires walking all the way down the ancestor chain
>>>         (since the revset did
>>>         not know it could stop walking at public nodes).
>>>
>>>
>>>     I was hoping to reproduce the slowness on the Mozilla repo (270k
>>>     revisions), but "hg log -r '::tip and obsolete()'" runs in 180
>>>     ms. Do you have a better command for me to try? How many
>>>     obsmarkers in the repo you tried it on?
>>     You need to make sure you pass --hidden, otherwise the obsolete()
>>     revset resolves to an empty set and tests against it are cheap.
>>
>>
>> I'm still not able to reproduce this :-( Some tests take ~800 ms, but
>> most of that time seems to be related to loading obsmarkers and not
>> about iterating over the revset.
>>
>> I wanted to see if I could get the same results by playing with the
>> revset optimizer. I have never looked at that code before and I don't
>> know if it's a good idea. If it is, I'll have to let you do it
>> yourself since I can't even test it.
> I looked into this a bit more.  I think this performance is due to the
> nature of our largest repo.  We had three large repos which were then
> merged together, so there are three distinct branches in history.  The
> --profile of this revset is as follows:
>
> ~/foo> time hg log -r '::tip and obsolete()'  --hidden --profile
> | 100.0%  cmdutil.py:     getlogrevs               line 4792:  revs,
> expr, filematcher = c...
>   \ 93.3%  revset.py:      __nonzero__              line 2135:  if not revs:
>     | 93.3%  revset.py:      _iterfilter            line 3110:  for r in it:
>     | 93.3%  revset.py:      _desccontains          line 3084:  if cond(x):
>     | 89.6%  revset.py:      _consumegen            line 3460:  for l in
> self._consumegen():
>     | 82.2%  revset.py:      iterate                line 3508:  for item
> in self._gen:
>     | 30.4%  changelog.py:   parentrevs             line 56:  for parent
> in cl.parentrevs...
>     | 13.3%  revlog.py:      parentrevs             line 231:  return
> super(changelog, sel...
>
> Most of the time is in iterate, which is where the heapq management
> goes. I think having the three branches in history cause more heap work
> than without (in fact, if I do "(A::tip | B::tip | C::tip) and
> obsolete()", where A B and C are roots of the three histories, it's way
> faster than just ::tip and the iterate disappears from the profile.
>
> Either way, I think my fix still applies, since it fixes the O() entirely.

A::tip is a whole different algorithm than ::tip. It is non lazy and in 
C. I'm not surprise this boost things up.
Pierre-Yves David - Nov. 18, 2015, 7:15 a.m.
On 11/07/2015 05:20 PM, Durham Goode wrote:
> # HG changeset patch
> # User Durham Goode <durham@fb.com>
> # Date 1446945001 28800
> #      Sat Nov 07 17:10:01 2015 -0800
> # Node ID 7c680f209f7af35c7c476eecc2f9eec13b32ad62
> # Parent  48547b4c77defdd17c670b1eb0eb94272edf0207
> inhibit: improve transaction marker perf

We found a bug in the original code that resulted in inhibit store to be 
rewritten in all cases. I've pushed a fix.

We've also used some dirty trick on the revset to make it acceptably fast.

Patch

diff --git a/hgext/inhibit.py b/hgext/inhibit.py
--- a/hgext/inhibit.py
+++ b/hgext/inhibit.py
@@ -23,6 +23,7 @@  from mercurial import scmutil
 from mercurial import commands
 from mercurial import lock as lockmod
 from mercurial import bookmarks
+from mercurial import phases
 from mercurial import util
 from mercurial.i18n import _
 
@@ -129,7 +130,15 @@  def _inhibitmarkers(repo, nodes):
     if not _inhibitenabled(repo):
         return
 
-    newinhibit = repo.set('::%ln and obsolete()', nodes)
+    newinhibit = set()
+    revs = [repo[node].rev() for node in nodes]
+    phase = repo._phasecache.phase
+    obsoletes = obsolete.getrevs(repo, 'obsolete')
+    for anc in repo.changelog.ancestors(revs, inclusive=True,
+                stopfunc=lambda rev: phase(repo, rev) == phases.public):
+        if anc in obsoletes:
+            newinhibit.add(repo[anc])
+
     if newinhibit:
         lock = tr = None
         try: