{"thread":{"id":"36504","subject":"[PATCH 2/2] Mention \"git blame\" improvements in release notes","startedAt":"2014-04-25T23:56:49Z","lastAt":"2014-04-28T20:26:45Z","messageCount":20,"participants":["David Kastrup","Shawn Pearce","Junio C Hamano","Ronnie Sahlberg"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"239733","messageId":"1398470210-28746-1-git-send-email-dak@gnu.org","threadId":"36504","inReplyTo":null,"subject":"[PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-25T23:56:49Z","receivedAt":"2014-04-25T23:56:49Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"The previous implementation used a single sorted linear list of blame\nentries for organizing all partial or completed work. Every subtask had\nto scan the whole list, with most entries not being relevant to the\ntask. The resulting run-time was quadratic to the number of separate\nchunks.\n\nThis change gives every subtask its own data to work with. Subtasks are\norganized into \"struct origin\" chains hanging off particular commits.\nCommits are organized into a priority queue, processing them in commit\ndate order in order to keep most of the work affecting a particular blob\ncollated even in the presence of an extensive merge history.\n\nFor large files with a diversified history, a speedup by a factor of 3\nor more is not unusual.\n\nSigned-off-by: David Kastrup \n---\n builtin/blame.c | 865 +++++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 567 insertions(+), 298 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex 88cb799..224f0ff 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1,7 +1,8 @@\n /*\n * Blame\n *\n- * Copyright (c) 2006, Junio C Hamano\n+ * Copyright (c) 2006, 2014 by its authors\n+ * See COPYING for licensing conditions\n */\n \n #include \"cache.h\"\n@@ -18,7 +19,9 @@\n #include \"cache-tree.h\"\n #include \"string-list.h\"\n #include \"mailmap.h\"\n+#include \"mergesort.h\"\n #include \"parse-options.h\"\n+#include \"prio-queue.h\"\n #include \"utf8.h\"\n #include \"userdiff.h\"\n #include \"line-range.h\"\n@@ -83,11 +86,42 @@ static unsigned blame_copy_score;\n */\n struct origin {\n \tint refcnt;\n+\t/* Record preceding blame record for this blob */\n \tstruct origin *previous;\n+\t/* origins are put in a list linked via `next' hanging off the\n+\t * corresponding commit's util field in order to make finding\n+\t * them fast. The presence in this chain does not count\n+\t * towards the origin's reference count. It is tempting to\n+\t * let it count as long as the commit is pending examination,\n+\t * but even under circumstances where the commit will be\n+\t * present multiple times in the priority queue of unexamined\n+\t * commits, processing the first instance will not leave any\n+\t * work requiring the origin data for the second instance. An\n+\t * interspersed commit changing that would have to be\n+\t * preexisting with a different ancestry and with the same\n+\t * commit date in order to wedge itself between two instances\n+\t * of the same commit in the priority queue _and_ produce\n+\t * blame entries relevant for it. While we don't want to let\n+\t * us get tripped up by this case, it certainly does not seem\n+\t * worth optimizing for.\n+\t */\n+\tstruct origin *next;\n \tstruct commit *commit;\n+\t/* `suspects' contains blame entries that may be attributed to\n+\t * this origin's commit or to parent commits. When a commit\n+\t * is being processed, all suspects will be moved, either by\n+\t * assigning them to an origin in a different commit, or by\n+\t * shipping them to the scoreboard's ent list because they\n+\t * cannot be attributed to a different commit.\n+\t */\n+\tstruct blame_entry *suspects;\n \tmmfile_t file;\n \tunsigned char blob_sha1[20];\n \tunsigned mode;\n+\t/* guilty gets set when shipping any suspects to the final\n+\t * blame list instead of other commits\n+\t */\n+\tchar guilty;\n \tchar path[FLEX_ARRAY];\n };\n \n@@ -176,10 +210,22 @@ static inline struct origin *origin_incref(struct origin *o)\n static void origin_decref(struct origin *o)\n {\n \tif (o && --o->refcnt <= 0) {\n+\t\tstruct origin *p, *l = NULL;\n \t\tif (o->previous)\n \t\t\torigin_decref(o->previous);\n \t\tfree(o->file.ptr);\n-\t\tfree(o);\n+\t\t/* Should be present exactly once in commit chain */\n+\t\tfor (p = o->commit->util; p; l = p, p = p->next) {\n+\t\t\tif (p == o) {\n+\t\t\t\tif (l)\n+\t\t\t\t\tl->next = p->next;\n+\t\t\t\telse\n+\t\t\t\t\to->commit->util = p->next;\n+\t\t\t\tfree(o);\n+\t\t\t\treturn;\n+\t\t\t}\n+\t\t}\n+\t\tdie(\"internal error in blame::origin_decref\");\n \t}\n }\n \n@@ -193,8 +239,12 @@ static void drop_origin_blob(struct origin *o)\n \n /*\n * Each group of lines is described by a blame_entry; it can be split\n- * as we pass blame to the parents. They form a linked list in the\n- * scoreboard structure, sorted by the target line number.\n+ * as we pass blame to the parents. They are arranged in linked lists\n+ * kept as `suspects' of some unprocessed origin, or entered (when the\n+ * blame origin has been finalized) into the scoreboard structure.\n+ * While the scoreboard structure is only sorted at the end of\n+ * processing (according to final image line number), the lists\n+ * attached to an origin are sorted by the target line number.\n */\n struct blame_entry {\n \tstruct blame_entry *next;\n@@ -210,15 +260,6 @@ struct blame_entry {\n \t/* the commit that introduced this group into the final image */\n \tstruct origin *suspect;\n \n-\t/* true if the suspect is truly guilty; false while we have not\n-\t * checked if the group came from one of its parents.\n-\t */\n-\tchar guilty;\n-\n-\t/* true if the entry has been scanned for copies in the current parent\n-\t */\n-\tchar scanned;\n-\n \t/* the line number of the first line of this group in the\n \t * suspect's file; internally all line numbers are 0 based.\n \t */\n@@ -231,11 +272,112 @@ struct blame_entry {\n };\n \n /*\n+ * Any merge of blames happens on lists of blames that arrived via\n+ * different parents in a single suspect. In this case, we want to\n+ * sort according to the suspect line numbers as opposed to the final\n+ * image line numbers. The function body is somewhat longish because\n+ * it avoids unnecessary writes.\n+ */\n+\n+static struct blame_entry *blame_merge(struct blame_entry *list1,\n+\t\t\t\t struct blame_entry *list2)\n+{\n+\tstruct blame_entry *p1 = list1, *p2 = list2,\n+\t\t**tail = &list1;\n+\n+\tif (!p1)\n+\t\treturn p2;\n+\tif (!p2)\n+\t\treturn p1;\n+\n+\tif (p1->s_lno <= p2->s_lno) {\n+\t\tdo {\n+\t\t\ttail = &p1->next;\n+\t\t\tif ((p1 = *tail) == NULL) {\n+\t\t\t\t*tail = p2;\n+\t\t\t\treturn list1;\n+\t\t\t}\n+\t\t} while (p1->s_lno <= p2->s_lno);\n+\t}\n+\tfor (;;) {\n+\t\t*tail = p2;\n+\t\tdo {\n+\t\t\ttail = &p2->next;\n+\t\t\tif ((p2 = *tail) == NULL) {\n+\t\t\t\t*tail = p1;\n+\t\t\t\treturn list1;\n+\t\t\t}\n+\t\t} while (p1->s_lno > p2->s_lno);\n+\t\t*tail = p1;\n+\t\tdo {\n+\t\t\ttail = &p1->next;\n+\t\t\tif ((p1 = *tail) == NULL) {\n+\t\t\t\t*tail = p2;\n+\t\t\t\treturn list1;\n+\t\t\t}\n+\t\t} while (p1->s_lno <= p2->s_lno);\n+\t}\n+}\n+\n+static void *get_next_blame(const void *p)\n+{\n+\treturn ((struct blame_entry *)p)->next;\n+}\n+\n+static void set_next_blame(void *p1, void *p2)\n+{\n+\t((struct blame_entry *)p1)->next = p2;\n+}\n+\n+/*\n+ * Final image line numbers are all different, so we don't need a\n+ * three-way comparison here.\n+ */\n+\n+static int compare_blame_final(const void *p1, const void *p2)\n+{\n+\treturn ((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno\n+\t\t? 1 : -1;\n+}\n+\n+static int compare_blame_suspect(const void *p1, const void *p2)\n+{\n+\tconst struct blame_entry *s1 = p1, *s2 = p2;\n+\t/*\n+\t * to allow for collating suspects, we sort according to the\n+\t * respective pointer value as the primary sorting criterion.\n+\t * The actual relation is pretty unimportant as long as it\n+\t * establishes a total order. Comparing as integers gives us\n+\t * that.\n+\t */\n+\tif (s1->suspect != s2->suspect)\n+\t\treturn (intptr_t)s1->suspect > (intptr_t)s2->suspect ? 1 : -1;\n+\tif (s1->s_lno == s2->s_lno)\n+\t\treturn 0;\n+\treturn s1->s_lno > s2->s_lno ? 1 : -1;\n+}\n+\n+static struct blame_entry *blame_sort(struct blame_entry *head,\n+\t\t\t\t int (*compare_fn)(const void *, const void *))\n+{\n+\treturn llist_mergesort (head, get_next_blame, set_next_blame, compare_fn);\n+}\n+\n+static int compare_commits_by_reverse_commit_date(const void *a,\n+\t\t\t\t\t\t const void *b,\n+\t\t\t\t\t\t void *c)\n+{\n+\treturn -compare_commits_by_commit_date(a, b, c);\n+}\n+\n+/*\n * The current state of the blame assignment.\n */\n struct scoreboard {\n \t/* the final commit (i.e. where we started digging from) */\n \tstruct commit *final;\n+\t/* Priority queue for commits with unassigned blame records */\n+\tstruct prio_queue commits;\n \tstruct rev_info *revs;\n \tconst char *path;\n \n@@ -268,7 +410,6 @@ static void coalesce(struct scoreboard *sb)\n \n \tfor (ent = sb->ent; ent && (next = ent->next); ent = next) {\n \t\tif (ent->suspect == next->suspect &&\n-\t\t ent->guilty == next->guilty &&\n \t\t ent->s_lno + ent->num_lines == next->s_lno) {\n \t\t\tent->num_lines += next->num_lines;\n \t\t\tent->next = next->next;\n@@ -284,6 +425,30 @@ static void coalesce(struct scoreboard *sb)\n }\n \n /*\n+ * Merge the given sorted list of blames into a preexisting origin.\n+ * If there were no previous blames to that commit, it is entered into\n+ * the commit priority queue of the score board.\n+ */\n+\n+static void queue_blames(struct scoreboard *sb, struct origin *porigin,\n+\t\t\t struct blame_entry *sorted)\n+{\n+\tif (porigin->suspects)\n+\t\tporigin->suspects = blame_merge(porigin->suspects, sorted);\n+\telse {\n+\t\tstruct origin *o;\n+\t\tfor (o = porigin->commit->util; o; o = o->next) {\n+\t\t\tif (o->suspects) {\n+\t\t\t\tporigin->suspects = sorted;\n+\t\t\t\treturn;\n+\t\t\t}\n+\t\t}\n+\t\tporigin->suspects = sorted;\n+\t\tprio_queue_put(&sb->commits, porigin->commit);\n+\t}\n+}\n+\n+/*\n * Given a commit and a path in it, create a new origin structure.\n * The callers that add blame to the scoreboard should use\n * get_origin() to obtain shared, refcounted copy instead of calling\n@@ -295,23 +460,32 @@ static struct origin *make_origin(struct commit *commit, const char *path)\n \to = xcalloc(1, sizeof(*o) + strlen(path) + 1);\n \to->commit = commit;\n \to->refcnt = 1;\n+\to->next = commit->util;\n+\tcommit->util = o;\n \tstrcpy(o->path, path);\n \treturn o;\n }\n \n /*\n * Locate an existing origin or create a new one.\n+ * This moves the origin to front position in the commit util list.\n */\n static struct origin *get_origin(struct scoreboard *sb,\n \t\t\t\t struct commit *commit,\n \t\t\t\t const char *path)\n {\n-\tstruct blame_entry *e;\n+\tstruct origin *o, *l;\n \n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->suspect->commit == commit &&\n-\t\t !strcmp(e->suspect->path, path))\n-\t\t\treturn origin_incref(e->suspect);\n+\tfor (o = commit->util, l = NULL; o; l = o, o = o->next) {\n+\t\tif (!strcmp(o->path, path)) {\n+\t\t\t/* bump to front */\n+\t\t\tif (l) {\n+\t\t\t\tl->next = o->next;\n+\t\t\t\to->next = commit->util;\n+\t\t\t\tcommit->util = o;\n+\t\t\t}\n+\t\t\treturn origin_incref(o);\n+\t\t}\n \t}\n \treturn make_origin(commit, path);\n }\n@@ -350,41 +524,19 @@ static struct origin *find_origin(struct scoreboard *sb,\n \t\t\t\t struct commit *parent,\n \t\t\t\t struct origin *origin)\n {\n-\tstruct origin *porigin = NULL;\n+\tstruct origin *porigin;\n \tstruct diff_options diff_opts;\n \tconst char *paths[2];\n \n-\tif (parent->util) {\n-\t\t/*\n-\t\t * Each commit object can cache one origin in that\n-\t\t * commit. This is a freestanding copy of origin and\n-\t\t * not refcounted.\n-\t\t */\n-\t\tstruct origin *cached = parent->util;\n-\t\tif (!strcmp(cached->path, origin->path)) {\n+\t/* First check any existing origins */\n+\tfor (porigin = parent->util; porigin; porigin = porigin->next)\n+\t\tif (!strcmp(porigin->path, origin->path)) {\n \t\t\t/*\n \t\t\t * The same path between origin and its parent\n \t\t\t * without renaming -- the most common case.\n \t\t\t */\n-\t\t\tporigin = get_origin(sb, parent, cached->path);\n-\n-\t\t\t/*\n-\t\t\t * If the origin was newly created (i.e. get_origin\n-\t\t\t * would call make_origin if none is found in the\n-\t\t\t * scoreboard), it does not know the blob_sha1/mode,\n-\t\t\t * so copy it. Otherwise porigin was in the\n-\t\t\t * scoreboard and already knows blob_sha1/mode.\n-\t\t\t */\n-\t\t\tif (porigin->refcnt == 1) {\n-\t\t\t\thashcpy(porigin->blob_sha1, cached->blob_sha1);\n-\t\t\t\tporigin->mode = cached->mode;\n-\t\t\t}\n-\t\t\treturn porigin;\n+\t\t\treturn origin_incref (porigin);\n \t\t}\n-\t\t/* otherwise it was not very useful; free it */\n-\t\tfree(parent->util);\n-\t\tparent->util = NULL;\n-\t}\n \n \t/* See if the origin->path is different between parent\n \t * and origin first. Most of the time they are the\n@@ -450,19 +602,6 @@ static struct origin *find_origin(struct scoreboard *sb,\n \t}\n \tdiff_flush(&diff_opts);\n \tfree_pathspec(&diff_opts.pathspec);\n-\tif (porigin) {\n-\t\t/*\n-\t\t * Create a freestanding copy that is not part of\n-\t\t * the refcounted origin found in the scoreboard, and\n-\t\t * cache it in the commit.\n-\t\t */\n-\t\tstruct origin *cached;\n-\n-\t\tcached = make_origin(porigin->commit, porigin->path);\n-\t\thashcpy(cached->blob_sha1, porigin->blob_sha1);\n-\t\tcached->mode = porigin->mode;\n-\t\tparent->util = cached;\n-\t}\n \treturn porigin;\n }\n \n@@ -509,46 +648,31 @@ static struct origin *find_rename(struct scoreboard *sb,\n }\n \n /*\n- * Link in a new blame entry to the scoreboard. Entries that cover the\n- * same line range have been removed from the scoreboard previously.\n+ * Append a new blame entry to a given output queue.\n */\n-static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n+static void add_blame_entry(struct blame_entry ***queue, struct blame_entry *e)\n {\n-\tstruct blame_entry *ent, *prev = NULL;\n-\n \torigin_incref(e->suspect);\n \n-\tfor (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)\n-\t\tprev = ent;\n-\n-\t/* prev, if not NULL, is the last one that is below e */\n-\n-\tif (prev) {\n-\t\te->next = prev->next;\n-\t\tprev->next = e;\n-\t}\n-\telse {\n-\t\te->next = sb->ent;\n-\t\tsb->ent = e;\n-\t}\n+\te->next = **queue;\n+\t**queue = e;\n+\t*queue = &e->next;\n }\n \n /*\n * src typically is on-stack; we want to copy the information in it to\n- * a malloced blame_entry that is already on the linked list of the\n- * scoreboard. The origin of dst loses a refcnt while the origin of src\n- * gains one.\n+ * a malloced blame_entry that gets added to the given queue. The\n+ * origin of dst loses a refcnt.\n */\n-static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n+static void dup_entry(struct blame_entry ***queue,\n+\t\t struct blame_entry *dst, struct blame_entry *src)\n {\n-\tstruct blame_entry *n;\n-\n-\tn = dst->next;\n \torigin_incref(src->suspect);\n \torigin_decref(dst->suspect);\n \tmemcpy(dst, src, sizeof(*src));\n-\tdst->next = n;\n-\tdst->score = 0;\n+\tdst->next = **queue;\n+\t**queue = dst;\n+\t*queue = &dst->next;\n }\n \n static const char *nth_line(struct scoreboard *sb, long lno)\n@@ -620,10 +744,11 @@ static void split_overlap(struct blame_entry *split,\n \n /*\n * split_overlap() divided an existing blame e into up to three parts\n- * in split. Adjust the linked list of blames in the scoreboard to\n+ * in split. Any assigned blame is moved to queue to\n * reflect the split.\n */\n-static void split_blame(struct scoreboard *sb,\n+static void split_blame(struct blame_entry ***blamed,\n+\t\t\tstruct blame_entry ***unblamed,\n \t\t\tstruct blame_entry *split,\n \t\t\tstruct blame_entry *e)\n {\n@@ -631,61 +756,39 @@ static void split_blame(struct scoreboard *sb,\n \n \tif (split[0].suspect && split[2].suspect) {\n \t\t/* The first part (reuse storage for the existing entry e) */\n-\t\tdup_entry(e, &split[0]);\n+\t\tdup_entry(unblamed, e, &split[0]);\n \n \t\t/* The last part -- me */\n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[2]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n+\t\tadd_blame_entry(unblamed, new_entry);\n \n \t\t/* ... and the middle part -- parent */\n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n+\t\tadd_blame_entry(blamed, new_entry);\n \t}\n \telse if (!split[0].suspect && !split[2].suspect)\n \t\t/*\n \t\t * The parent covers the entire area; reuse storage for\n \t\t * e and replace it with the parent.\n \t\t */\n-\t\tdup_entry(e, &split[1]);\n+\t\tdup_entry(blamed, e, &split[1]);\n \telse if (split[0].suspect) {\n \t\t/* me and then parent */\n-\t\tdup_entry(e, &split[0]);\n+\t\tdup_entry(unblamed, e, &split[0]);\n \n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n+\t\tadd_blame_entry(blamed, new_entry);\n \t}\n \telse {\n \t\t/* parent and then me */\n-\t\tdup_entry(e, &split[1]);\n+\t\tdup_entry(blamed, e, &split[1]);\n \n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[2]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n-\t}\n-\n-\tif (DEBUG) { /* sanity */\n-\t\tstruct blame_entry *ent;\n-\t\tint lno = sb->ent->lno, corrupt = 0;\n-\n-\t\tfor (ent = sb->ent; ent; ent = ent->next) {\n-\t\t\tif (lno != ent->lno)\n-\t\t\t\tcorrupt = 1;\n-\t\t\tif (ent->s_lno < 0)\n-\t\t\t\tcorrupt = 1;\n-\t\t\tlno += ent->num_lines;\n-\t\t}\n-\t\tif (corrupt) {\n-\t\t\tlno = sb->ent->lno;\n-\t\t\tfor (ent = sb->ent; ent; ent = ent->next) {\n-\t\t\t\tprintf(\"L %8d l %8d n %8d\\n\",\n-\t\t\t\t lno, ent->lno, ent->num_lines);\n-\t\t\t\tlno = ent->lno + ent->num_lines;\n-\t\t\t}\n-\t\t\tdie(\"oops\");\n-\t\t}\n+\t\tadd_blame_entry(unblamed, new_entry);\n \t}\n }\n \n@@ -702,74 +805,146 @@ static void decref_split(struct blame_entry *split)\n }\n \n /*\n- * Helper for blame_chunk(). blame_entry e is known to overlap with\n- * the patch hunk; split it and pass blame to the parent.\n+ * reverse_blame reverses the list given in head, appending tail.\n+ * That allows us to build lists in reverse order, then reverse them\n+ * afterwards. This can be faster than building the list in proper\n+ * order right away. The reason is that building in proper order\n+ * requires writing a link in the _previous_ element, while building\n+ * in reverse order just requires placing the list head into the\n+ * _current_ element.\n */\n-static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,\n-\t\t\t int tlno, int plno, int same,\n-\t\t\t struct origin *parent)\n-{\n-\tstruct blame_entry split[3];\n-\n-\tsplit_overlap(split, e, tlno, plno, same, parent);\n-\tif (split[1].suspect)\n-\t\tsplit_blame(sb, split, e);\n-\tdecref_split(split);\n-}\n \n-/*\n- * Find the line number of the last line the target is suspected for.\n- */\n-static int find_last_in_target(struct scoreboard *sb, struct origin *target)\n+static struct blame_entry *reverse_blame(struct blame_entry *head,\n+\t\t\t\t\t struct blame_entry *tail)\n {\n-\tstruct blame_entry *e;\n-\tint last_in_target = -1;\n-\n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || e->suspect != target)\n-\t\t\tcontinue;\n-\t\tif (last_in_target < e->s_lno + e->num_lines)\n-\t\t\tlast_in_target = e->s_lno + e->num_lines;\n+\twhile (head) {\n+\t\tstruct blame_entry *next = head->next;\n+\t\thead->next = tail;\n+\t\ttail = head;\n+\t\thead = next;\n \t}\n-\treturn last_in_target;\n+\treturn tail;\n }\n \n /*\n * Process one hunk from the patch between the current suspect for\n- * blame_entry e and its parent. Find and split the overlap, and\n- * pass blame to the overlapping part to the parent.\n+ * blame_entry e and its parent. This first blames any unfinished\n+ * entries before the chunk (which is where target and parent start\n+ * differing) on the parent, and then splits blame entries at the\n+ * start and at the end of the difference region. Since use of -M and\n+ * -C options may lead to overlapping/duplicate source line number\n+ * ranges, all we can rely on from sorting/merging is the order of the\n+ * first suspect line number.\n */\n-static void blame_chunk(struct scoreboard *sb,\n-\t\t\tint tlno, int plno, int same,\n-\t\t\tstruct origin *target, struct origin *parent)\n+static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,\n+\t\t\tint tlno, int offset, int same,\n+\t\t\tstruct origin *parent)\n {\n-\tstruct blame_entry *e;\n+\tstruct blame_entry *e = **srcq;\n+\tstruct blame_entry *samep = NULL, *diffp = NULL;\n \n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || e->suspect != target)\n-\t\t\tcontinue;\n-\t\tif (same <= e->s_lno)\n-\t\t\tcontinue;\n-\t\tif (tlno < e->s_lno + e->num_lines)\n-\t\t\tblame_overlap(sb, e, tlno, plno, same, parent);\n+\twhile (e && e->s_lno < tlno) {\n+\t\tstruct blame_entry *next = e->next;\n+\t\t/*\n+\t\t * current record starts before differing portion. If\n+\t\t * it reaches into it, we need to split it up and\n+\t\t * examine the second part separately.\n+\t\t */\n+\t\tif (e->s_lno + e->num_lines > tlno) {\n+\t\t\t/* Move second half to a new record */\n+\t\t\tint len = tlno - e->s_lno;\n+\t\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n+\t\t\tn->suspect = e->suspect;\n+\t\t\tn->lno = e->lno + len;\n+\t\t\tn->s_lno = e->s_lno + len;\n+\t\t\tn->num_lines = e->num_lines - len;\n+\t\t\te->num_lines = len;\n+\t\t\te->score = 0;\n+\t\t\t/* Push new record to diffp */\n+\t\t\tn->next = diffp;\n+\t\t\tdiffp = n;\n+\t\t} else\n+\t\t\torigin_decref(e->suspect);\n+\t\t/* Pass blame for everything before the differing\n+\t\t * chunk to the parent */\n+\t\te->suspect = origin_incref(parent);\n+\t\te->s_lno += offset;\n+\t\te->next = samep;\n+\t\tsamep = e;\n+\t\te = next;\n+\t}\n+\t/*\n+\t * As we don't know how much of a common stretch after this\n+\t * diff will occur, the currently blamed parts are all that we\n+\t * can assign to the parent for now.\n+\t */\n+\n+\tif (samep) {\n+\t\t**dstq = reverse_blame(samep, **dstq);\n+\t\t*dstq = &samep->next;\n \t}\n+\t/*\n+\t * Prepend the split off portions: everything after e starts\n+\t * after the blameable portion.\n+\t */\n+\te = reverse_blame(diffp, e);\n+\n+\t/*\n+\t * Now retain records on the target while parts are different\n+\t * from the parent.\n+\t */\n+\tsamep = NULL;\n+\tdiffp = NULL;\n+\twhile (e && e->s_lno < same) {\n+\t\tstruct blame_entry *next = e->next;\n+\n+\t\t/*\n+\t\t * If current record extends into sameness, need to split.\n+\t\t */\n+\t\tif (e->s_lno + e->num_lines > same) {\n+\t\t\t/*\n+\t\t\t * Move second half to a new record to be\n+\t\t\t * processed by later chunks\n+\t\t\t */\n+\t\t\tint len = same - e->s_lno;\n+\t\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n+\t\t\tn->suspect = origin_incref(e->suspect);\n+\t\t\tn->lno = e->lno + len;\n+\t\t\tn->s_lno = e->s_lno + len;\n+\t\t\tn->num_lines = e->num_lines - len;\n+\t\t\te->num_lines = len;\n+\t\t\te->score = 0;\n+\t\t\t/* Push new record to samep */\n+\t\t\tn->next = samep;\n+\t\t\tsamep = n;\n+\t\t}\n+\t\te->next = diffp;\n+\t\tdiffp = e;\n+\t\te = next;\n+\t}\n+\t**srcq = reverse_blame(diffp, reverse_blame(samep, e));\n+\t/* Move across elements that are in the unblamable portion */\n+\tif (diffp)\n+\t\t*srcq = &diffp->next;\n }\n \n struct blame_chunk_cb_data {\n-\tstruct scoreboard *sb;\n-\tstruct origin *target;\n \tstruct origin *parent;\n-\tlong plno;\n-\tlong tlno;\n+\tlong offset;\n+\tstruct blame_entry **dstq;\n+\tstruct blame_entry **srcq;\n };\n \n+/* diff chunks are from parent to target */\n static int blame_chunk_cb(long start_a, long count_a,\n \t\t\t long start_b, long count_b, void *data)\n {\n \tstruct blame_chunk_cb_data *d = data;\n-\tblame_chunk(d->sb, d->tlno, d->plno, start_b, d->target, d->parent);\n-\td->plno = start_a + count_a;\n-\td->tlno = start_b + count_b;\n+\tif (start_a - start_b != d->offset)\n+\t\tdie(\"internal error in blame::blame_chunk_cb\");\n+\tblame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b,\n+\t\t start_b + count_b, d->parent);\n+\td->offset = start_a + count_a - (start_b + count_b);\n \treturn 0;\n }\n \n@@ -778,29 +953,32 @@ static int blame_chunk_cb(long start_a, long count_a,\n * for the lines it is suspected to its parent. Run diff to find\n * which lines came from parent and pass blame for them.\n */\n-static int pass_blame_to_parent(struct scoreboard *sb,\n-\t\t\t\tstruct origin *target,\n-\t\t\t\tstruct origin *parent)\n+static void pass_blame_to_parent(struct scoreboard *sb,\n+\t\t\t\t struct origin *target,\n+\t\t\t\t struct origin *parent)\n {\n-\tint last_in_target;\n \tmmfile_t file_p, file_o;\n \tstruct blame_chunk_cb_data d;\n+\tstruct blame_entry *newdest = NULL;\n \n-\tmemset(&d, 0, sizeof(d));\n-\td.sb = sb; d.target = target; d.parent = parent;\n-\tlast_in_target = find_last_in_target(sb, target);\n-\tif (last_in_target < 0)\n-\t\treturn 1; /* nothing remains for this target */\n+\tif (!target->suspects)\n+\t\treturn; /* nothing remains for this target */\n+\n+\td.parent = parent;\n+\td.offset = 0;\n+\td.dstq = &newdest; d.srcq = &target->suspects;\n \n \tfill_origin_blob(&sb->revs->diffopt, parent, &file_p);\n \tfill_origin_blob(&sb->revs->diffopt, target, &file_o);\n \tnum_get_patch++;\n \n \tdiff_hunks(&file_p, &file_o, 0, blame_chunk_cb, &d);\n-\t/* The rest (i.e. anything after tlno) are the same as the parent */\n-\tblame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);\n+\t/* The rest are the same as the parent */\n+\tblame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, parent);\n+\t*d.dstq = NULL;\n+\tqueue_blames(sb, parent, newdest);\n \n-\treturn 0;\n+\treturn;\n }\n \n /*\n@@ -945,43 +1123,80 @@ static void find_copy_in_blob(struct scoreboard *sb,\n \thandle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);\n }\n \n+/* Move all blame entries from list *source that have a score smaller\n+ * than score_min to the front of list *small.\n+ * Returns a pointer to the link pointing to the old head of the small list.\n+ */\n+\n+static struct blame_entry **filter_small(struct scoreboard *sb,\n+\t\t\t\t\t struct blame_entry **small,\n+\t\t\t\t\t struct blame_entry **source,\n+\t\t\t\t\t unsigned score_min)\n+{\n+\tstruct blame_entry *p = *source;\n+\tstruct blame_entry *oldsmall = *small;\n+\twhile (p) {\n+\t\tif (ent_score(sb, p) <= score_min) {\n+\t\t\t*small = p;\n+\t\t\tsmall = &p->next;\n+\t\t\tp = *small;\n+\t\t} else {\n+\t\t\t*source = p;\n+\t\t\tsource = &p->next;\n+\t\t\tp = *source;\n+\t\t}\n+\t}\n+\t*small = oldsmall;\n+\t*source = NULL;\n+\treturn small;\n+}\n+\n /*\n * See if lines currently target is suspected for can be attributed to\n * parent.\n */\n-static int find_move_in_parent(struct scoreboard *sb,\n-\t\t\t struct origin *target,\n-\t\t\t struct origin *parent)\n+static void find_move_in_parent(struct scoreboard *sb,\n+\t\t\t\tstruct blame_entry ***blamed,\n+\t\t\t\tstruct blame_entry **toosmall,\n+\t\t\t\tstruct origin *target,\n+\t\t\t\tstruct origin *parent)\n {\n-\tint last_in_target, made_progress;\n \tstruct blame_entry *e, split[3];\n+\tstruct blame_entry *unblamed = target->suspects;\n+\tstruct blame_entry *leftover = NULL;\n \tmmfile_t file_p;\n \n-\tlast_in_target = find_last_in_target(sb, target);\n-\tif (last_in_target < 0)\n-\t\treturn 1; /* nothing remains for this target */\n+\tif (!unblamed)\n+\t\treturn; /* nothing remains for this target */\n \n \tfill_origin_blob(&sb->revs->diffopt, parent, &file_p);\n \tif (!file_p.ptr)\n-\t\treturn 0;\n+\t\treturn;\n \n-\tmade_progress = 1;\n-\twhile (made_progress) {\n-\t\tmade_progress = 0;\n-\t\tfor (e = sb->ent; e; e = e->next) {\n-\t\t\tif (e->guilty || e->suspect != target ||\n-\t\t\t ent_score(sb, e) < blame_move_score)\n-\t\t\t\tcontinue;\n+\t/* At each iteration, unblamed has a NULL-terminated list of\n+\t * entries that have not yet been tested for blame. leftover\n+\t * contains the reversed list of entries that have been tested\n+\t * without being assignable to the parent.\n+\t */\n+\tdo {\n+\t\tstruct blame_entry **unblamedtail = &unblamed;\n+\t\tstruct blame_entry *next;\n+\t\tfor (e = unblamed; e; e = next) {\n+\t\t\tnext = e->next;\n \t\t\tfind_copy_in_blob(sb, e, parent, split, &file_p);\n \t\t\tif (split[1].suspect &&\n \t\t\t blame_move_score < ent_score(sb, &split[1])) {\n-\t\t\t\tsplit_blame(sb, split, e);\n-\t\t\t\tmade_progress = 1;\n+\t\t\t\tsplit_blame(blamed, &unblamedtail, split, e);\n+\t\t\t} else {\n+\t\t\t\te->next = leftover;\n+\t\t\t\tleftover = e;\n \t\t\t}\n \t\t\tdecref_split(split);\n \t\t}\n-\t}\n-\treturn 0;\n+\t\t*unblamedtail = NULL;\n+\t\ttoosmall = filter_small(sb, toosmall, &unblamed, blame_move_score);\n+\t} while (unblamed);\n+\ttarget->suspects = reverse_blame(leftover, NULL);\n }\n \n struct blame_list {\n@@ -993,62 +1208,46 @@ struct blame_list {\n * Count the number of entries the target is suspected for,\n * and prepare a list of entry and the best split.\n */\n-static struct blame_list *setup_blame_list(struct scoreboard *sb,\n-\t\t\t\t\t struct origin *target,\n-\t\t\t\t\t int min_score,\n+static struct blame_list *setup_blame_list(struct blame_entry *unblamed,\n \t\t\t\t\t int *num_ents_p)\n {\n \tstruct blame_entry *e;\n \tint num_ents, i;\n \tstruct blame_list *blame_list = NULL;\n \n-\tfor (e = sb->ent, num_ents = 0; e; e = e->next)\n-\t\tif (!e->scanned && !e->guilty &&\n-\t\t e->suspect == target &&\n-\t\t min_score < ent_score(sb, e))\n-\t\t\tnum_ents++;\n+\tfor (e = unblamed, num_ents = 0; e; e = e->next)\n+\t\tnum_ents++;\n \tif (num_ents) {\n \t\tblame_list = xcalloc(num_ents, sizeof(struct blame_list));\n-\t\tfor (e = sb->ent, i = 0; e; e = e->next)\n-\t\t\tif (!e->scanned && !e->guilty &&\n-\t\t\t e->suspect == target &&\n-\t\t\t min_score < ent_score(sb, e))\n-\t\t\t\tblame_list[i++].ent = e;\n+\t\tfor (e = unblamed, i = 0; e; e = e->next)\n+\t\t\tblame_list[i++].ent = e;\n \t}\n \t*num_ents_p = num_ents;\n \treturn blame_list;\n }\n \n /*\n- * Reset the scanned status on all entries.\n- */\n-static void reset_scanned_flag(struct scoreboard *sb)\n-{\n-\tstruct blame_entry *e;\n-\tfor (e = sb->ent; e; e = e->next)\n-\t\te->scanned = 0;\n-}\n-\n-/*\n * For lines target is suspected for, see if we can find code movement\n * across file boundary from the parent commit. porigin is the path\n * in the parent we already tried.\n */\n-static int find_copy_in_parent(struct scoreboard *sb,\n-\t\t\t struct origin *target,\n-\t\t\t struct commit *parent,\n-\t\t\t struct origin *porigin,\n-\t\t\t int opt)\n+static void find_copy_in_parent(struct scoreboard *sb,\n+\t\t\t\tstruct blame_entry ***blamed,\n+\t\t\t\tstruct blame_entry **toosmall,\n+\t\t\t\tstruct origin *target,\n+\t\t\t\tstruct commit *parent,\n+\t\t\t\tstruct origin *porigin,\n+\t\t\t\tint opt)\n {\n \tstruct diff_options diff_opts;\n \tint i, j;\n-\tint retval;\n \tstruct blame_list *blame_list;\n \tint num_ents;\n+\tstruct blame_entry *unblamed = target->suspects;\n+\tstruct blame_entry *leftover = NULL;\n \n-\tblame_list = setup_blame_list(sb, target, blame_copy_score, &num_ents);\n-\tif (!blame_list)\n-\t\treturn 1; /* nothing remains for this target */\n+\tif (!unblamed)\n+\t\treturn; /* nothing remains for this target */\n \n \tdiff_setup(&diff_opts);\n \tDIFF_OPT_SET(&diff_opts, RECURSIVE);\n@@ -1078,9 +1277,9 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \tif (!DIFF_OPT_TST(&diff_opts, FIND_COPIES_HARDER))\n \t\tdiffcore_std(&diff_opts);\n \n-\tretval = 0;\n-\twhile (1) {\n-\t\tint made_progress = 0;\n+\tdo {\n+\t\tstruct blame_entry **unblamedtail = &unblamed;\n+\t\tblame_list = setup_blame_list(unblamed, &num_ents);\n \n \t\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n \t\t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n@@ -1117,27 +1316,21 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \t\t\tstruct blame_entry *split = blame_list[j].split;\n \t\t\tif (split[1].suspect &&\n \t\t\t blame_copy_score < ent_score(sb, &split[1])) {\n-\t\t\t\tsplit_blame(sb, split, blame_list[j].ent);\n-\t\t\t\tmade_progress = 1;\n+\t\t\t\tsplit_blame(blamed, &unblamedtail, split,\n+\t\t\t\t\t blame_list[j].ent);\n+\t\t\t} else {\n+\t\t\t\tblame_list[j].ent->next = leftover;\n+\t\t\t\tleftover = blame_list[j].ent;\n \t\t\t}\n-\t\t\telse\n-\t\t\t\tblame_list[j].ent->scanned = 1;\n \t\t\tdecref_split(split);\n \t\t}\n \t\tfree(blame_list);\n-\n-\t\tif (!made_progress)\n-\t\t\tbreak;\n-\t\tblame_list = setup_blame_list(sb, target, blame_copy_score, &num_ents);\n-\t\tif (!blame_list) {\n-\t\t\tretval = 1;\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\treset_scanned_flag(sb);\n+\t\t*unblamedtail = NULL;\n+\t\ttoosmall = filter_small(sb, toosmall, &unblamed, blame_copy_score);\n+\t} while (unblamed);\n+\ttarget->suspects = reverse_blame(leftover, NULL);\n \tdiff_flush(&diff_opts);\n \tfree_pathspec(&diff_opts.pathspec);\n-\treturn retval;\n }\n \n /*\n@@ -1147,20 +1340,21 @@ static int find_copy_in_parent(struct scoreboard *sb,\n static void pass_whole_blame(struct scoreboard *sb,\n \t\t\t struct origin *origin, struct origin *porigin)\n {\n-\tstruct blame_entry *e;\n+\tstruct blame_entry *e, *suspects;\n \n \tif (!porigin->file.ptr && origin->file.ptr) {\n \t\t/* Steal its file */\n \t\tporigin->file = origin->file;\n \t\torigin->file.ptr = NULL;\n \t}\n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->suspect != origin)\n-\t\t\tcontinue;\n+\tsuspects = origin->suspects;\n+\torigin->suspects = NULL;\n+\tfor (e = suspects; e; e = e->next) {\n \t\torigin_incref(porigin);\n \t\torigin_decref(e->suspect);\n \t\te->suspect = porigin;\n \t}\n+\tqueue_blames(sb, porigin, suspects);\n }\n \n /*\n@@ -1184,6 +1378,27 @@ static int num_scapegoats(struct rev_info *revs, struct commit *commit)\n \treturn cnt;\n }\n \n+/* Distribute collected unsorted blames to the respected sorted lists\n+ * in the various origins.\n+ */\n+static void distribute_blame(struct scoreboard *sb, struct blame_entry *blamed)\n+{\n+\tblamed = blame_sort(blamed, compare_blame_suspect);\n+\twhile (blamed)\n+\t{\n+\t\tstruct origin *porigin = blamed->suspect;\n+\t\tstruct blame_entry *suspects = NULL;\n+\t\tdo {\n+\t\t\tstruct blame_entry *next = blamed->next;\n+\t\t\tblamed->next = suspects;\n+\t\t\tsuspects = blamed;\n+\t\t\tblamed = next;\n+\t\t} while (blamed && blamed->suspect == porigin);\n+\t\tsuspects = reverse_blame(suspects, NULL);\n+\t\tqueue_blames(sb, porigin, suspects);\n+\t}\n+}\n+\n #define MAXSG 16\n \n static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n@@ -1194,6 +1409,8 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n \tstruct commit_list *sg;\n \tstruct origin *sg_buf[MAXSG];\n \tstruct origin *porigin, **sg_origin = sg_buf;\n+\tstruct blame_entry *toosmall = NULL;\n+\tstruct blame_entry *blames, **blametail = &blames;\n \n \tnum_sg = num_scapegoats(revs, commit);\n \tif (!num_sg)\n@@ -1255,38 +1472,71 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n \t\t\torigin_incref(porigin);\n \t\t\torigin->previous = porigin;\n \t\t}\n-\t\tif (pass_blame_to_parent(sb, origin, porigin))\n+\t\tpass_blame_to_parent(sb, origin, porigin);\n+\t\tif (!origin->suspects)\n \t\t\tgoto finish;\n \t}\n \n \t/*\n \t * Optionally find moves in parents' files.\n \t */\n-\tif (opt & PICKAXE_BLAME_MOVE)\n-\t\tfor (i = 0, sg = first_scapegoat(revs, commit);\n-\t\t i < num_sg && sg;\n-\t\t sg = sg->next, i++) {\n-\t\t\tstruct origin *porigin = sg_origin[i];\n-\t\t\tif (!porigin)\n-\t\t\t\tcontinue;\n-\t\t\tif (find_move_in_parent(sb, origin, porigin))\n-\t\t\t\tgoto finish;\n+\tif (opt & PICKAXE_BLAME_MOVE) {\n+\t\tfilter_small(sb, &toosmall, &origin->suspects, blame_move_score);\n+\t\tif (origin->suspects) {\n+\t\t\tfor (i = 0, sg = first_scapegoat(revs, commit);\n+\t\t\t i < num_sg && sg;\n+\t\t\t sg = sg->next, i++) {\n+\t\t\t\tstruct origin *porigin = sg_origin[i];\n+\t\t\t\tif (!porigin)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tfind_move_in_parent(sb, &blametail, &toosmall, origin, porigin);\n+\t\t\t\tif (!origin->suspects)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n \t\t}\n+\t}\n \n \t/*\n \t * Optionally find copies from parents' files.\n \t */\n-\tif (opt & PICKAXE_BLAME_COPY)\n+\tif (opt & PICKAXE_BLAME_COPY) {\n+\t\tif (blame_copy_score > blame_move_score)\n+\t\t\tfilter_small(sb, &toosmall, &origin->suspects, blame_copy_score);\n+\t\telse if (blame_copy_score < blame_move_score) {\n+\t\t\torigin->suspects = blame_merge(origin->suspects, toosmall);\n+\t\t\ttoosmall = NULL;\n+\t\t\tfilter_small(sb, &toosmall, &origin->suspects, blame_copy_score);\n+\t\t}\n+\t\tif (!origin->suspects)\n+\t\t\tgoto finish;\n+\n \t\tfor (i = 0, sg = first_scapegoat(revs, commit);\n \t\t i < num_sg && sg;\n \t\t sg = sg->next, i++) {\n \t\t\tstruct origin *porigin = sg_origin[i];\n-\t\t\tif (find_copy_in_parent(sb, origin, sg->item,\n-\t\t\t\t\t\tporigin, opt))\n+\t\t\tfind_copy_in_parent(sb, &blametail, &toosmall,\n+\t\t\t\t\t origin, sg->item, porigin, opt);\n+\t\t\tif (!origin->suspects)\n \t\t\t\tgoto finish;\n \t\t}\n+\t}\n \n- finish:\n+finish:\n+\t*blametail = NULL;\n+\tdistribute_blame(sb, blames);\n+\t/*\n+\t * prepend toosmall to origin->suspects\n+\t *\n+\t * There is no point in sorting: this ends up on a big\n+\t * unsorted list in the caller anyway.\n+\t */\n+\tif (toosmall) {\n+\t\tstruct blame_entry **tail = &toosmall;\n+\t\twhile (*tail)\n+\t\t\ttail = &(*tail)->next;\n+\t\t*tail = origin->suspects;\n+\t\torigin->suspects = toosmall;\n+\t}\n \tfor (i = 0; i < num_sg; i++) {\n \t\tif (sg_origin[i]) {\n \t\t\tdrop_origin_blob(sg_origin[i]);\n@@ -1481,14 +1731,11 @@ static int emit_one_suspect_detail(struct origin *suspect, int repeat)\n }\n \n /*\n- * The blame_entry is found to be guilty for the range. Mark it\n- * as such, and show it in incremental output.\n+ * The blame_entry is found to be guilty for the range.\n+ * Show it in incremental output.\n */\n static void found_guilty_entry(struct blame_entry *ent)\n {\n-\tif (ent->guilty)\n-\t\treturn;\n-\tent->guilty = 1;\n \tif (incremental) {\n \t\tstruct origin *suspect = ent->suspect;\n \n@@ -1502,32 +1749,34 @@ static void found_guilty_entry(struct blame_entry *ent)\n }\n \n /*\n- * The main loop -- while the scoreboard has lines whose true origin\n- * is still unknown, pick one blame_entry, and allow its current\n- * suspect to pass blames to its parents.\n- */\n+ * The main loop -- while we have blobs with lines whose true origin\n+ * is still unknown, pick one blob, and allow its lines to pass blames\n+ * to its parents. */\n static void assign_blame(struct scoreboard *sb, int opt)\n {\n \tstruct rev_info *revs = sb->revs;\n+\tstruct commit *commit = prio_queue_get(&sb->commits);\n \n-\twhile (1) {\n+\twhile (commit) {\n \t\tstruct blame_entry *ent;\n-\t\tstruct commit *commit;\n-\t\tstruct origin *suspect = NULL;\n+\t\tstruct origin *suspect = commit->util;\n \n \t\t/* find one suspect to break down */\n-\t\tfor (ent = sb->ent; !suspect && ent; ent = ent->next)\n-\t\t\tif (!ent->guilty)\n-\t\t\t\tsuspect = ent->suspect;\n-\t\tif (!suspect)\n-\t\t\treturn; /* all done */\n+\t\twhile (suspect && !suspect->suspects)\n+\t\t\tsuspect = suspect->next;\n+\n+\t\tif (!suspect) {\n+\t\t\tcommit = prio_queue_get(&sb->commits);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tassert(commit == suspect->commit);\n \n \t\t/*\n \t\t * We will use this suspect later in the loop,\n \t\t * so hold onto it in the meantime.\n \t\t */\n \t\torigin_incref(suspect);\n-\t\tcommit = suspect->commit;\n \t\tparse_commit(commit);\n \t\tif (reverse ||\n \t\t (!(commit->object.flags & UNINTERESTING) &&\n@@ -1543,9 +1792,22 @@ static void assign_blame(struct scoreboard *sb, int opt)\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \n \t\t/* Take responsibility for the remaining entries */\n-\t\tfor (ent = sb->ent; ent; ent = ent->next)\n-\t\t\tif (ent->suspect == suspect)\n+\t\tent = suspect->suspects;\n+\t\tif (ent) {\n+\t\t\tsuspect->guilty = 1;\n+\t\t\tfor (;;) {\n+\t\t\t\tstruct blame_entry *next = ent->next;\n \t\t\t\tfound_guilty_entry(ent);\n+\t\t\t\tif (next) {\n+\t\t\t\t\tent = next;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\tent->next = sb->ent;\n+\t\t\t\tsb->ent = suspect->suspects;\n+\t\t\t\tsuspect->suspects = NULL;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n \t\torigin_decref(suspect);\n \n \t\tif (DEBUG) /* sanity */\n@@ -1602,9 +1864,8 @@ static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent,\n \tchar hex[41];\n \n \tstrcpy(hex, sha1_to_hex(suspect->commit->object.sha1));\n-\tprintf(\"%s%c%d %d %d\\n\",\n+\tprintf(\"%s %d %d %d\\n\",\n \t hex,\n-\t ent->guilty ? ' ' : '*', /* purely for debugging */\n \t ent->s_lno + 1,\n \t ent->lno + 1,\n \t ent->num_lines);\n@@ -1717,17 +1978,16 @@ static void output(struct scoreboard *sb, int option)\n \n \tif (option & OUTPUT_PORCELAIN) {\n \t\tfor (ent = sb->ent; ent; ent = ent->next) {\n-\t\t\tstruct blame_entry *oth;\n-\t\t\tstruct origin *suspect = ent->suspect;\n-\t\t\tstruct commit *commit = suspect->commit;\n+\t\t\tint count = 0;\n+\t\t\tstruct origin *suspect;\n+\t\t\tstruct commit *commit = ent->suspect->commit;\n \t\t\tif (commit->object.flags & MORE_THAN_ONE_PATH)\n \t\t\t\tcontinue;\n-\t\t\tfor (oth = ent->next; oth; oth = oth->next) {\n-\t\t\t\tif ((oth->suspect->commit != commit) ||\n-\t\t\t\t !strcmp(oth->suspect->path, suspect->path))\n-\t\t\t\t\tcontinue;\n-\t\t\t\tcommit->object.flags |= MORE_THAN_ONE_PATH;\n-\t\t\t\tbreak;\n+\t\t\tfor (suspect = commit->util; suspect; suspect = suspect->next) {\n+\t\t\t\tif (suspect->guilty && count++) {\n+\t\t\t\t\tcommit->object.flags |= MORE_THAN_ONE_PATH;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n@@ -2092,7 +2352,6 @@ static struct commit *fake_working_tree_commit(struct diff_options *opt,\n \torigin->file.ptr = buf.buf;\n \torigin->file.size = buf.len;\n \tpretend_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_sha1);\n-\tcommit->util = origin;\n \n \t/*\n \t * Read the current index, replace the path entry with\n@@ -2403,12 +2662,16 @@ parse_done:\n \tmemset(&sb, 0, sizeof(sb));\n \n \tsb.revs = &revs;\n-\tif (!reverse)\n+\tif (!reverse) {\n \t\tfinal_commit_name = prepare_final(&sb);\n+\t\tsb.commits.compare = compare_commits_by_commit_date;\n+\t}\n \telse if (contents_from)\n \t\tdie(\"--contents and --children do not blend well.\");\n-\telse\n+\telse {\n \t\tfinal_commit_name = prepare_initial(&sb);\n+\t\tsb.commits.compare = compare_commits_by_reverse_commit_date;\n+\t}\n \n \tif (!sb.final) {\n \t\t/*\n@@ -2497,12 +2760,16 @@ parse_done:\n \t\tent->next = next;\n \t\torigin_incref(o);\n \t}\n+\n+\to->suspects = ent;\n+\tprio_queue_put(&sb.commits, o->commit);\n+\n \torigin_decref(o);\n \n \trange_set_release(&ranges);\n \tstring_list_clear(&range_list, 0);\n \n-\tsb.ent = ent;\n+\tsb.ent = NULL;\n \tsb.path = path;\n \n \tread_mailmap(&mailmap, NULL);\n@@ -2515,6 +2782,8 @@ parse_done:\n \tif (incremental)\n \t\treturn 0;\n \n+\tsb.ent = blame_sort(sb.ent, compare_blame_final);\n+\n \tcoalesce(&sb);\n \n \tif (!(output_option & OUTPUT_PORCELAIN))\n-- \n1.9.1\n"},{"id":"239732","messageId":"1398470210-28746-2-git-send-email-dak@gnu.org","threadId":"36504","inReplyTo":"1398470210-28746-1-git-send-email-dak@gnu.org","subject":"[PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-25T23:56:50Z","receivedAt":"2014-04-25T23:56:50Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Includes reasonably tasteful begging.\n\nSigned-off-by: David Kastrup \n---\n Documentation/RelNotes/2.0.0.txt | 6 ++++++\n 1 file changed, 6 insertions(+)\n\ndiff --git a/Documentation/RelNotes/2.0.0.txt b/Documentation/RelNotes/2.0.0.txt\nindex ffd4899..27b23c3 100644\n--- a/Documentation/RelNotes/2.0.0.txt\n+++ b/Documentation/RelNotes/2.0.0.txt\n@@ -144,6 +144,12 @@ UI, Workflows & Features\n \n Performance, Internal Implementation, etc.\n \n+ * Significant parts of \"git blame\" have been reimplemented by David\n+ Kastrup for a vast gain in performance with complex\n+ histories and large files. As working on free software is his sole\n+ source of income, please consider contributing to his remuneration\n+ if you find this useful.\n+\n * The compilation options to port to AIX and to MSVC have been\n updated.\n \n-- \n1.9.1\n"},{"id":"239734","messageId":"CAJo=hJukmej1rJXuVoECwd7AxmSue8Wmv4rBmCHEYcWBWNarSw@mail.gmail.com","threadId":"36504","inReplyTo":"1398470210-28746-1-git-send-email-dak@gnu.org","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-04-26T00:53:31Z","receivedAt":"2014-04-26T00:53:31Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Apr 25, 2014 at 4:56 PM, David Kastrup wrote:\n> The previous implementation used a single sorted linear list of blame\n> entries for organizing all partial or completed work. Every subtask had\n> to scan the whole list, with most entries not being relevant to the\n> task. The resulting run-time was quadratic to the number of separate\n> chunks.\n>\n> This change gives every subtask its own data to work with. Subtasks are\n> organized into \"struct origin\" chains hanging off particular commits.\n> Commits are organized into a priority queue, processing them in commit\n> date order in order to keep most of the work affecting a particular blob\n> collated even in the presence of an extensive merge history.\n\nWithout reading the code, this sounds like how JGit runs blame.\n\n> For large files with a diversified history, a speedup by a factor of 3\n> or more is not unusual.\n\nAnd JGit was already usually slower than git-core. Now it will be even\nslower! :-)\n"},{"id":"239746","messageId":"87wqec8rb5.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"CAJo=hJukmej1rJXuVoECwd7AxmSue8Wmv4rBmCHEYcWBWNarSw@mail.gmail.com","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T07:48:14Z","receivedAt":"2014-04-26T07:48:14Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Shawn Pearce writes:\n\n> On Fri, Apr 25, 2014 at 4:56 PM, David Kastrup wrote:\n>> The previous implementation used a single sorted linear list of blame\n>> entries for organizing all partial or completed work. Every subtask had\n>> to scan the whole list, with most entries not being relevant to the\n>> task. The resulting run-time was quadratic to the number of separate\n>> chunks.\n>>\n>> This change gives every subtask its own data to work with. Subtasks are\n>> organized into \"struct origin\" chains hanging off particular commits.\n>> Commits are organized into a priority queue, processing them in commit\n>> date order in order to keep most of the work affecting a particular blob\n>> collated even in the presence of an extensive merge history.\n>\n> Without reading the code, this sounds like how JGit runs blame.\n>\n>> For large files with a diversified history, a speedup by a factor of 3\n>> or more is not unusual.\n>\n> And JGit was already usually slower than git-core. Now it will be even\n> slower! :-)\n\nIf your statement about JGit is accurate, it should likely have beat Git\nfor large use cases (where the performance improvements are most\nimportant) as O(n) beats O(n^2) in the long run.\n\nAt any rate, I see that I ended up posting this patch series at the end\nof the week again which makes for a somewhat lacklustre initial response\nfrom those who code Git for a regular living.\n\nApropos: shaking the bugs regarding -M and -C options out of the code\nhad taken a large toll because -M can cause the same or overlapping line\nregions to be responsible for different target regions and the original\ncode implementing the \"straightforward\" blame blew up on the overlap.\nI spent a _lot_ of time tracking down that problem.\n\nAs I am lousy focusing on more than one task, and as I don't get a\nregular paycheck anyway, this will have to remain my last contribution\nto Git if I am not going to recoup my losses.\n\nPatch 2 of this series tries giving the community of Git a serious\nchance at picking that option (I mean, there are literally millions of\nGit users around with a sizable number profiting) while not being\nobnoxious about it.\n\nMy personal guess is that it will fail regarding both objectives. But\nthen I've been surprised before by other free software communities when\ntrying to make those particular two ends meet.\n\nAt any rate, feedback about the performance of the patch from users\ndisappointed by regular git blame would be welcome.\n\nApart from the objective measurement of \"total time\", the more\nsubjective impression of interactive/incremental response (like in git\ngui blame) where the order of results will significantly differ (current\ngit-blame --incremental focuses on getting blames resolved in\nfirst-lines-first manner, the proposed git-blame rather works on a\nnewest-commits-first basis which might better match typical use cases)\nmight be worth reporting.\n\n-- \nDavid Kastrup\n"},{"id":"239755","messageId":"CAJo=hJs=ap=Ct_PzOsO=vHmDVMvUF+nvbB7b67bgnmug+Yrohg@mail.gmail.com","threadId":"36504","inReplyTo":"87wqec8rb5.fsf@fencepost.gnu.org","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-04-26T16:01:22Z","receivedAt":"2014-04-26T16:01:22Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Apr 26, 2014 at 12:48 AM, David Kastrup wrote:\n> Shawn Pearce writes:\n>\n>> On Fri, Apr 25, 2014 at 4:56 PM, David Kastrup wrote:\n>>> The previous implementation used a single sorted linear list of blame\n>>> entries for organizing all partial or completed work. Every subtask had\n>>> to scan the whole list, with most entries not being relevant to the\n>>> task. The resulting run-time was quadratic to the number of separate\n>>> chunks.\n>>>\n>>> This change gives every subtask its own data to work with. Subtasks are\n>>> organized into \"struct origin\" chains hanging off particular commits.\n>>> Commits are organized into a priority queue, processing them in commit\n>>> date order in order to keep most of the work affecting a particular blob\n>>> collated even in the presence of an extensive merge history.\n>>\n>> Without reading the code, this sounds like how JGit runs blame.\n>>\n>>> For large files with a diversified history, a speedup by a factor of 3\n>>> or more is not unusual.\n>>\n>> And JGit was already usually slower than git-core. Now it will be even\n>> slower! :-)\n>\n> If your statement about JGit is accurate, it should likely have beat Git\n> for large use cases (where the performance improvements are most\n> important) as O(n) beats O(n^2) in the long run.\n\nAgreed.\n\nIn a few cases yes, JGit did beat git-core at blame running time.\nUnfortunately according to my profiling blame performance is still\ndominated by inflation and scanning of commit and tree objects to\nidentify unmodified blobs and advance to the next scapegoat ancestor.\n\nIts entirely possible my blame implementation in JGit is still doing\nsomething stupid. Or its possible JIT translated Java just takes\nlonger than natively compiled C. I am including JVM startup and JIT\ntime in the timing comparison with git-core.\n\n> Apart from the objective measurement of \"total time\", the more\n> subjective impression of interactive/incremental response (like in git\n> gui blame) where the order of results will significantly differ (current\n> git-blame --incremental focuses on getting blames resolved in\n> first-lines-first manner, the proposed git-blame rather works on a\n> newest-commits-first basis which might better match typical use cases)\n> might be worth reporting.\n\nSeeing this fill during execution was the initial motivation I had for\nwriting git gui blame. I don't think anyone cares about the order it\ndisplays in. In fact ordering my timestamp may be more what the user\nwants anyway, as you suggest above.\n\nThanks for doing this. Unfortunately I can't read the patch itself as\nI am also trying to improve JGit's blame code for $DAY_JOB, and JGit\nis BSD licensed.\n"},{"id":"239756","messageId":"87ha5g8286.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"CAJo=hJs=ap=Ct_PzOsO=vHmDVMvUF+nvbB7b67bgnmug+Yrohg@mail.gmail.com","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T16:50:01Z","receivedAt":"2014-04-26T16:50:01Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Shawn Pearce writes:\n\n> On Sat, Apr 26, 2014 at 12:48 AM, David Kastrup wrote:\n>> Shawn Pearce writes:\n>>>\n>>> And JGit was already usually slower than git-core. Now it will be\n>>> even slower! :-)\n>>\n>> If your statement about JGit is accurate, it should likely have beat\n>> Git for large use cases (where the performance improvements are most\n>> important) as O(n) beats O(n^2) in the long run.\n>\n> Agreed.\n>\n> In a few cases yes, JGit did beat git-core at blame running time.\n> Unfortunately according to my profiling blame performance is still\n> dominated by inflation and scanning of commit and tree objects to\n> identify unmodified blobs and advance to the next scapegoat ancestor.\n\nOh, the C version is most certainly significantly impacted by that after\nmy patch. One can _significantly_ speed it up by increasing\ncore.deltaBaseCacheLimit from its rather silly value of 16M. If you\nhave a comparable control in JGit and if your benchmarking points to the\nunpacking, that's where I'd suggest tweaking first.\n\n>> Apart from the objective measurement of \"total time\", the more\n>> subjective impression of interactive/incremental response (like in\n>> git gui blame) where the order of results will significantly differ\n>> (current git-blame --incremental focuses on getting blames resolved\n>> in first-lines-first manner, the proposed git-blame rather works on a\n>> newest-commits-first basis which might better match typical use\n>> cases) might be worth reporting.\n>\n> Seeing this fill during execution was the initial motivation I had for\n> writing git gui blame.\n\nIt does not look impressively better to me, actually. Probably because\n\"git gui blame\" is running \"git blame\" several times.\n\n> I don't think anyone cares about the order it displays in. In fact\n> ordering my timestamp may be more what the user wants anyway, as you\n> suggest above.\n\nWhat the user wants anyway is that \"git gui blame\" notifies \"git blame\"\nof the currently displayed window area whenever that changes, and that\ngit blame then _first_ deals with all chunks with a visible on-screen\npart.\n\n> Thanks for doing this. Unfortunately I can't read the patch itself as\n> I am also trying to improve JGit's blame code for $DAY_JOB, and JGit\n> is BSD licensed.\n\nShrug. The patch is functionally equivalent to the previous behavior,\nthe arrangement of linear lists on underlying data structures is hardly\ncopyrightable, and Java implements linear lists differently anyhow.\nMerging two sorted linear lists is a straightforward operation,\nsplitting a linear list into several others also is.\n\nThe really tricky/expensive part was realizing that as opposed to target\nline number ranges, source line number ranges may overlap and/or be\nduplicate when using -M or -C options. That really messed things up for\na long time and was hard to debug. Once I figured out what was going\nwrong, recoding the respective stuff was straightforward.\n\nI doubt that there is much copyrightable material to transfer as I seem\nto remember that Java does not have anything like a pointer. So the\nmain stuff, juggling with linear lists, would not likely transfer in a\nreasonably recognizable manner.\n\n-- \nDavid Kastrup\n"},{"id":"239757","messageId":"87d2g481nb.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"CAJo=hJs=ap=Ct_PzOsO=vHmDVMvUF+nvbB7b67bgnmug+Yrohg@mail.gmail.com","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T17:02:32Z","receivedAt":"2014-04-26T17:02:32Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Shawn Pearce writes:\n\n> Thanks for doing this. Unfortunately I can't read the patch itself as\n> I am also trying to improve JGit's blame code for $DAY_JOB, and JGit\n> is BSD licensed.\n\nActually, I'd have suggested asking $EMPLOYER to buy the rights for\nlooking at the code, but as I wrote previously, I'd seriously doubt that\nhe'd get his money's worth for use in a _Java_ implementation.\n\nThe C code I proposed is good for files with many small changes: I'd\nsuggest benchmarking your JGit code with some of them. If the JGit is\nstill dominated by unpacking, your implementation should be fine. The\ncurrent C version instead thrashes around digging through its own\nall-purpose single linear list.\n\nHere are two real-world test cases:\n\ngit://git.savannah.gnu.org/emacs.git\ngit blame [-M / -C] src/xdisp.c\n\nhttp://repo.or.cz/r/wortliste.git\ngit blame [-M / -C] wortliste\n\nThe latter one is _really_ taking a severe hit from the O(n^2)\nalgorithms. If your benchmarks for that one still point mostly to the\nunpacking, your jgit blame should be fine regarding the stuff\nI reimplemented.\n\n-- \nDavid Kastrup\n"},{"id":"239758","messageId":"CAJo=hJsrFb+FdBDoHiYOPeB0nEQhD+9dBXTK84bDSj1MgBBdQA@mail.gmail.com","threadId":"36504","inReplyTo":"87ha5g8286.fsf@fencepost.gnu.org","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-04-26T17:09:00Z","receivedAt":"2014-04-26T17:09:00Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Apr 26, 2014 at 9:50 AM, David Kastrup wrote:\n> Shawn Pearce writes:\n>\n>> On Sat, Apr 26, 2014 at 12:48 AM, David Kastrup wrote:\n>>> Shawn Pearce writes:\n>>>>\n>>>> And JGit was already usually slower than git-core. Now it will be\n>>>> even slower! :-)\n>>>\n>>> If your statement about JGit is accurate, it should likely have beat\n>>> Git for large use cases (where the performance improvements are most\n>>> important) as O(n) beats O(n^2) in the long run.\n>>\n>> Agreed.\n>>\n>> In a few cases yes, JGit did beat git-core at blame running time.\n>> Unfortunately according to my profiling blame performance is still\n>> dominated by inflation and scanning of commit and tree objects to\n>> identify unmodified blobs and advance to the next scapegoat ancestor.\n>\n> Oh, the C version is most certainly significantly impacted by that after\n> my patch. One can _significantly_ speed it up by increasing\n> core.deltaBaseCacheLimit from its rather silly value of 16M. If you\n> have a comparable control in JGit and if your benchmarking points to the\n> unpacking, that's where I'd suggest tweaking first.\n\nGood point, we have that control but I always forget to play with it\nduring benchmarking.\n\n>>> Apart from the objective measurement of \"total time\", the more\n>>> subjective impression of interactive/incremental response (like in\n>>> git gui blame) where the order of results will significantly differ\n>>> (current git-blame --incremental focuses on getting blames resolved\n>>> in first-lines-first manner, the proposed git-blame rather works on a\n>>> newest-commits-first basis which might better match typical use\n>>> cases) might be worth reporting.\n>>\n>> Seeing this fill during execution was the initial motivation I had for\n>> writing git gui blame.\n>\n> It does not look impressively better to me, actually. Probably because\n> \"git gui blame\" is running \"git blame\" several times.\n\nIIRC git gui blame runs blame only twice. Once with the simple blame,\nand then again with -M -C or something like that. Its a nice display\nbecause you can see who moved code here, and then who originally wrote\nit. Unfortunately it has to be done as two passes as the blame\nimplementation does not know how to compute both in one pass.\n\nThe move/copy detection is also computationally more expensive per\nrevision visited, so it really slows down the simple \"who put it here\"\nif the two passes were somehow run in a single iteration.\n\n>> I don't think anyone cares about the order it displays in. In fact\n>> ordering my timestamp may be more what the user wants anyway, as you\n>> suggest above.\n>\n> What the user wants anyway is that \"git gui blame\" notifies \"git blame\"\n> of the currently displayed window area whenever that changes, and that\n> git blame then _first_ deals with all chunks with a visible on-screen\n> part.\n\nThat is a really good idea. Unfortunately finding that part of the\nwindow in the blame data can still take a while. You may compute other\nparts of the file anyway while looking for this part, as you had to\ncompare two revisions and scapegoat sections to find out that commit\ndidn't touch the interesting region and keep going back through\nhistory.\n\nYou may get lucky and be able to fill in a recent region quickly, but\nI somehow suspect giving priority to the visible region in the\npriority queue won't really help to reduce latency of the visible\nregion for the user.\n\n> The really tricky/expensive part was realizing that as opposed to target\n> line number ranges, source line number ranges may overlap and/or be\n> duplicate when using -M or -C options. That really messed things up for\n> a long time and was hard to debug. Once I figured out what was going\n> wrong, recoding the respective stuff was straightforward.\n\nRight, and JGit blame still is missing the -M and -C options, as I\nhave not implemented those yet. I got basic blame and reverse blame\nworking a few years ago and then stopped working on the code for a\nwhile. Now we have interest in improving the latency for $DAY_JOB, so\nI've been poking at the code again for the last week or so.\n\nBut that -M and -C thing is still not implemented, and I know its\ngoing to be tricky to get right with the way the scapegoating is\npassed along.\n"},{"id":"239759","messageId":"878uqs80pt.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"CAJo=hJsrFb+FdBDoHiYOPeB0nEQhD+9dBXTK84bDSj1MgBBdQA@mail.gmail.com","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T17:22:38Z","receivedAt":"2014-04-26T17:22:38Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Shawn Pearce writes:\n\n> Right, and JGit blame still is missing the -M and -C options, as I\n> have not implemented those yet. I got basic blame and reverse blame\n> working a few years ago and then stopped working on the code for a\n> while. Now we have interest in improving the latency for $DAY_JOB, so\n> I've been poking at the code again for the last week or so.\n>\n> But that -M and -C thing is still not implemented, and I know its\n> going to be tricky to get right with the way the scapegoating is\n> passed along.\n\nActually, for -M/-C it would be saner to rip open the whole xdiff\nblackbox which internally goes to quite some effort in order to produce\nthe linear ordering of a diff, and then -M has to simulate dropping that\nlinear ordering requirement by doing a host of parallel diffs for each\nchunk.\n\n-- \nDavid Kastrup\n"},{"id":"239762","messageId":"7vmwf8huey.fsf@alter.siamese.dyndns.org","threadId":"36504","inReplyTo":"1398470210-28746-2-git-send-email-dak@gnu.org","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-26T17:28:37Z","receivedAt":"2014-04-26T17:28:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Includes reasonably tasteful begging.\n\nThanks, but no thanks---I do not see it tasteful.\n\nIn any case, any large change that is not a regression fix (or a fix\nto a code added since 1.9 series) is way too late for 2.0 at this\npoint, but I do look forward to reading the patch over, queuing to\nmy tree, cooking in 'next' and eventually having this in 2.1 or\nlater.\n\nIf you want help in a fundraising campaign, I can lend my name\n(especially after this change settles and proves to be useful ;-),\nbut let's do that elsewhere. I do not want to do this in the release\nnotes (e.g., an entry in git-blame blog can mention it when it\ntouches the blame improvements).\n\nThis by the way touches another thing I have been wondering.\nPerhaps I should stop having the top-level RelNotes as a symbolic\nlink, but keep it as a regular file, which I *copy* to its current\nlocation in the commit that tags the release. And then I start a\nskeletal RelNotes at the top of the tree when the next cycle begins,\nand new topics will build on top of that commit.\n\nThat way, this patch would have been against the top-level RelNotes,\napplied as part of the topic, and when the topic is merged to\n'master', it would make it less likely for me to forget about\nmentioning it.\n\nThanks for working on the topic.\n\n>\n> Signed-off-by: David Kastrup \n> ---\n> Documentation/RelNotes/2.0.0.txt | 6 ++++++\n> 1 file changed, 6 insertions(+)\n>\n> diff --git a/Documentation/RelNotes/2.0.0.txt b/Documentation/RelNotes/2.0.0.txt\n> index ffd4899..27b23c3 100644\n> --- a/Documentation/RelNotes/2.0.0.txt\n> +++ b/Documentation/RelNotes/2.0.0.txt\n> @@ -144,6 +144,12 @@ UI, Workflows & Features\n> \n> Performance, Internal Implementation, etc.\n> \n> + * Significant parts of \"git blame\" have been reimplemented by David\n> + Kastrup for a vast gain in performance with complex\n> + histories and large files. As working on free software is his sole\n> + source of income, please consider contributing to his remuneration\n> + if you find this useful.\n> +\n> * The compilation options to port to AIX and to MSVC have been\n> updated.\n"},{"id":"239763","messageId":"874n1g80dd.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"87d2g481nb.fsf@fencepost.gnu.org","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T17:30:06Z","receivedAt":"2014-04-26T17:30:06Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"David Kastrup writes:\n\n> http://repo.or.cz/r/wortliste.git\n> git blame [-M / -C] wortliste\n>\n> The latter one is _really_ taking a severe hit from the O(n^2)\n> algorithms. If your benchmarks for that one still point mostly to the\n> unpacking, your jgit blame should be fine regarding the stuff\n> I reimplemented.\n\nHere's some example:\n\ndak@lola:/usr/local/tmp/wortliste$ time git blame -n -s wortliste >/tmp/wl1\n\nreal\t15m47.118s\nuser\t14m39.928s\nsys\t1m1.872s\ndak@lola:/usr/local/tmp/wortliste$ time ../git/git blame -n -s wortliste >/tmp/wl2\n\nreal\t3m40.947s\nuser\t2m40.296s\nsys\t0m59.440s\n\nNote how the system time is almost the same. I have some patches which\nmake quite a bit of difference with that (at best, saving about half of\nthe system time), but I have not yet found the silver bullet where I'd\nbe reasonably sure that temporary memory use with non-linear history\nstays strictly in nice bounds.\n\n-- \nDavid Kastrup\n"},{"id":"239770","messageId":"CAJo=hJs-Nn=o=aGS_3bO9mnxb+urst6JTZf29_qAejBipz_ZHg@mail.gmail.com","threadId":"36504","inReplyTo":"874n1g80dd.fsf@fencepost.gnu.org","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-04-26T17:56:22Z","receivedAt":"2014-04-26T17:56:22Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Apr 26, 2014 at 10:30 AM, David Kastrup wrote:\n> David Kastrup writes:\n>\n>> http://repo.or.cz/r/wortliste.git\n>> git blame [-M / -C] wortliste\n>>\n>> The latter one is _really_ taking a severe hit from the O(n^2)\n>> algorithms. If your benchmarks for that one still point mostly to the\n>> unpacking, your jgit blame should be fine regarding the stuff\n>> I reimplemented.\n>\n> Here's some example:\n>\n> dak@lola:/usr/local/tmp/wortliste$ time git blame -n -s wortliste >/tmp/wl1\n>\n> real 15m47.118s\n> user 14m39.928s\n> sys 1m1.872s\n\nHah, this is quite the torture test. git before your patch is taking\n22m11s on my laptop to compute this. (This was with default options, I\nnoticed you passed -s to suppress the author formatting.)\n\n> dak@lola:/usr/local/tmp/wortliste$ time ../git/git blame -n -s wortliste >/tmp/wl2\n>\n> real 3m40.947s\n> user 2m40.296s\n> sys 0m59.440s\n\nMeanwhile JGit computed in 4m30s on the same hardware. So I guess we\nare \"fine\". Its still not as fast as I want it to be. :-)\n"},{"id":"239772","messageId":"87zjj86j4a.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"7vmwf8huey.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T18:28:05Z","receivedAt":"2014-04-26T18:28:05Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Includes reasonably tasteful begging.\n>\n> Thanks, but no thanks---I do not see it tasteful.\n\nWell, begging rarely is. The point simply is that without commensurate\nrecompensation, I cannot afford any more work of that kind on Git, and\nthere is a reasonable likelihood that such work is worth more to some\nsubset of Git users than what it would take to enable me doing it.\n\nMy experience with \"tasteful\" asking for contributions in the context of\nAUCTeX and preview-latex development is about €100 plus two cases of\nbeer in 10 years.\n\nWith GNU LilyPond, I've been way more blunt. Its community certainly is\ndwarved by the Git community, and still they've been able to support my\nwork with more than €1000 per month for several years now. I've been\nletting those people down for several months now because of the\ngit-blame stuff, with a respective decline in support to show for that.\nSure, partly because of misestimates of the involved work and the\ninvolved self-motivation to get it over with.\n\nIf that's not worth anything to the Git community, I can just chalk it\noff as a somewhat expensive one-time experience and that's it. I can\nlive with that.\n\nWhat I want to avoid, however, is the situation where this kind of work\nwould actually _have_ been worth enough to enough people to enable it\nbut they don't get to make a decision whether to support more of it\nand/or express their appreciation in the manner that actually counts,\nbecause of being blissfully unaware.\n\nNow of course, people having an independent and/or guaranteed can afford\nto be tasteful. And there are probably enough of those around for\nrunning the show.\n\nBut then \"git blame\" performance has been sub-par for a very long time\nalready.\n\n> In any case, any large change that is not a regression fix (or a fix\n> to a code added since 1.9 series) is way too late for 2.0 at this\n> point,\n\nFor what it's worth, the user interface is unchanged. And results\nshould be the same as previously apart from the runtime requirements.\nNaturally, this is \"should\", and problems, particularly regarding\ndifferent output, may take a long time until somebody notices since few\npeople will actually compare the old and new results.\n\n> but I do look forward to reading the patch over, queuing to my tree,\n> cooking in 'next' and eventually having this in 2.1 or later.\n>\n> If you want help in a fundraising campaign, I can lend my name\n> (especially after this change settles and proves to be useful ;-),\n\nIn my book, it is a large usability improvement but not necessarily a\ngame changer. Waiting for 1 minute rather than 3 minutes is still\nnothing one wants enabled in a web server, or that turns stuff into the\n\"interactive response\" ballpark.\n\nTo get that, one will have to work on the remaining performance which is\nprimarily the responsibility of the object store and associated caching.\nThe advantage is that its impact on the performance is now readily\nvisible: previous to this patch it is strongly masked by the sub-par\nperformance of the git-blame code itself.\n\n> but let's do that elsewhere.\n\nIf you have a reasonable idea for that. It would be pointless wherever\nit safely becomes \"somebody else's problem\" for pretty much everybody.\nI'm not overly happy with trying to recruit active developers/power\nusers for that kind of thing when they are\n\na) actively investing time and effort themselves\nb) outnumbered by profiting users 1000:1\n\nbut I've not yet found a better approach myself with regard to LilyPond.\nIf you have a better idea for Git...\n\n> I do not want to do this in the release notes (e.g., an entry in\n> git-blame blog can mention it when it touches the blame improvements).\n\nAgain: it's important to be visible to those people who might care about\nputting money in, or it's pointless.\n\nAt any rate, I'm glad that the work is closed for now.\n\n-- \nDavid Kastrup\n"},{"id":"239794","messageId":"87vbtv7ou0.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"CAJo=hJs-Nn=o=aGS_3bO9mnxb+urst6JTZf29_qAejBipz_ZHg@mail.gmail.com","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-26T21:39:19Z","receivedAt":"2014-04-26T21:39:19Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Shawn Pearce writes:\n\n> On Sat, Apr 26, 2014 at 10:30 AM, David Kastrup wrote:\n>> David Kastrup writes:\n>>\n>> Here's some example:\n>>\n>> dak@lola:/usr/local/tmp/wortliste$ time git blame -n -s wortliste >/tmp/wl1\n>>\n>> real 15m47.118s\n>> user 14m39.928s\n>> sys 1m1.872s\n>\n> Hah, this is quite the torture test. git before your patch is taking\n> 22m11s on my laptop to compute this. (This was with default options, I\n> noticed you passed -s to suppress the author formatting.)\n>\n>> dak@lola:/usr/local/tmp/wortliste$ time ../git/git blame -n -s wortliste >/tmp/wl2\n>>\n>> real 3m40.947s\n>> user 2m40.296s\n>> sys 0m59.440s\n>\n> Meanwhile JGit computed in 4m30s on the same hardware. So I guess we\n> are \"fine\".\n\nAt least the stuff I fixed with regard to performance would seem to be\ndone right in JGit to start with.\n\n> Its still not as fast as I want it to be. :-)\n\nMost of the diff data/CRC is computed over and over because of the\nblackbox use of xdiff. And then the delta-chain storage is packing\nstuff based on CRCs as well (not sure whether it keeps them around for\nunpacking). So there is a lot that could likely be improved while\nkeeping the same basic algorithms, by cracking open the black boxes of\nthe xdiff engine and the delta-chain coding.\n\n-- \nDavid Kastrup\n"},{"id":"239806","messageId":"CAJo=hJvHiCu8WdHdD7wjnbZeCmKkCdCQwvuLAcF6rfMc2nzLsw@mail.gmail.com","threadId":"36504","inReplyTo":"87vbtv7ou0.fsf@fencepost.gnu.org","subject":"Re: [PATCH 1/2] blame: large-scale performance rewrite","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-04-27T17:53:09Z","receivedAt":"2014-04-27T17:53:09Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Apr 26, 2014 at 2:39 PM, David Kastrup wrote:\n>\n> At least the stuff I fixed with regard to performance would seem to be\n> done right in JGit to start with.\n\nHah! Its Java. We have to do things right, otherwise its too slow. :-)\n\n>> Its still not as fast as I want it to be. :-)\n>\n> Most of the diff data/CRC is computed over and over because of the\n> blackbox use of xdiff.\n\nYes, I have been thinking about this all week.\n\nJGit blame uses HistogramDiff by default instead of MyersDiff. The\nfirst stage after we trim common header/trailer from both files is to\ncompute a hash of each line and store those hashes. Those hashes are\ndiscarded as the blame algorithm moves to the next commit.\n\nClearly for a commit chain of A -> B -> C, the hashes computed at B\nfor the A->B compare can be reused for the B->C compare. This is not\nthe case in either git-core or JGit, because the diff algorithm is a\nblock box to the blame algorithm. I think this is what you mean by the\nCRC being computed again.\n\n\nFor any given compare blame has a list of regions it is interested in\nlearning about from the diff algorithm. Anything outside of those\nregions is useless noise that will be discarded. I have been pondering\npushing that region list down into the diff algorithm so it can avoid\nexecuting on sections that are not relevant to the caller. At least\nfor HistogramDiff this makes some sense, the algorithm is recursively\napplied after it finds a longest common subsequence. If one side of\nthe LCS is outside of the region of interest from blame, there is no\nvalue in recursing on that portion.\n\nIf the blame region list covers a small enough portion, it may even\nmake sense to avoid the common header/trailer elimination\npreprocessing step. Unfortunately that sounds \"hard\" as you could be\nworking with a file like a ChangeLog which grows on one of those\nsides.\n\n\n> And then the delta-chain storage is packing\n> stuff based on CRCs as well (not sure whether it keeps them around for\n> unpacking).\n\nThere are CRCs validated by libz during inflation, but these aren't\nrechecked once the inflated bytes are cached in that silly undersized\n16M delta base cache.\n\n> So there is a lot that could likely be improved while\n> keeping the same basic algorithms, by cracking open the black boxes of\n> the xdiff engine and the delta-chain coding.\n\nThe delta chain coding has no relationship to the source file.\nCurrently even plain text files are delta chain coded on a byte basis,\nnot a line basis. Just matching up the delta coding against a source\ntext file to determine lines 0-N are common is costly, since you have\na byte range in the delta coding and you want a line range out the\nend.\n\nTo make things more challenging, the delta chain coding can be against\ncompletely different blobs. In a compare of A->B from the commit graph\nbeing walked by blame there is no requirement the delta coding uses\nthis pairing, and it almost certainly never uses this direction (its\nusually B->A, if its even this pair!).\n\n\nGiven your comments in the other patch, I understand why you probably\nwon't be working on blame more. But the above may help someone else\nthat has available time to continue.\n"},{"id":"239984","messageId":"87y4yp4ame.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"xmqqzjj5s8hs.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-28T17:39:05Z","receivedAt":"2014-04-28T17:39:05Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>>> Thanks, but no thanks---I do not see it tasteful.\n>>\n>> Well, begging rarely is....\n>> ...\n>> If that's not worth anything to the Git community,...\n>\n> Concurred on the first point. If you thought in any way I meant\n> to say that blame improvements do not matter, then I am sorry, I did\n> not mean that.\n>\n> But still, I am not convinced that the release notes is a good place\n> to do this, and would be happier if you can think of a better venue.\n\n\"This change has been contributed by an independent developer on a\ncontingency base. To make this approach work, please contact him if you\nconsider it worth recompensating.\"\n\nThis sort of text can be placed in the commit message (where it will be\nmostly visible to actual other developers) and in the \"What's cooking\"\nreports while, well, it's cooking. It won't reach the mass of \"ordinary\nusers\", but while they are quite a large audience, they are also least\nlikely to care enough about isolated performance changes. And while it\nwill be a limited run, \"What's cooking\" is also read by non-developers.\n\nThose are the two venues I can currently think of that would seem\n\"scalable\", at least with a text of that size. Namely where it would\nnot become quite a total nuisance (though naturally less effective) if\neverybody tried doing the same.\n\n-- \nDavid Kastrup\n"},{"id":"240008","messageId":"xmqq38gxqmc9.fsf@gitster.dls.corp.google.com","threadId":"36504","inReplyTo":"87y4yp4ame.fsf@fencepost.gnu.org","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-28T19:35:02Z","receivedAt":"2014-04-28T19:35:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Junio C Hamano writes:\n>\n>> But still, I am not convinced that the release notes is a good place\n>> to do this, and would be happier if you can think of a better venue.\n>\n> \"This change has been contributed by an independent developer on a\n> contingency base. To make this approach work, please contact him if you\n> consider it worth recompensating.\"\n\nI write things under three personalities. As just one of the people\nactive in the Git development community, as the maintainer of the\nproject, and saying things on behalf of \"the Git project\".\n\nThe distinction between the latter two may be subtle, but it matters\nto me. And in my mind, I write the Release Notes on behalf of the\nproject.\n\n * The performance of \"git blame\" has been greatly improved. Thanks\n David Kastrup for his huge effort.\n\nis perhaps as far as I can go in that capacity, without singling out\none contributor among 80+ contributors with changes between 1.9 and\n2.0 (among which a dozen or so have more than 10 patches---some are\ntrivial and patch count alone does not do justice, though) with\nsimilar \"pay them to show your appreciation\" pleas.\n\nI however feel that I can certainly do that as an active (and highly\nvisible) contributor, and even as the maintainer.\n\nI guess we probably can add \"See $URL if you are interested in his\nfurther plans\" after that two-line item and let you write whatever\nyou want at that page pointed at by the URL, though.\n"},{"id":"240025","messageId":"87ha5d4480.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"xmqq38gxqmc9.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-28T19:57:19Z","receivedAt":"2014-04-28T19:57:19Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> I guess we probably can add \"See $URL if you are interested in his\n> further plans\" after that two-line item and let you write whatever\n> you want at that page pointed at by the URL, though.\n\nI most definitely am _not_ planning to invest any more time into Git\nsince even designing such plans would be throwing good time after bad\ntime. And I don't have a web presence anyway. As it does not appear\nthat there is any realistic manner in which Git users could even be made\naware of a connection between monetary requirements and work for a\nfreelancer like myself, I'll be just writing this off as a one-time\nmistake on my part given my personal situation. It's not the first, and\nit will certainly not be the last, but at least I can avoid doing the\nsame mistake twice on the same project.\n\nThere are some low-hanging fruit for further speeding up git-blame now\nthat its internal thrashing has been addressed. I will point out those\nlow-hanging fruit so that anybody can follow up on it and do all the\narguing and benchmarking required to go anywhere and get the credit for\nit.\n\nBut that's as far as my willingness to \"do the right thing\" will carry.\nIf nobody picks up either the tab or the rather simple followup tasks,\nthen that's what the community and customer base of Git is capable of\nsustaining and I'm not in a position to change it.\n\n-- \nDavid Kastrup\n"},{"id":"240030","messageId":"CAL=YDW=iTQz-S+ZByZnVhrpebPgZxq6p46MC2yqW-HF3eVw+2g@mail.gmail.com","threadId":"36504","inReplyTo":"xmqq38gxqmc9.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"Ronnie Sahlberg","fromEmail":"sahlberg@google.com","sentAt":"2014-04-28T20:05:28Z","receivedAt":"2014-04-28T20:05:28Z","isPatch":true,"sender":{"key":"sahlberg@google.com","avatar":"https://avatars.githubusercontent.com/u/7320636?v=4"},"body":"On Mon, Apr 28, 2014 at 12:35 PM, Junio C Hamano wrote:\n> David Kastrup writes:\n>\n>> Junio C Hamano writes:\n>>\n>>> But still, I am not convinced that the release notes is a good place\n>>> to do this, and would be happier if you can think of a better venue.\n>>\n>> \"This change has been contributed by an independent developer on a\n>> contingency base. To make this approach work, please contact him if you\n>> consider it worth recompensating.\"\n>\n> I write things under three personalities. As just one of the people\n> active in the Git development community, as the maintainer of the\n> project, and saying things on behalf of \"the Git project\".\n>\n> The distinction between the latter two may be subtle, but it matters\n> to me. And in my mind, I write the Release Notes on behalf of the\n> project.\n>\n> * The performance of \"git blame\" has been greatly improved. Thanks\n> David Kastrup for his huge effort.\n>\n> is perhaps as far as I can go in that capacity, without singling out\n> one contributor among 80+ contributors with changes between 1.9 and\n> 2.0 (among which a dozen or so have more than 10 patches---some are\n> trivial and patch count alone does not do justice, though) with\n> similar \"pay them to show your appreciation\" pleas.\n>\n> I however feel that I can certainly do that as an active (and highly\n> visible) contributor, and even as the maintainer.\n>\n> I guess we probably can add \"See $URL if you are interested in his\n> further plans\" after that two-line item and let you write whatever\n> you want at that page pointed at by the URL, though.\n>\n\nSome projects, for example samba, provide a dedicated page on the\nproject web site\nwhere vendors, and I think individuals, that provide services can list\ntheir information :\n\nhttp://www.samba.org/samba/support/\n\nWould this perhaps be a better solution?\n\n\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"240034","messageId":"87d2g142uy.fsf@fencepost.gnu.org","threadId":"36504","inReplyTo":"CAL=YDW=iTQz-S+ZByZnVhrpebPgZxq6p46MC2yqW-HF3eVw+2g@mail.gmail.com","subject":"Re: [PATCH 2/2] Mention \"git blame\" improvements in release notes","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-04-28T20:26:45Z","receivedAt":"2014-04-28T20:26:45Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Ronnie Sahlberg writes:\n\n> Some projects, for example samba, provide a dedicated page on the\n> project web site\n> where vendors, and I think individuals, that provide services can list\n> their information :\n>\n> http://www.samba.org/samba/support/\n>\n> Would this perhaps be a better solution?\n\nActually, it does not work for my situation at all but then my situation\nis likely not typical enough to be worth catering for specifically.\n\nThe salient point with me is that my productivity drops by more than a\nfactor of 100 (no, that's not an exaggeration) when having to do\nsomething I'm not interested in.\n\nWhich is the reason my deal with GNU LilyPond where I'm (interrupted by\nthe git-blame episode) basically lead programmer is that LilyPond users\ngive me whatever money they consider my work to be worth to them, and in\nreturn I work on whatever I like on LilyPond. Nobody gets to say _what_\nI do, and that's to the best of everyone's interest since only that way\na reasonable amount of work actually gets done.\n\nSo I cannot actually provide \"services for hire\" but it's more like a\n\"themed money sink\" I can offer. And in the case of Git, since it does\nnot even appear that there is a continuing base to make it work\nreasonably in the context of other contributors and their interests,\nit's more like \"oops, I ended up wasting months on your project, but at\nleast there was something to show for it from my side, how about\nyours?\". That's not something one can reasonably put on a \"support\"\nthemed page. It's actually bloody ridiculous but then that's the sort\nof handicap I have to organize my life around. Even while it's\nunpredictable what I end up doing, once I do get something done it tends\nto be pretty good (there are a few old performance patches of mine in\nthe Git code base where I did not start out from what happens to be\npretty awful code and still got considerable return).\n\n-- \nDavid Kastrup\n"}]}