{"thread":{"id":"1057","subject":"[EXPERIMENTAL PATCH] O(n) bisection algorithm","startedAt":"2005-06-30T08:11:35Z","lastAt":"2005-06-30T09:03:51Z","messageCount":2,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"5445","messageId":"20050630081135.27577.qmail@blackcubes.dyndns.org","threadId":"1057","inReplyTo":null,"subject":"[EXPERIMENTAL PATCH] O(n) bisection algorithm","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-30T08:11:35Z","receivedAt":"2005-06-30T08:11:35Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis is a rollup of an experimental patch to Linus' HEAD that adds\na O(n) bisection algorithm to git.\n\nFor the purposes of comparison, this version:\n   * enables debugging (-DDEBUG)\n   * adds a --debug switch to git-rev-list\n   * adds a --bisect-by-cut switch to git-rev-list\n\nThis allows the same git-rev-list binary to be used to compare the existing\nO(n^2) behaviour (--bisect) with the O(n) behaviour (--bisect-by-cut).\n\nA measure of complexity of each algorithm can be obtained on stderr,\nby using the --debug switch.\n\nMy measurements suggest that on a 2000 commit kernel history, this\nalgorithm is ~ 5 times faster than the O(n^2) algorithm. If this\nis true, it should be ~25 times faster on a 10,000 commit kernel history.\nThis is the difference between a 16 second bisection and a 0.6 second\nbisection on that size repository.\n\nThis patch also includes my latest topological sort implementation\nso there is no need to apply that separately.\n\nLinus: if you are happy to adopt this as the default bisection\nalgorithm, I'll rework it as a formal patch submission, meaning that I'll:\n   * remove the Makefile change\n   * remove --debug switch\n   * remove the #ifdef'd DEBUG code\n   * replace --bisect implementation with --bisect-by-cut implementation\n     and remove --bisect-by-cut switch\n\nCleanly applies to Linus HEAD e4b5c7fff47d3a794249ea2da6b9ec4e33e157f3.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\nLinus: this isn't fit for inclusion in the mainline yet. I have\nposted it to the list for review purposes only.\n---\n\n Makefile   |    2 \n commit.c   |  117 ++++++++++++++++++++++++++++\n commit.h   |    5 +\n rev-list.c |  248 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n 4 files changed, 361 insertions(+), 11 deletions(-)\n\n83df29ec101718325fbb0c6c8e5dcb891a224edf\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -10,7 +10,7 @@\n # break unless your underlying filesystem supports those sub-second times\n # (my ext3 doesn't).\n COPTS=-O2\n-CFLAGS=-g $(COPTS) -Wall\n+CFLAGS=-DDEBUG -g $(COPTS) -Wall\n \n prefix=$(HOME)\n bin=$(prefix)/bin\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -3,6 +3,27 @@\n #include \"commit.h\"\n #include \"cache.h\"\n \n+struct sort_node\n+{\n+\t/*\n+         * the number of children of the associated commit\n+         * that also occur in the list being sorted.\n+         */\n+\tunsigned int indegree;\n+\n+\t/*\n+         * reference to original list item that we will re-use\n+         * on output.\n+         */\n+\tstruct commit_list * list_item;\n+\n+\t/*\n+         * copy of original object.util pointer that is saved\n+         * during the topological sort.\n+         */\n+\tvoid * save_util;\n+};\n+\n const char *commit_type = \"commit\";\n \n enum cmit_fmt get_commit_format(const char *arg)\n@@ -346,3 +367,99 @@ int count_parents(struct commit * commit\n         return count;\n }\n \n+/*\n+ * Performs an in-place topological sort on the list supplied\n+ * \n+ * Invariant of resulting list is:\n+ *        a reachable from b => ord(b) < ord(a)\n+ */\n+void sort_in_topological_order(struct commit_list ** list)\n+{\n+\tstruct commit_list * next = *list;\n+\tstruct commit_list * work = NULL;\n+\tstruct commit_list ** pptr = list;\n+\tstruct sort_node * nodes;\n+\tstruct sort_node * next_nodes;\n+\tint count = 0;\n+\n+\t/* determine the size of the list */\n+\twhile (next) {\n+\t\tnext = next->next;\n+\t\tcount++;\n+\t}\n+\t/* allocate an array to help sort the list */\n+\tnodes = xcalloc(count, sizeof(*nodes));\n+\t/* link the list to the array */\n+\tnext_nodes = nodes;\n+\tnext=*list;\n+\twhile (next) {\n+\t\tnext_nodes->list_item = next;\n+\t\tnext_nodes->save_util = next->item->object.util;\n+\t\tnext->item->object.util = next_nodes;\n+\t\tnext_nodes++;\n+\t\tnext = next->next;\n+\t}\n+\t/* update the indegree */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct commit_list * parents = next->item->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn)\n+\t\t\t\tpn->indegree++;\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* \n+         * find the tips\n+         *\n+         * tips are nodes not reachable from any other node in the list \n+         * \n+         * the tips serve as a starting set for the work queue.\n+         */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct sort_node * node = (struct sort_node *)next->item->object.util;\n+\n+\t\tif (node->indegree == 0) {\n+\t\t\tcommit_list_insert(next->item, &work);\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* process the list in topological order */\n+\twhile (work) {\n+\t\tstruct commit * work_item = pop_commit(&work);\n+\t\tstruct sort_node * work_node = (struct sort_node *)work_item->object.util;\n+\t\tstruct commit_list * parents = work_item->parents;\n+\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn) {\n+\t\t\t\t/* \n+\t\t\t\t * parents are only enqueed for emission \n+                                 * when all their children have been emitted thereby\n+                                 * guaranteeing topological order.\n+                                 */\n+\t\t\t\tpn->indegree--;\n+\t\t\t\tif (!pn->indegree) \n+\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t}\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\t/*\n+                 * work_item is a commit all of whose children\n+                 * have already been emitted. we can emit it now\n+                 * and restore its util pointer.\n+                 */\n+\t\t*pptr = work_node->list_item;\n+\t\tpptr = &(*pptr)->next;\n+\t\t*pptr = NULL;\n+\t\twork_item->object.util = work_node->save_util;\n+\t}\n+\tfree(nodes);\n+}\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -55,4 +55,9 @@ struct commit *pop_most_recent_commit(st\n struct commit *pop_commit(struct commit_list **stack);\n \n int count_parents(struct commit * commit);\n+\n+/*\n+ * Performs an in-place topological sort of list supplied.\n+ */\n+void sort_in_topological_order(struct commit_list ** list);\n #endif /* COMMIT_H */\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -5,10 +5,19 @@\n #include \"blob.h\"\n #include \"epoch.h\"\n \n-#define SEEN\t\t(1u << 0)\n-#define INTERESTING\t(1u << 1)\n-#define COUNTED\t\t(1u << 2)\n-#define SHOWN\t\t(LAST_EPOCH_FLAG << 2)\n+#define ABOVE        (1u<<1)\n+struct bisect_by_cut_node \n+{\n+\tunsigned int flags;\n+\tunsigned int count;\n+\tstruct commit_list * children;\n+\tstruct commit_list * visible_parents;\n+};\n+\n+#define SEEN        (LAST_EPOCH_FLAG << 1)\n+#define INTERESTING (LAST_EPOCH_FLAG << 2)\n+#define COUNTED     (LAST_EPOCH_FLAG << 3)\n+#define SHOWN       (LAST_EPOCH_FLAG << 4)\n \n static const char rev_list_usage[] =\n \t\"usage: git-rev-list [OPTION] commit-id <commit-id>\\n\"\n@@ -34,6 +43,13 @@ static enum cmit_fmt commit_format = CMI\n static int merge_order = 0;\n static int show_breaks = 0;\n static int stop_traversal = 0;\n+static int bisect_by_cut_option = 0;\n+static struct commit_list * topological_order = NULL;\n+static struct commit_list ** t_o_tail = &topological_order;\n+#ifdef DEBUG\n+static int debug = 0;\n+static unsigned int complexity = 0;\n+#endif\n \n static void show_commit(struct commit *commit)\n {\n@@ -95,8 +111,10 @@ static int process_commit(struct commit \n \t\treturn CONTINUE;\n \t}\n \n-\tshow_commit(commit);\n-\n+\tif (!bisect_by_cut_option) {\n+\t\tshow_commit(commit);\n+\t} else\n+\t\tt_o_tail = &commit_list_insert(commit, t_o_tail)->next;\n \treturn CONTINUE;\n }\n \n@@ -264,7 +282,7 @@ static int count_distance(struct commit_\n \t\t\twhile (p) {\n \t\t\t\tnr += count_distance(p);\n \t\t\t\tp = p->next;\n-\t\t\t}\n+\t\t\t}\t\t\t\n \t\t}\n \t}\n \treturn nr;\n@@ -272,6 +290,9 @@ static int count_distance(struct commit_\n \n static void clear_distance(struct commit_list *list)\n {\n+#ifdef DEBUG\n+\tcomplexity++;\n+#endif\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n \t\tcommit->object.flags &= ~COUNTED;\n@@ -403,6 +424,196 @@ static struct commit *get_commit_referen\n \tdie(\"%s is unknown object\", name);\n }\n \n+static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)\n+{\n+\treturn (struct bisect_by_cut_node *)commit->object.util;\n+}\n+\n+#ifdef DEBUG\n+static void print_bisect_by_cut_node(struct commit * commit, const char * prefix)\n+{\n+\tstruct bisect_by_cut_node * node = get_bisect_by_cut_node(commit);\n+\tfprintf(stderr, \"%s%s %u %d\\n\", prefix, sha1_to_hex(commit->object.sha1), node->flags, node->count);\n+}\n+#endif\n+\n+/*\n+ * Find the best bisection point by cutting a topological order in two then\n+ * identifying a set of boundary nodes with a reachability known to be \n+ * less than the desired bisection point. The boundary is advanced until all nodes\n+ * in the boundary have a reachability greater than or equal to the desired \n+ * reachability.\n+ *\n+ * This algorithm is roughly O(kn) where k is a factor related to the typical\n+ * amount of parallel branching within the graph and is not related to n.\n+ *\n+ * The algorithm borrows the notion of making an arbitrary cut in the graph\n+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in\n+ * other respects. In particular, by using the topological order to make the\n+ * cut the width of the advancing boundary is reduced to some kind of minimum.\n+ * Full graph scans (e.g. calls to count_distance()) are avoided except where\n+ * absolutely necessary (i.e. a merge node is encountered).\n+ */\n+struct commit * bisect_by_cut(struct commit_list * topological_order)\n+{\n+\tunsigned int count=0;\n+\tunsigned int i;\n+\tstruct commit_list * next;\n+\tstruct commit_list * work = NULL;\n+\tstruct commit * best = topological_order->item;\n+\tstruct bisect_by_cut_node * nodes;\n+\tstruct bisect_by_cut_node * next_node;\n+\tstruct commit_list counter;\n+\tunsigned int fittest, goal;\n+\n+\tcounter.next=NULL;\n+\t/* count the size of the topological order */\n+\tnext=topological_order;\n+\twhile (next) {\n+\t\tcount++;\n+\t\tnext = next->next;\n+\t}\n+\tfittest=count;\n+\ti=(count+1)/2;\n+\tgoal=count/2;\n+\t/* allocate and initialize the bisect_by_cut_node structure */\n+\tnext_node=nodes=xmalloc(sizeof(*nodes)*count);\n+\tmemset(nodes, 0, sizeof(*nodes)*count);\n+\t/* \n+\t * initialize the structures for all nodes of interest\n+\t */\n+\tnext=topological_order;\n+\tnext_node=nodes;\n+\twhile (next) {\t\t\n+\t\tnext->item->object.util=next_node++;\n+\t\tnext=next->next;\n+\t}\n+\t/*\n+\t * Mark half the nodes as being above the boundary.\n+\t * Mark nodes that aren't in the topological order as uninteresting.\n+\t * Initialize lists of visible children and parents.\n+\t */\n+\tnext=topological_order;\n+\tnext_node=nodes;\n+\twhile (next) {\t\t\n+\t\tstruct commit * next_item = next->item;\n+\t\tstruct commit_list * parents;\n+\t\t\n+\t\tif (i > 0) {\n+\t\t\tnext_node->flags |= ABOVE;\n+\t\t\ti--;\n+\t\t}\t\t\t\n+\t\tparents=next_item->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent = parents->item;\n+\t\t\tstruct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);\n+\n+\t\t\tif (pn) {\n+\t\t\t\tcommit_list_insert(next_item, &pn->children);\n+\t\t\t\tcommit_list_insert(parent, &next_node->visible_parents);\n+\t\t\t} else \n+\t\t\t\tparent->object.flags |= UNINTERESTING;\n+\t\t\tparent->object.flags &= ~COUNTED;\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t\tnext_node++;\n+\t}\n+\t/*\n+\t * Initialize the work queue with commits that are on the boundary\n+\t * and with <= the desired reachability.\n+\t * \n+\t * We know these commits have less than or equal to the desired \n+\t * reachability because by the definition of the topological order\n+\t * nodes can only reach nodes to the right of them in the topological\n+\t * order and by construction, there there are no more than \n+\t * (count-1)/2 nodes to the right of each node in the boundary.\n+\t */\n+\tnext=topological_order;\n+\tnext_node=nodes;\n+\twhile (next) {\n+\t\tstruct commit_list * parents;\n+\n+\t\tparents=next_node->visible_parents;\n+\t\twhile (parents) {\n+\t\t\tstruct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);\n+\n+\t\t\tif ((next_node->flags & ABOVE) \n+\t\t\t     && !(pn->flags & ABOVE) \n+\t\t\t     && (pn->count == 0)) {\n+\t\t\t\tcounter.item=parents->item;\n+\t\t\t\tpn->count = count_distance(&counter);\n+\t\t\t\tclear_distance(topological_order);\n+\t\t\t\tcommit_list_insert(parents->item, &work);\n+\t\t\t}\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t\tnext_node++;\n+\t}\n+\t/*\n+\t * Process the work queue until done.\n+\t */\n+\twhile (work) {\n+\t\tstruct commit * work_item = pop_commit(&work);\n+\t\tstruct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);\n+\t\tstruct commit_list * children = wn->children;\n+\t\tunsigned int goal_test = wn->count;\n+\t        unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);\n+\n+\t\tif (fitness < fittest) {\n+\t\t\tbest = work_item;\n+\t\t\tfittest = fitness;\n+\t\t}\n+#ifdef DEBUG\n+\t\tif (debug) {\n+\t\t\tprint_bisect_by_cut_node(work_item, \"work \");\n+\t\t}\n+#endif\n+\t\tif (goal_test < goal) {\n+\t\t\twhile (children) {\n+\t\t\t\tstruct bisect_by_cut_node * cn \n+\t\t\t\t\t= get_bisect_by_cut_node(children->item);\n+\t\t\t\tif (cn->flags & ABOVE) {\n+\t\t\t\t\t/* move the boundary up */\n+\t\t\t\t\tcn->flags &= ~ABOVE;\n+\t\t\t\t\tif (cn->visible_parents && !cn->visible_parents->next)\n+\t\t\t\t\t\t/* \n+\t\t\t\t\t\t * If the child only has one visible parent\n+\t\t\t\t\t\t * the goal_test increases by one\n+\t\t\t\t\t\t */\n+\t\t\t\t\t\tcn->count = wn->count+1;\n+\t\t\t\t\telse {\n+\t\t\t\t\t\t/*\n+\t\t\t\t\t\t * Otherwise, we need to count it explicitly.\n+\t\t\t\t\t\t */\n+\t\t\t\t\t\tcounter.item=children->item;\n+\t\t\t\t\t\tcn->count = count_distance(&counter);\n+\t\t\t\t\t\tclear_distance(topological_order);\n+\t\t\t\t\t}\n+\t\t\t\t\tcommit_list_insert(children->item, &work);\n+\t\t\t\t}\n+\t\t\t\tchildren=children->next;\n+\t\t\t}\n+\t\t} else if (goal_test > goal)\n+\t\t\tcontinue;\n+\t\telse \n+\t\t\tbreak; /* can't do better than this */\n+\t}\n+\tif (work)\n+\t\tfree_commit_list(work);\n+\t/*\n+\t * reset the util pointers.\n+\t */\n+\tnext=topological_order;\n+\twhile (next) {\n+\t\tnext->item->object.util=NULL;\n+\t\tnext = next->next;\n+\t}\n+\tfree(nodes);\n+\treturn best;\n+}\n+\n int main(int argc, char **argv)\n {\n \tstruct commit_list *list = NULL;\n@@ -440,6 +651,10 @@ int main(int argc, char **argv)\n \t\t\tshow_parents = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--bisect-by-cut\")) {\n+\t\t\tbisect_by_cut_option = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"--bisect\")) {\n \t\t\tbisect_list = 1;\n \t\t\tcontinue;\n@@ -458,7 +673,12 @@ int main(int argc, char **argv)\n \t\t\tshow_breaks = 1;\n \t\t\tcontinue;\n \t\t}\n-\n+#ifdef DEBUG\n+\t\tif (!strcmp(arg, \"--debug\")) {\n+\t\t\tdebug = 1;\n+\t\t\tcontinue;\n+\t\t}\n+#endif\n \t\tflags = 0;\n \t\tif (*arg == '^') {\n \t\t\tflags = UNINTERESTING;\n@@ -476,12 +696,20 @@ int main(int argc, char **argv)\n \tif (!merge_order) {\t\t\n \t        if (limited)\n \t\t\tlist = limit_list(list);\n-\t\tshow_commit_list(list);\n+\t\tif (!bisect_by_cut_option) \n+\t\t\tshow_commit_list(list);\n+\t\telse {\n+\t\t\tsort_in_topological_order(&list);\n+\t\t\tshow_commit(bisect_by_cut(list));\n+\t\t}\n \t} else {\n \t\tif (sort_list_in_merge_order(list, &process_commit)) {\n \t\t\t  die(\"merge order sort failed\\n\");\n \t\t}\n \t}\n-\n+#ifdef DEBUG\n+\tif (debug) \n+\t\tfprintf(stderr, \"complexity=%d\\n\", complexity);\n+#endif\n \treturn 0;\n }\n------------\n"},{"id":"5446","messageId":"2cfc4032050630020359c76147@mail.gmail.com","threadId":"1057","inReplyTo":"20050630081135.27577.qmail@blackcubes.dyndns.org","subject":"Re: [EXPERIMENTAL PATCH] O(n) bisection algorithm","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-30T09:03:51Z","receivedAt":"2005-06-30T09:03:51Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"BTW: just in case you are wondering what these variables are for and\nwhy they and the associated code is there...\n\n> +static struct commit_list * topological_order = NULL;\n> +static struct commit_list ** t_o_tail = &topological_order;\n\nThey are not required. This was a remnant of a previous version that\nused the --merge-order code to obtain the topological order. Of\ncourse, the final submission will remove this redundant code.\n\njon.\n"}]}