{"thread":{"id":"1081","subject":"[PATCH 4/8] This patch introduces a O(n) bisection algorithm to git.","startedAt":"2005-07-01T06:46:58Z","lastAt":"2005-07-01T06:46:58Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"5523","messageId":"20050701064658.5129.qmail@blackcubes.dyndns.org","threadId":"1081","inReplyTo":null,"subject":"[PATCH 4/8] This patch introduces a O(n) bisection algorithm to git.","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-07-01T06:46:58Z","receivedAt":"2005-07-01T06:46:58Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nFor the purposes of comparison, this patch:\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\nThe next patch in the series removes all the debug code.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\nThe Makefile is modified for one patch only to enable experimentation\nwith this patch. The next patch reverses the Makefile mods.\n---\n\n Makefile                   |    2 \n rev-list.c                 |  243 ++++++++++++++++++++++++++++++++++++++++++--\n t/t6002-rev-list-bisect.sh |    1 \n 3 files changed, 234 insertions(+), 12 deletions(-)\n\nf26b313fc06d18a0aa44b0d3113805bcde0c0c1f\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/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,11 @@ 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+#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@@ -90,13 +104,10 @@ static int process_commit(struct commit \n \tif (action == STOP) {\n \t\treturn STOP;\n \t}\n-\n \tif (action == CONTINUE) {\n \t\treturn CONTINUE;\n \t}\n-\n \tshow_commit(commit);\n-\n \treturn CONTINUE;\n }\n \n@@ -264,7 +275,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 +283,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 +417,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 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 +644,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 +666,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 +689,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 }\ndiff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh\n--- a/t/t6002-rev-list-bisect.sh\n+++ b/t/t6002-rev-list-bisect.sh\n@@ -241,6 +241,7 @@ EOF\n }\n \n test_sequence \"--bisect\"\n+test_sequence \"--bisect-by-cut\"\n \n #\n #\n------------\n"}]}