Patchwork [V2] obsolete: use C code for headrevs calculation

login
register
mail settings
Submitter Durham Goode
Date Sept. 17, 2014, 4:15 a.m.
Message ID <343bbf22f779af310555.1410927309@dev2000.prn2.facebook.com>
Download mbox | patch
Permalink /patch/5843/
State Superseded
Commit 2b5940f64750f027b9a12e55d33a74854365539c
Headers show

Comments

Durham Goode - Sept. 17, 2014, 4:15 a.m.
# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 1410908601 25200
#      Tue Sep 16 16:03:21 2014 -0700
# Node ID 343bbf22f779af310555d8c242b42578e1d2591f
# Parent  48791c2bea1ceda4e4f28bc11651e281d636ce1a
obsolete: use C code for headrevs calculation

Previously, if there were filtered revs the repository could not use the C fast
path for computing the head revs in the changelog. This slowed down many
operations in large repositories.

This adds the ability to filter revs to the C fast path. This speeds up histedit
on repositories with filtered revs by 30% (13s to 9s). This could be improved
further by sorting the filtered revs and walking the sorted list while we walk
the changelog, but even this initial version that just calls __contains__ is
still massively faster.

The new C api is compatible for both new and old python clients, and the new
python client can call both new and old C apis.
Antoine Pitrou - Sept. 17, 2014, 8:37 a.m.
On Tue, 16 Sep 2014 21:15:09 -0700
Durham Goode <durham@fb.com> wrote:
> +static int check_filter(PyObject *filter, Py_ssize_t arg) {
> +	if (filter) {
> +		PyObject *arglist = Py_BuildValue("(i)", arg);

With a Py_ssize_t you should use "n", not "i".

> +		PyObject *isfiltered = PyEval_CallObject(filter, arglist);
> +		Py_DECREF(arglist);

arglist or isfiltered could be NULL here.

> +static PyObject *index_headrevs(indexObject *self, PyObject *args)
>  {
>  	Py_ssize_t i, len, addlen;
>  	char *nothead = NULL;
> -	PyObject *heads;
> +	PyObject *heads, *filteredrevs;
>  
> -	if (self->headrevs)
> +	if (PyTuple_Size(args) == 0) {
> +		filteredrevs = Py_None;

Is that some kind of micro-optimization? You are already asking for an
optional argument below:

> +	} else if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
> +		return NULL;
> +	}

> +	PyObject *filter = NULL;

Is the C code supposed to be compilable with MSVC? MSVC will choke on
declarations in the middle of blocks (unless you are in C++ mode).

> +	if (filteredrevs != Py_None) {
> +		filter = PyObject_GetAttrString(filteredrevs, "__contains__");
> +	}

So filter could be NULL here.

> +
>  	len = index_length(self) - 1;
>  	heads = PyList_New(0);
>  	if (heads == NULL)
> @@ -850,6 +880,11 @@
>  		goto bail;
>  
>  	for (i = 0; i < self->raw_length; i++) {
> +		if (check_filter(filter, i)) {
> +			nothead[i] = 1;
> +			continue;
> +		}

Now the declarations below will fail under MSVC :-)

>  		const char *data = index_deref(self, i);
>  		int parent_1 = getbe32(data + 24);
>  		int parent_2 = getbe32(data + 28);
Durham Goode - Sept. 17, 2014, 7:34 p.m.
On 9/17/14, 1:37 AM, Antoine Pitrou wrote:
> On Tue, 16 Sep 2014 21:15:09 -0700
> Durham Goode <durham@fb.com> wrote:
>> +static int check_filter(PyObject *filter, Py_ssize_t arg) {
>> +	if (filter) {
>> +		PyObject *arglist = Py_BuildValue("(i)", arg);
> With a Py_ssize_t you should use "n", not "i".
>
>> +		PyObject *isfiltered = PyEval_CallObject(filter, arglist);
>> +		Py_DECREF(arglist);
> arglist or isfiltered could be NULL here.
>
>> +static PyObject *index_headrevs(indexObject *self, PyObject *args)
>>   {
>>   	Py_ssize_t i, len, addlen;
>>   	char *nothead = NULL;
>> -	PyObject *heads;
>> +	PyObject *heads, *filteredrevs;
>>   
>> -	if (self->headrevs)
>> +	if (PyTuple_Size(args) == 0) {
>> +		filteredrevs = Py_None;
> Is that some kind of micro-optimization? You are already asking for an
> optional argument below:
I tried relying on the  "|O" below, but filteredrevs was still being 
filled with data (something of type 'super'). I couldn't figure out what 
was going on, so I worked around it.
>
>> +	} else if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
>> +		return NULL;
>> +	}
>> +	PyObject *filter = NULL;
> Is the C code supposed to be compilable with MSVC? MSVC will choke on
> declarations in the middle of blocks (unless you are in C++ mode).
>
>> +	if (filteredrevs != Py_None) {
>> +		filter = PyObject_GetAttrString(filteredrevs, "__contains__");
>> +	}
> So filter could be NULL here.
>
>> +
>>   	len = index_length(self) - 1;
>>   	heads = PyList_New(0);
>>   	if (heads == NULL)
>> @@ -850,6 +880,11 @@
>>   		goto bail;
>>   
>>   	for (i = 0; i < self->raw_length; i++) {
>> +		if (check_filter(filter, i)) {
>> +			nothead[i] = 1;
>> +			continue;
>> +		}
> Now the declarations below will fail under MSVC :-)
>
>>   		const char *data = index_deref(self, i);
>>   		int parent_1 = getbe32(data + 24);
>>   		int parent_2 = getbe32(data + 28);
>
>
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
Durham Goode - Sept. 17, 2014, 7:50 p.m.
On 9/17/14, 1:37 AM, Antoine Pitrou wrote:
> On Tue, 16 Sep 2014 21:15:09 -0700
> Durham Goode <durham@fb.com> wrote:
>> +		PyObject *isfiltered = PyEval_CallObject(filter, arglist);
>> +		Py_DECREF(arglist);
> arglist or isfiltered could be NULL here.
So what is the appropriate pattern here?  Change this function to return 
an error code, pass the actual result out as a reference parameter, and 
if arglist or isfiltered is NULL return a bad error code?  Then handle 
that in the caller?

I'd almost rather just allow the segfault and not ugly up the code with 
all that handling :/  c is so obtuse...
Antoine Pitrou - Sept. 17, 2014, 9:14 p.m.
On Wed, 17 Sep 2014 12:34:58 -0700
Durham Goode <durham@fb.com> wrote:
> >>   	char *nothead = NULL;
> >> -	PyObject *heads;
> >> +	PyObject *heads, *filteredrevs;
> >>   
> >> -	if (self->headrevs)
> >> +	if (PyTuple_Size(args) == 0) {
> >> +		filteredrevs = Py_None;
> > Is that some kind of micro-optimization? You are already asking for an
> > optional argument below:
> I tried relying on the  "|O" below, but filteredrevs was still being 
> filled with data (something of type 'super'). I couldn't figure out what 
> was going on, so I worked around it.

You must first initialize the variable to its default value, e.g.:

  PyObject *filteredrevs = Py_None;

You were probably getting a value from previous stack contents.

Regards

Antoine.
Antoine Pitrou - Sept. 17, 2014, 9:15 p.m.
On Wed, 17 Sep 2014 12:50:01 -0700
Durham Goode <durham@fb.com> wrote:
> 
> On 9/17/14, 1:37 AM, Antoine Pitrou wrote:
> > On Tue, 16 Sep 2014 21:15:09 -0700
> > Durham Goode <durham@fb.com> wrote:
> >> +		PyObject *isfiltered = PyEval_CallObject(filter, arglist);
> >> +		Py_DECREF(arglist);
> > arglist or isfiltered could be NULL here.
> So what is the appropriate pattern here?  Change this function to return 
> an error code, pass the actual result out as a reference parameter, and 
> if arglist or isfiltered is NULL return a bad error code?  Then handle 
> that in the caller?

Yes, you should return an error code, and handle it in the caller.
-1 sounds reasonable (and consistent with the CPython C API).

Regards

Antoine.

Patch

diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -171,8 +171,13 @@ 
 
     def headrevs(self):
         if self.filteredrevs:
-            # XXX we should fix and use the C version
-            return self._headrevs()
+            try:
+                return self.index.headrevs(self.filteredrevs)
+            # AttributeError covers non-c-extension environments.
+            # TypeError allows us work with old c extensions.
+            except (AttributeError, TypeError):
+                return self._headrevs()
+
         return super(changelog, self).headrevs()
 
     def strip(self, *args, **kwargs):
diff --git a/mercurial/parsers.c b/mercurial/parsers.c
--- a/mercurial/parsers.c
+++ b/mercurial/parsers.c
@@ -508,6 +508,7 @@ 
 	Py_ssize_t length;     /* current number of elements */
 	PyObject *added;       /* populated on demand */
 	PyObject *headrevs;    /* cache, invalidated on changes */
+	PyObject *filteredrevs;/* filtered revs set */
 	nodetree *nt;          /* base-16 trie */
 	int ntlength;          /* # nodes in use */
 	int ntcapacity;        /* # nodes allocated */
@@ -823,15 +824,44 @@ 
 	return newlist;
 }
 
-static PyObject *index_headrevs(indexObject *self)
+static int check_filter(PyObject *filter, Py_ssize_t arg) {
+	if (filter) {
+		PyObject *arglist = Py_BuildValue("(i)", arg);
+		PyObject *isfiltered = PyEval_CallObject(filter, arglist);
+		Py_DECREF(arglist);
+		if (PyObject_IsTrue(isfiltered)) {
+			Py_DECREF(isfiltered);
+			return 1;
+		}
+		Py_DECREF(isfiltered);
+	}
+	return 0;
+}
+
+static PyObject *index_headrevs(indexObject *self, PyObject *args)
 {
 	Py_ssize_t i, len, addlen;
 	char *nothead = NULL;
-	PyObject *heads;
+	PyObject *heads, *filteredrevs;
 
-	if (self->headrevs)
+	if (PyTuple_Size(args) == 0) {
+		filteredrevs = Py_None;
+	} else if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
+		return NULL;
+	}
+
+	if (self->headrevs && filteredrevs == self->filteredrevs)
 		return list_copy(self->headrevs);
 
+	Py_DECREF(self->filteredrevs);
+	self->filteredrevs = filteredrevs;
+	Py_INCREF(filteredrevs);
+
+	PyObject *filter = NULL;
+	if (filteredrevs != Py_None) {
+		filter = PyObject_GetAttrString(filteredrevs, "__contains__");
+	}
+
 	len = index_length(self) - 1;
 	heads = PyList_New(0);
 	if (heads == NULL)
@@ -850,6 +880,11 @@ 
 		goto bail;
 
 	for (i = 0; i < self->raw_length; i++) {
+		if (check_filter(filter, i)) {
+			nothead[i] = 1;
+			continue;
+		}
+
 		const char *data = index_deref(self, i);
 		int parent_1 = getbe32(data + 24);
 		int parent_2 = getbe32(data + 28);
@@ -872,6 +907,12 @@ 
 					"revlog parents are invalid");
 			goto bail;
 		}
+
+		if (check_filter(filter, i)) {
+			nothead[i] = 1;
+			continue;
+		}
+
 		parent_1 = PyInt_AS_LONG(p1);
 		parent_2 = PyInt_AS_LONG(p2);
 		if (parent_1 >= 0)
@@ -894,9 +935,11 @@ 
 
 done:
 	self->headrevs = heads;
+	Py_XDECREF(filter);
 	free(nothead);
 	return list_copy(self->headrevs);
 bail:
+	Py_XDECREF(filter);
 	Py_XDECREF(heads);
 	free(nothead);
 	return NULL;
@@ -1896,6 +1939,8 @@ 
 	self->cache = NULL;
 	self->data = NULL;
 	self->headrevs = NULL;
+	self->filteredrevs = Py_None;
+	Py_INCREF(Py_None);
 	self->nt = NULL;
 	self->offsets = NULL;
 
@@ -1945,6 +1990,7 @@ 
 static void index_dealloc(indexObject *self)
 {
 	_index_clearcaches(self);
+	Py_XDECREF(self->filteredrevs);
 	Py_XDECREF(self->data);
 	Py_XDECREF(self->added);
 	PyObject_Del(self);
@@ -1977,7 +2023,7 @@ 
 	 "clear the index caches"},
 	{"get", (PyCFunction)index_m_get, METH_VARARGS,
 	 "get an index entry"},
-	{"headrevs", (PyCFunction)index_headrevs, METH_NOARGS,
+	{"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
 	 "get head revisions"},
 	{"insert", (PyCFunction)index_insert, METH_VARARGS,
 	 "insert an index entry"},