( )⚙ D4150 linelog: optimize replacelines

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4150

linelog: optimize replacelines
ClosedPublic

Authored by quark on Aug 6 2018, 10:00 PM.

Details

Reviewers
durin42
Group Reviewers
hg-reviewers
Commits
rHGee97f7a677f3: linelog: optimize replacelines
Summary

The optimization to avoid calling annotate inside replacelines is significant
for practical use patterns.

Before this patch:

hg perflinelogedits
! wall 6.778478 comb 6.710000 user 6.700000 sys 0.010000 (best of 3)

After this patch:

hg perflinelogedits
! wall 0.136573 comb 0.140000 user 0.130000 sys 0.010000 (best of 63)

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Aug 6 2018, 10:00 PM
quark edited the summary of this revision. (Show Details)Aug 6 2018, 10:35 PM
quark edited the summary of this revision. (Show Details)Aug 6 2018, 11:05 PM
quark edited the summary of this revision. (Show Details)Aug 7 2018, 8:22 PM
quark updated this revision to Diff 10067.
durin42 accepted this revision.Aug 9 2018, 1:56 PM
durin42 added a subscriber: durin42.

Thanks for the optimization! I had gotten too worn out tracing things in the original code to figure out how the splicing worked, and I had something that worked so I moved along with it. This makes a lot of sense (possibly just because I'm less tired than I was when I finished understanding linelog the first time.)

This revision is now accepted and ready to land.Aug 9 2018, 1:56 PM
Closed by commit rHGee97f7a677f3: linelog: optimize replacelines (authored by quark). · Explain WhyAug 9 2018, 2:06 PM
This revision was automatically updated to reflect the committed changes.
quark added a comment.EditedAug 9 2018, 6:12 PM

To clarify, I do think stateless API is better. It can be done by keeping _lastannotate as a private cache inaccessible from other APIs, move annotateresult to the return value of annotate, then add arev to replacelines to verify the cache. The C code use brev instead of rev as the parameter name for a reason.

The original annotateresult is used as an attempt to reduce C code to be reviewed. Reviewing C code took too long.

The choice of C was because I pursued performance, C is not bad for this particular work (ex. linelog.c has similar LOC), and C is also friendly for the Git community.

To provide more context, mpm commented internally on how the linelog format might be improved. That is to add a LINESPAN instruction replacing a range of continuous LINE instructions. Again, not implemented because of C. But it seems much easier with Python now.

Revision Contents
Changeset List

PathPackages
Mmercurial/linelog.py (26 lines)

Diff 10135

mercurial/linelog.py

else: else:
a1info = ar.lines[a1] a1info = ar.lines[a1]
a1inst = self._program[a1info._offset] a1inst = self._program[a1info._offset]
programlen = self._program.__len__ programlen = self._program.__len__
oldproglen = programlen() oldproglen = programlen()
appendinst = self._program.append appendinst = self._program.append
# insert # insert
blineinfos = []
bappend = blineinfos.append
if b1 < b2: if b1 < b2:
# Determine the jump target for the JGE at the start of # Determine the jump target for the JGE at the start of
# the new block. # the new block.
tgt = oldproglen + (b2 - b1 + 1) tgt = oldproglen + (b2 - b1 + 1)
# Jump to skip the insert if we're at an older revision. # Jump to skip the insert if we're at an older revision.
appendinst(_jl(rev, tgt)) appendinst(_jl(rev, tgt))
for linenum in pycompat.xrange(b1, b2): for linenum in pycompat.xrange(b1, b2):
if _internal_blines is None: if _internal_blines is None:
bappend(lineinfo(rev, linenum, programlen()))
appendinst(_line(rev, linenum)) appendinst(_line(rev, linenum))
else: else:
appendinst(_line(*_internal_blines[linenum])) newrev, newlinenum = _internal_blines[linenum]
bappend(lineinfo(newrev, newlinenum, programlen()))
appendinst(_line(newrev, newlinenum))
# delete # delete
if a1 < a2: if a1 < a2:
if a2 > len(ar.lines): if a2 > len(ar.lines):
raise LineLogError( raise LineLogError(
'%d contains %d lines, tried to access line %d' % ( '%d contains %d lines, tried to access line %d' % (
rev, len(ar.lines), a2)) rev, len(ar.lines), a2))
elif a2 == len(ar.lines): elif a2 == len(ar.lines):
endaddr = ar._eof endaddr = ar._eof
else: else:
endaddr = ar.lines[a2]._offset endaddr = ar.lines[a2]._offset
if a2 > 0 and rev < self._maxrev: if a2 > 0 and rev < self._maxrev:
# If we're here, we're deleting a chunk of an old # If we're here, we're deleting a chunk of an old
# commit, so we need to be careful and not touch # commit, so we need to be careful and not touch
# invisible lines between a2-1 and a2 (IOW, lines that # invisible lines between a2-1 and a2 (IOW, lines that
# are added later). # are added later).
endaddr = ar.lines[a2 - 1]._offset + 1 endaddr = ar.lines[a2 - 1]._offset + 1
appendinst(_jge(rev, endaddr)) appendinst(_jge(rev, endaddr))
# copy instruction from a1 # copy instruction from a1
a1instpc = programlen()
appendinst(a1inst) appendinst(a1inst)
# if a1inst isn't a jump or EOF, then we need to add an unconditional # if a1inst isn't a jump or EOF, then we need to add an unconditional
# jump back into the program here. # jump back into the program here.
if not isinstance(a1inst, (_jump, _eof)): if not isinstance(a1inst, (_jump, _eof)):
appendinst(_jump(0, a1info._offset + 1)) appendinst(_jump(0, a1info._offset + 1))
# Patch instruction at a1, which makes our patch live. # Patch instruction at a1, which makes our patch live.
self._program[a1info._offset] = _jump(0, oldproglen) self._program[a1info._offset] = _jump(0, oldproglen)
# For compat with the C version, re-annotate rev so that
# self.annotateresult is cromulent.. We could fix up the # Update self._lastannotate in place. This serves as a cache to avoid
# annotateresult in place (which is how the C version works), # expensive "self.annotate" in this function, when "replacelines" is
# but for now we'll pass on that and see if it matters in # used continuously.
# practice. if len(self._lastannotate.lines) > a1:
self.annotate(max(self._lastannotate.rev, rev)) self._lastannotate.lines[a1]._offset = a1instpc
else:
assert isinstance(a1inst, _eof)
self._lastannotate._eof = a1instpc
self._lastannotate.lines[a1:a2] = blineinfos
self._lastannotate.rev = max(self._lastannotate.rev, rev)
if rev > self._maxrev: if rev > self._maxrev:
self._maxrev = rev self._maxrev = rev
def annotate(self, rev): def annotate(self, rev):
pc = 1 pc = 1
lines = [] lines = []
executed = 0 executed = 0
# Sanity check: if instructions executed exceeds len(program), we # Sanity check: if instructions executed exceeds len(program), we