Mercurial > hg
comparison mercurial/parsers.c @ 24443:539b3c7eea44
phase: compute phases in C
Previously, the phase computation would grow much slower as the oldest draft
commit in the repository grew older (which is very common in repos with evolve
on) and the number of commits increase.
By rewriting the computation in C we can speed it up from 700ms to 7ms on
a large repository whose oldest draft commit is a year old.
author | Laurent Charignon <lcharignon@fb.com> |
---|---|
date | Tue, 24 Mar 2015 11:00:09 -0700 |
parents | a5f1bccd2996 |
children | 90db70de6f9c |
comparison
equal
deleted
inserted
replaced
24442:98042b0e19f9 | 24443:539b3c7eea44 |
---|---|
909 } else { | 909 } else { |
910 return 0; | 910 return 0; |
911 } | 911 } |
912 } | 912 } |
913 | 913 |
914 static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list, | |
915 int marker, char *phases) | |
916 { | |
917 PyObject *iter = NULL; | |
918 PyObject *iter_item = NULL; | |
919 Py_ssize_t min_idx = index_length(self) + 1; | |
920 long iter_item_long; | |
921 | |
922 if (PyList_GET_SIZE(list) != 0) { | |
923 iter = PyObject_GetIter(list); | |
924 if (iter == NULL) | |
925 return -2; | |
926 while ((iter_item = PyIter_Next(iter))) | |
927 { | |
928 iter_item_long = PyInt_AS_LONG(iter_item); | |
929 Py_DECREF(iter_item); | |
930 if (iter_item_long < min_idx) | |
931 min_idx = iter_item_long; | |
932 phases[iter_item_long] = marker; | |
933 } | |
934 Py_DECREF(iter); | |
935 } | |
936 | |
937 return min_idx; | |
938 } | |
939 | |
940 static inline void set_phase_from_parents(char *phases, int parent_1, | |
941 int parent_2, int i) | |
942 { | |
943 if (parent_1 >= 0 && phases[parent_1] > phases[i]) | |
944 phases[i] = phases[parent_1]; | |
945 if (parent_2 >= 0 && phases[parent_2] > phases[i]) | |
946 phases[i] = phases[parent_2]; | |
947 } | |
948 | |
949 static PyObject *compute_phases(indexObject *self, PyObject *args) | |
950 { | |
951 PyObject *roots = Py_None; | |
952 PyObject *phaseslist = NULL; | |
953 PyObject *phaseroots = NULL; | |
954 PyObject *rev = NULL; | |
955 PyObject *p1 = NULL; | |
956 PyObject *p2 = NULL; | |
957 Py_ssize_t addlen = self->added ? PyList_GET_SIZE(self->added) : 0; | |
958 Py_ssize_t len = index_length(self) - 1; | |
959 Py_ssize_t numphase = 0; | |
960 Py_ssize_t minrevallphases = 0; | |
961 Py_ssize_t minrevphase = 0; | |
962 Py_ssize_t i = 0; | |
963 long parent_1, parent_2; | |
964 char *phases = NULL; | |
965 const char *data; | |
966 | |
967 if (!PyArg_ParseTuple(args, "O", &roots)) | |
968 goto release_none; | |
969 if (roots == NULL || !PyList_Check(roots)) | |
970 goto release_none; | |
971 | |
972 phases = calloc(len, 1); /* phase per rev: {0: public, 1: draft, 2: secret} */ | |
973 if (phases == NULL) | |
974 goto release_none; | |
975 /* Put the phase information of all the roots in phases */ | |
976 numphase = PyList_GET_SIZE(roots)+1; | |
977 minrevallphases = len + 1; | |
978 for (i = 0; i < numphase-1; i++) { | |
979 phaseroots = PyList_GET_ITEM(roots, i); | |
980 if (!PyList_Check(phaseroots)) | |
981 goto release_phases; | |
982 minrevphase = add_roots_get_min(self, phaseroots, i+1, phases); | |
983 if (minrevphase == -2) /* Error from add_roots_get_min */ | |
984 goto release_phases; | |
985 minrevallphases = MIN(minrevallphases, minrevphase); | |
986 } | |
987 /* Propagate the phase information from the roots to the revs */ | |
988 if (minrevallphases != -1) { | |
989 for (i = minrevallphases; i < self->raw_length; i++) { | |
990 data = index_deref(self, i); | |
991 set_phase_from_parents(phases, getbe32(data+24), getbe32(data+28), i); | |
992 } | |
993 for (i = 0; i < addlen; i++) { | |
994 rev = PyList_GET_ITEM(self->added, i); | |
995 p1 = PyTuple_GET_ITEM(rev, 5); | |
996 p2 = PyTuple_GET_ITEM(rev, 6); | |
997 if (!PyInt_Check(p1) || !PyInt_Check(p2)) { | |
998 PyErr_SetString(PyExc_TypeError, "revlog parents are invalid"); | |
999 goto release_phases; | |
1000 } | |
1001 parent_1 = PyInt_AS_LONG(p1); | |
1002 parent_2 = PyInt_AS_LONG(p2); | |
1003 set_phase_from_parents(phases, parent_1, parent_2, i+self->raw_length); | |
1004 } | |
1005 } | |
1006 /* Transform phase list to a python list */ | |
1007 phaseslist = PyList_New(len); | |
1008 if (phaseslist == NULL) | |
1009 goto release_phases; | |
1010 for (i = 0; i < len; i++) | |
1011 PyList_SET_ITEM(phaseslist, i, PyInt_FromLong(phases[i])); | |
1012 | |
1013 release_phases: | |
1014 free(phases); | |
1015 release_none: | |
1016 return phaseslist; | |
1017 } | |
1018 | |
914 static PyObject *index_headrevs(indexObject *self, PyObject *args) | 1019 static PyObject *index_headrevs(indexObject *self, PyObject *args) |
915 { | 1020 { |
916 Py_ssize_t i, len, addlen; | 1021 Py_ssize_t i, len, addlen; |
917 char *nothead = NULL; | 1022 char *nothead = NULL; |
918 PyObject *heads = NULL; | 1023 PyObject *heads = NULL; |
2041 "return the heads of the common ancestors of the given revs"}, | 2146 "return the heads of the common ancestors of the given revs"}, |
2042 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS, | 2147 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS, |
2043 "clear the index caches"}, | 2148 "clear the index caches"}, |
2044 {"get", (PyCFunction)index_m_get, METH_VARARGS, | 2149 {"get", (PyCFunction)index_m_get, METH_VARARGS, |
2045 "get an index entry"}, | 2150 "get an index entry"}, |
2151 {"computephases", (PyCFunction)compute_phases, METH_VARARGS, | |
2152 "compute phases"}, | |
2046 {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS, | 2153 {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS, |
2047 "get head revisions"}, /* Can do filtering since 3.2 */ | 2154 "get head revisions"}, /* Can do filtering since 3.2 */ |
2048 {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS, | 2155 {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS, |
2049 "get filtered head revisions"}, /* Can always do filtering */ | 2156 "get filtered head revisions"}, /* Can always do filtering */ |
2050 {"insert", (PyCFunction)index_insert, METH_VARARGS, | 2157 {"insert", (PyCFunction)index_insert, METH_VARARGS, |