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
$ cat << EOF >> $HGRCPATH
> [extensions]
> rebase=
> EOF
==================================
Test backup-bundle config option |
==================================
Test with Pre-obsmarker rebase:
1) When config option is not set:
$ hg init repo1
$ cd repo1
$ echo a>a
$ hg ci -qAma
$ echo b>b
$ hg ci -qAmb
$ echo c>c
$ hg ci -qAmc
$ hg up 0 -q
$ echo d>d
$ hg ci -qAmd
$ echo e>e
$ hg ci -qAme
$ hg log -GT "{rev}: {firstline(desc)}\n"
@ 4: e
|
o 3: d
|
| o 2: c
| |
| o 1: b
|/
o 0: a
$ hg rebase -s 1 -d .
rebasing 1:d2ae7f538514 "b"
rebasing 2:177f92b77385 "c"
saved backup bundle to $TESTTMP/repo1/.hg/strip-backup/d2ae7f538514-c7ed7a78-rebase.hg
$ hg log -GT "{rev}: {firstline(desc)}\n"
o 4: c
|
o 3: b
|
@ 2: e
|
o 1: d
|
o 0: a
2) When config option is set:
$ cat << EOF >> $HGRCPATH
> [rewrite]
> backup-bundle = False
> EOF
$ echo f>f
$ hg ci -Aqmf
$ echo g>g
$ hg ci -Aqmg
$ hg log -GT "{rev}: {firstline(desc)}\n"
@ 6: g
|
o 5: f
|
| o 4: c
| |
| o 3: b
|/
o 2: e
|
o 1: d
|
o 0: a
$ hg rebase -s 3 -d .
rebasing 3:05bff2a95b12 "b"
rebasing 4:1762bde4404d "c"
$ hg log -GT "{rev}: {firstline(desc)}\n"
o 6: c
|
o 5: b
|
@ 4: g
|
o 3: f
|
o 2: e
|
o 1: d
|
o 0: a
Test when rebased revisions are stripped during abort:
======================================================
$ echo conflict > c
$ hg ci -Am "conflict with c"
adding c
created new head
$ hg log -GT "{rev}: {firstline(desc)}\n"
@ 7: conflict with c
|
| o 6: c
| |
| o 5: b
|/
o 4: g
|
o 3: f
|
o 2: e
|
o 1: d
|
o 0: a
When backup-bundle = True:
$ cat << EOF >> $HGRCPATH
> [rewrite]
> backup-bundle = True
> EOF
$ hg rebase -s 5 -d .
rebasing 5:1f8148a544ee "b"
rebasing 6:f8bc7d28e573 "c"
merging c
warning: conflicts while merging c! (edit, then use 'hg resolve --mark')
unresolved conflicts (see 'hg resolve', then 'hg rebase --continue')
[240]
$ hg rebase --abort
saved backup bundle to $TESTTMP/repo1/.hg/strip-backup/818c1a43c916-2b644d96-backup.hg
rebase aborted
When backup-bundle = False:
$ cat << EOF >> $HGRCPATH
> [rewrite]
> backup-bundle = False
> EOF
$ hg rebase -s 5 -d .
rebasing 5:1f8148a544ee "b"
rebasing 6:f8bc7d28e573 "c"
merging c
warning: conflicts while merging c! (edit, then use 'hg resolve --mark')
unresolved conflicts (see 'hg resolve', then 'hg rebase --continue')
[240]
$ hg rebase --abort
rebase aborted
$ cd ..