dirstate-tree: Avoid BTreeMap double-lookup when inserting a dirstate entry
The child nodes of a given node in the tree-shaped dirstate are kept in a
`BTreeMap` where keys are file names as strings. Finding or inserting a value
in the map takes `O(log(n))` string comparisons, which adds up when constructing
the tree.
The `entry` API allows finding a "spot" in the map that may or may not be
occupied and then access that value or insert a new one without doing map
lookup again. However the current API is limited in that calling `entry`
requires an owned key (and so a memory allocation), even if it ends up not
being used in the case where the map already has a value with an equal key.
This is still a win, with 4% better end-to-end time for `hg status` measured
here with hyperfine:
```
Benchmark #1: ../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1
Time (mean ± σ): 1.337 s ± 0.018 s [User: 892.9 ms, System: 437.5 ms]
Range (min … max): 1.316 s … 1.373 s 10 runs
Benchmark #2: ./hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1
Time (mean ± σ): 1.291 s ± 0.008 s [User: 853.4 ms, System: 431.1 ms]
Range (min … max): 1.283 s … 1.309 s 10 runs
Summary
'./hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ran
1.04 ± 0.02 times faster than '../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1'
```
* ./hg is this revision
* ../hg2/hg is its parent
* $REPO is an old snapshot of mozilla-central
Differential Revision: https://phab.mercurial-scm.org/D10550
#require no-windows
$ . "$TESTDIR/remotefilelog-library.sh"
$ hg init master
$ cd master
$ cat >> .hg/hgrc <<EOF
> [remotefilelog]
> server=True
> EOF
$ echo x > x
$ echo y > y
$ echo z > z
$ hg commit -qAm xy
$ cd ..
$ hgcloneshallow ssh://user@dummy/master shallow -q
3 files fetched over 1 fetches - (3 misses, 0.00% hit ratio) over *s (glob)
$ cd shallow
# status
$ clearcache
$ echo xx > x
$ echo yy > y
$ touch a
$ hg status
M x
M y
? a
1 files fetched over 1 fetches - (1 misses, 0.00% hit ratio) over *s (glob)
$ hg add a
$ hg status
M x
M y
A a
# diff
$ hg debugrebuilddirstate # fixes dirstate non-determinism
$ hg add a
$ clearcache
$ hg diff
diff -r f3d0bb0d1e48 x
--- a/x* (glob)
+++ b/x* (glob)
@@ -1,1 +1,1 @@
-x
+xx
diff -r f3d0bb0d1e48 y
--- a/y* (glob)
+++ b/y* (glob)
@@ -1,1 +1,1 @@
-y
+yy
3 files fetched over 1 fetches - (3 misses, 0.00% hit ratio) over *s (glob)
# local commit
$ clearcache
$ echo a > a
$ echo xxx > x
$ echo yyy > y
$ hg commit -m a
? files fetched over 1 fetches - (? misses, 0.00% hit ratio) over *s (glob)
# local commit where the dirstate is clean -- ensure that we do just one fetch
# (update to a commit on the server first)
$ hg --config debug.dirstate.delaywrite=1 up 0
2 files updated, 0 files merged, 1 files removed, 0 files unresolved
$ clearcache
$ hg debugdirstate
n 644 2 * x (glob)
n 644 2 * y (glob)
n 644 2 * z (glob)
$ echo xxxx > x
$ echo yyyy > y
$ hg commit -m x
created new head
2 files fetched over 1 fetches - (2 misses, 0.00% hit ratio) over *s (glob)
# restore state for future tests
$ hg -q strip .
$ hg -q up tip
# rebase
$ clearcache
$ cd ../master
$ echo w > w
$ hg commit -qAm w
$ cd ../shallow
$ hg pull
pulling from ssh://user@dummy/master
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 0 changes to 0 files (+1 heads)
new changesets fed61014d323
(run 'hg heads' to see heads, 'hg merge' to merge)
$ hg rebase -d tip
rebasing 1:9abfe7bca547 "a"
saved backup bundle to $TESTTMP/shallow/.hg/strip-backup/9abfe7bca547-8b11e5ff-rebase.hg (glob)
3 files fetched over 2 fetches - (3 misses, 0.00% hit ratio) over *s (glob)
# strip
$ clearcache
$ hg debugrebuilddirstate # fixes dirstate non-determinism
$ hg strip -r .
2 files updated, 0 files merged, 1 files removed, 0 files unresolved
saved backup bundle to $TESTTMP/shallow/.hg/strip-backup/19edf50f4de7-df3d0f74-backup.hg (glob)
3 files fetched over 2 fetches - (3 misses, 0.00% hit ratio) over *s (glob)
# unbundle
$ clearcache
$ ls -A
.hg
w
x
y
z
$ hg debugrebuilddirstate # fixes dirstate non-determinism
$ hg unbundle .hg/strip-backup/19edf50f4de7-df3d0f74-backup.hg
adding changesets
adding manifests
adding file changes
added 1 changesets with 3 changes to 3 files
new changesets 19edf50f4de7 (1 drafts)
(run 'hg update' to get a working copy)
2 files fetched over 1 fetches - (2 misses, 0.00% hit ratio) over *s (glob)
$ hg up
3 files updated, 0 files merged, 0 files removed, 0 files unresolved
1 files fetched over 1 fetches - (1 misses, 0.00% hit ratio) over *s (glob)
$ cat a
a
# revert
$ clearcache
$ hg revert -r .~2 y z
no changes needed to z
1 files fetched over 1 fetches - (1 misses, 0.00% hit ratio) over *s (glob)
$ hg checkout -C -r . -q
# explicit bundle should produce full bundle file
$ hg bundle -r 2 --base 1 ../local.bundle
1 changesets found
1 files fetched over 1 fetches - (1 misses, 0.00% hit ratio) over *s (glob)
$ cd ..
$ hgcloneshallow ssh://user@dummy/master shallow2 -q
2 files fetched over 1 fetches - (2 misses, 0.00% hit ratio) over *s (glob)
$ cd shallow2
$ hg unbundle ../local.bundle
adding changesets
adding manifests
adding file changes
added 1 changesets with 3 changes to 3 files
new changesets 19edf50f4de7 (1 drafts)
(run 'hg update' to get a working copy)
$ hg log -r 2 --stat
changeset: 2:19edf50f4de7
tag: tip
user: test
date: Thu Jan 01 00:00:00 1970 +0000
summary: a
a | 1 +
x | 2 +-
y | 2 +-
3 files changed, 3 insertions(+), 2 deletions(-)
# Merge
$ echo merge >> w
$ hg commit -m w
created new head
$ hg merge 2
3 files updated, 0 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
$ hg commit -m merge
$ hg strip -q -r ".^"
# commit without producing new node
$ cd $TESTTMP
$ hgcloneshallow ssh://user@dummy/master shallow3 -q
$ cd shallow3
$ echo 1 > A
$ hg commit -m foo -A A
$ hg log -r . -T '{node}\n'
383ce605500277f879b7460a16ba620eb6930b7f
$ hg update -r '.^' -q
$ echo 1 > A
$ hg commit -m foo -A A
warning: commit already existed in the repository!
$ hg log -r . -T '{node}\n'
383ce605500277f879b7460a16ba620eb6930b7f