rust: peek_mut optim for lazy ancestors
This is one of the two optimizations that are also
present in the Python code: replacing pairs of pop/push
on the BinaryHeap by single updates, hence having it
under the hood maintain its consistency (sift) only once.
On Mozilla central, the measured gain (see details below)
is around 7%.
Creating the PeekMut object by calling peek_mut() right away
instead of peek() first is less efficient (gain is only 4%, stats
not included).
Our interpretation is that its creation has a cost which is vasted
in the cases where it ends by droping the value (Peekmut::pop()
just does self.heap.pop() anyway). On the other hand, the immutable
peek() is very fast: it's just taking a reference in the
underlying vector.
The Python version still has another optimization:
if parent(current) == current-1, then the heap doesn't need
to maintain its consistency, since we already know that
it's bigger than all the others in the heap.
Rust's BinaryHeap doesn't allow us to mutate its biggest
element with no housekeeping, but we tried it anyway, with a
copy of the BinaryHeap implementation with a dedicaded added
method: it's not worth the technical debt in our opinion
(we measured only a further 1.6% improvement).
One possible explanation would be that the sift is really fast
anyway in that case, whereas it's not in the case of Python,
because it's at least partly done in slow Python code.
Still it's possible that replacing BinaryHeap by something more
dedicated to discrete ordered types could be faster.
Measurements on mozilla-central:
Three runs of 'hg perfancestors' on the parent changeset:
Moyenne des médianes: 0.100587
! wall 0.100062 comb 0.100000 user 0.100000 sys 0.000000 (best of 98)
! wall 0.135804 comb 0.130000 user 0.130000 sys 0.000000 (max of 98)
! wall 0.102864 comb 0.102755 user 0.099286 sys 0.003469 (avg of 98)
! wall 0.101486 comb 0.110000 user 0.110000 sys 0.000000 (median of 98)
! wall 0.096804 comb 0.090000 user 0.090000 sys 0.000000 (best of 100)
! wall 0.132235 comb 0.130000 user 0.120000 sys 0.010000 (max of 100)
! wall 0.100258 comb 0.100300 user 0.096000 sys 0.004300 (avg of 100)
! wall 0.098384 comb 0.100000 user 0.100000 sys 0.000000 (median of 100)
! wall 0.099925 comb 0.100000 user 0.100000 sys 0.000000 (best of 98)
! wall 0.133518 comb 0.140000 user 0.130000 sys 0.010000 (max of 98)
! wall 0.102381 comb 0.102449 user 0.098265 sys 0.004184 (avg of 98)
! wall 0.101891 comb 0.090000 user 0.090000 sys 0.000000 (median of 98)
Mean of the medians: 0.100587
On the present changeset:
! wall 0.091344 comb 0.090000 user 0.090000 sys 0.000000 (best of 100)
! wall 0.122728 comb 0.120000 user 0.110000 sys 0.010000 (max of 100)
! wall 0.093268 comb 0.093300 user 0.089300 sys 0.004000 (avg of 100)
! wall 0.092567 comb 0.100000 user 0.090000 sys 0.010000 (median of 100)
! wall 0.093294 comb 0.080000 user 0.080000 sys 0.000000 (best of 100)
! wall 0.144887 comb 0.150000 user 0.140000 sys 0.010000 (max of 100)
! wall 0.097708 comb 0.097700 user 0.093400 sys 0.004300 (avg of 100)
! wall 0.094980 comb 0.100000 user 0.090000 sys 0.010000 (median of 100)
! wall 0.091262 comb 0.090000 user 0.080000 sys 0.010000 (best of 100)
! wall 0.123772 comb 0.130000 user 0.120000 sys 0.010000 (max of 100)
! wall 0.093188 comb 0.093200 user 0.089300 sys 0.003900 (avg of 100)
! wall 0.092364 comb 0.100000 user 0.090000 sys 0.010000 (median of 100)
Mean of the medians is 0.0933
Differential Revision: https://phab.mercurial-scm.org/D5358
#testcases flat tree
#testcases lfs-on lfs-off
#if lfs-on
$ cat >> $HGRCPATH <<EOF
> [extensions]
> lfs =
> EOF
#endif
$ . "$TESTDIR/narrow-library.sh"
#if tree
$ cat << EOF >> $HGRCPATH
> [experimental]
> treemanifest = 1
> EOF
#endif
$ hg init master
$ cd master
$ cat >> .hg/hgrc <<EOF
> [narrow]
> serveellipses=True
> EOF
$ for x in `$TESTDIR/seq.py 0 10`
> do
> mkdir d$x
> echo $x > d$x/f
> hg add d$x/f
> hg commit -m "add d$x/f"
> done
$ hg log -T "{rev}: {desc}\n"
10: add d10/f
9: add d9/f
8: add d8/f
7: add d7/f
6: add d6/f
5: add d5/f
4: add d4/f
3: add d3/f
2: add d2/f
1: add d1/f
0: add d0/f
$ cd ..
Error if '.' or '..' are in the directory to track.
$ hg clone --narrow ssh://user@dummy/master foo --include ./asdf
abort: "." and ".." are not allowed in narrowspec paths
[255]
$ hg clone --narrow ssh://user@dummy/master foo --include asdf/..
abort: "." and ".." are not allowed in narrowspec paths
[255]
$ hg clone --narrow ssh://user@dummy/master foo --include a/./c
abort: "." and ".." are not allowed in narrowspec paths
[255]
Names with '.' in them are OK.
$ hg clone --narrow ssh://user@dummy/master should-work --include a/.b/c
requesting all changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 0 changes to 0 files
new changesets * (glob)
updating to branch default
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
Test repo with local changes
$ hg clone --narrow ssh://user@dummy/master narrow-local-changes --include d0 --include d3 --include d6
requesting all changes
adding changesets
adding manifests
adding file changes
added 6 changesets with 3 changes to 3 files
new changesets *:* (glob)
updating to branch default
3 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd narrow-local-changes
$ cat >> $HGRCPATH << EOF
> [experimental]
> evolution=createmarkers
> EOF
$ echo local change >> d0/f
$ hg ci -m 'local change to d0'
$ hg co '.^'
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ echo local change >> d3/f
$ hg ci -m 'local hidden change to d3'
created new head
$ hg ci --amend -m 'local change to d3'
$ hg tracked --removeinclude d0
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
The following changeset(s) or their ancestors have local changes not on the remote:
* (glob)
abort: local changes found
(use --force-delete-local-changes to ignore)
[255]
Check that nothing was removed by the failed attempts
$ hg tracked
I path:d0
I path:d3
I path:d6
$ hg files
d0/f
d3/f
d6/f
$ find *
d0
d0/f
d3
d3/f
d6
d6/f
$ hg verify -q
Force deletion of local changes
$ hg log -T "{rev}: {desc} {outsidenarrow}\n"
8: local change to d3
6: local change to d0
5: add d10/f outsidenarrow
4: add d6/f
3: add d5/f outsidenarrow
2: add d3/f
1: add d2/f outsidenarrow
0: add d0/f
$ hg tracked --removeinclude d0 --force-delete-local-changes
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
The following changeset(s) or their ancestors have local changes not on the remote:
* (glob)
saved backup bundle to $TESTTMP/narrow-local-changes/.hg/strip-backup/*-narrow.hg (glob)
deleting data/d0/f.i (reporevlogstore !)
deleting meta/d0/00manifest.i (tree !)
deleting data/d0/f/362fef284ce2ca02aecc8de6d5e8a1c3af0556fe (reposimplestore !)
deleting data/d0/f/4374b5650fc5ae54ac857c0f0381971fdde376f7 (reposimplestore !)
deleting data/d0/f/index (reposimplestore !)
$ hg log -T "{rev}: {desc} {outsidenarrow}\n"
7: local change to d3
5: add d10/f outsidenarrow
4: add d6/f
3: add d5/f outsidenarrow
2: add d3/f
1: add d2/f outsidenarrow
0: add d0/f outsidenarrow
Can restore stripped local changes after widening
$ hg tracked --addinclude d0 -q
$ hg unbundle .hg/strip-backup/*-narrow.hg -q
$ hg --hidden co -r 'desc("local change to d0")' -q
$ cat d0/f
0
local change
Pruned commits affecting removed paths should not prevent narrowing
$ hg co '.^'
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg debugobsolete `hg log -T '{node}' -r 'desc("local change to d0")'`
obsoleted 1 changesets
$ hg tracked --removeinclude d0
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
saved backup bundle to $TESTTMP/narrow-local-changes/.hg/strip-backup/*-narrow.hg (glob)
deleting data/d0/f.i (reporevlogstore !)
deleting meta/d0/00manifest.i (tree !)
deleting data/d0/f/362fef284ce2ca02aecc8de6d5e8a1c3af0556fe (reposimplestore !)
deleting data/d0/f/4374b5650fc5ae54ac857c0f0381971fdde376f7 (reposimplestore !)
deleting data/d0/f/index (reposimplestore !)
Updates off of stripped commit if necessary
$ hg co -r 'desc("local change to d3")' -q
$ echo local change >> d6/f
$ hg ci -m 'local change to d6'
$ hg tracked --removeinclude d3 --force-delete-local-changes
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
The following changeset(s) or their ancestors have local changes not on the remote:
* (glob)
* (glob)
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
saved backup bundle to $TESTTMP/narrow-local-changes/.hg/strip-backup/*-narrow.hg (glob)
deleting data/d3/f.i (reporevlogstore !)
deleting meta/d3/00manifest.i (tree !)
deleting data/d3/f/2661d26c649684b482d10f91960cc3db683c38b4 (reposimplestore !)
deleting data/d3/f/99fa7136105a15e2045ce3d9152e4837c5349e4d (reposimplestore !)
deleting data/d3/f/index (reposimplestore !)
$ hg log -T '{desc}\n' -r .
add d10/f
Updates to nullid if necessary
$ hg tracked --addinclude d3 -q
$ hg co null -q
$ mkdir d3
$ echo local change > d3/f
$ hg add d3/f
$ hg ci -m 'local change to d3'
created new head
$ hg tracked --removeinclude d3 --force-delete-local-changes
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
The following changeset(s) or their ancestors have local changes not on the remote:
* (glob)
0 files updated, 0 files merged, 1 files removed, 0 files unresolved
saved backup bundle to $TESTTMP/narrow-local-changes/.hg/strip-backup/*-narrow.hg (glob)
deleting data/d3/f.i (reporevlogstore !)
deleting meta/d3/00manifest.i (tree !)
deleting data/d3/f/2661d26c649684b482d10f91960cc3db683c38b4 (reposimplestore !)
deleting data/d3/f/5ce0767945cbdbca3b924bb9fbf5143f72ab40ac (reposimplestore !)
deleting data/d3/f/index (reposimplestore !)
$ hg id
000000000000
$ cd ..
Can remove last include, making repo empty
$ hg clone --narrow ssh://user@dummy/master narrow-empty --include d0 -r 5
adding changesets
adding manifests
adding file changes
added 2 changesets with 1 changes to 1 files
new changesets *:* (glob)
updating to branch default
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd narrow-empty
$ hg tracked --removeinclude d0
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
deleting data/d0/f.i (reporevlogstore !)
deleting meta/d0/00manifest.i (tree !)
deleting data/d0/f/362fef284ce2ca02aecc8de6d5e8a1c3af0556fe (reposimplestore !)
deleting data/d0/f/index (reposimplestore !)
$ hg tracked
$ hg files
[1]
$ test -d d0
[1]
Do some work in the empty clone
$ hg diff --change .
$ hg branch foo
marked working directory as branch foo
(branches are permanent and global, did you want a bookmark?)
$ hg ci -m empty
$ hg pull -q
Can widen the empty clone
$ hg tracked --addinclude d0
comparing with ssh://user@dummy/master
searching for changes
no changes found
saved backup bundle to $TESTTMP/narrow-empty/.hg/strip-backup/*-widen.hg (glob)
adding changesets
adding manifests
adding file changes
added 3 changesets with 1 changes to 1 files
new changesets *:* (glob)
$ hg tracked
I path:d0
$ hg files
d0/f
$ find *
d0
d0/f
$ cd ..
TODO(martinvonz): test including e.g. d3/g and then removing it once
https://bitbucket.org/Google/narrowhg/issues/6 is fixed
$ hg clone --narrow ssh://user@dummy/master narrow --include d0 --include d3 --include d6 --include d9
requesting all changes
adding changesets
adding manifests
adding file changes
added 8 changesets with 4 changes to 4 files
new changesets *:* (glob)
updating to branch default
4 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd narrow
$ hg tracked
I path:d0
I path:d3
I path:d6
I path:d9
$ hg tracked --removeinclude d6
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
deleting data/d6/f.i (reporevlogstore !)
deleting meta/d6/00manifest.i (tree !)
deleting data/d6/f/7339d30678f451ac8c3f38753beeb4cf2e1655c7 (reposimplestore !)
deleting data/d6/f/index (reposimplestore !)
$ hg tracked
I path:d0
I path:d3
I path:d9
#if repofncache
$ hg debugrebuildfncache
fncache already up to date
#endif
$ find *
d0
d0/f
d3
d3/f
d9
d9/f
$ hg verify -q
$ hg tracked --addexclude d3/f
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
deleting data/d3/f.i (reporevlogstore !)
deleting data/d3/f/2661d26c649684b482d10f91960cc3db683c38b4 (reposimplestore !)
deleting data/d3/f/index (reposimplestore !)
$ hg tracked
I path:d0
I path:d3
I path:d9
X path:d3/f
#if repofncache
$ hg debugrebuildfncache
fncache already up to date
#endif
$ find *
d0
d0/f
d9
d9/f
$ hg verify -q
$ hg tracked --addexclude d0
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
deleting data/d0/f.i (reporevlogstore !)
deleting meta/d0/00manifest.i (tree !)
deleting data/d0/f/362fef284ce2ca02aecc8de6d5e8a1c3af0556fe (reposimplestore !)
deleting data/d0/f/index (reposimplestore !)
$ hg tracked
I path:d3
I path:d9
X path:d0
X path:d3/f
#if repofncache
$ hg debugrebuildfncache
fncache already up to date
#endif
$ find *
d9
d9/f
Make a 15 of changes to d9 to test the path without --verbose
(Note: using regexes instead of "* (glob)" because if the test fails, it
produces more sensible diffs)
$ hg tracked
I path:d3
I path:d9
X path:d0
X path:d3/f
$ for x in `$TESTDIR/seq.py 1 15`
> do
> echo local change >> d9/f
> hg commit -m "change $x to d9/f"
> done
$ hg tracked --removeinclude d9
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
The following changeset(s) or their ancestors have local changes not on the remote:
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
...and 5 more, use --verbose to list all
abort: local changes found
(use --force-delete-local-changes to ignore)
[255]
Now test it *with* verbose.
$ hg tracked --removeinclude d9 --verbose
comparing with ssh://user@dummy/master
searching for changes
looking for local changes to affected paths
The following changeset(s) or their ancestors have local changes not on the remote:
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
^[0-9a-f]{12}$ (re)
abort: local changes found
(use --force-delete-local-changes to ignore)
[255]