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
#!/usr/bin/env python3
#
# hgperf - measure performance of Mercurial commands
#
# Copyright 2014 Olivia Mackall <olivia@selenic.com>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
'''measure performance of Mercurial commands
Using ``hgperf`` instead of ``hg`` measures performance of the target
Mercurial command. For example, the execution below measures
performance of :hg:`heads --topo`::
$ hgperf heads --topo
All command output via ``ui`` is suppressed, and just measurement
result is displayed: see also "perf" extension in "contrib".
Costs of processing before dispatching to the command function like
below are not measured::
- parsing command line (e.g. option validity check)
- reading configuration files in
But ``pre-`` and ``post-`` hook invocation for the target command is
measured, even though these are invoked before or after dispatching to
the command function, because these may be required to repeat
execution of the target command correctly.
'''
import os
import sys
libdir = '@LIBDIR@'
if libdir != '@' 'LIBDIR' '@':
if not os.path.isabs(libdir):
libdir = os.path.join(
os.path.dirname(os.path.realpath(__file__)), libdir
)
libdir = os.path.abspath(libdir)
sys.path.insert(0, libdir)
# enable importing on demand to reduce startup time
try:
from mercurial import demandimport
demandimport.enable()
except ImportError:
import sys
sys.stderr.write(
"abort: couldn't find mercurial libraries in [%s]\n"
% ' '.join(sys.path)
)
sys.stderr.write("(check your install and PYTHONPATH)\n")
sys.exit(-1)
from mercurial import (
dispatch,
util,
)
def timer(func, title=None):
results = []
begin = util.timer()
count = 0
while True:
ostart = os.times()
cstart = util.timer()
r = func()
cstop = util.timer()
ostop = os.times()
count += 1
a, b = ostart, ostop
results.append((cstop - cstart, b[0] - a[0], b[1] - a[1]))
if cstop - begin > 3 and count >= 100:
break
if cstop - begin > 10 and count >= 3:
break
if title:
sys.stderr.write("! %s\n" % title)
if r:
sys.stderr.write("! result: %s\n" % r)
m = min(results)
sys.stderr.write(
"! wall %f comb %f user %f sys %f (best of %d)\n"
% (m[0], m[1] + m[2], m[1], m[2], count)
)
orgruncommand = dispatch.runcommand
def runcommand(lui, repo, cmd, fullargs, ui, options, d, cmdpats, cmdoptions):
ui.pushbuffer()
lui.pushbuffer()
timer(
lambda: orgruncommand(
lui, repo, cmd, fullargs, ui, options, d, cmdpats, cmdoptions
)
)
ui.popbuffer()
lui.popbuffer()
dispatch.runcommand = runcommand
dispatch.run()