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.

Download Raw Diff

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

Lint Skipped

Unit

Unit Tests Skipped

Event Timeline

quark created this revision.Aug 6 2018, 10:00 PM

Herald added a reviewer: hg-reviewers. · View Herald TranscriptAug 6 2018, 10:00 PM

Herald added a subscriber: mercurial-devel. · View Herald Transcript

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.

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.

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

			Path	Packages
M			mercurial/linelog.py (26 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	10025		Aug 6 2018, 10:00 PM	★	★
Diff 2	10067		Aug 7 2018, 8:22 PM	★	★
Diff 3	10135	rHGee97f7a677f3233ee3d0aeef2eabd4494bf8d887	Aug 7 2018, 8:22 PM	★	★

Status	Author	Revision
Closed	quark	D4150 linelog: optimize replacelines
Closed	quark	D4149 linelog: extract `len(self._program)` to a local function
Closed	quark	D4148 perf: add a command to benchmark linelog edits
Closed	quark	D4147 linelog: update internal help text

Diff 10025

mercurial/linelog.py

	a1info = lineinfo(0, 0, ar._eof)			a1info = lineinfo(0, 0, ar._eof)
	else:			else:
	a1info = ar.lines[a1]			a1info = ar.lines[a1]
	a1inst = self._program[a1info._offset]			a1inst = self._program[a1info._offset]
	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. It is critical to
	# but for now we'll pass on that and see if it matters in			# performance.
	# 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 = []
	# Sanity check: if len(lines) is longer than len(program), we			# Sanity check: if len(lines) is longer than len(program), we
	# hit an infinite loop in the linelog program somehow and we			# hit an infinite loop in the linelog program somehow and we