This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1973

bdiff: write a native version of splitnewlines
ClosedPublic

Authored by durin42 on Feb 1 2018, 4:58 PM.

Download Raw Diff

Details

Reviewers

indygreg
yuja

Group Reviewers

hg-reviewers

Commits

rHG29dd37a418aa: bdiff: write a native version of splitnewlines

Summary

./hg perfunidiff mercurial/manifest.py 0 --count 500 --profile before:
! wall 0.309280 comb 0.350000 user 0.290000 sys 0.060000 (best of 32)

./hg perfunidiff mercurial/manifest.py 0 --count 500 --profile after:
! wall 0.241572 comb 0.260000 user 0.240000 sys 0.020000 (best of 39)

so it's about 20% faster. I hate Python. I wish we could usefully
write this in Rust, but it doesn't look like that's realistic without
using the cpython crate, which I'd still like to avoid.

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

durin42 created this revision.Feb 1 2018, 4:58 PM

Herald added a reviewer: hg-reviewers. · View Herald TranscriptFeb 1 2018, 4:58 PM

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

This looks mostly good. Needs some minor tweaks. Some of my comments are informative and can probably be ignored as far as reviewing goes.

mercurial/cext/bdiff.c
185	Let's use `PyBytes` here for compatibility with Python 3. Also, `Py_buffer` here would let us avoid a memory allocation. Unfortunately, various C extensions in older versions of Python 2.7 don't recognize the `Py_buffer` interface (I'm looking at you `zlib`). So we need to be careful about where all we use `Py_buffer` tricks :( It would be really nice if all of this code were in C so we didn't have to allocate a `PyObject` for every line: we could just pass an array of line offsets around.
188	The `PyList` is pre-allocated. That means you can use `PyList_SET_ITEM()` for even faster execution.
199–200	Does our style guideline not require braces yet? Seeing this reminds me of `goto fail` :(
206–210	For a micro optimization, I bet if you rewrite this to iterate over chunks of size `size_t` and do bit tests that this will be even faster. The searching for newlines is a hot loop in the `bdiff` code. Unfortunately, I never completed my refactor to optimize the line scanning.
214–215	I have a feeling this extra line scan will matter in a benchmark. Could you `perf record` the new `hg perf*` command and verify? If it is a big deal, I would allocate an `int[16384]` array on the stack or something to deal with the common case and store additional newline offsets on the heap so we only do the newline scan once.
mercurial/mdiff.py
34	@yuja may have an opinion on this, but mine is that we now have stronger guarantees around C extension versioning, so if the active module policy is to use C extensions, we should ensure we get `splitnewlines` from the C module. I /think/ if we move `splitnewlines` to the `bdiff` module that things will sort themselves out? This could be done as a follow-up easily enough though.

This revision now requires changes to proceed.Feb 1 2018, 6:08 PM

yuja added inline comments.Feb 2 2018, 8:34 AM

mercurial/cext/bdiff.c
195	Perhaps Py_ssize_t is preferred.
200	Here `result` isn't initialized to NULL yet.
214–215	I don't know which is faster, but if we do preallocate a buffer, we can create a large `PyList` and shrink it by `PyList_SetSlice(..., NULL)` at the end. `builtin_filter()` of Python 2 do that.
mercurial/mdiff.py
34	if we move splitnewlines to the bdiff module that things will sort themselves out Yes, splitnewlines should be moved to pure/bdiff.py. And we need to bump the C API version.

durin42 marked 7 inline comments as done.Feb 2 2018, 11:26 AM

durin42 updated this revision to Diff 5160.

durin42 added inline comments.Feb 2 2018, 11:26 AM

mercurial/cext/bdiff.c
214–215	It's already enough of a win I'd like to land the simple version and then focus on spending effort on a Rust version rather than continuing with this. How do you feel about that as a plan?

Looks mostly good to me. I hesitated to fix minor nits in flight because
it's C.

mercurial/cext/bdiff.c
183	Nit: `static bool sliceintolist(`
222	`start < size` should be always true because `size > 0`. Otherwise, `PyList_New(nelts + 1)` could be wrong.

This revision now requires changes to proceed.Feb 3 2018, 3:17 AM

durin42 marked an inline comment as done.Feb 12 2018, 10:23 AM

durin42 updated this revision to Diff 5487.

Good catches. This should be ready now.

I also added bdiff.c to clang-format oversight in a newly inserted parent, because the file is simple enough that doing so was easy.

durin42 edited parent revisions, added: D2177: bdiff: add to clang-format oversight; removed: D1972: tests: start a set of unit tests for mdiff.py, starting with splitnewlines.Feb 12 2018, 10:25 AM

I'm happy with this as a first revision.

While I'm accepting as hg-reviewers, I think C code should have an extra set of eyes. So I'll defer to @yuja to queue it.

For the record, I'm no fan of not having braces for all bodies of conditionals. Can't wait to globally reformat our code to fix that.

mercurial/cext/bdiff.c
183	This doesn't need to be static. I'd declare it as `inline bool sliceintolist(`.

Queued, thanks.

mercurial/cext/bdiff.c
183	IIRC, `inline` doesn't imply a function has a file scope, and `inline` could be `` on unsupported platforms.

This revision is now accepted and ready to land.Feb 13 2018, 7:10 AM

Closed by commit rHG29dd37a418aa: bdiff: write a native version of splitnewlines (authored by durin42). · Explain WhyFeb 13 2018, 7:24 AM

This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

			Path	Packages
M			mercurial/cext/bdiff.c (52 lines)
M			mercurial/mdiff.py (11 lines)
M			mercurial/policy.py (2 lines)
M			mercurial/pure/bdiff.py (10 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	5086		Feb 1 2018, 4:58 PM	★	★
Diff 2	5160		Feb 2 2018, 11:25 AM	★	★
Diff 3	5487		Feb 12 2018, 10:23 AM	★	★
Diff 4	5627	rHG29dd37a418aa26194a40ad603e918a7373e8c5e2	Jan 25 2018, 9:16 PM	★	★

	Status	Author	Revision
	Closed	durin42	D1973 bdiff: write a native version of splitnewlines
	Closed	durin42	D2177 bdiff: add to clang-format oversight

Diff 5627

mercurial/cext/bdiff.c


	result = PyBytes_FromStringAndSize(w, wlen);			result = PyBytes_FromStringAndSize(w, wlen);

	nomem:			nomem:
	PyMem_Free(w);			PyMem_Free(w);
	return result ? result : PyErr_NoMemory();			return result ? result : PyErr_NoMemory();
	}			}

				static bool sliceintolist(PyObject *list, Py_ssize_t destidx,
				yujaUnsubmitted Done Nit: `static bool sliceintolist(` yuja: Nit: `static bool sliceintolist(`
				indygregUnsubmitted Not Done This doesn't need to be static. I'd declare it as `inline bool sliceintolist(`. indygreg: This doesn't need to be static. I'd declare it as `inline bool sliceintolist(`.
				yujaUnsubmitted Not Done IIRC, `inline` doesn't imply a function has a file scope, and `inline` could be `` on unsupported platforms. yuja: IIRC, `inline` doesn't imply a function has a file scope, and `inline` could be `` on…
				const char *source, Py_ssize_t len)
				{
				indygregUnsubmitted Done Let's use `PyBytes` here for compatibility with Python 3. Also, `Py_buffer` here would let us avoid a memory allocation. Unfortunately, various C extensions in older versions of Python 2.7 don't recognize the `Py_buffer` interface (I'm looking at you `zlib`). So we need to be careful about where all we use `Py_buffer` tricks :( It would be really nice if all of this code were in C so we didn't have to allocate a `PyObject` for every line: we could just pass an array of line offsets around. indygreg: Let's use `PyBytes` here for compatibility with Python 3. Also, `Py_buffer` here would let us…
				PyObject *sliced = PyBytes_FromStringAndSize(source, len);
				if (sliced == NULL)
				return false;
				indygregUnsubmitted Done The `PyList` is pre-allocated. That means you can use `PyList_SET_ITEM()` for even faster execution. indygreg: The `PyList` is pre-allocated. That means you can use `PyList_SET_ITEM()` for even faster…
				PyList_SET_ITEM(list, destidx, sliced);
				return true;
				}

				static PyObject splitnewlines(PyObject self, PyObject *args)
				{
				const char *text;
				yujaUnsubmitted Done Perhaps Py_ssize_t is preferred. yuja: Perhaps Py_ssize_t is preferred.
				Py_ssize_t nelts = 0, size, i, start = 0;
				PyObject *result = NULL;

				if (!PyArg_ParseTuple(args, "s#", &text, &size)) {
				goto abort;
				indygregUnsubmitted Done Does our style guideline not require braces yet? Seeing this reminds me of `goto fail` :( indygreg: Does our style guideline not require braces yet? Seeing this reminds me of `goto fail` :(
				yujaUnsubmitted Done Here `result` isn't initialized to NULL yet. yuja: Here `result` isn't initialized to NULL yet.
				}
				if (!size) {
				return PyList_New(0);
				}
				/* This loops to size-1 because if the last byte is a newline,
				* we don't want to perform a split there. */
				for (i = 0; i < size - 1; ++i) {
				if (text[i] == '\n') {
				++nelts;
				}
				indygregUnsubmitted Not Done For a micro optimization, I bet if you rewrite this to iterate over chunks of size `size_t` and do bit tests that this will be even faster. The searching for newlines is a hot loop in the `bdiff` code. Unfortunately, I never completed my refactor to optimize the line scanning. indygreg: For a micro optimization, I bet if you rewrite this to iterate over chunks of size `size_t` and…
				}
				if ((result = PyList_New(nelts + 1)) == NULL)
				goto abort;
				nelts = 0;
				for (i = 0; i < size - 1; ++i) {
				indygregUnsubmitted Not Done I have a feeling this extra line scan will matter in a benchmark. Could you `perf record` the new `hg perf` command and verify? If it is a big deal, I would allocate an `int[16384]` array on the stack or something to deal with the common case and store additional newline offsets on the heap so we only do the newline scan once. indygreg:* I have a feeling this extra line scan will matter in a benchmark. Could you `perf record` the…
				yujaUnsubmitted Not Done I don't know which is faster, but if we do preallocate a buffer, we can create a large `PyList` and shrink it by `PyList_SetSlice(..., NULL)` at the end. `builtin_filter()` of Python 2 do that. yuja: I don't know which is faster, but if we do preallocate a buffer, we can create a large…
				durin42AuthorUnsubmitted Not Done It's already enough of a win I'd like to land the simple version and then focus on spending effort on a Rust version rather than continuing with this. How do you feel about that as a plan? durin42: It's already enough of a win I'd like to land the simple version and then focus on spending…
				if (text[i] == '\n') {
				if (!sliceintolist(result, nelts++, text + start,
				i - start + 1))
				goto abort;
				start = i + 1;
				}
				}
				yujaUnsubmitted Done `start < size` should be always true because `size > 0`. Otherwise, `PyList_New(nelts + 1)` could be wrong. yuja: `start < size` should be always true because `size > 0`. Otherwise, `PyList_New(nelts + 1)`…
				if (!sliceintolist(result, nelts++, text + start, size - start))
				goto abort;
				return result;
				abort:
				Py_XDECREF(result);
				return NULL;
				}

	static char mdiff_doc[] = "Efficient binary diff.";			static char mdiff_doc[] = "Efficient binary diff.";

	static PyMethodDef methods[] = {			static PyMethodDef methods[] = {
	{"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"},			{"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"},
	{"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"},			{"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"},
	{"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"},			{"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"},
				{"splitnewlines", splitnewlines, METH_VARARGS,
				"like str.splitlines, but only split on newlines\n"},
	{NULL, NULL},			{NULL, NULL},
	};			};

	static const int version = 1;			static const int version = 2;

	#ifdef IS_PY3K			#ifdef IS_PY3K
	static struct PyModuleDef bdiff_module = {			static struct PyModuleDef bdiff_module = {
	PyModuleDef_HEAD_INIT, "bdiff", mdiff_doc, -1, methods,			PyModuleDef_HEAD_INIT, "bdiff", mdiff_doc, -1, methods,
	};			};

	PyMODINIT_FUNC PyInit_bdiff(void)			PyMODINIT_FUNC PyInit_bdiff(void)
	{			{

mercurial/mdiff.py

	bdiff = policy.importmod(r'bdiff')			bdiff = policy.importmod(r'bdiff')
	mpatch = policy.importmod(r'mpatch')			mpatch = policy.importmod(r'mpatch')

	blocks = bdiff.blocks			blocks = bdiff.blocks
	fixws = bdiff.fixws			fixws = bdiff.fixws
	patches = mpatch.patches			patches = mpatch.patches
	patchedsize = mpatch.patchedsize			patchedsize = mpatch.patchedsize
	textdiff = bdiff.bdiff			textdiff = bdiff.bdiff
				splitnewlines = bdiff.splitnewlines
	def splitnewlines(text):
	'''like str.splitlines, but only split on newlines.'''
	lines = [l + '\n' for l in text.split('\n')]
	if lines:
	if lines[-1] == '\n':
	lines.pop()
	else:
	lines[-1] = lines[-1][:-1]
	return lines

	class diffopts(object):			class diffopts(object):
				indygregUnsubmitted Done @yuja may have an opinion on this, but mine is that we now have stronger guarantees around C extension versioning, so if the active module policy is to use C extensions, we should ensure we get `splitnewlines` from the C module. I /think/ if we move `splitnewlines` to the `bdiff` module that things will sort themselves out? This could be done as a follow-up easily enough though. indygreg: @yuja may have an opinion on this, but mine is that we now have stronger guarantees around C…
				yujaUnsubmitted Done if we move splitnewlines to the bdiff module that things will sort themselves out Yes, splitnewlines should be moved to pure/bdiff.py. And we need to bump the C API version. yuja: > if we move splitnewlines to the bdiff module that things will sort themselves out Yes…
	'''context is the number of context lines			'''context is the number of context lines
	text treats all files as text			text treats all files as text
	showfunc enables diff -p output			showfunc enables diff -p output
	git enables the git extended patch format			git enables the git extended patch format
	nodates removes dates from diff headers			nodates removes dates from diff headers
	nobinary ignores binary files			nobinary ignores binary files
	noprefix disables the 'a/' and 'b/' prefixes (ignored in plain mode)			noprefix disables the 'a/' and 'b/' prefixes (ignored in plain mode)
	ignorews ignores all whitespace changes in the diff			ignorews ignores all whitespace changes in the diff

mercurial/policy.py

	raise ImportError(r'cannot import name %s' % modname)			raise ImportError(r'cannot import name %s' % modname)
	# force import; fakelocals[modname] may be replaced with the real module			# force import; fakelocals[modname] may be replaced with the real module
	getattr(mod, r'__doc__', None)			getattr(mod, r'__doc__', None)
	return fakelocals[modname]			return fakelocals[modname]

	# keep in sync with "version" in C modules			# keep in sync with "version" in C modules
	_cextversions = {			_cextversions = {
	(r'cext', r'base85'): 1,			(r'cext', r'base85'): 1,
	(r'cext', r'bdiff'): 1,			(r'cext', r'bdiff'): 2,
	(r'cext', r'diffhelpers'): 1,			(r'cext', r'diffhelpers'): 1,
	(r'cext', r'mpatch'): 1,			(r'cext', r'mpatch'): 1,
	(r'cext', r'osutil'): 3,			(r'cext', r'osutil'): 3,
	(r'cext', r'parsers'): 4,			(r'cext', r'parsers'): 4,
	}			}

	# map import request to other package or module			# map import request to other package or module
	_modredirects = {			_modredirects = {

mercurial/pure/bdiff.py


	def fixws(text, allws):			def fixws(text, allws):
	if allws:			if allws:
	text = re.sub('[ \t\r]+', '', text)			text = re.sub('[ \t\r]+', '', text)
	else:			else:
	text = re.sub('[ \t\r]+', ' ', text)			text = re.sub('[ \t\r]+', ' ', text)
	text = text.replace(' \n', '\n')			text = text.replace(' \n', '\n')
	return text			return text

				def splitnewlines(text):
				'''like str.splitlines, but only split on newlines.'''
				lines = [l + '\n' for l in text.split('\n')]
				if lines:
				if lines[-1] == '\n':
				lines.pop()
				else:
				lines[-1] = lines[-1][:-1]
				return lines