revset: add depth limit to descendants() (issue5374)
This is naive implementation using two-pass scanning. Tracking descendants
isn't an easy problem if both start and stop depths are specified. It's
impractical to remember all possible depths of each node while scanning from
roots to descendants because the number of depths explodes. Instead, we could
cache (min, max) depths as a good approximation and track ancestors back when
needed, but that's likely to have off-by-one bug.
Since this implementation appears not significantly slower, and is quite
straightforward, I think it's good enough for practical use cases. The time
and space complexity is O(n) ish.
revisions:
0) 1-pass scanning with (min, max)-depth cache (worst-case quadratic)
1) 2-pass scanning (this version)
repository:
mozilla-central
# descendants(0) (for reference)
*) 0.430353
# descendants(0, depth=1000)
0) 0.264889
1) 0.398289
# descendants(limit(tip:0, 1, offset=10000), depth=1000)
0) 0.025478
1) 0.029099
# descendants(0, depth=2000, startdepth=1000)
0) painfully slow (due to quadratic backtracking of ancestors)
1) 1.531138
# memory.py - track memory usage
#
# Copyright 2009 Matt Mackall <mpm@selenic.com> and others
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
'''helper extension to measure memory usage
Reads current and peak memory usage from ``/proc/self/status`` and
prints it to ``stderr`` on exit.
'''
from __future__ import absolute_import
def memusage(ui):
"""Report memory usage of the current process."""
result = {'peak': 0, 'rss': 0}
with open('/proc/self/status', 'r') as status:
# This will only work on systems with a /proc file system
# (like Linux).
for line in status:
parts = line.split()
key = parts[0][2:-1].lower()
if key in result:
result[key] = int(parts[1])
ui.write_err(", ".join(["%s: %.1f MiB" % (k, v / 1024.0)
for k, v in result.iteritems()]) + "\n")
def extsetup(ui):
ui.atexit(memusage, ui)