revset: stop serializing node when using "%ln"
Turning hundred of thousand of node from node to hex and back can be slow… what
about we stop doing it?
In many case were we are using node id we should be using revision id. However
this is not a good reason to have a stupidly slow implementation of "%ln".
This caught my attention again because the phase discovery during push make an
extensive use of "%ln" or huge set. In absolute, that phase discovery probably
should use "%ld" and need to improves its algorithmic complexity, but improving
"%ln" seems simple and long overdue. This greatly speeds up `hg push` on
repository with many drafts.
Here are some relevant poulpe benchmarks:
### data-env-vars.name = mozilla-try-2023-03-22-zstd-sparse-revlog
# benchmark.name = hg.command.push
# bin-env-vars.hg.flavor = default
# bin-env-vars.hg.py-re2-module = default
# benchmark.variants.explicit-rev = all-out-heads
# benchmark.variants.issue6528 = disabled
# benchmark.variants.protocol = ssh
# benchmark.variants.reuse-external-delta-parent = default
## benchmark.variants.revs = any-1-extra-rev
before: 44.235070
after: 20.416329 (-53.85%, -23.82)
## benchmark.variants.revs = any-100-extra-rev
before: 49.234697
after: 26.519829 (-46.14%, -22.71)
### benchmark.name = hg.command.bundle
# bin-env-vars.hg.flavor = default
# bin-env-vars.hg.py-re2-module = default
# benchmark.variants.revs = all
# benchmark.variants.type = none-streamv2
## data-env-vars.name = heptapod-public-2024-03-25-zstd-sparse-revlog
before: 10.138396
after: 7.750458 (-23.55%, -2.39)
## data-env-vars.name = mercurial-public-2024-03-22-zstd-sparse-revlog
before: 1.263859
after: 0.700229 (-44.60%, -0.56)
## data-env-vars.name = mozilla-try-2023-03-22-zstd-sparse-revlog
before: 399.484481
after: 346.5089 (-13.26%, -52.98)
## data-env-vars.name = pypy-2024-03-22-zstd-sparse-revlog
before: 4.540080
after: 3.401700 (-25.07%, -1.14)
## data-env-vars.name = tryton-public-2024-03-22-zstd-sparse-revlog
before: 2.975765
after: 1.870798 (-37.13%, -1.10)
import difflib
import random
import unittest
from mercurial import linelog
vecratio = 3 # number of replacelines / number of replacelines_vec
maxlinenum = 0xFFFFFF
maxb1 = 0xFFFFFF
maxdeltaa = 10
maxdeltab = 10
def _genedits(seed, endrev):
lines = []
random.seed(seed)
for rev in range(0, endrev):
n = len(lines)
a1 = random.randint(0, n)
a2 = random.randint(a1, min(n, a1 + maxdeltaa))
b1 = random.randint(0, maxb1)
b2 = random.randint(b1, b1 + maxdeltab)
usevec = not bool(random.randint(0, vecratio))
if usevec:
blines = [
(random.randint(0, rev), random.randint(0, maxlinenum))
for _ in range(b1, b2)
]
else:
blines = [(rev, bidx) for bidx in range(b1, b2)]
lines[a1:a2] = blines
yield lines, rev, a1, a2, b1, b2, blines, usevec
class linelogtests(unittest.TestCase):
def testlinelogencodedecode(self):
program = [
linelog._eof(0, 0),
linelog._jge(41, 42),
linelog._jump(0, 43),
linelog._eof(0, 0),
linelog._jl(44, 45),
linelog._line(46, 47),
]
ll = linelog.linelog(program, maxrev=100)
enc = ll.encode()
# round-trips okay
self.assertEqual(linelog.linelog.fromdata(enc)._program, ll._program)
self.assertEqual(linelog.linelog.fromdata(enc), ll)
# This encoding matches the encoding used by hg-experimental's
# linelog file, or is supposed to if it doesn't.
self.assertEqual(
enc,
(
b'\x00\x00\x01\x90\x00\x00\x00\x06'
b'\x00\x00\x00\xa4\x00\x00\x00*'
b'\x00\x00\x00\x00\x00\x00\x00+'
b'\x00\x00\x00\x00\x00\x00\x00\x00'
b'\x00\x00\x00\xb1\x00\x00\x00-'
b'\x00\x00\x00\xba\x00\x00\x00/'
),
)
def testsimpleedits(self):
ll = linelog.linelog()
# Initial revision: add lines 0, 1, and 2
ll.replacelines(1, 0, 0, 0, 3)
self.assertEqual(
[(l.rev, l.linenum) for l in ll.annotate(1)],
[
(1, 0),
(1, 1),
(1, 2),
],
)
# Replace line 1 with a new line
ll.replacelines(2, 1, 2, 1, 2)
self.assertEqual(
[(l.rev, l.linenum) for l in ll.annotate(2)],
[
(1, 0),
(2, 1),
(1, 2),
],
)
# delete a line out of 2
ll.replacelines(3, 1, 2, 0, 0)
self.assertEqual(
[(l.rev, l.linenum) for l in ll.annotate(3)],
[
(1, 0),
(1, 2),
],
)
# annotation of 1 is unchanged
self.assertEqual(
[(l.rev, l.linenum) for l in ll.annotate(1)],
[
(1, 0),
(1, 1),
(1, 2),
],
)
ll.annotate(3) # set internal state to revision 3
start = ll.getoffset(0)
end = ll.getoffset(1)
self.assertEqual(
ll.getalllines(start, end),
[
(1, 0),
(2, 1),
(1, 1),
],
)
self.assertEqual(
ll.getalllines(),
[
(1, 0),
(2, 1),
(1, 1),
(1, 2),
],
)
def testparseclinelogfile(self):
# This data is what the replacements in testsimpleedits
# produce when fed to the original linelog.c implementation.
data = (
b'\x00\x00\x00\x0c\x00\x00\x00\x0f'
b'\x00\x00\x00\x00\x00\x00\x00\x02'
b'\x00\x00\x00\x05\x00\x00\x00\x06'
b'\x00\x00\x00\x06\x00\x00\x00\x00'
b'\x00\x00\x00\x00\x00\x00\x00\x07'
b'\x00\x00\x00\x06\x00\x00\x00\x02'
b'\x00\x00\x00\x00\x00\x00\x00\x00'
b'\x00\x00\x00\t\x00\x00\x00\t'
b'\x00\x00\x00\x00\x00\x00\x00\x0c'
b'\x00\x00\x00\x08\x00\x00\x00\x05'
b'\x00\x00\x00\x06\x00\x00\x00\x01'
b'\x00\x00\x00\x00\x00\x00\x00\x05'
b'\x00\x00\x00\x0c\x00\x00\x00\x05'
b'\x00\x00\x00\n\x00\x00\x00\x01'
b'\x00\x00\x00\x00\x00\x00\x00\t'
)
llc = linelog.linelog.fromdata(data)
self.assertEqual(
[(l.rev, l.linenum) for l in llc.annotate(1)],
[
(1, 0),
(1, 1),
(1, 2),
],
)
self.assertEqual(
[(l.rev, l.linenum) for l in llc.annotate(2)],
[
(1, 0),
(2, 1),
(1, 2),
],
)
self.assertEqual(
[(l.rev, l.linenum) for l in llc.annotate(3)],
[
(1, 0),
(1, 2),
],
)
# Check we emit the same bytecode.
ll = linelog.linelog()
# Initial revision: add lines 0, 1, and 2
ll.replacelines(1, 0, 0, 0, 3)
# Replace line 1 with a new line
ll.replacelines(2, 1, 2, 1, 2)
# delete a line out of 2
ll.replacelines(3, 1, 2, 0, 0)
diff = '\n ' + '\n '.join(
difflib.unified_diff(
ll.debugstr().splitlines(),
llc.debugstr().splitlines(),
'python',
'c',
lineterm='',
)
)
self.assertEqual(ll._program, llc._program, 'Program mismatch: ' + diff)
# Done as a secondary step so we get a better result if the
# program is where the mismatch is.
self.assertEqual(ll, llc)
self.assertEqual(ll.encode(), data)
def testanothersimplecase(self):
ll = linelog.linelog()
ll.replacelines(3, 0, 0, 0, 2)
ll.replacelines(4, 0, 2, 0, 0)
self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(4)], [])
self.assertEqual(
[(l.rev, l.linenum) for l in ll.annotate(3)], [(3, 0), (3, 1)]
)
# rev 2 is empty because contents were only ever introduced in rev 3
self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(2)], [])
def testrandomedits(self):
# Inspired by original linelog tests.
seed = random.random()
numrevs = 2000
ll = linelog.linelog()
# Populate linelog
for lines, rev, a1, a2, b1, b2, blines, usevec in _genedits(
seed, numrevs
):
if usevec:
ll.replacelines_vec(rev, a1, a2, blines)
else:
ll.replacelines(rev, a1, a2, b1, b2)
ll.annotate(rev)
self.assertEqual(ll.annotateresult, lines)
# Verify we can get back these states by annotating each rev
for lines, rev, a1, a2, b1, b2, blines, usevec in _genedits(
seed, numrevs
):
ar = ll.annotate(rev)
self.assertEqual([(l.rev, l.linenum) for l in ar], lines)
def testinfinitebadprogram(self):
ll = linelog.linelog.fromdata(
b'\x00\x00\x00\x00\x00\x00\x00\x02' # header
b'\x00\x00\x00\x00\x00\x00\x00\x01' # JUMP to self
)
with self.assertRaises(linelog.LineLogError):
# should not be an infinite loop and raise
ll.annotate(1)
if __name__ == '__main__':
import silenttestrunner
silenttestrunner.main(__name__)