phases: rework the logic of _pushdiscoveryphase to bound complexity
This rework the various graph traversal in _pushdiscoveryphase to keep the
complexity in check.
This is done though a couple of things:
- first, limiting the space we have to explore, for example, if we are not in
publishing push, we don't need to consider remote draft roots that are also
draft locally, as there is nothing to be moved there.
- avoid unbounded descendant computation, and use the faster "rev between"
computation.
This provide a massive boost to performance when exchanging with repository with
a massive amount of draft, like mozilla-try:
### data-env-vars.name = mozilla-try-2023-03-22-zstd-sparse-revlog
# benchmark.name = hg.command.push
# bin-env-vars.hg.flavor = default
# bin-env-vars.hg.py-re2-module = default
# benchmark.variants.explicit-rev = all-out-heads
# benchmark.variants.issue6528 = disabled
# benchmark.variants.protocol = ssh
# benchmark.variants.reuse-external-delta-parent = default
## benchmark.variants.revs = any-1-extra-rev
before: 20.346590 seconds
after: 11.232059 seconds (-38.15%, -7.48 seconds)
## benchmark.variants.revs = any-100-extra-rev
before: 24.752051 seconds
after: 15.367412 seconds (-37.91%, -9.38 seconds)
After this changes, the push operation is still quite too slow. Some of this
can be attributed to general phases slowness (reading all the roots from disk
for example) and other know slowness (not using persistent-nodemap, branchmap,
tags, etc. We are also working on them, but with this series, phase discovery
during push no longer showing up in profile and this is a pretty nice and bit
low-hanging fruit out of the way.
### (same case as the above)
# benchmark.variants.revs = any-1-extra-rev
pre-%ln-change: 44.235070
this-changeset: 11.232059 seconds (-74.61%, -33.00 seconds)
# benchmark.variants.revs = any-100-extra-rev
pre-%ln-change: 49.234697
this-changeset: 15.367412 seconds (-68.79%, -33.87 seconds)
Note that with this change, the `hg push` performance is now much closer to the
`hg pull` performance, even it still lagging behind a bit. (and the overall
performance are still too slow).
### data-env-vars.name = mozilla-try-2023-03-22-ds2-pnm
# benchmark.variants.explicit-rev = all-out-heads
# benchmark.variants.issue6528 = disabled
# benchmark.variants.protocol = ssh
# benchmark.variants.pulled-delta-reuse-policy = default
# bin-env-vars.hg.flavor = rust
## benchmark.variants.revs = any-1-extra-rev
hg.command.pull: 6.517450
hg.command.push: 11.219888
## benchmark.variants.revs = any-100-extra-rev
hg.command.pull: 10.160991
hg.command.push: 14.251107
### data-env-vars.name = mozilla-try-2023-03-22-zstd-sparse-revlog
# bin-env-vars.hg.py-re2-module = default
# benchmark.variants.explicit-rev = all-out-heads
# benchmark.variants.issue6528 = disabled
# benchmark.variants.protocol = ssh
# benchmark.variants.pulled-delta-reuse-policy = default
## bin-env-vars.hg.flavor = default
## benchmark.variants.revs = any-1-extra-rev
hg.command.pull: 8.577772
hg.command.push: 11.232059
## bin-env-vars.hg.flavor = default
## benchmark.variants.revs = any-100-extra-rev
hg.command.pull: 13.152976
hg.command.push: 15.367412
## bin-env-vars.hg.flavor = rust
## benchmark.variants.revs = any-1-extra-rev
hg.command.pull: 8.731982
hg.command.push: 11.178751
## bin-env-vars.hg.flavor = rust
## benchmark.variants.revs = any-100-extra-rev
hg.command.pull: 13.184236
hg.command.push: 15.620843
GNU diff is the reference for all of these results.
Prepare tests:
$ echo '[alias]' >> $HGRCPATH
$ echo 'ndiff = diff --nodates' >> $HGRCPATH
$ hg init repo
$ cd repo
$ printf 'hello world\ngoodbye world\n' >foo
$ hg ci -Amfoo -ufoo
adding foo
Test added blank lines:
$ printf '\nhello world\n\ngoodbye world\n\n' >foo
>>> two diffs showing three added lines <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
+
hello world
+
goodbye world
+
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
+
hello world
+
goodbye world
+
>>> no diffs <<<
$ hg ndiff -B
$ hg ndiff -Bb
Test added horizontal space first on a line():
$ printf '\t hello world\ngoodbye world\n' >foo
>>> four diffs showing added space first on the first line <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+ hello world
goodbye world
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+ hello world
goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+ hello world
goodbye world
$ hg ndiff -Bb
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+ hello world
goodbye world
Test added horizontal space last on a line:
$ printf 'hello world\t \ngoodbye world\n' >foo
>>> two diffs showing space appended to the first line <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+hello world
goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+hello world
goodbye world
>>> no diffs <<<
$ hg ndiff -b
$ hg ndiff -Bb
Test added horizontal space in the middle of a word:
$ printf 'hello world\ngood bye world\n' >foo
>>> four diffs showing space inserted into "goodbye" <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
hello world
-goodbye world
+good bye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
hello world
-goodbye world
+good bye world
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
hello world
-goodbye world
+good bye world
$ hg ndiff -Bb
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
hello world
-goodbye world
+good bye world
Test increased horizontal whitespace amount:
$ printf 'hello world\ngoodbye\t\t \tworld\n' >foo
>>> two diffs showing changed whitespace amount in the last line <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
hello world
-goodbye world
+goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
hello world
-goodbye world
+goodbye world
>>> no diffs <<<
$ hg ndiff -b
$ hg ndiff -Bb
Test added blank line with horizontal whitespace:
$ printf 'hello world\n \t\ngoodbye world\n' >foo
>>> three diffs showing added blank line with horizontal space <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+
goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+
goodbye world
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+
goodbye world
>>> no diffs <<<
$ hg ndiff -Bb
Test added blank line with other whitespace:
$ printf 'hello world\n \t\ngoodbye world \n' >foo
>>> three diffs showing added blank line with other space <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
-hello world
-goodbye world
+hello world
+
+goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
-hello world
-goodbye world
+hello world
+
+goodbye world
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+
goodbye world
>>> no diffs <<<
$ hg ndiff -Bb
Test whitespace changes:
$ printf 'helloworld\ngoodbye\tworld \n' >foo
>>> four diffs showing changed whitespace <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
-goodbye world
+helloworld
+goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
-goodbye world
+helloworld
+goodbye world
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+helloworld
goodbye world
$ hg ndiff -Bb
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,2 @@
-hello world
+helloworld
goodbye world
>>> no diffs <<<
$ hg ndiff -w
Test whitespace changes and blank lines:
$ printf 'helloworld\n\n\n\ngoodbye\tworld \n' >foo
>>> five diffs showing changed whitespace <<<
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
-hello world
-goodbye world
+helloworld
+
+
+
+goodbye world
$ hg ndiff -B
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
-hello world
-goodbye world
+helloworld
+
+
+
+goodbye world
$ hg ndiff -b
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
-hello world
+helloworld
+
+
+
goodbye world
$ hg ndiff -Bb
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
-hello world
+helloworld
+
+
+
goodbye world
$ hg ndiff -w
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,5 @@
hello world
+
+
+
goodbye world
>>> no diffs <<<
$ hg ndiff -wB
Test \r (carriage return) as used in "DOS" line endings:
$ printf 'hello world\r\n\r\ngoodbye\rworld\n' >foo
$ hg ndiff
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
-hello world
-goodbye world
+hello world\r (esc)
+\r (esc)
+goodbye\r (no-eol) (esc)
world
Test \r (carriage return) as used in "DOS" line endings:
$ printf 'hello world \r\n\t\ngoodbye world\n' >foo
$ hg ndiff --ignore-space-at-eol
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+\t (esc)
goodbye world
No completely blank lines to ignore:
$ printf 'hello world\r\n\r\ngoodbye\rworld\n' >foo
$ hg ndiff --ignore-blank-lines
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
-hello world
-goodbye world
+hello world\r (esc)
+\r (esc)
+goodbye\r (no-eol) (esc)
world
Only new line noticed:
$ hg ndiff --ignore-space-change
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+\r (esc)
goodbye world
$ hg ndiff --ignore-all-space
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
hello world
+\r (esc)
goodbye world
New line not noticed when space change ignored:
$ hg ndiff --ignore-blank-lines --ignore-all-space
Do not ignore all newlines, only blank lines
$ printf 'hello \nworld\ngoodbye world\n' > foo
$ hg ndiff --ignore-blank-lines
diff -r 540c40a65b78 foo
--- a/foo
+++ b/foo
@@ -1,2 +1,3 @@
-hello world
+hello
+world
goodbye world
Test hunk offsets adjustments with --ignore-blank-lines
$ hg revert -aC
reverting foo
$ printf '\nb\nx\nd\n' > a
$ printf 'b\ny\nd\n' > b
$ hg add a b
$ hg ci -m add
$ hg cat -r . a > b
$ hg cat -r . b > a
$ hg diff -B --nodates a > ../diffa
$ cat ../diffa
diff -r 0e66aa54f318 a
--- a/a
+++ b/a
@@ -1,4 +1,4 @@
b
-x
+y
d
$ hg diff -B --nodates b > ../diffb
$ cat ../diffb
diff -r 0e66aa54f318 b
--- a/b
+++ b/b
@@ -1,3 +1,3 @@
b
-y
+x
d
$ hg revert -aC
reverting a
reverting b
$ hg import --no-commit ../diffa
applying ../diffa
$ hg revert -aC
reverting a
$ hg import --no-commit ../diffb
applying ../diffb
$ hg revert -aC
reverting b