| Submitter | Boris Feld |
|---|---|
| Date | Nov. 15, 2018, 10:38 a.m. |
| Message ID | <465af090febebc1c8ca8.1542278326@localhost.localdomain> |
| Download | mbox | patch |
| Permalink | /patch/36598/ |
| State | Accepted |
| Headers | show |
Comments
On Thu, 15 Nov 2018 11:38:46 +0100, Boris Feld wrote: > # HG changeset patch > # User Boris Feld <boris.feld@octobus.net> > # Date 1542276598 -3600 > # Thu Nov 15 11:09:58 2018 +0100 > # Node ID 465af090febebc1c8ca8e402c279349ccd09e091 > # Parent f76fc4ed86fd2072c861f57a3c1c3e892648fc92 > # EXP-Topic sparse-perf > # Available At https://bitbucket.org/octobus/mercurial-devel/ > # hg pull https://bitbucket.org/octobus/mercurial-devel/ -r 465af090febe > sparse-revlog: introduce native (C) implementation of slicechunktodensity > > This is a C implementation of `_slicechunktodensity` in the > `mercurial/revlogutils/deltas.py` file. > > The algorithm involves a lot of integer manipulation and low-level access to > index data. Having a C implementation of it raises a large performance > improvement. See later changeset in this series for details. > > diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c > --- a/mercurial/cext/revlog.c > +++ b/mercurial/cext/revlog.c > @@ -11,6 +11,7 @@ > #include <assert.h> > #include <ctype.h> > #include <stddef.h> > +#include <stdlib.h> > #include <string.h> > > #include "bitmanipulation.h" > @@ -1050,6 +1051,210 @@ static PyObject *_trimchunk(indexObject > return chunk; > } > > +struct Gap { > + Py_ssize_t size; > + Py_ssize_t idx; > +}; > + > +static int gap_compare(const void *left, const void *right) > +{ > + const struct Gap *_left = ((const struct Gap *)left); > + const struct Gap *_right = ((const struct Gap *)right); > + if (_left->size < _right->size) { > + return -1; > + } else if (_left->size > _right->size) { > + return 1; > + } > + return 0; > +} > +static int Py_ssize_t_compare(const void *left, const void *right) > +{ > + const Py_ssize_t _left = *(const Py_ssize_t *)left; > + const Py_ssize_t _right = *(const Py_ssize_t *)right; > + if (_left < _right) { > + return -1; > + } else if (_left > _right) { > + return 1; > + } > + return 0; Nit: IIRC, names starting with _ is reserved for compilers. Better to not use such variables. > +static PyObject *index_slicechunktodensity(indexObject *self, PyObject *args) > +{ > + /* method arguments */ > + PyObject *list_revs = NULL; /* revisions in the chain */ > + double targetdensity = 0.5; /* min density to achieve */ > + Py_ssize_t mingapsize = 0; /* threshold to ignore gaps */ Nit: perhaps these default values, 0.5 and 0, wouldn't be used since function arguments aren't optional. This patch looks good to me. As a follow up, can you somehow rewrite the doctests in deltas.py to run with the C implementation? Since _testrevlog() isn't backed by the index object, C functions aren't covered by the doctests. That's unfortunate.
On 16/11/2018 14:40, Yuya Nishihara wrote: > On Thu, 15 Nov 2018 11:38:46 +0100, Boris Feld wrote: >> # HG changeset patch >> # User Boris Feld <boris.feld@octobus.net> >> # Date 1542276598 -3600 >> # Thu Nov 15 11:09:58 2018 +0100 >> # Node ID 465af090febebc1c8ca8e402c279349ccd09e091 >> # Parent f76fc4ed86fd2072c861f57a3c1c3e892648fc92 >> # EXP-Topic sparse-perf >> # Available At https://bitbucket.org/octobus/mercurial-devel/ >> # hg pull https://bitbucket.org/octobus/mercurial-devel/ -r 465af090febe >> sparse-revlog: introduce native (C) implementation of slicechunktodensity >> >> This is a C implementation of `_slicechunktodensity` in the >> `mercurial/revlogutils/deltas.py` file. >> >> The algorithm involves a lot of integer manipulation and low-level access to >> index data. Having a C implementation of it raises a large performance >> improvement. See later changeset in this series for details. >> >> diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c >> --- a/mercurial/cext/revlog.c >> +++ b/mercurial/cext/revlog.c >> @@ -11,6 +11,7 @@ >> #include <assert.h> >> #include <ctype.h> >> #include <stddef.h> >> +#include <stdlib.h> >> #include <string.h> >> >> #include "bitmanipulation.h" >> @@ -1050,6 +1051,210 @@ static PyObject *_trimchunk(indexObject >> return chunk; >> } >> >> +struct Gap { >> + Py_ssize_t size; >> + Py_ssize_t idx; >> +}; >> + >> +static int gap_compare(const void *left, const void *right) >> +{ >> + const struct Gap *_left = ((const struct Gap *)left); >> + const struct Gap *_right = ((const struct Gap *)right); >> + if (_left->size < _right->size) { >> + return -1; >> + } else if (_left->size > _right->size) { >> + return 1; >> + } >> + return 0; >> +} >> +static int Py_ssize_t_compare(const void *left, const void *right) >> +{ >> + const Py_ssize_t _left = *(const Py_ssize_t *)left; >> + const Py_ssize_t _right = *(const Py_ssize_t *)right; >> + if (_left < _right) { >> + return -1; >> + } else if (_left > _right) { >> + return 1; >> + } >> + return 0; > Nit: IIRC, names starting with _ is reserved for compilers. Better to not > use such variables. Oops, fixed. > >> +static PyObject *index_slicechunktodensity(indexObject *self, PyObject *args) >> +{ >> + /* method arguments */ >> + PyObject *list_revs = NULL; /* revisions in the chain */ >> + double targetdensity = 0.5; /* min density to achieve */ >> + Py_ssize_t mingapsize = 0; /* threshold to ignore gaps */ > Nit: perhaps these default values, 0.5 and 0, wouldn't be used since function > arguments aren't optional. I updated the code to set them both to 0. Should we leave them non-initialized? > > This patch looks good to me. > > As a follow up, can you somehow rewrite the doctests in deltas.py to run with > the C implementation? Since _testrevlog() isn't backed by the index object, > C functions aren't covered by the doctests. That's unfortunate. That won't be easy, the doctest use a mock python class to emulate the revlog. On the other hand, the C code expects the real object. > _______________________________________________ > Mercurial-devel mailing list > Mercurial-devel@mercurial-scm.org > https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
On Mon, 19 Nov 2018 10:19:55 +0100, Boris FELD wrote: > >> + double targetdensity = 0.5; /* min density to achieve */ > >> + Py_ssize_t mingapsize = 0; /* threshold to ignore gaps */ > > Nit: perhaps these default values, 0.5 and 0, wouldn't be used since function > > arguments aren't optional. > I updated the code to set them both to 0. Should we leave them > non-initialized? I don't care much about that. 0 should be fine. > > This patch looks good to me. > > > > As a follow up, can you somehow rewrite the doctests in deltas.py to run with > > the C implementation? Since _testrevlog() isn't backed by the index object, > > C functions aren't covered by the doctests. That's unfortunate. > That won't be easy, the doctest use a mock python class to emulate the > revlog. On the other hand, the C code expects the real object. Can't they be extracted to unit tests? I don't think doctests fit well to these somewhat complex functions.
Patch
diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c --- a/mercurial/cext/revlog.c +++ b/mercurial/cext/revlog.c @@ -11,6 +11,7 @@ #include <assert.h> #include <ctype.h> #include <stddef.h> +#include <stdlib.h> #include <string.h> #include "bitmanipulation.h" @@ -1050,6 +1051,210 @@ static PyObject *_trimchunk(indexObject return chunk; } +struct Gap { + Py_ssize_t size; + Py_ssize_t idx; +}; + +static int gap_compare(const void *left, const void *right) +{ + const struct Gap *_left = ((const struct Gap *)left); + const struct Gap *_right = ((const struct Gap *)right); + if (_left->size < _right->size) { + return -1; + } else if (_left->size > _right->size) { + return 1; + } + return 0; +} +static int Py_ssize_t_compare(const void *left, const void *right) +{ + const Py_ssize_t _left = *(const Py_ssize_t *)left; + const Py_ssize_t _right = *(const Py_ssize_t *)right; + if (_left < _right) { + return -1; + } else if (_left > _right) { + return 1; + } + return 0; +} + +static PyObject *index_slicechunktodensity(indexObject *self, PyObject *args) +{ + /* method arguments */ + PyObject *list_revs = NULL; /* revisions in the chain */ + double targetdensity = 0.5; /* min density to achieve */ + Py_ssize_t mingapsize = 0; /* threshold to ignore gaps */ + + /* other core variables */ + Py_ssize_t i; /* used for various iteration */ + PyObject *result = NULL; /* the final return of the function */ + + /* generic information about the delta chain being slice */ + Py_ssize_t num_revs = 0; /* size of the full delta chain */ + Py_ssize_t *revs = NULL; /* native array of revision in the chain */ + Py_ssize_t chainpayload = 0; /* sum of all delta in the chain */ + Py_ssize_t deltachainspan = + 0; /* distance from first byte to last byte */ + + /* variable used for slicing the delta chain */ + Py_ssize_t readdata = + 0; /* amount of data currently planned to be read */ + double density = 0; /* ration of payload data compared to read ones */ + struct Gap *gaps = NULL; /* array of notable gap in the chain */ + Py_ssize_t num_gaps = + 0; /* total number of notable gap recorded so far */ + Py_ssize_t *selected_indices = NULL; /* indices of gap skipped over */ + Py_ssize_t num_selected = 0; /* number of gaps skipped */ + PyObject *chunk = NULL; /* individual slice */ + PyObject *allchunks = NULL; /* all slices */ + + /* parsing argument */ + if (!PyArg_ParseTuple(args, "O!dl", &PyList_Type, &list_revs, + &targetdensity, &mingapsize)) { + goto bail; + } + + /* If the delta chain contains a single element, we do not need slicing + */ + num_revs = PyList_GET_SIZE(list_revs); + if (num_revs <= 1) { + result = PyTuple_Pack(1, list_revs); + goto done; + } + + /* Turn the python list into a native integer array (for efficiency) */ + revs = (Py_ssize_t *)calloc(num_revs, sizeof(Py_ssize_t)); + if (revs == NULL) { + PyErr_NoMemory(); + goto bail; + } + Py_ssize_t idxlen = index_length(self); + for (i = 0; i < num_revs; i++) { + Py_ssize_t revnum = PyInt_AsLong(PyList_GET_ITEM(list_revs, i)); + if (revnum == -1 && PyErr_Occurred()) { + goto bail; + } + if (revnum < 0 || revnum >= idxlen) { + PyErr_SetString(PyExc_IndexError, "index out of range"); + goto bail; + } + revs[i] = revnum; + } + + /* Compute and check various property of the unsliced delta chain */ + deltachainspan = index_segment_span(self, revs[0], revs[num_revs - 1]); + + if (deltachainspan <= mingapsize) { + result = PyTuple_Pack(1, list_revs); + goto done; + } + chainpayload = 0; + for (i = 0; i < num_revs; i++) { + chainpayload += index_get_length(self, revs[i]); + } + + readdata = deltachainspan; + density = 1.0; + + if (0 < deltachainspan) { + density = (double)chainpayload / (double)deltachainspan; + }; + + if (density >= targetdensity) { + result = PyTuple_Pack(1, list_revs); + goto done; + } + + /* if chain is too sparse, look for relevant gaps */ + gaps = (struct Gap *)calloc(num_revs, sizeof(struct Gap)); + if (gaps == NULL) { + PyErr_NoMemory(); + goto bail; + } + + Py_ssize_t previous_end = -1; + for (i = 0; i < num_revs; i++) { + Py_ssize_t revstart = index_get_start(self, revs[i]); + Py_ssize_t revsize = index_get_length(self, revs[i]); + if (revsize <= 0) { + continue; + } + if (previous_end >= 0) { + Py_ssize_t gapsize = revstart - previous_end; + if (gapsize > mingapsize) { + gaps[num_gaps].size = gapsize; + gaps[num_gaps].idx = i; + num_gaps += 1; + } + } + previous_end = revstart + revsize; + } + if (num_gaps == 0) { + result = PyTuple_Pack(1, list_revs); + goto done; + } + qsort(gaps, num_gaps, sizeof(struct Gap), &gap_compare); + + /* Slice the largest gap first, they improve the density the most */ + selected_indices = + (Py_ssize_t *)malloc((num_gaps + 1) * sizeof(Py_ssize_t)); + if (selected_indices == NULL) { + PyErr_NoMemory(); + goto bail; + } + + for (i = num_gaps - 1; i >= 0; i--) { + selected_indices[num_selected] = gaps[i].idx; + readdata -= gaps[i].size; + num_selected += 1; + if (readdata <= 0) { + density = 1.0; + } else { + density = (double)chainpayload / (double)readdata; + } + if (density >= targetdensity) { + break; + } + } + qsort(selected_indices, num_selected, sizeof(Py_ssize_t), + &Py_ssize_t_compare); + + /* create the resulting slice */ + allchunks = PyList_New(0); + if (allchunks == NULL) { + goto bail; + } + Py_ssize_t previdx = 0; + selected_indices[num_selected] = num_revs; + for (i = 0; i <= num_selected; i++) { + Py_ssize_t idx = selected_indices[i]; + chunk = _trimchunk(self, list_revs, previdx, idx); + if (chunk == NULL) { + goto bail; + } + if (PyList_GET_SIZE(chunk) > 0) { + if (PyList_Append(allchunks, chunk) == -1) { + goto bail; + } + } + Py_DECREF(chunk); + chunk = NULL; + previdx = idx; + } + result = allchunks; + goto done; + +bail: + Py_XDECREF(allchunks); + Py_XDECREF(chunk); +done: + free(revs); + free(gaps); + free(selected_indices); + return result; +} + static inline int nt_level(const char *node, Py_ssize_t level) { int v = node[level >> 1]; @@ -2282,6 +2487,8 @@ static PyMethodDef index_methods[] = { "get filtered head revisions"}, /* Can always do filtering */ {"deltachain", (PyCFunction)index_deltachain, METH_VARARGS, "determine revisions with deltas to reconstruct fulltext"}, + {"slicechunktodensity", (PyCFunction)index_slicechunktodensity, + METH_VARARGS, "determine revisions with deltas to reconstruct fulltext"}, {"append", (PyCFunction)index_append, METH_O, "append an index entry"}, {"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS, "match a potentially ambiguous node ID"},