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
$ remove() {
> hg rm $@
> echo "exit code: $?"
> hg st
> # do not use ls -R, which recurses in .hg subdirs on Mac OS X 10.5
> find . -name .hg -prune -o -type f -print | sort
> hg up -C
> }
$ cat >> $HGRCPATH <<EOF
> [progress]
> disable=False
> assume-tty = 1
> delay = 0
> # set changedelay really large so we don't see nested topics
> changedelay = 30000
> format = topic bar number
> refresh = 0
> width = 60
> EOF
$ hg init a
$ cd a
$ echo a > foo
file not managed
$ remove foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing foo: file is untracked
exit code: 1
? foo
./foo
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg add foo
$ hg commit -m1
the table cases
00 state added, options none
$ echo b > bar
$ hg add bar
$ remove bar
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing bar: file has been marked for add (use 'hg forget' to undo add)
exit code: 1
A bar
./bar
./foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
01 state clean, options none
$ remove foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
? bar
./bar
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
02 state modified, options none
$ echo b >> foo
$ remove foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing foo: file is modified (use -f to force removal)
exit code: 1
M foo
? bar
./bar
./foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
03 state missing, options none
$ rm foo
$ remove foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
? bar
./bar
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
10 state added, options -f
$ echo b > bar
$ hg add bar
$ remove -f bar
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
? bar
./bar
./foo
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ rm bar
11 state clean, options -f
$ remove -f foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
12 state modified, options -f
$ echo b >> foo
$ remove -f foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
13 state missing, options -f
$ rm foo
$ remove -f foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
20 state added, options -A
$ echo b > bar
$ hg add bar
$ remove -A bar
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing bar: file still exists
exit code: 1
A bar
./bar
./foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
21 state clean, options -Av
$ remove -Av foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing foo: file still exists
exit code: 1
? bar
./bar
./foo
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
22 state modified, options -Av
$ echo b >> foo
$ remove -Av foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing foo: file still exists
exit code: 1
M foo
? bar
./bar
./foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
23 state missing, options -A
$ rm foo
$ remove -A foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
? bar
./bar
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
30 state added, options -Af
$ echo b > bar
$ hg add bar
$ remove -Af bar
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
? bar
./bar
./foo
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ rm bar
31 state clean, options -Af
$ remove -Af foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
./foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
32 state modified, options -Af
$ echo b >> foo
$ remove -Af foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
./foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
33 state missing, options -Af
$ rm foo
$ remove -Af foo
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
exit code: 0
R foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
test some directory stuff
$ mkdir test
$ echo a > test/foo
$ echo b > test/bar
$ hg ci -Am2
adding test/bar
adding test/foo
dir, options none
$ rm test/bar
$ remove test
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [=====================> ] 1/2\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
removing test/bar
removing test/foo
exit code: 0
R test/bar
R test/foo
./foo
\r (no-eol) (esc)
updating [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
dir, options -f
$ rm test/bar
$ remove -f test
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [=====================> ] 1/2\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
removing test/bar
removing test/foo
exit code: 0
R test/bar
R test/foo
./foo
\r (no-eol) (esc)
updating [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
dir, options -Av
$ rm test/bar
$ remove -Av test
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
removing test/bar
not removing test/foo: file still exists
exit code: 1
R test/bar
./foo
./test/foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
dir, options -A <dir>
$ rm test/bar
$ remove -A test
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
skipping [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
removing test/bar
exit code: 1
R test/bar
./foo
./test/foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
without any files/dirs, options -A
$ rm test/bar
$ remove -A
\r (no-eol) (esc)
skipping [=====================> ] 1/2\r (no-eol) (esc)
skipping [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
removing test/bar
exit code: 1
R test/bar
./foo
./test/foo
\r (no-eol) (esc)
updating [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
dir, options -Af
$ rm test/bar
$ remove -Af test
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [=====================> ] 1/2\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
removing test/bar
removing test/foo
exit code: 0
R test/bar
R test/foo
./foo
./test/foo
\r (no-eol) (esc)
updating [===========================================>] 2/2\r (no-eol) (esc)
\r (no-eol) (esc)
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
test remove dropping empty trees (issue1861)
$ mkdir -p issue1861/b/c
$ echo x > issue1861/x
$ echo y > issue1861/b/c/y
$ hg ci -Am add
adding issue1861/b/c/y
adding issue1861/x
$ hg rm issue1861/b
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
removing issue1861/b/c/y
$ hg ci -m remove
$ ls issue1861
x
test that commit does not crash if the user removes a newly added file
$ touch f1
$ hg add f1
$ rm f1
$ hg ci -A -mx
removing f1
nothing changed
[1]
handling of untracked directories and missing files
$ mkdir d1
$ echo a > d1/a
$ hg rm --after d1
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
not removing d1: no tracked files
[1]
$ hg add d1/a
$ rm d1/a
$ hg rm --after d1
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
removing d1/a
$ hg rm --after nosuch
nosuch: * (glob)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
[1]
test dry-run for remove
$ hg init testdryrun
$ cd testdryrun
$ echo a>a
$ hg ci -qAm1
$ hg remove a -nv
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
removing a
$ hg remove a -nv --color debug
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
\r (no-eol) (esc)
deleting [===========================================>] 1/1\r (no-eol) (esc)
\r (no-eol) (esc)
[ui.addremove.removed ui.status|removing a]
$ hg diff
$ cat >> .hg/hgrc <<EOF
> [extensions]
> largefiles=
> EOF
$ echo 'B as largefile' > B
$ hg add --large B
$ hg ci -m "B"
$ hg remove B -nv
removing B
$ hg st
$ cd ..