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

Gregory Szorc gregory.szorc at gmail.com
Tue Mar 14 01:15:45 EDT 2017


# 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)

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;
 }


More information about the Mercurial-devel mailing list