[PATCH 4 of 5] parsers: a C implementation of the new ancestors algorithm
Bryan O'Sullivan
bos at serpentine.com
Wed May 2 18:22:41 CDT 2012
# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1336000854 25200
# Branch stable
# Node ID 4e2a64dbe7083462f7614851cdc1b1541df75f75
# Parent 52d62ae25ab408f3c645790feb78f564383588bd
parsers: a C implementation of the new ancestors algorithm
The performance of both the old and new Python ancestor algorithms
depends on the number of revs they need to traverse. Although the
new algorithm performs far better than the old when revs are
numerically and topologically close, both algorithms become slow
under other circumstances, taking up to 1.8 seconds to give answers
in a Linux kernel repo.
This C implementation of the new algorithm is a fairly straightforward
transliteration. The only corner case of interest is that it raises
an OverflowError if the number of GCA candidates found during the
first pass is greater than 24, to avoid the dual perils of fixnum
overflow and trying to allocate too much memory. (If this exception
is raised, the Python implementation is used instead.)
Performance numbers are good: in a Linux kernel repo, time for "hg
debugancestors" on two distant revs (24bf01de7537 and c2a8808f5943)
is as follows:
Old Python: 0.36 sec
New Python: 0.42 sec
New C: 0.02 sec
For a case where the new algorithm should perform well:
Old Python: 1.84 sec
New Python: 0.07 sec
New C: measures as zero when using --time
(This commit includes a paranoid cross-check to ensure that the
Python and C implementations give identical answers. The above
performance numbers were measured with that check disabled.)
diff -r 52d62ae25ab4 -r 4e2a64dbe708 mercurial/parsers.c
--- a/mercurial/parsers.c Wed May 02 16:19:43 2012 -0700
+++ b/mercurial/parsers.c Wed May 02 16:20:54 2012 -0700
@@ -819,6 +819,371 @@
}
}
+
+static inline void index_get_parents(indexObject *self, int rev, int *ps)
+{
+ if (rev >= self->length - 1) {
+ PyObject *tuple = PyList_GET_ITEM(self->added,
+ rev - self->length + 1);
+ ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));
+ ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));
+ } else {
+ const char *data = index_deref(self, rev);
+ ps[0] = getbe32(data + 24);
+ ps[1] = getbe32(data + 28);
+ }
+}
+
+typedef uint64_t bitmask;
+
+/*
+ * Given a disjoint set of revs, return all candidates for the
+ * greatest common ancestor. In revset notation, this is the set
+ * "heads(::a and ::b and ...)"
+ */
+static PyObject *find_gca_candidates(indexObject *self, const int *revs,
+ int revcount)
+{
+ const bitmask allseen = (1ull << revcount) - 1;
+ const bitmask poison = 1ull << revcount;
+ PyObject *gca = PyList_New(0);
+ int i, v, interesting, left;
+ int maxrev = -1;
+ bitmask *seen;
+
+ for (i = 0; i < revcount; i++) {
+ if (revs[i] > maxrev)
+ maxrev = revs[i];
+ }
+
+ seen = malloc(sizeof(*seen) * (maxrev + 1));
+ if (seen == NULL)
+ return PyErr_NoMemory();
+ memset(seen, 0, sizeof(*seen) * (maxrev + 1));
+
+ for (i = 0; i < revcount; i++)
+ seen[revs[i]] = 1ull << i;
+
+ interesting = left = revcount;
+
+ for (v = maxrev; v >= 0 && interesting; v--) {
+ long sv = seen[v];
+ int parents[2];
+
+ if (!sv)
+ continue;
+
+ if (sv < poison) {
+ interesting -= 1;
+ if (sv == allseen) {
+ PyObject *obj = PyInt_FromLong(v);
+ if (obj == NULL)
+ goto bail;
+ if (PyList_Append(gca, obj) == -1) {
+ Py_DECREF(obj);
+ goto bail;
+ }
+ sv |= poison;
+ for (i = 0; i < revcount; i++) {
+ if (revs[i] == v) {
+ if (--left <= 1)
+ goto done;
+ break;
+ }
+ }
+ }
+ }
+ index_get_parents(self, v, parents);
+
+ for (i = 0; i < 2; i++) {
+ int p = parents[i];
+ if (p == -1)
+ continue;
+ const long sp = seen[p];
+ if (sv < poison) {
+ if (sp == 0) {
+ seen[p] = sv;
+ interesting++;
+ }
+ else if (sp != sv)
+ seen[p] |= sv;
+ } else {
+ if (sp && sp < poison)
+ interesting--;
+ seen[p] = sv;
+ }
+ }
+ }
+
+done:
+ free(seen);
+ return gca;
+bail:
+ free(seen);
+ Py_XDECREF(gca);
+ return NULL;
+}
+
+/*
+ * Given a disjoint set of revs, return the subset with the longest
+ * path to the root.
+ */
+static PyObject *find_deepest(indexObject *self, PyObject *revs)
+{
+ const Py_ssize_t revcount = PyList_GET_SIZE(revs);
+ static const Py_ssize_t capacity = 24;
+ int *depth, *interesting = NULL;
+ int i, j, v, ninteresting;
+ PyObject *dict, *keys;
+ long *seen = NULL;
+ int maxrev = -1;
+ long final;
+
+ if (revcount > capacity) {
+ PyErr_Format(PyExc_OverflowError,
+ "bitset size (%ld) > capacity (%ld)",
+ revcount, capacity);
+ return NULL;
+ }
+
+ for (i = 0; i < revcount; i++) {
+ int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
+ if (n > maxrev)
+ maxrev = n;
+ }
+
+ depth = malloc((maxrev + 1) * sizeof(*depth));
+ if (depth == NULL)
+ return PyErr_NoMemory();
+ memset(depth, 0, (maxrev + 1) * sizeof(*depth));
+
+ seen = malloc((maxrev + 1) * sizeof(*seen));
+ if (seen == NULL) {
+ PyErr_NoMemory();
+ goto bail;
+ }
+ memset(seen, 0, (maxrev + 1) * sizeof(*seen));
+
+ interesting = malloc((2 << revcount) * sizeof(*interesting));
+ if (interesting == NULL) {
+ PyErr_NoMemory();
+ goto bail;
+ }
+ memset(interesting, 0, (2 << revcount) * sizeof(*interesting));
+
+ for (i = 0; i < revcount; i++) {
+ int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
+ long b = 1l << i;
+ depth[n] = 1;
+ seen[n] = b;
+ interesting[b] = 1;
+ }
+
+ ninteresting = (int)revcount;
+
+ for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
+ int dv = depth[v];
+ int parents[2];
+ long sv;
+
+ if (dv == 0)
+ continue;
+
+ sv = seen[v];
+ index_get_parents(self, v, parents);
+
+ for (i = 0; i < 2; i++) {
+ int p = parents[i];
+ long nsp, sp;
+ int dp;
+
+ if (p == -1)
+ continue;
+
+ dp = depth[p];
+ nsp = sp = seen[p];
+ if (dp <= dv) {
+ depth[p] = dv + 1;
+ if (sp != sv) {
+ interesting[sv] += 1;
+ nsp = seen[p] = sv;
+ if (sp) {
+ interesting[sp] -= 1;
+ if (interesting[sp] == 0)
+ ninteresting -= 1;
+ }
+ }
+ }
+ else if (dv == dp - 1) {
+ nsp = sp | sv;
+ if (nsp == sp)
+ continue;
+ seen[p] = nsp;
+ interesting[nsp] += 1;
+ interesting[sp] -= 1;
+ if (interesting[sp] == 0)
+ ninteresting -= 1;
+ }
+ }
+ interesting[sv] -= 1;
+ if (interesting[sv] == 0)
+ ninteresting -= 1;
+ }
+
+ final = 0;
+ j = ninteresting;
+ for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
+ if (interesting[i] == 0)
+ continue;
+ final |= i;
+ j -= 1;
+ }
+ if (final == 0)
+ return PyList_New(0);
+
+ dict = PyDict_New();
+ if (dict == NULL)
+ goto bail;
+
+ j = ninteresting;
+ for (i = 0; i < revcount && j > 0; i++) {
+ PyObject *key;
+
+ if ((final & (1 << i)) == 0)
+ continue;
+
+ key = PyList_GET_ITEM(revs, i);
+ Py_INCREF(key);
+ Py_INCREF(Py_None);
+ if (PyDict_SetItem(dict, key, Py_None) == -1) {
+ Py_DECREF(key);
+ Py_DECREF(Py_None);
+ goto bail;
+ }
+ j -= 1;
+ }
+
+ keys = PyDict_Keys(dict);
+
+ free(depth);
+ free(seen);
+ free(interesting);
+ Py_DECREF(dict);
+
+ return keys;
+bail:
+ free(depth);
+ free(seen);
+ free(interesting);
+ Py_XDECREF(dict);
+
+ return NULL;
+}
+
+/*
+ * Given a (possibly overlapping) set of revs, return the greatest
+ * common ancestors: those with the longest path to the root.
+ */
+static PyObject *index_ancestors(indexObject *self, PyObject *args)
+{
+ PyObject *ret = NULL, *gca = NULL;
+ Py_ssize_t argcount, i, len;
+ bitmask repeat = 0;
+ int revcount = 0;
+ int *revs;
+
+ argcount = PySequence_Length(args);
+ revs = malloc(argcount * sizeof(*revs));
+ if (argcount > 0 && revs == NULL)
+ return PyErr_NoMemory();
+ len = index_length(self) - 1;
+
+ for (i = 0; i < argcount; i++) {
+ static const int capacity = 24;
+ PyObject *obj = PySequence_GetItem(args, i);
+ bitmask x;
+ long val;
+
+ if (!PyInt_Check(obj)) {
+ PyErr_SetString(PyExc_TypeError,
+ "arguments must all be ints");
+ goto bail;
+ }
+ val = PyInt_AsLong(obj);
+ if (val == -1) {
+ ret = PyList_New(0);
+ goto done;
+ }
+ if (val < 0 || val >= len) {
+ PyErr_SetString(PyExc_IndexError,
+ "index out of range");
+ goto bail;
+ }
+ /* this cheesy bloom filter lets us avoid some more
+ * expensive duplicate checks in the common set-is-disjoint
+ * case */
+ x = 1ull << (val & 0x3f);
+ if (repeat & x) {
+ int k;
+ for (k = 0; k < revcount; k++) {
+ if (val == revs[k])
+ goto duplicate;
+ }
+ }
+ else repeat |= x;
+ if (revcount >= capacity) {
+ PyErr_Format(PyExc_OverflowError,
+ "bitset size (%d) > capacity (%d)",
+ revcount, capacity);
+ goto bail;
+ }
+ revs[revcount++] = (int)val;
+ duplicate:;
+ }
+
+ if (revcount == 0) {
+ ret = PyList_New(0);
+ goto done;
+ }
+ if (revcount == 1) {
+ PyObject *obj;
+ ret = PyList_New(1);
+ if (ret == NULL)
+ goto bail;
+ obj = PyInt_FromLong(revs[0]);
+ if (obj == NULL)
+ goto bail;
+ PyList_SET_ITEM(ret, 0, obj);
+ goto done;
+ }
+
+ gca = find_gca_candidates(self, revs, revcount);
+ if (gca == NULL)
+ goto bail;
+
+ if (PyList_GET_SIZE(gca) <= 1) {
+ ret = gca;
+ Py_INCREF(gca);
+ }
+ else if (PyList_GET_SIZE(gca) == 1) {
+ ret = PyList_GET_ITEM(gca, 0);
+ Py_INCREF(ret);
+ }
+ else ret = find_deepest(self, gca);
+
+done:
+ free(revs);
+ Py_XDECREF(gca);
+
+ return ret;
+
+bail:
+ free(revs);
+ Py_XDECREF(gca);
+ Py_XDECREF(ret);
+ return NULL;
+}
+
/*
* Invalidate any trie entries introduced by added revs.
*/
@@ -1053,6 +1418,8 @@
};
static PyMethodDef index_methods[] = {
+ {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,
+ "return the gca set of the given revs"},
{"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
"clear the index caches"},
{"get", (PyCFunction)index_m_get, METH_VARARGS,
diff -r 52d62ae25ab4 -r 4e2a64dbe708 mercurial/revlog.py
--- a/mercurial/revlog.py Wed May 02 16:19:43 2012 -0700
+++ b/mercurial/revlog.py Wed May 02 16:20:54 2012 -0700
@@ -707,7 +707,13 @@
"""calculate the least common ancestor of nodes a and b"""
a, b = self.rev(a), self.rev(b)
- ancs = ancestor.ancestors(self.parentrevs, a, b)
+ try:
+ ancs = self.index.ancestors(a, b)
+ old = ancestor.ancestors(self.parentrevs, a, b)
+ assert set(ancs) == old, ('opinions differ over ancestor(%d, %d)' %
+ (a, b))
+ except (AttributeError, OverflowError):
+ ancs = ancestor.ancestors(self.parentrevs, a, b)
if not ancs:
return nullid
if len(ancs) == 1:
More information about the Mercurial-devel
mailing list