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
$ hg init test-content
$ cd test-content
$ hg debugbuilddag '+2*2*3*4+7'
$ hg bookmark -r 1 @
$ hg log -G --template '{rev}:{node|short}'
o 11:1d876b1f862c
|
o 10:ea5f71948eb8
|
o 9:f1b0356d867a
|
o 8:e8d1253fb0d7
|
o 7:d423bbba4459
|
o 6:a2f58e9c1e56
|
o 5:3a367db1fabc
|
o 4:e7bd5218ca15
|
| o 3:6100d3090acf
|/
| o 2:fa942426a6fd
|/
| o 1:66f7d451a68b
|/
o 0:1ea73414a91b
$ hg --config extensions.closehead= close-head -m 'Not a head' 0 1
abort: revision is not an open head: 0
[255]
$ hg --config extensions.closehead= close-head -m 'Not a head' -r 0 1
abort: revision is not an open head: 0
[255]
$ hg id
000000000000
$ hg --config extensions.closehead= close-head -m 'Close old heads' -r 1 2
$ hg id
000000000000
$ hg bookmark
@ 1:66f7d451a68b
$ hg heads
changeset: 11:1d876b1f862c
user: debugbuilddag
date: Thu Jan 01 00:00:11 1970 +0000
summary: r11
changeset: 3:6100d3090acf
parent: 0:1ea73414a91b
user: debugbuilddag
date: Thu Jan 01 00:00:03 1970 +0000
summary: r3
$ hg --config extensions.closehead= close-head -m 'Close more old heads' -r 11
$ hg heads
changeset: 3:6100d3090acf
parent: 0:1ea73414a91b
user: debugbuilddag
date: Thu Jan 01 00:00:03 1970 +0000
summary: r3
$ hg --config extensions.closehead= close-head -m 'Not a head' 0
abort: revision is not an open head: 0
[255]
$ hg --config extensions.closehead= close-head -m 'Already closed head' 1
abort: revision is not an open head: 1
[255]
$ hg init ../test-empty
$ cd ../test-empty
$ hg debugbuilddag '+1'
$ hg log -G --template '{rev}:{node|short}'
o 0:1ea73414a91b
$ hg --config extensions.closehead= close-head -m 'Close initial revision' 0
$ hg heads
[1]