{"thread":{"id":"24288","subject":"[PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","startedAt":"2010-07-05T06:06:57Z","lastAt":"2010-07-06T03:11:17Z","messageCount":7,"participants":["Dylan Reid","Michael J Gruber","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"144795","messageId":"1278310017-24299-1-git-send-email-dgreid@gmail.com","threadId":"24288","inReplyTo":null,"subject":"[PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Dylan Reid","fromEmail":"dgreid@gmail.com","sentAt":"2010-07-05T06:06:57Z","receivedAt":"2010-07-05T06:06:57Z","isPatch":true,"sender":{"key":"dgreid@gmail.com","avatar":"https://avatars.githubusercontent.com/u/113378?v=4"},"body":"Invert the order of the memcmp and flag check are done in xdl_recmatch,\nas it makes the common case (there is no whitespace difference) faster.\nIt costs the case where lines are the same length and contain\nwhitespace differences, but the common case is more than 20% faster.\n\nSigned-off-by: Dylan Reid \n---\n xdiff/xutils.c | 6 ++++--\n 1 files changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex bc12f29..dc97a21 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n {\n \tint i1, i2;\n \n-\tif (!(flags & XDF_WHITESPACE_FLAGS))\n-\t\treturn s1 == s2 && !memcmp(l1, l2, s1);\n+\tif (s1 == s2 && !memcmp(l1, l2, s1))\n+\t\treturn 1;\n+\telse if (!(flags & XDF_WHITESPACE_FLAGS))\n+\t\treturn 0;\n \n \ti1 = 0;\n \ti2 = 0;\n-- \n1.7.1\n"},{"id":"144803","messageId":"4C319931.4020603@drmicha.warpmail.net","threadId":"24288","inReplyTo":"1278310017-24299-1-git-send-email-dgreid@gmail.com","subject":"Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2010-07-05T08:34:57Z","receivedAt":"2010-07-05T08:34:57Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Dylan Reid venit, vidit, dixit 05.07.2010 08:06:\n> Invert the order of the memcmp and flag check are done in xdl_recmatch,\n\nI was wondering whether you describe old (before patch) or new (after\npatch) here. Maybe one of the following is clearer:\n\n\"Invert the order of the memcmp and flag check which are done in\nxdl_recmatch,\"\n\n\"Invert the order of the memcmp and flag check in xdl_recmatch,\"\n\n> as it makes the common case (there is no whitespace difference) faster.\n> It costs the case where lines are the same length and contain\n> whitespace differences, but the common case is more than 20% faster.\n> \n> Signed-off-by: Dylan Reid \n> ---\n> xdiff/xutils.c | 6 ++++--\n> 1 files changed, 4 insertions(+), 2 deletions(-)\n> \n> diff --git a/xdiff/xutils.c b/xdiff/xutils.c\n> index bc12f29..dc97a21 100644\n> --- a/xdiff/xutils.c\n> +++ b/xdiff/xutils.c\n> @@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n> {\n> \tint i1, i2;\n> \n> -\tif (!(flags & XDF_WHITESPACE_FLAGS))\n> -\t\treturn s1 == s2 && !memcmp(l1, l2, s1);\n> +\tif (s1 == s2 && !memcmp(l1, l2, s1))\n> +\t\treturn 1;\n> +\telse if (!(flags & XDF_WHITESPACE_FLAGS))\n\nYou can do without the \"else\" here.\n\n> +\t\treturn 0;\n> \n> \ti1 = 0;\n> \ti2 = 0;\n\nBTW: How did you find this? Are you profiling parts of git?\n\nMichael\n"},{"id":"144816","messageId":"AANLkTinmdeTSRVCTblnGrG5lGpNKCiYIb8BO8jMhajXW@mail.gmail.com","threadId":"24288","inReplyTo":"4C319931.4020603@drmicha.warpmail.net","subject":"Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Dylan Reid","fromEmail":"dgreid@gmail.com","sentAt":"2010-07-05T12:34:29Z","receivedAt":"2010-07-05T12:34:29Z","isPatch":true,"sender":{"key":"dgreid@gmail.com","avatar":"https://avatars.githubusercontent.com/u/113378?v=4"},"body":"On Mon, Jul 5, 2010 at 4:34 AM, Michael J Gruber\n wrote:\n> Dylan Reid venit, vidit, dixit 05.07.2010 08:06:\n>> Invert the order of the memcmp and flag check are done in xdl_recmatch,\n>\n> I was wondering whether you describe old (before patch) or new (after\n> patch) here. Maybe one of the following is clearer:\n>\n> \"Invert the order of the memcmp and flag check which are done in\n> xdl_recmatch,\"\n>\n> \"Invert the order of the memcmp and flag check in xdl_recmatch,\"\n>\n\nI'll make that more clear.\n\n>> +     if (s1 == s2 && !memcmp(l1, l2, s1))\n>> +             return 1;\n>> +     else if (!(flags & XDF_WHITESPACE_FLAGS))\n>\n> You can do without the \"else\" here.\n\nsure can, will do.\n\n>> +             return 0;\n>>\n>>       i1 = 0;\n>>       i2 = 0;\n>\n> BTW: How did you find this? Are you profiling parts of git?\n>\n> Michael\n>\n\nI was looking to add an unrelated feature and just happened to notice\nthis. It was a really cheap change for a good speedup.\n\nThanks,\n\nDylan\n"},{"id":"144820","messageId":"1278334842-9701-1-git-send-email-dgreid@gmail.com","threadId":"24288","inReplyTo":"1278310017-24299-1-git-send-email-dgreid@gmail.com","subject":"[PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Dylan Reid","fromEmail":"dgreid@gmail.com","sentAt":"2010-07-05T13:00:42Z","receivedAt":"2010-07-05T13:00:42Z","isPatch":true,"sender":{"key":"dgreid@gmail.com","avatar":"https://avatars.githubusercontent.com/u/113378?v=4"},"body":"In xdl_recmatch, do the memcmp to check if the two lines are equal before\nchecking if whitespace flags are set. If the lines are identicle, then\nthere is no need to check if they differ only in whitespace.\nThis makes the common case (there is no whitespace difference) faster.\nIt costs the case where lines are the same length and contain\nwhitespace differences, but the common case is more than 20% faster.\n\nSigned-off-by: Dylan Reid \n---\n xdiff/xutils.c | 4 +++-\n 1 files changed, 3 insertions(+), 1 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex bc12f29..22f9bd6 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n {\n \tint i1, i2;\n \n+\tif (s1 == s2 && !memcmp(l1, l2, s1))\n+\t\treturn 1;\n \tif (!(flags & XDF_WHITESPACE_FLAGS))\n-\t\treturn s1 == s2 && !memcmp(l1, l2, s1);\n+\t\treturn 0;\n \n \ti1 = 0;\n \ti2 = 0;\n-- \n1.7.1\n"},{"id":"144864","messageId":"7vsk3x72wb.fsf@alter.siamese.dyndns.org","threadId":"24288","inReplyTo":"1278334842-9701-1-git-send-email-dgreid@gmail.com","subject":"Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-07-06T02:36:04Z","receivedAt":"2010-07-06T02:36:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dylan Reid writes:\n\n> In xdl_recmatch, do the memcmp to check if the two lines are equal before\n> checking if whitespace flags are set. If the lines are identicle, then\n\n\"identical\"?\n\n> there is no need to check if they differ only in whitespace.\n> This makes the common case (there is no whitespace difference) faster.\n> It costs the case where lines are the same length and contain\n> whitespace differences, but the common case is more than 20% faster.\n\n\"more than 20% faster\" based on what dataset and benchmark?\n\n>\n> Signed-off-by: Dylan Reid \n> ---\n> xdiff/xutils.c | 4 +++-\n> 1 files changed, 3 insertions(+), 1 deletions(-)\n>\n> diff --git a/xdiff/xutils.c b/xdiff/xutils.c\n> index bc12f29..22f9bd6 100644\n> --- a/xdiff/xutils.c\n> +++ b/xdiff/xutils.c\n> @@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n> {\n> \tint i1, i2;\n> \n> +\tif (s1 == s2 && !memcmp(l1, l2, s1))\n> +\t\treturn 1;\n> \tif (!(flags & XDF_WHITESPACE_FLAGS))\n> -\t\treturn s1 == s2 && !memcmp(l1, l2, s1);\n> +\t\treturn 0;\n> \n> \ti1 = 0;\n> \ti2 = 0;\n> -- \n> 1.7.1\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":"144870","messageId":"AANLkTilkML1edHz6JSj7w3u60oFt3Va-5Z2ZBWVphxVI@mail.gmail.com","threadId":"24288","inReplyTo":"7vsk3x72wb.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Dylan Reid","fromEmail":"dgreid@gmail.com","sentAt":"2010-07-06T03:04:09Z","receivedAt":"2010-07-06T03:04:09Z","isPatch":true,"sender":{"key":"dgreid@gmail.com","avatar":"https://avatars.githubusercontent.com/u/113378?v=4"},"body":"On Mon, Jul 5, 2010 at 10:36 PM, Junio C Hamano wrote:\n> Dylan Reid writes:\n>\n>> In xdl_recmatch, do the memcmp to check if the two lines are equal before\n>> checking if whitespace flags are set.  If the lines are identicle, then\n>\n> \"identical\"?\n\nThat's exaclty what I meant. Correct patch sent.\n\n>\n>> there is no need to check if they differ only in whitespace.\n>> This makes the common case (there is no whitespace difference) faster.\n>> It costs the case where lines are the same length and contain\n>> whitespace differences, but the common case is more than 20% faster.\n>\n> \"more than 20% faster\" based on what dataset and benchmark?\n>\n\nI benchmarked it with some of the bigger files from Linux. The\nresults were consistenly > 20% faster\nacross different file sizes. I tested it by simply running the\ncommand a few times then running it with\nmy local build a few times to see if I had achieved any speedup.\n\n~/linux-2.6(119)$ time git blame --incremental -w\n./sound/pci/hda/patch_realtek.c > /dev/null\n\nreal 0m8.166s\nuser 0m8.063s\nsys 0m0.090s\n~/linux-2.6(120)$ time git blame --incremental -w\n./sound/pci/hda/patch_realtek.c > /dev/null\n\nreal 0m8.010s\nuser 0m7.866s\nsys 0m0.137s\n~/linux-2.6(121)$ time ~/work/git/git blame --incremental -w\n./sound/pci/hda/patch_realtek.c > /dev/null\n\nreal 0m6.115s\nuser 0m5.986s\nsys 0m0.123s\n~/linux-2.6(122)$ time ~/work/git/git blame --incremental -w\n./sound/pci/hda/patch_realtek.c > /dev/null\n\nreal 0m6.119s\nuser 0m5.986s\nsys 0m0.127s\n\n\nThanks for taking the time to read the patch.\n\nDylan\n"},{"id":"144868","messageId":"1278385877-13902-1-git-send-email-dgreid@gmail.com","threadId":"24288","inReplyTo":"1278310017-24299-1-git-send-email-dgreid@gmail.com","subject":"[PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.","fromName":"Dylan Reid","fromEmail":"dgreid@gmail.com","sentAt":"2010-07-06T03:11:17Z","receivedAt":"2010-07-06T03:11:17Z","isPatch":true,"sender":{"key":"dgreid@gmail.com","avatar":"https://avatars.githubusercontent.com/u/113378?v=4"},"body":"In xdl_recmatch, do the memcmp to check if the two lines are equal before\nchecking if whitespace flags are set. If the lines are identical, then\nthere is no need to check if they differ only in whitespace.\nThis makes the common case (there is no whitespace difference) faster.\nIt costs the case where lines are the same length and contain\nwhitespace differences, but the common case is more than 20% faster.\n\nSigned-off-by: Dylan Reid \n---\n xdiff/xutils.c | 4 +++-\n 1 files changed, 3 insertions(+), 1 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex bc12f29..22f9bd6 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n {\n \tint i1, i2;\n \n+\tif (s1 == s2 && !memcmp(l1, l2, s1))\n+\t\treturn 1;\n \tif (!(flags & XDF_WHITESPACE_FLAGS))\n-\t\treturn s1 == s2 && !memcmp(l1, l2, s1);\n+\t\treturn 0;\n \n \ti1 = 0;\n \ti2 = 0;\n-- \n1.7.1\n"}]}