[PATCH 3 of 7] parsers: avoid PyList_Append when parsing obs markers

Gregory Szorc gregory.szorc at gmail.com
Tue Mar 14 01:24:21 EDT 2017


On Mon, Mar 13, 2017 at 10:15 PM, Gregory Szorc <gregory.szorc at gmail.com>
wrote:

> # HG changeset patch
> # User Gregory Szorc <gregory.szorc at gmail.com>
> # Date 1489454332 25200
> #      Mon Mar 13 18:18:52 2017 -0700
> # Node ID 6d3b13f243bea2c9200eecb827d7ec0ea771fc54
> # Parent  3b997adb7efece7395fb585a70b2d70522626648
> parsers: avoid PyList_Append when parsing obs markers
>
> PyList_Append() has to continuously grow the underlying list as
> available storage is exhausted. This adds overhead within tight
> loops.
>
> It is better to create a new list of known size then use the
> PyList_SET_ITEM macro to populate each element of the list
> without error checking. This commit switches us to that
> mechanism.
>
> The new code establishes an array to hold PyObject* instances
> then iterates the array at the end. The bulk of the new code
> is for memory management of the new array. There are some
> inline comments explaining how the array is sized.
>
> `hg perfloadmarkers` show an improvement with this change:
>
> ! result: 130264
> ! wall 0.125479 comb 0.130000 user 0.120000 sys 0.010000 (best of 76)
> ! wall 0.120487 comb 0.130000 user 0.120000 sys 0.010000 (best of 79)
>

This series makes obs marker loading (`hg perfloadmarkers`) ~4x faster.

However, on that same repo where this series made just loading ~95ms faster
(which is nothing to sneeze at), `hg log -r .` decreased from ~740ms to
~440ms. So I guess the lazy loading of obs markers has benefits to other
operations. Perhaps we're loading the obs store multiple times? Or perhaps
my series busted things so much in the RFC parts that the numbers are
misleading.

Assuming there is some truth to the numbers, holy cow the overhead of
PyObject creation is crazy. I suddenly feel like auditing the C code for
everywhere we're instantiating PyObjects before it is necessary. I know we
do this in the revlog index. I wonder if dirstate is impacted...


>
> diff --git a/mercurial/parsers.c b/mercurial/parsers.c
> --- a/mercurial/parsers.c
> +++ b/mercurial/parsers.c
> @@ -2792,33 +2792,77 @@ static PyObject *fm1readmarkers(PyObject
>         int datalen;
>         Py_ssize_t offset, stop;
>         PyObject *markers = NULL;
> +       PyObject **tmpmarkers = NULL;
> +       Py_ssize_t tmpmarkerssize;
> +       Py_ssize_t tmpmarkersoffset = 0;
>
>         if (!PyArg_ParseTuple(args, "s#nn", &data, &datalen, &offset,
> &stop)) {
>                 return NULL;
>         }
>         dataend = data + datalen;
>         data += offset;
> -       markers = PyList_New(0);
> -       if (!markers) {
> +
> +       /*
> +          We store an array of pointers to markers then build a list from
> +          it at the end. This is faster than appending to a PyList for
> each
> +          element.
> +
> +          Reallocating the array constantly could be expensive. We
> estimate
> +          the size of the array by assuming 90 bytes per marker, which is
> +          based on data seen in the wild.
> +       */
> +       tmpmarkerssize = datalen / 90;
> +       /* Handle datalen < 90 */
> +       tmpmarkerssize = tmpmarkerssize ? tmpmarkerssize : 10;
> +
> +       tmpmarkers = (PyObject **)PyMem_Malloc(
> +               tmpmarkerssize * sizeof(PyObject *));
> +       if (!tmpmarkers) {
> +               PyErr_NoMemory();
>                 return NULL;
>         }
> +
>         while (offset < stop) {
>                 uint32_t msize;
> -               int error;
> +               void *tmpbuffer;
>                 PyObject *record = fm1readmarker(data, dataend, &msize);
>                 if (!record) {
>                         goto bail;
>                 }
> -               error = PyList_Append(markers, record);
> -               Py_DECREF(record);
> -               if (error) {
> -                       goto bail;
> +
> +               /* Allocate more array storage if needed */
> +               if (tmpmarkersoffset + 1 == tmpmarkerssize) {
> +                       /* 5000 chosen somewhat arbitrarily. */
> +                       tmpmarkerssize += 5000;
> +                       tmpbuffer = PyMem_Realloc(tmpmarkers,
> +                               tmpmarkerssize * sizeof(PyObject*));
> +                       if (!tmpbuffer) {
> +                               PyErr_NoMemory();
> +                               goto bail;
> +                       }
> +                       tmpmarkers = (PyObject **)tmpbuffer;
>                 }
> +
> +               tmpmarkers[tmpmarkersoffset++] = record;
>                 data += msize;
>                 offset += msize;
>         }
> +
> +       /* Convert our array of pointers to a PyList */
> +       markers = PyList_New(tmpmarkersoffset);
> +       if (!markers) {
> +               goto bail;
> +       }
> +
> +       for (offset = 0; offset < tmpmarkersoffset; offset++) {
> +               PyList_SET_ITEM(markers, offset, tmpmarkers[offset]);
> +       }
> +
> +       free(tmpmarkers);
> +
>         return markers;
>  bail:
> +       free(tmpmarkers);
>         Py_DECREF(markers);
>         return NULL;
>  }
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mercurial-scm.org/pipermail/mercurial-devel/attachments/20170313/cd24a5d4/attachment.html>


More information about the Mercurial-devel mailing list