D1973: bdiff: write a native version of splitnewlines

indygreg (Gregory Szorc) phabricator at mercurial-scm.org
Thu Feb 1 18:08:20 EST 2018

indygreg added subscribers: yuja, indygreg.
indygreg requested changes to this revision.
indygreg added a comment.
This revision now requires changes to proceed.

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


> bdiff.c:187
> +		   const char *source, Py_ssize_t len) {
> +	PyObject *sliced = PyString_FromStringAndSize(source, len);
> +	if (sliced == NULL)

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.

> bdiff.c:190
> +		return false;
> +	PyList_SetItem(list, destidx, sliced);
> +	return true;

The `PyList` is pre-allocated. That means you can use `PyList_SET_ITEM()` for even faster execution.

> bdiff.c:201-202
> +
> +	if (!PyArg_ParseTuple(args, "s#", &text, &size))
> +		goto abort;
> +	if (!size) {

Does our style guideline not require braces yet? Seeing this reminds me of `goto fail` :(

> bdiff.c:208-212
> +	for (i = 0; i < size - 1; ++i) {
> +		if (text[i] == '\n') {
> +			++nelts;
> +		}
> +	}

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.

> bdiff.c:216-217
> +	nelts = 0;
> +	for (i = 0; i < size - 1; ++i) {
> +		if (text[i] == '\n') {
> +			if (!sliceintolist(

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.

> mdiff.py:43
> +splitnewlines = getattr(bdiff, 'splitnewlines', splitnewlines)
> +

@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.

  rHG Mercurial


To: durin42, #hg-reviewers, indygreg
Cc: indygreg, yuja, mercurial-devel

More information about the Mercurial-devel mailing list