diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -171,8 +171,13 @@ class changelog(revlog.revlog):
 
     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 @@ typedef struct {
 	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,60 @@ static PyObject *list_copy(PyObject *lis
 	return newlist;
 }
 
-static PyObject *index_headrevs(indexObject *self)
+static int check_filter(PyObject *filter, Py_ssize_t arg) {
+	if (filter) {
+		PyObject *arglist, *result;
+		int isfiltered;
+
+		arglist = Py_BuildValue("(n)", arg);
+		if (!arglist) {
+			return -1;
+		}
+
+		result = PyEval_CallObject(filter, arglist);
+		Py_DECREF(arglist);
+		if (!result) {
+			return -1;
+		}
+
+		/* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error,
+		 * same as this function, so we can just return it directly.*/
+		isfiltered = PyObject_IsTrue(result);
+		Py_DECREF(result);
+		return isfiltered;
+	} else {
+		return 0;
+	}
+}
+
+static PyObject *index_headrevs(indexObject *self, PyObject *args)
 {
 	Py_ssize_t i, len, addlen;
 	char *nothead = NULL;
 	PyObject *heads;
+	PyObject *filter = NULL;
+	PyObject *filteredrevs = Py_None;
 
-	if (self->headrevs)
+	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);
+
+	if (filteredrevs != Py_None) {
+		filter = PyObject_GetAttrString(filteredrevs, "__contains__");
+		if (!filter) {
+			PyErr_SetString(PyExc_TypeError,
+				"filteredrevs has no attribute __contains__");
+			goto bail;
+		}
+	}
+
 	len = index_length(self) - 1;
 	heads = PyList_New(0);
 	if (heads == NULL)
@@ -850,9 +896,25 @@ static PyObject *index_headrevs(indexObj
 		goto bail;
 
 	for (i = 0; i < self->raw_length; i++) {
-		const char *data = index_deref(self, i);
-		int parent_1 = getbe32(data + 24);
-		int parent_2 = getbe32(data + 28);
+		const char *data;
+		int parent_1, parent_2, isfiltered;
+
+		isfiltered = check_filter(filter, i);
+		if (isfiltered == -1) {
+			PyErr_SetString(PyExc_TypeError,
+				"unable to check filter");
+			goto bail;
+		}
+
+		if (isfiltered) {
+			nothead[i] = 1;
+			continue;
+		}
+
+		data = index_deref(self, i);
+		parent_1 = getbe32(data + 24);
+		parent_2 = getbe32(data + 28);
+
 		if (parent_1 >= 0)
 			nothead[parent_1] = 1;
 		if (parent_2 >= 0)
@@ -866,12 +928,26 @@ static PyObject *index_headrevs(indexObj
 		PyObject *p1 = PyTuple_GET_ITEM(rev, 5);
 		PyObject *p2 = PyTuple_GET_ITEM(rev, 6);
 		long parent_1, parent_2;
+		int isfiltered;
 
 		if (!PyInt_Check(p1) || !PyInt_Check(p2)) {
 			PyErr_SetString(PyExc_TypeError,
 					"revlog parents are invalid");
 			goto bail;
 		}
+
+		isfiltered = check_filter(filter, i);
+		if (isfiltered == -1) {
+			PyErr_SetString(PyExc_TypeError,
+				"unable to check filter");
+			goto bail;
+		}
+
+		if (isfiltered) {
+			nothead[i] = 1;
+			continue;
+		}
+
 		parent_1 = PyInt_AS_LONG(p1);
 		parent_2 = PyInt_AS_LONG(p2);
 		if (parent_1 >= 0)
@@ -894,9 +970,11 @@ static PyObject *index_headrevs(indexObj
 
 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 +1974,8 @@ static int index_init(indexObject *self,
 	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 +2025,7 @@ static PyObject *index_nodemap(indexObje
 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 +2058,7 @@ static PyMethodDef index_methods[] = {
 	 "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"},