D1973: bdiff: write a native version of splitnewlines

[indygreg (Gregory Szorc)]

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.

INLINE COMMENTS

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

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D1973

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