On 05/24/2017 06:43 AM, Martin von Zweigbergk wrote:
On Tue, May 23, 2017 at 9:04 PM, Martin von Zweigbergk
<martinv...@google.com> wrote:
On Tue, May 23, 2017 at 7:10 PM, Gregory Szorc <gregory.sz...@gmail.com> wrote:
On Tue, May 23, 2017 at 1:02 PM, Pierre-Yves David
<pierre-yves.da...@ens-lyon.org> wrote:
# HG changeset patch
# User Pierre-Yves David <pierre-yves.da...@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,
--
Pierre-Yves David
_______________________________________________
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
