{"thread":{"id":"14473","subject":"[RFC/PATCH 0/2] Enhance performance of blame -C -C","startedAt":"2008-07-15T21:58:34Z","lastAt":"2008-07-15T22:25:29Z","messageCount":5,"participants":["Alexander Gavrilov","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"83441","messageId":"200807160158.34994.angavrilov@gmail.com","threadId":"14473","inReplyTo":null,"subject":"[RFC/PATCH 0/2] Enhance performance of blame -C -C","fromName":"Alexander Gavrilov","fromEmail":"angavrilov@gmail.com","sentAt":"2008-07-15T21:58:34Z","receivedAt":"2008-07-15T21:58:34Z","isPatch":true,"sender":{"key":"angavrilov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42666?v=4"},"body":"This pair of patches aims at increasing performance of copy detection in blame\nby avoiding unnecessary comparisons. Note that since I'm new to this code, I\nmight have misunderstood something.\n\nThere are two cases than I aim to fix:\n\n1) Copy detection is done by comparing all outstanding chunks of the target file\n  to all blobs in the parent. After that, chunks with suitable matches are split, and\n  comparison is repeated again, until there are no new matches. The trouble is,\n  chunks that didn't match the first time, and weren't split, are compared against\n  the same set of blobs again and again. I add a flag to track that.\n\n  On my test case it decreased blame -C -C time from over 10min to ~6min; 4min with -C80.\n\n2) Chunks are split only if the match scores above a certain threshold. I understand\n  that a split of an entry cannot score more than the entry itself. Thus, it is pointless\n  to even try doing costly comparisons for small entries.\n\n  (Time goes down to 4min; 2min with -C80)\n\n\n\nAlexander Gavrilov (2):\n      Avoid rescanning unchanged entries in search for copies.\n      Do not try to detect move/copy for entries below threshold.\n\n\n builtin-blame.c |   33 ++++++++++++++++++++++++++++-----\n 1 files changed, 28 insertions(+), 5 deletions(-)\n\n\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex b451f6c..01453e2 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -161,6 +161,10 @@ struct blame_entry {\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@@ -1016,7 +1020,8 @@ 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 || !same_suspect(e->suspect, target) ||\n+\t\t\t    blame_move_score >= ent_score(sb, e))\n \t\t\t\tcontinue;\n \t\t\tfind_copy_in_blob(sb, e, parent, split, &file_p);\n \t\t\tif (split[1].suspect &&\n@@ -1041,6 +1046,7 @@ struct blame_list {\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 \t\t\t\t\t   int *num_ents_p)\n {\n \tstruct blame_entry *e;\n@@ -1048,12 +1054,16 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\n \tstruct blame_list *blame_list = NULL;\n \n \tfor (e = sb->ent, num_ents = 0; e; e = e->next)\n-\t\tif (!e->guilty && same_suspect(e->suspect, target))\n+\t\tif (!e->scanned && !e->guilty &&\n+\t\t    same_suspect(e->suspect, target) &&\n+\t\t    ent_score(sb, e) > min_score)\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->guilty && same_suspect(e->suspect, target))\n+\t\t\tif (!e->scanned && !e->guilty &&\n+\t\t\t    same_suspect(e->suspect, target) &&\n+\t\t\t    ent_score(sb, e) > min_score)\n \t\t\t\tblame_list[i++].ent = e;\n \t}\n \t*num_ents_p = num_ents;\n@@ -1061,6 +1071,16 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\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@@ -1078,7 +1098,7 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \tstruct blame_list *blame_list;\n \tint num_ents;\n \n-\tblame_list = setup_blame_list(sb, target, &num_ents);\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 \n@@ -1152,18 +1172,21 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \t\t\t\tsplit_blame(sb, split, blame_list[j].ent);\n \t\t\t\tmade_progress = 1;\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, &num_ents);\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 \tdiff_flush(&diff_opts);\n \tdiff_tree_release_paths(&diff_opts);\n \treturn retval;\n"},{"id":"83442","messageId":"200807160159.56228.angavrilov@gmail.com","threadId":"14473","inReplyTo":"200807160158.34994.angavrilov@gmail.com","subject":"[RFC/PATCH 1/2] Avoid rescanning unchanged entries in search for copies.","fromName":"Alexander Gavrilov","fromEmail":"angavrilov@gmail.com","sentAt":"2008-07-15T21:59:56Z","receivedAt":"2008-07-15T21:59:56Z","isPatch":true,"sender":{"key":"angavrilov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42666?v=4"},"body":"Repeatedly comparing the same entry against the same set\nof blobs in search for copies is quite pointless. This\nhuge waste of effort can be avoided using a flag in\nthe blame_entry structure.\n\nSigned-off-by: Alexander Gavrilov <angavrilov@gmail.com>\n---\n builtin-blame.c |   21 +++++++++++++++++++--\n 1 files changed, 19 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex b451f6c..a6cf6b6 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -161,6 +161,10 @@ struct blame_entry {\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@@ -1048,12 +1052,12 @@ static struct blame_list *setup_blame_list(struct \nscoreboard *sb,\n \tstruct blame_list *blame_list = NULL;\n \n \tfor (e = sb->ent, num_ents = 0; e; e = e->next)\n-\t\tif (!e->guilty && same_suspect(e->suspect, target))\n+\t\tif (!e->scanned && !e->guilty && same_suspect(e->suspect, target))\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->guilty && same_suspect(e->suspect, target))\n+\t\t\tif (!e->scanned && !e->guilty && same_suspect(e->suspect, target))\n \t\t\t\tblame_list[i++].ent = e;\n \t}\n \t*num_ents_p = num_ents;\n@@ -1061,6 +1065,16 @@ static struct blame_list *setup_blame_list(struct \nscoreboard *sb,\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@@ -1152,6 +1166,8 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \t\t\t\tsplit_blame(sb, split, blame_list[j].ent);\n \t\t\t\tmade_progress = 1;\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@@ -1164,6 +1180,7 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \t\t\tbreak;\n \t\t}\n \t}\n+\treset_scanned_flag(sb);\n \tdiff_flush(&diff_opts);\n \tdiff_tree_release_paths(&diff_opts);\n \treturn retval;\n-- \n1.5.6.2.39.gd084\n"},{"id":"83443","messageId":"200807160200.58603.angavrilov@gmail.com","threadId":"14473","inReplyTo":"200807160159.56228.angavrilov@gmail.com","subject":"[RFC/PATCH 2/2] Do not try to detect move/copy for entries below threshold.","fromName":"Alexander Gavrilov","fromEmail":"angavrilov@gmail.com","sentAt":"2008-07-15T22:00:58Z","receivedAt":"2008-07-15T22:00:58Z","isPatch":true,"sender":{"key":"angavrilov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42666?v=4"},"body":"Splits for such entries are rejected anyway, so there is no\npoint even trying to compute them.\n\nSigned-off-by: Alexander Gavrilov <angavrilov@gmail.com>\n---\n builtin-blame.c |   16 +++++++++++-----\n 1 files changed, 11 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex a6cf6b6..01453e2 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -1020,7 +1020,8 @@ 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 || !same_suspect(e->suspect, target) ||\n+\t\t\t    blame_move_score >= ent_score(sb, e))\n \t\t\t\tcontinue;\n \t\t\tfind_copy_in_blob(sb, e, parent, split, &file_p);\n \t\t\tif (split[1].suspect &&\n@@ -1045,6 +1046,7 @@ struct blame_list {\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 \t\t\t\t\t   int *num_ents_p)\n {\n \tstruct blame_entry *e;\n@@ -1052,12 +1054,16 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\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 && same_suspect(e->suspect, target))\n+\t\tif (!e->scanned && !e->guilty &&\n+\t\t    same_suspect(e->suspect, target) &&\n+\t\t    ent_score(sb, e) > min_score)\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 && same_suspect(e->suspect, target))\n+\t\t\tif (!e->scanned && !e->guilty &&\n+\t\t\t    same_suspect(e->suspect, target) &&\n+\t\t\t    ent_score(sb, e) > min_score)\n \t\t\t\tblame_list[i++].ent = e;\n \t}\n \t*num_ents_p = num_ents;\n@@ -1092,7 +1098,7 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \tstruct blame_list *blame_list;\n \tint num_ents;\n \n-\tblame_list = setup_blame_list(sb, target, &num_ents);\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 \n@@ -1174,7 +1180,7 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \n \t\tif (!made_progress)\n \t\t\tbreak;\n-\t\tblame_list = setup_blame_list(sb, target, &num_ents);\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-- \n1.5.6.2.39.gd084\n"},{"id":"83444","messageId":"200807160205.20908.angavrilov@gmail.com","threadId":"14473","inReplyTo":"200807160159.56228.angavrilov@gmail.com","subject":"[RFC/PATCH 1/2 (No Wrap)] Avoid rescanning unchanged entries in search for copies.","fromName":"Alexander Gavrilov","fromEmail":"angavrilov@gmail.com","sentAt":"2008-07-15T22:05:20Z","receivedAt":"2008-07-15T22:05:20Z","isPatch":true,"sender":{"key":"angavrilov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42666?v=4"},"body":"Repeatedly comparing the same entry against the same set\nof blobs in search for copies is quite pointless. This\nhuge waste of effort can be avoided using a flag in\nthe blame_entry structure.\n\nSigned-off-by: Alexander Gavrilov <angavrilov@gmail.com>\n---\n\n\tI'm terribly sorry, word wrap was turned on. I disabled it permanently.\n\n\t-- Alexander\n\n builtin-blame.c |   21 +++++++++++++++++++--\n 1 files changed, 19 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex b451f6c..a6cf6b6 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -161,6 +161,10 @@ struct blame_entry {\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@@ -1048,12 +1052,12 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\n \tstruct blame_list *blame_list = NULL;\n \n \tfor (e = sb->ent, num_ents = 0; e; e = e->next)\n-\t\tif (!e->guilty && same_suspect(e->suspect, target))\n+\t\tif (!e->scanned && !e->guilty && same_suspect(e->suspect, target))\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->guilty && same_suspect(e->suspect, target))\n+\t\t\tif (!e->scanned && !e->guilty && same_suspect(e->suspect, target))\n \t\t\t\tblame_list[i++].ent = e;\n \t}\n \t*num_ents_p = num_ents;\n@@ -1061,6 +1065,16 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\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@@ -1152,6 +1166,8 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \t\t\t\tsplit_blame(sb, split, blame_list[j].ent);\n \t\t\t\tmade_progress = 1;\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@@ -1164,6 +1180,7 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \t\t\tbreak;\n \t\t}\n \t}\n+\treset_scanned_flag(sb);\n \tdiff_flush(&diff_opts);\n \tdiff_tree_release_paths(&diff_opts);\n \treturn retval;\n-- \n1.5.6.2.39.gd084\n"},{"id":"83447","messageId":"7vhcaqzsx2.fsf@gitster.siamese.dyndns.org","threadId":"14473","inReplyTo":"200807160158.34994.angavrilov@gmail.com","subject":"Re: [RFC/PATCH 0/2] Enhance performance of blame -C -C","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-15T22:25:29Z","receivedAt":"2008-07-15T22:25:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Gavrilov <angavrilov@gmail.com> writes:\n\n> This pair of patches aims at increasing performance of copy detection in\n> blame by avoiding unnecessary comparisons. Note that since I'm new to\n> this code, I might have misunderstood something.\n>\n> There are two cases than I aim to fix:\n>\n> 1) Copy detection is done by comparing all outstanding chunks of the\n> target file to all blobs in the parent. After that, chunks with suitable\n> matches are split, and comparison is repeated again, until there are no\n> new matches. The trouble is, chunks that didn't match the first time,\n> and weren't split, are compared against the same set of blobs again and\n> again. I add a flag to track that.\n>\n>   On my test case it decreased blame -C -C time from over 10min to\n>   ~6min; 4min with -C80.\n>\n> 2) Chunks are split only if the match scores above a certain\n> threshold. I understand that a split of an entry cannot score more than\n> the entry itself. Thus, it is pointless to even try doing costly\n> comparisons for small entries.\n>\n>   (Time goes down to 4min; 2min with -C80)\n\nIdeas for both patches sound very sane.  Will take a deeper look later.\n\nThanks.\n"}]}