{"thread":{"id":"35788","subject":"[PATCH 0/5] git-blame: further performance preview","startedAt":"2014-02-03T19:14:04Z","lastAt":"2014-02-03T19:14:09Z","messageCount":6,"participants":["David Kastrup"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"234124","messageId":"1391454849-26558-1-git-send-email-dak@gnu.org","threadId":"35788","inReplyTo":null,"subject":"[PATCH 0/5] git-blame: further performance preview","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-03T19:14:04Z","receivedAt":"2014-02-03T19:14:04Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Ok, I'm progressing rather like molasses with getting -M and -C\noptions back to work.  In the mean time, here is another performance\npreview without them.  The main patch in the middle has basically\ngotten some formatting/style fixes as opposed to last time round and\none small bug fix (concerning incremental output).\n\nIt still contains a significant amount of dead code: this series is\nnot supposed to be merged, it's just supposed to be exciting to see\nhow it performs.\n\nThere are two simple performance patches on top of the main patch, the\nfirst of which offers somewhat significant savings in I/O time (which\nwas quite unaffected by the main rewrite so far).  The gist of that\npatch makes convenient use of the changed data layout to avoid\ndiscarding blob data predictably required again right away.\n\nIt's likely that this is not the only opportunity to save performance\nby better data management.\n\nThe second \"performance\" patch is not likely to measurably affect\noverall performance.  Avoiding irrelevant iterations might make\ndebugging more pleasant, however.\n\nDavid Kastrup (5):\n  builtin/blame.c: struct blame_entry does not need a prev link\n  Eliminate same_suspect function in builtin/blame.c\n  builtin/blame.c: large-scale rewrite\n  Performance improvement: don't drop origin blobs that are going to get\n    tested next.\n  Avoid queuing commits multiple times for the same origin\n\n builtin/blame.c | 595 +++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 371 insertions(+), 224 deletions(-)\n\n-- \n1.8.3.2\n"},{"id":"234125","messageId":"1391454849-26558-2-git-send-email-dak@gnu.org","threadId":"35788","inReplyTo":"1391454849-26558-1-git-send-email-dak@gnu.org","subject":"[PATCH 1/5] builtin/blame.c: struct blame_entry does not need a prev link","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-03T19:14:05Z","receivedAt":"2014-02-03T19:14:05Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Signed-off-by: David Kastrup <dak@gnu.org>\n---\n builtin/blame.c | 13 ++-----------\n 1 file changed, 2 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex e44a6bb..2195595 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -197,7 +197,6 @@ static void drop_origin_blob(struct origin *o)\n  * scoreboard structure, sorted by the target line number.\n  */\n struct blame_entry {\n-\tstruct blame_entry *prev;\n \tstruct blame_entry *next;\n \n \t/* the first line of this group in the final image;\n@@ -282,8 +281,6 @@ static void coalesce(struct scoreboard *sb)\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-\t\t\tif (ent->next)\n-\t\t\t\tent->next->prev = ent;\n \t\t\torigin_decref(next->suspect);\n \t\t\tfree(next);\n \t\t\tent->score = 0;\n@@ -534,7 +531,7 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n \t\tprev = ent;\n \n \t/* prev, if not NULL, is the last one that is below e */\n-\te->prev = prev;\n+\n \tif (prev) {\n \t\te->next = prev->next;\n \t\tprev->next = e;\n@@ -543,8 +540,6 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n \t\te->next = sb->ent;\n \t\tsb->ent = e;\n \t}\n-\tif (e->next)\n-\t\te->next->prev = e;\n }\n \n /*\n@@ -555,14 +550,12 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n  */\n static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n {\n-\tstruct blame_entry *p, *n;\n+\tstruct blame_entry *n;\n \n-\tp = dst->prev;\n \tn = dst->next;\n \torigin_incref(src->suspect);\n \torigin_decref(dst->suspect);\n \tmemcpy(dst, src, sizeof(*src));\n-\tdst->prev = p;\n \tdst->next = n;\n \tdst->score = 0;\n }\n@@ -2502,8 +2495,6 @@ parse_done:\n \t\tent->suspect = o;\n \t\tent->s_lno = bottom;\n \t\tent->next = next;\n-\t\tif (next)\n-\t\t\tnext->prev = ent;\n \t\torigin_incref(o);\n \t}\n \torigin_decref(o);\n-- \n1.8.3.2\n"},{"id":"234128","messageId":"1391454849-26558-3-git-send-email-dak@gnu.org","threadId":"35788","inReplyTo":"1391454849-26558-1-git-send-email-dak@gnu.org","subject":"[PATCH 2/5] Eliminate same_suspect function in builtin/blame.c","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-03T19:14:06Z","receivedAt":"2014-02-03T19:14:06Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Since the origin pointers are \"interned\" and reference-counted, comparing\nthe pointers rather than the content is enough.  The only uninterned\norigins are cached values kept in commit->util, but same_suspect is not\ncalled on them.\n\nSigned-off-by: David Kastrup <dak@gnu.org>\n---\n builtin/blame.c | 25 ++++++++-----------------\n 1 file changed, 8 insertions(+), 17 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex 2195595..ead6148 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -255,15 +255,6 @@ struct scoreboard {\n \tint *lineno;\n };\n \n-static inline int same_suspect(struct origin *a, struct origin *b)\n-{\n-\tif (a == b)\n-\t\treturn 1;\n-\tif (a->commit != b->commit)\n-\t\treturn 0;\n-\treturn !strcmp(a->path, b->path);\n-}\n-\n static void sanity_check_refcnt(struct scoreboard *);\n \n /*\n@@ -276,7 +267,7 @@ static void coalesce(struct scoreboard *sb)\n \tstruct blame_entry *ent, *next;\n \n \tfor (ent = sb->ent; ent && (next = ent->next); ent = next) {\n-\t\tif (same_suspect(ent->suspect, next->suspect) &&\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@@ -735,7 +726,7 @@ static int find_last_in_target(struct scoreboard *sb, struct origin *target)\n \tint last_in_target = -1;\n \n \tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || !same_suspect(e->suspect, target))\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@@ -755,7 +746,7 @@ static void blame_chunk(struct scoreboard *sb,\n \tstruct blame_entry *e;\n \n \tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || !same_suspect(e->suspect, target))\n+\t\tif (e->guilty || e->suspect != target)\n \t\t\tcontinue;\n \t\tif (same <= e->s_lno)\n \t\t\tcontinue;\n@@ -985,7 +976,7 @@ static int find_move_in_parent(struct scoreboard *sb,\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 || !same_suspect(e->suspect, target) ||\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\t\tfind_copy_in_blob(sb, e, parent, split, &file_p);\n@@ -1020,14 +1011,14 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\n \n \tfor (e = sb->ent, num_ents = 0; e; e = e->next)\n \t\tif (!e->scanned && !e->guilty &&\n-\t\t    same_suspect(e->suspect, target) &&\n+\t\t    e->suspect == target &&\n \t\t    min_score < ent_score(sb, e))\n \t\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    same_suspect(e->suspect, target) &&\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}\n@@ -1171,7 +1162,7 @@ static void pass_whole_blame(struct scoreboard *sb,\n \t\torigin->file.ptr = NULL;\n \t}\n \tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (!same_suspect(e->suspect, origin))\n+\t\tif (e->suspect != origin)\n \t\t\tcontinue;\n \t\torigin_incref(porigin);\n \t\torigin_decref(e->suspect);\n@@ -1560,7 +1551,7 @@ static void assign_blame(struct scoreboard *sb, int opt)\n \n \t\t/* Take responsibility for the remaining entries */\n \t\tfor (ent = sb->ent; ent; ent = ent->next)\n-\t\t\tif (same_suspect(ent->suspect, suspect))\n+\t\t\tif (ent->suspect == suspect)\n \t\t\t\tfound_guilty_entry(ent);\n \t\torigin_decref(suspect);\n \n-- \n1.8.3.2\n"},{"id":"234126","messageId":"1391454849-26558-4-git-send-email-dak@gnu.org","threadId":"35788","inReplyTo":"1391454849-26558-1-git-send-email-dak@gnu.org","subject":"[PATCH 3/5] builtin/blame.c: large-scale rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-03T19:14:07Z","receivedAt":"2014-02-03T19:14:07Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"The previous implementation uses a sorted linear list of struct\nblame_entry in a struct scoreboard for organizing all partial or\ncompleted work.  Every task that is done requires going through the\nwhole list where most entries are not relevant to the task at hand.\n\nThis commit reorganizes the data structures in order to have each\nremaining subtask work with its own sorted linear list it can work off\nfront to back.  Subtasks are organized into \"struct origin\" chains\nhanging off particular commits.  Commits are organized into a priority\nqueue, processing them in commit date order in order to keep most of\nthe work affecting a particular blob collated even in the presence of\nan extensive merge history.  In that manner, linear searches can be\nbasically avoided anywhere.  They still are done for identifying one\nof multiple analyzed files in a given commit, but the degenerate case\nof a single large file being assembled from a multitude of smaller\nfiles in the past is not likely to occur often enough to warrant\nspecial treatment.\n---\n builtin/blame.c | 559 ++++++++++++++++++++++++++++++++++++--------------------\n 1 file changed, 358 insertions(+), 201 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex ead6148..e881b6e 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -18,7 +18,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 +85,43 @@ 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/* shipped gets set when shipping any suspects to the final\n+\t * blame list instead of other commits\n+\t */\n+\tchar shipped;\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,11 +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@@ -230,12 +275,88 @@ struct blame_entry {\n \tunsigned score;\n };\n \n+/* This is subtle.  Any _merge_ of blames happens on lists of blames\n+ * that arrived via different parents in a single suspect.  In this\n+ * case, we want to sort according to the _suspect_ line numbers.  In\n+ * contrast to that, blame_sort is used for the final sorting of blame\n+ * data and consequently works with final image line numbers.\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+static int\n+compare_blame (const void *p1, const void *p2)\n+{\n+\treturn ((struct blame_entry *)p1)->lno - ((struct blame_entry *)p2)->lno;\n+}\n+\n+static struct blame_entry *\n+blame_sort (struct blame_entry *head)\n+{\n+\treturn llist_mergesort (head, get_next_blame, set_next_blame, compare_blame);\n+}\n+\n+int compare_commits_by_reverse_commit_date(const void *a, const void *b, 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 +389,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@@ -295,23 +415,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 +479,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 +557,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@@ -508,49 +602,53 @@ static struct origin *find_rename(struct scoreboard *sb,\n \treturn porigin;\n }\n \n+#if 0\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+ * Add 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 blame_entry that is allocated in one queue and will be relocated\n+ * to another.\n  */\n-static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n+static void dup_entry(struct blame_entry ***dstq, struct blame_entry ***srcq,\n+\t\t      struct blame_entry *src)\n {\n-\tstruct blame_entry *n;\n-\n-\tn = dst->next;\n+\tstruct blame_entry *dst = **srcq;\n \torigin_incref(src->suspect);\n \torigin_decref(dst->suspect);\n+\t**srcq = dst->next;\t/* unlinked from source queue */\n \tmemcpy(dst, src, sizeof(*src));\n-\tdst->next = n;\n \tdst->score = 0;\n+\tdst->next = **dstq;\n+\t*dstq = &dst->next;\t/* linked into destination queue */\n }\n \n+/* This copies a changed entry over the existing entry in the queue */\n+static void trim_entry(struct blame_entry ***queue, struct blame_entry *src)\n+{\n+\tstruct blame_entry *dst = **queue;\n+\tstruct blame_entry *n = dst->next;\n+\t/* No need to mess with reference counts as we stay with the\n+\t * same suspect\n+\t */\n+\tmemcpy(dst, src, sizeof(*src));\n+\tdst->score = 0;\n+\tdst->next = n;\n+\t*queue = &dst->next;\t/* move after entry */\n+}\n+\n+#endif\n+\n static const char *nth_line(struct scoreboard *sb, long lno)\n {\n \treturn sb->final_buf + sb->lineno[lno];\n@@ -561,6 +659,7 @@ static const char *nth_line_cb(void *data, long lno)\n \treturn nth_line((struct scoreboard *)data, lno);\n }\n \n+#if 0\n /*\n  * It is known that lines between tlno to same came from parent, and e\n  * has an overlap with that range.  it also is known that parent's\n@@ -573,7 +672,10 @@ static const char *nth_line_cb(void *data, long lno)\n  *             <------------------>\n  *\n  * Split e into potentially three parts; before this chunk, the chunk\n- * to be blamed for the parent, and after that portion.\n+ * to be blamed for the parent, and after that portion.  As the chunks\n+ * are processed in sequence, any part before the overlap can be\n+ * terminally blamed on the target while parts after the overlap can\n+ * only be properly evaluated after examining future diffs.\n  */\n static void split_overlap(struct blame_entry *split,\n \t\t\t  struct blame_entry *e,\n@@ -620,72 +722,55 @@ 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- * reflect the split.\n+ * in split.  Adjust the linked list of blames to reflect the split,\n+ * the first part being common to target and parent and consequently\n+ * being blamed on the parent, the second part being different and\n+ * consequently blamed on the target, and the third part starting out\n+ * as being the same but without conclusive information where to place\n+ * the blame, so leaving it in the target subject to further\n+ * processing.\n  */\n-static void split_blame(struct scoreboard *sb,\n-\t\t\tstruct blame_entry *split,\n-\t\t\tstruct blame_entry *e)\n+static void split_blame(struct blame_entry *split,\n+\t\t\tstruct blame_entry ***dstq,\n+\t\t\tstruct blame_entry ***srcq)\n {\n \tstruct blame_entry *new_entry;\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\ttrim_entry(srcq, &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(srcq, 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(dstq, 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(dstq, srcq, &split[1]);\n \telse if (split[0].suspect) {\n \t\t/* me and then parent */\n-\t\tdup_entry(e, &split[0]);\n+\t\ttrim_entry(srcq, &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(dstq, new_entry);\n \t}\n \telse {\n \t\t/* parent and then me */\n-\t\tdup_entry(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+\t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n+\t\tadd_blame_entry(dstq, new_entry);\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\ttrim_entry(srcq, &split[2]);\n \t}\n }\n \n@@ -702,74 +787,116 @@ 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+ * Helper for blame_chunk().  blame_entry in srcq is known to overlap with\n  * the patch hunk; split it and pass blame to the parent.\n  */\n-static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,\n+static void blame_overlap(struct blame entry ***dstq, struct blame_entry ***srcq,\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+\tsplit_overlap(split, **srcq, tlno, plno, same, parent);\n \tif (split[1].suspect)\n-\t\tsplit_blame(sb, split, e);\n+\t  split_blame(split, dstq, srcq);\n \tdecref_split(split);\n }\n+#endif\n \n /*\n- * Find the line number of the last line the target is suspected for.\n+ * Process one hunk from the patch between the current suspect for\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.\n  */\n-static int find_last_in_target(struct scoreboard *sb, struct origin *target)\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 *target, struct origin *parent)\n {\n-\tstruct blame_entry *e;\n-\tint last_in_target = -1;\n+\tstruct blame_entry *e = **srcq;\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+/* Pass blame for everything before the differing chunk to the parent */\n+\twhile (e && e->s_lno + e->num_lines <= tlno) {\n+\t\t**dstq = e;\n+\t\torigin_decref(e->suspect);\n+\t\te->suspect = origin_incref(parent);\n+\t\te->s_lno += offset;\n+\t\te = *(*dstq = &e->next);\n \t}\n-\treturn last_in_target;\n-}\n-\n+\t**srcq = e;\n+\tif (!e)\n+\t\treturn;\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+ * current record _ends_ after the start of the difference region.  If\n+ * it starts before it, we need to split it up and pass blame for its\n+ * first part to the parent.\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-{\n-\tstruct blame_entry *e;\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+\tif (e->s_lno < tlno) {\n+\t\t/* we move the first half to a new record */\n+\t\tint len = tlno - e->s_lno;\n+\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n+\t\tn->suspect = origin_incref(parent);\n+\t\tn->lno = e->lno;\n+\t\tn->s_lno = e->s_lno + offset;\n+\t\tn->num_lines = len;\n+\t\tn->score = 0;\n+\t\t**dstq = n;\n+\t\t*dstq = &n->next;\n+\n+\t\te->lno += len;\n+\t\te->s_lno = tlno;\n+\t\te->num_lines -= len;\n+\t\te->score = 0;\n+\t}\n+/*\n+ * Now retain records on the target while it is different from the parent.\n+ */\n+\twhile (e->s_lno + e->num_lines <= same) {\n+\t\te = *(*srcq = &e->next);\n+\t\tif (!e)\n+\t\t\treturn;\n \t}\n+/*\n+ * If current record starts before sameness, need to split.\n+ */\n+\tif (e->s_lno < same) {\n+\t\tint len = same - e->s_lno;\n+\t\tstruct blame_entry *n = xcalloc(1, sizeof(struct blame_entry));\n+\t\tn->suspect = origin_incref(target);\n+\t\tn->lno = e->lno;\n+\t\tn->s_lno = e->s_lno;\n+\t\tn->num_lines = len;\n+\t\tn->score = 0;\n+\t\t**srcq = n;\n+\t\t*(*srcq = &n->next) = e;\n+\t\t/* keep second half in target queue */\n+\t\te->lno += len;\n+\t\te->s_lno = same;\n+\t\te->num_lines -= len;\n+\t\te->score = 0;\n+\t}\n+\treturn;\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->target, d->parent);\n+\td->offset = start_a + count_a - (start_b + count_b);\n \treturn 0;\n }\n \n@@ -782,23 +909,28 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n \t\t\t\tstruct origin *target,\n \t\t\t\tstruct 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+\tif (!target->suspects)\n \t\treturn 1; /* nothing remains for this target */\n \n+\td.target = target; d.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, target, parent);\n+\t*d.dstq = NULL;\n+\tparent->suspects = blame_merge(parent->suspects, newdest);\n+\tif (parent->suspects)\n+\t\tprio_queue_put(&sb->commits, parent->commit);\n \n \treturn 0;\n }\n@@ -833,6 +965,7 @@ static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)\n \treturn score;\n }\n \n+#if 0\n /*\n  * best_so_far[] and this[] are both a split of an existing blame_entry\n  * that passes blame to the parent.  Maintain best_so_far the best split\n@@ -1147,6 +1280,8 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \treturn retval;\n }\n \n+#endif\n+\n /*\n  * The blobs of origin and porigin exactly match, so everything\n  * origin is suspected for can be blamed on the parent.\n@@ -1154,20 +1289,22 @@ 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+\tporigin->suspects = blame_merge(porigin->suspects, suspects);\n+\tprio_queue_put(&sb->commits, porigin->commit);\n }\n \n /*\n@@ -1266,6 +1403,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n \t\t\tgoto finish;\n \t}\n \n+#if 0\n \t/*\n \t * Optionally find moves in parents' files.\n \t */\n@@ -1292,6 +1430,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n \t\t\t\t\t\tporigin, opt))\n \t\t\t\tgoto finish;\n \t\t}\n+#endif\n \n  finish:\n \tfor (i = 0; i < num_sg; i++) {\n@@ -1488,14 +1627,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@@ -1509,32 +1645,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@@ -1550,9 +1688,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@@ -1609,9 +1760,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@@ -1724,17 +1874,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@@ -2083,7 +2232,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@@ -2394,12 +2542,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@@ -2493,7 +2645,7 @@ parse_done:\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@@ -2501,11 +2653,16 @@ parse_done:\n \tif (!incremental)\n \t\tsetup_pager();\n \n+\tprio_queue_put(&sb.commits, o->commit);\n+\to->suspects = ent;\n+\n \tassign_blame(&sb, opt);\n \n \tif (incremental)\n \t\treturn 0;\n \n+\tsb.ent = blame_sort(sb.ent);\n+\n \tcoalesce(&sb);\n \n \tif (!(output_option & OUTPUT_PORCELAIN))\n-- \n1.8.3.2\n"},{"id":"234127","messageId":"1391454849-26558-5-git-send-email-dak@gnu.org","threadId":"35788","inReplyTo":"1391454849-26558-1-git-send-email-dak@gnu.org","subject":"[PATCH 4/5] Performance improvement: don't drop origin blobs that are going to get tested next.","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-03T19:14:08Z","receivedAt":"2014-02-03T19:14:08Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"---\n builtin/blame.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex e881b6e..0188115 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1435,7 +1435,8 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n  finish:\n \tfor (i = 0; i < num_sg; i++) {\n \t\tif (sg_origin[i]) {\n-\t\t\tdrop_origin_blob(sg_origin[i]);\n+\t\t\tif (!sg_origin[i]->suspects)\n+\t\t\t\tdrop_origin_blob(sg_origin[i]);\n \t\t\torigin_decref(sg_origin[i]);\n \t\t}\n \t}\n-- \n1.8.3.2\n"},{"id":"234129","messageId":"1391454849-26558-6-git-send-email-dak@gnu.org","threadId":"35788","inReplyTo":"1391454849-26558-1-git-send-email-dak@gnu.org","subject":"[PATCH 5/5] Avoid queuing commits multiple times for the same origin","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-03T19:14:09Z","receivedAt":"2014-02-03T19:14:09Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"---\n builtin/blame.c | 13 ++++++++++---\n 1 file changed, 10 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex 0188115..80345db 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -928,9 +928,12 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n \t/* The rest are the same as the parent */\n \tblame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, target, parent);\n \t*d.dstq = NULL;\n-\tparent->suspects = blame_merge(parent->suspects, newdest);\n \tif (parent->suspects)\n+\t\tparent->suspects = blame_merge(parent->suspects, newdest);\n+\telse if (newdest) {\n+\t\tparent->suspects = newdest;\n \t\tprio_queue_put(&sb->commits, parent->commit);\n+\t}\n \n \treturn 0;\n }\n@@ -1303,8 +1306,12 @@ static void pass_whole_blame(struct scoreboard *sb,\n \t\torigin_decref(e->suspect);\n \t\te->suspect = porigin;\n \t}\n-\tporigin->suspects = blame_merge(porigin->suspects, suspects);\n-\tprio_queue_put(&sb->commits, porigin->commit);\n+\tif (porigin->suspects)\n+\t\tporigin->suspects = blame_merge(porigin->suspects, suspects);\n+\telse if (suspects) {\n+\t\tporigin->suspects = suspects;\n+\t\tprio_queue_put(&sb->commits, porigin->commit);\n+\t}\n }\n \n /*\n-- \n1.8.3.2\n"}]}