Mercurial > hg
comparison mercurial/parsers.c @ 26004:ff89383a97db
reachableroots: add a C implementation
This patch is part of a series of patches to speed up the computation of
revset.reachableroots by introducing a C implementation. The main motivation is to
speed up smartlog on big repositories. At the end of the series, on our big
repositories the computation of reachableroots is 10-50x faster and smartlog on is
2x-5x faster.
This patch introduces a C implementation for reachableroots following closely the
Python implementation but optimized by using C data structures.
author | Laurent Charignon <lcharignon@fb.com> |
---|---|
date | Thu, 06 Aug 2015 21:28:45 -0700 |
parents | f4386cb3252e |
children | 1ebf4ac07582 |
comparison
equal
deleted
inserted
replaced
26003:62371c539c89 | 26004:ff89383a97db |
---|---|
1103 phases[i] = phases[parent_1]; | 1103 phases[i] = phases[parent_1]; |
1104 if (parent_2 >= 0 && phases[parent_2] > phases[i]) | 1104 if (parent_2 >= 0 && phases[parent_2] > phases[i]) |
1105 phases[i] = phases[parent_2]; | 1105 phases[i] = phases[parent_2]; |
1106 } | 1106 } |
1107 | 1107 |
1108 static PyObject *reachableroots(indexObject *self, PyObject *args) | |
1109 { | |
1110 | |
1111 /* Input */ | |
1112 long minroot; | |
1113 PyObject *includepatharg = NULL; | |
1114 int includepath = 0; | |
1115 PyObject *heads = NULL; | |
1116 Py_ssize_t numheads; | |
1117 PyObject *roots = NULL; | |
1118 PyObject *reachable = NULL; | |
1119 | |
1120 PyObject *val; | |
1121 Py_ssize_t len = index_length(self) - 1; | |
1122 long revnum; | |
1123 Py_ssize_t k; | |
1124 Py_ssize_t i; | |
1125 int r; | |
1126 int minidx; | |
1127 int parents[2]; | |
1128 | |
1129 /* Internal data structure: | |
1130 * tovisit: array of length len+1 (all revs + nullrev), filled upto lentovisit | |
1131 * seen: array of length len+1 (all revs + nullrev) 0: not seen, 1 seen*/ | |
1132 int *tovisit = NULL; | |
1133 long lentovisit = 0; | |
1134 char *seen = NULL; | |
1135 | |
1136 /* Get arguments */ | |
1137 if (!PyArg_ParseTuple(args, "lO!O!O!", &minroot, &PySet_Type, &heads, | |
1138 &PyList_Type, &roots, &PyBool_Type, &includepatharg)) | |
1139 goto bail; | |
1140 | |
1141 if (includepatharg == Py_True) | |
1142 includepath = 1; | |
1143 | |
1144 /* Initialize return set */ | |
1145 reachable = PySet_New(0); | |
1146 if (reachable == NULL) | |
1147 goto bail; | |
1148 | |
1149 /* Initialize internal datastructures */ | |
1150 tovisit = (int *)malloc((len + 1) * sizeof(int)); | |
1151 if (tovisit == NULL) { | |
1152 PyErr_SetNone(PyExc_MemoryError); | |
1153 goto release_reachable; | |
1154 } | |
1155 | |
1156 seen = (char *)calloc(len+1, 1); | |
1157 if (seen == NULL) { | |
1158 PyErr_SetNone(PyExc_MemoryError); | |
1159 goto release_seen_and_tovisit; | |
1160 } | |
1161 | |
1162 /* Populate tovisit with all the heads */ | |
1163 numheads = PyList_GET_SIZE(heads); | |
1164 for (i = 0; i < numheads; i++) { | |
1165 revnum = PyInt_AS_LONG(PyList_GET_ITEM(heads, i)); | |
1166 if (seen[revnum+1] == 0) { | |
1167 tovisit[lentovisit++] = revnum; | |
1168 seen[revnum+1]=1; | |
1169 } | |
1170 } | |
1171 | |
1172 /* Visit the tovisit list and find the reachable roots */ | |
1173 k = 0; | |
1174 while (k < lentovisit) { | |
1175 /* Add the node to reachable if it is a root*/ | |
1176 revnum = tovisit[k++]; | |
1177 val = PyInt_FromLong(revnum); | |
1178 if (PySet_Contains(roots, val) == 1) { | |
1179 PySet_Add(reachable, val); | |
1180 if (includepath == 0) { | |
1181 Py_XDECREF(val); | |
1182 continue; | |
1183 } | |
1184 } | |
1185 Py_XDECREF(val); | |
1186 | |
1187 /* Add its parents to the list of nodes to visit */ | |
1188 if (revnum != -1) { | |
1189 r = index_get_parents(self, revnum, parents, (int)len - 1); | |
1190 if (r < 0) | |
1191 goto release_seen_and_tovisit; | |
1192 | |
1193 for (i = 0; i < 2; i++) { | |
1194 if (seen[parents[i] + 1] == 0 && parents[i] >= minroot) { | |
1195 tovisit[lentovisit++] = parents[i]; | |
1196 seen[parents[i] + 1] = 1; | |
1197 } | |
1198 } | |
1199 } | |
1200 } | |
1201 | |
1202 /* Find all the nodes in between the roots we found and the heads | |
1203 * and add them to the reachable set */ | |
1204 if (includepath == 1) { | |
1205 minidx = minroot; | |
1206 if (minidx < 0) | |
1207 minidx = 0; | |
1208 for (i = minidx; i < len; i++) { | |
1209 if (seen[i + 1] == 1) { | |
1210 r = index_get_parents(self, i, parents, (int)len - 1); | |
1211 /* Corrupted index file, error is set from index_get_parents */ | |
1212 if (r < 0) | |
1213 goto release_seen_and_tovisit; | |
1214 for (k = 0; k < 2; k++) { | |
1215 PyObject *p = PyInt_FromLong(parents[k]); | |
1216 if (PySet_Contains(reachable, p) == 1) | |
1217 PySet_Add(reachable, PyInt_FromLong(i)); | |
1218 Py_XDECREF(p); | |
1219 } | |
1220 } | |
1221 } | |
1222 } | |
1223 | |
1224 release_seen_and_tovisit: | |
1225 free(seen); | |
1226 free(tovisit); | |
1227 return reachable; | |
1228 release_reachable: | |
1229 Py_XDECREF(reachable); | |
1230 bail: | |
1231 val = Py_None; | |
1232 Py_INCREF(Py_None); | |
1233 return val; | |
1234 } | |
1235 | |
1108 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args) | 1236 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args) |
1109 { | 1237 { |
1110 PyObject *roots = Py_None; | 1238 PyObject *roots = Py_None; |
1111 PyObject *ret = NULL; | 1239 PyObject *ret = NULL; |
1112 PyObject *phaseslist = NULL; | 1240 PyObject *phaseslist = NULL; |
2280 "clear the index caches"}, | 2408 "clear the index caches"}, |
2281 {"get", (PyCFunction)index_m_get, METH_VARARGS, | 2409 {"get", (PyCFunction)index_m_get, METH_VARARGS, |
2282 "get an index entry"}, | 2410 "get an index entry"}, |
2283 {"computephasesmapsets", (PyCFunction)compute_phases_map_sets, | 2411 {"computephasesmapsets", (PyCFunction)compute_phases_map_sets, |
2284 METH_VARARGS, "compute phases"}, | 2412 METH_VARARGS, "compute phases"}, |
2413 {"reachableroots", (PyCFunction)reachableroots, METH_VARARGS, | |
2414 "reachableroots"}, | |
2285 {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS, | 2415 {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS, |
2286 "get head revisions"}, /* Can do filtering since 3.2 */ | 2416 "get head revisions"}, /* Can do filtering since 3.2 */ |
2287 {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS, | 2417 {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS, |
2288 "get filtered head revisions"}, /* Can always do filtering */ | 2418 "get filtered head revisions"}, /* Can always do filtering */ |
2289 {"insert", (PyCFunction)index_insert, METH_VARARGS, | 2419 {"insert", (PyCFunction)index_insert, METH_VARARGS, |