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.

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
indygreg added subscribers: yuja, indygreg.Feb 1 2018, 6:08 PM
indygreg requested changes to this revision.

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?

yuja requested changes to this revision.Feb 3 2018, 3:17 AM

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.
durin42 marked an inline comment as done.Feb 12 2018, 10:24 AM

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.

indygreg accepted this revision.Feb 12 2018, 2:11 PM

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

yuja accepted this revision.Feb 13 2018, 7:10 AM

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

PathPackages
Mmercurial/cext/bdiff.c (52 lines)
Mmercurial/mdiff.py (11 lines)
Mmercurial/policy.py (2 lines)
Mmercurial/pure/bdiff.py (10 lines)

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