obsolete: order of magnitude speedup in _computebumpedset
Reminder: a changeset is said "bumped" if it tries to obsolete a immutable
changeset.
The previous algorithm for computing bumped changeset was:
1) Get all public changesets
2) Find all they successors
3) Search for stuff that are eligible for being "bumped"
(mutable and non obsolete)
The entry size of this algorithm is `O(len(public))` which is mostly the same as
`O(len(repo))`. Even this this approach mean fewer obsolescence marker are
traveled, this is not very scalable.
The new algorithm is:
1) For each potential bumped changesets (non obsolete mutable)
2) iterate over precursors
3) if a precursors is public. changeset is bumped
We travel more obsolescence marker, but the entry size is much smaller since
the amount of potential bumped should remains mostly stable with time `O(1)`.
On some confidential gigantic repo this move bumped computation from 15.19s to
0.46s (×33 speedup…). On "smaller" repo (mercurial, cubicweb's review) no
significant gain were seen. The additional traversal of obsolescence marker is
probably probably counter balance the advantage of it.
Other optimisation could be done in the future (eg: sharing precursors cache
for divergence detection)
$ "$TESTDIR/hghave" killdaemons || exit 80
$ hgserve() {
> hg serve -a localhost -p $HGPORT1 -d --pid-file=hg.pid \
> -E errors.log -v $@ > startup.log
> # Grepping hg serve stdout would hang on Windows
> grep -v 'listening at' startup.log
> cat hg.pid >> "$DAEMON_PIDS"
> }
$ hg init a
$ hg --encoding utf-8 -R a branch æ
marked working directory as branch \xc3\xa6 (esc)
(branches are permanent and global, did you want a bookmark?)
$ echo foo > a/foo
$ hg -R a ci -Am foo
adding foo
$ hgserve -R a --config web.push_ssl=False --config web.allow_push=* --encoding latin1
$ hg --encoding utf-8 clone http://localhost:$HGPORT1 b
requesting all changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 1 changes to 1 files
updating to branch \xc3\xa6 (esc)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg --encoding utf-8 -R b log
changeset: 0:867c11ce77b8
branch: \xc3\xa6 (esc)
tag: tip
user: test
date: Thu Jan 01 00:00:00 1970 +0000
summary: foo
$ echo bar >> b/foo
$ hg -R b ci -m bar
$ hg --encoding utf-8 -R b push
pushing to http://localhost:$HGPORT1/
searching for changes
remote: adding changesets
remote: adding manifests
remote: adding file changes
remote: added 1 changesets with 1 changes to 1 files
$ hg -R a --encoding utf-8 log
changeset: 1:58e7c90d67cb
branch: \xc3\xa6 (esc)
tag: tip
user: test
date: Thu Jan 01 00:00:00 1970 +0000
summary: bar
changeset: 0:867c11ce77b8
branch: \xc3\xa6 (esc)
user: test
date: Thu Jan 01 00:00:00 1970 +0000
summary: foo
$ "$TESTDIR/killdaemons.py" hg.pid
verify 7e7d56fe4833 (encoding fallback in branchmap to maintain compatibility with 1.3.x)
$ cat <<EOF > oldhg
> import sys
> from mercurial import ui, hg, commands
>
> class StdoutWrapper(object):
> def __init__(self, stdout):
> self._file = stdout
>
> def write(self, data):
> if data == '47\n':
> # latin1 encoding is one %xx (3 bytes) shorter
> data = '44\n'
> elif data.startswith('%C3%A6 '):
> # translate to latin1 encoding
> data = '%%E6 %s' % data[7:]
> self._file.write(data)
>
> def __getattr__(self, name):
> return getattr(self._file, name)
>
> sys.stdout = StdoutWrapper(sys.stdout)
> sys.stderr = StdoutWrapper(sys.stderr)
>
> myui = ui.ui()
> repo = hg.repository(myui, 'a')
> commands.serve(myui, repo, stdio=True, cmdserver=False)
> EOF
$ echo baz >> b/foo
$ hg -R b ci -m baz
$ hg push -R b -e 'python oldhg' ssh://dummy/ --encoding latin1
pushing to ssh://dummy/
searching for changes
remote: adding changesets
remote: adding manifests
remote: adding file changes
remote: added 1 changesets with 1 changes to 1 files