{"thread":{"id":"5940","subject":"git-diff-tree inordinately (O(M*N)) slow on files with many changes","startedAt":"2006-10-16T14:12:51Z","lastAt":"2006-10-16T23:52:00Z","messageCount":27,"participants":["Jim Meyering","Linus Torvalds","Davide Libenzi","Jakub Narebski","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"28846","messageId":"87slhopcws.fsf@rho.meyering.net","threadId":"5940","inReplyTo":null,"subject":"git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jim Meyering","fromEmail":"jim@meyering.net","sentAt":"2006-10-16T14:12:51Z","receivedAt":"2006-10-16T14:12:51Z","isPatch":false,"sender":{"key":"jim@meyering.net","avatar":"https://avatars.githubusercontent.com/u/710630?v=4"},"body":"[using very latest code, built an hour ago:\n git version 1.4.3.rc3.gb32db-dirty ]\n\nI found that git-diff-tree is *very* slow when processing files with\nmany changes.  The offending example involves comparing the configure\nfile from coreutils-6.3 with that from the latest coreutils development\nsources.  Both are over 50k lines long, and the diff -u output is almost\n50k-lines long, divided into ~700 hunks.\n\n  http://meyering.net/code/git-perf/configure.gz\n  http://meyering.net/code/git-perf/configure-curr.gz\n\nComparing them with \"diff -u\" takes about 0.3s.\nPutting them in a git repo (uncompressed, and with the same name,\nof course) and comparing with git-diff-tree takes over a minute.\nThat's 200 times slower.\n\nI traced the problem to xdiff/xprepare.c's xdl_cleanup_records function.\nEach of its two doubly-nested loops ends up running the inner-loop\ncode more than 2 *billion* times.\n\nThat seems to be due to the two typos fixed by this patch:\nWith this patch, my \"git-diff-tree --no-commit-id -r -p 2c2172\"\ncommand completes in just 2 seconds.\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 1be7b31..e5438a9 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -381,7 +381,7 @@ static int xdl_cleanup_records(xdfile_t\n \t\thav = (*recs)->ha;\n \t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n \t\tfor (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n+\t\t\tif (rec->ha == hav || ++nm == mlim)\n \t\t\t\tbreak;\n \t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n \t}\n@@ -392,7 +392,7 @@ static int xdl_cleanup_records(xdfile_t\n \t\thav = (*recs)->ha;\n \t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n \t\tfor (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n+\t\t\tif (rec->ha == hav || ++nm == mlim)\n \t\t\t\tbreak;\n \t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n \t}\n\nHowever, that change causes the t800*.sh (14,16,18) annotate/blame\ntests to fail, so take it with a grain of salt.\n\nI.e., running one of them manually gave this:\n\n    $ sh t8001-annotate.sh --immediate --verbose\n    * expecting success: check_count A 2 B 1 B1 2 B2 1 \"A U Thor\" 1\n    Author A (expected 2, attributed 2) good\n    Author B1 (expected 2, attributed 1) bad\n    Author A U Thor (expected 1, attributed 2) bad\n    Author B2 (expected 1, attributed 1) good\n    Author B (expected 1, attributed 1) good\n    * FAIL 14: Two lines blamed on A, one on B, two on B1, one on B2, one on A U Thor\n            check_count A 2 B 1 B1 2 B2 1 \"A U Thor\" 1\n    [Exit 1]\n"},{"id":"28848","messageId":"Pine.LNX.4.64.0610160838200.3962@g5.osdl.org","threadId":"5940","inReplyTo":"87slhopcws.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T15:47:31Z","receivedAt":"2006-10-16T15:47:31Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nDavide? I'm quoting the whole report, because I suspect you don't follow \nthe git lists, and this is all original libxdiff code.\n\nJim: the annotation failure _may_ just be due to a \"valid\" diff change \n(there is not always a unique correct answer for a diff, and so two \ndifferent diff algorithms can validly give two different answers, which \nwill also mean that git-annotate/blame would give different explanations). \n\nBut it could certainly also be that you just broke the diffs entirely, so \nI would like to wait for Davide to comment on your diff before Junio \nshould apply it. \n\nOthers may be intimately familiar with the diff algorithms too, of course. \nIt just scares me personally ;)\n\n\t\tLinus\n\nOn Mon, 16 Oct 2006, Jim Meyering wrote:\n>\n> [using very latest code, built an hour ago:\n>  git version 1.4.3.rc3.gb32db-dirty ]\n> \n> I found that git-diff-tree is *very* slow when processing files with\n> many changes.  The offending example involves comparing the configure\n> file from coreutils-6.3 with that from the latest coreutils development\n> sources.  Both are over 50k lines long, and the diff -u output is almost\n> 50k-lines long, divided into ~700 hunks.\n> \n>   http://meyering.net/code/git-perf/configure.gz\n>   http://meyering.net/code/git-perf/configure-curr.gz\n> \n> Comparing them with \"diff -u\" takes about 0.3s.\n> Putting them in a git repo (uncompressed, and with the same name,\n> of course) and comparing with git-diff-tree takes over a minute.\n> That's 200 times slower.\n> \n> I traced the problem to xdiff/xprepare.c's xdl_cleanup_records function.\n> Each of its two doubly-nested loops ends up running the inner-loop\n> code more than 2 *billion* times.\n> \n> That seems to be due to the two typos fixed by this patch:\n> With this patch, my \"git-diff-tree --no-commit-id -r -p 2c2172\"\n> command completes in just 2 seconds.\n> \n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index 1be7b31..e5438a9 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -381,7 +381,7 @@ static int xdl_cleanup_records(xdfile_t\n>  \t\thav = (*recs)->ha;\n>  \t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n>  \t\tfor (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n> -\t\t\tif (rec->ha == hav && ++nm == mlim)\n> +\t\t\tif (rec->ha == hav || ++nm == mlim)\n>  \t\t\t\tbreak;\n>  \t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n>  \t}\n> @@ -392,7 +392,7 @@ static int xdl_cleanup_records(xdfile_t\n>  \t\thav = (*recs)->ha;\n>  \t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n>  \t\tfor (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n> -\t\t\tif (rec->ha == hav && ++nm == mlim)\n> +\t\t\tif (rec->ha == hav || ++nm == mlim)\n>  \t\t\t\tbreak;\n>  \t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n>  \t}\n> \n> However, that change causes the t800*.sh (14,16,18) annotate/blame\n> tests to fail, so take it with a grain of salt.\n> \n> I.e., running one of them manually gave this:\n> \n>     $ sh t8001-annotate.sh --immediate --verbose\n>     * expecting success: check_count A 2 B 1 B1 2 B2 1 \"A U Thor\" 1\n>     Author A (expected 2, attributed 2) good\n>     Author B1 (expected 2, attributed 1) bad\n>     Author A U Thor (expected 1, attributed 2) bad\n>     Author B2 (expected 1, attributed 1) good\n>     Author B (expected 1, attributed 1) good\n>     * FAIL 14: Two lines blamed on A, one on B, two on B1, one on B2, one on A U Thor\n>             check_count A 2 B 1 B1 2 B2 1 \"A U Thor\" 1\n>     [Exit 1]\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> \n"},{"id":"28849","messageId":"Pine.LNX.4.64.0610160904400.3962@g5.osdl.org","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160838200.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T16:12:35Z","receivedAt":"2006-10-16T16:12:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Oct 2006, Linus Torvalds wrote:\n> \n> But it could certainly also be that you just broke the diffs entirely, so \n> I would like to wait for Davide to comment on your diff before Junio \n> should apply it. \n\nI think you broke it. \n\nIf the \"&& vs ||\" makes a difference (and it clearly does), that implies \nthat you have lots of different hash values on the same hash chain, and \nyou end up considering those _different_ hash values to be all equivalent \nfor the counting, even though they obviously aren't.\n\nI think the real problem is that with big input, the hash tables are too \nsmall, making the hash chains too long - even though the values on the \nchains are different (ie we're not hashing different records with the same \nhash value over and over again - if that was true, the \"&& vs ||\" change \nwouldn't make any difference).\n\nSo I think xdiff has chosen too small a hash. Can you try what happens if \nyou change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return \na bigger value (for example, by initializing \"bits\" to 2 instead of 0), \nand see if that makes a difference.\n\nBut again, I'm not actually all _that_ familiar with the libxdiff \nalgorithms, _especially_ the line-based ones (I can follow the regular \nbinary delta code, but the line-based one just makes my head hurt). So \ntake anything I say with a pinch of salt.\n\n\t\tLinus\n"},{"id":"28850","messageId":"Pine.LNX.4.64.0610160920250.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160838200.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T16:24:58Z","receivedAt":"2006-10-16T16:24:58Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Linus Torvalds wrote:\n\n> \n> Davide? I'm quoting the whole report, because I suspect you don't follow \n> the git lists, and this is all original libxdiff code.\n> \n> Jim: the annotation failure _may_ just be due to a \"valid\" diff change \n> (there is not always a unique correct answer for a diff, and so two \n> different diff algorithms can validly give two different answers, which \n> will also mean that git-annotate/blame would give different explanations). \n> \n> But it could certainly also be that you just broke the diffs entirely, so \n> I would like to wait for Davide to comment on your diff before Junio \n> should apply it. \n> \n> Others may be intimately familiar with the diff algorithms too, of course. \n> It just scares me personally ;)\n\nThe test is fine as is. Only really bad hash collisions can show O(M*N). \nCan I have the two sample files to test?\n\n\n\n- Davide\n"},{"id":"28851","messageId":"87mz7wp6ek.fsf@rho.meyering.net","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160904400.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jim Meyering","fromEmail":"jim@meyering.net","sentAt":"2006-10-16T16:33:23Z","receivedAt":"2006-10-16T16:33:23Z","isPatch":false,"sender":{"key":"jim@meyering.net","avatar":"https://avatars.githubusercontent.com/u/710630?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> wrote:\n> On Mon, 16 Oct 2006, Linus Torvalds wrote:\n...\n> So I think xdiff has chosen too small a hash. Can you try what happens if\n> you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return\n> a bigger value (for example, by initializing \"bits\" to 2 instead of 0),\n> and see if that makes a difference.\n\nIt makes no difference.\n\nBear in mind that there are a *lot* of duplicate lines in the files\nbeing compared: filtering each through \"sort -u\" removes 40-50k lines.\n"},{"id":"28852","messageId":"Pine.LNX.4.64.0610160932100.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160904400.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T16:36:06Z","receivedAt":"2006-10-16T16:36:06Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Linus Torvalds wrote:\n\n> On Mon, 16 Oct 2006, Linus Torvalds wrote:\n> > \n> > But it could certainly also be that you just broke the diffs entirely, so \n> > I would like to wait for Davide to comment on your diff before Junio \n> > should apply it. \n> \n> I think you broke it. \n> \n> If the \"&& vs ||\" makes a difference (and it clearly does), that implies \n> that you have lots of different hash values on the same hash chain, and \n> you end up considering those _different_ hash values to be all equivalent \n> for the counting, even though they obviously aren't.\n> \n> I think the real problem is that with big input, the hash tables are too \n> small, making the hash chains too long - even though the values on the \n> chains are different (ie we're not hashing different records with the same \n> hash value over and over again - if that was true, the \"&& vs ||\" change \n> wouldn't make any difference).\n> \n> So I think xdiff has chosen too small a hash. Can you try what happens if \n> you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return \n> a bigger value (for example, by initializing \"bits\" to 2 instead of 0), \n> and see if that makes a difference.\n\nI think the xdl_hashbits() picks up the hash table size \"almost\" \ncorrectly. I think we're looking at some bad hash *collisions* (not \nrecords with same hash value, that'd be stopped by the mlim check). \nSend me the files and I'll take a look ...\n\n\n\n\n> But again, I'm not actually all _that_ familiar with the libxdiff \n> algorithms, _especially_ the line-based ones (I can follow the regular \n> binary delta code, but the line-based one just makes my head hurt). So \n> take anything I say with a pinch of salt.\n\nThat's my revenge on myself having to follow your code in the kernel  :D\n\n\n\n\n- Davide\n"},{"id":"28853","messageId":"Pine.LNX.4.64.0610160941270.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"87mz7wp6ek.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T16:42:04Z","receivedAt":"2006-10-16T16:42:04Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Jim Meyering wrote:\n\n> Linus Torvalds <torvalds@osdl.org> wrote:\n> > On Mon, 16 Oct 2006, Linus Torvalds wrote:\n> ...\n> > So I think xdiff has chosen too small a hash. Can you try what happens if\n> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return\n> > a bigger value (for example, by initializing \"bits\" to 2 instead of 0),\n> > and see if that makes a difference.\n> \n> It makes no difference.\n> \n> Bear in mind that there are a *lot* of duplicate lines in the files\n> being compared: filtering each through \"sort -u\" removes 40-50k lines.\n\nOk, try to bring down XDL_MAX_EQLIMIT to something like 8 or 16 ...\n\n\n\n- Davide\n"},{"id":"28854","messageId":"87ejt8p5l9.fsf@rho.meyering.net","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160941270.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jim Meyering","fromEmail":"jim@meyering.net","sentAt":"2006-10-16T16:50:58Z","receivedAt":"2006-10-16T16:50:58Z","isPatch":false,"sender":{"key":"jim@meyering.net","avatar":"https://avatars.githubusercontent.com/u/710630?v=4"},"body":"Davide Libenzi <davidel@xmailserver.org> wrote:\n> On Mon, 16 Oct 2006, Jim Meyering wrote:\n>\n>> Linus Torvalds <torvalds@osdl.org> wrote:\n>> > On Mon, 16 Oct 2006, Linus Torvalds wrote:\n>> ...\n>> > So I think xdiff has chosen too small a hash. Can you try what happens if\n>> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return\n>> > a bigger value (for example, by initializing \"bits\" to 2 instead of 0),\n>> > and see if that makes a difference.\n>>\n>> It makes no difference.\n>>\n>> Bear in mind that there are a *lot* of duplicate lines in the files\n>> being compared: filtering each through \"sort -u\" removes 40-50k lines.\n>\n> Ok, try to bring down XDL_MAX_EQLIMIT to something like 8 or 16 ...\n\nThat helps a little.\nNow, instead of taking 63s, my test takes ~30s.\n(32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n"},{"id":"28855","messageId":"eh0del$g4t$1@sea.gmane.org","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160920250.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-10-16T16:54:08Z","receivedAt":"2006-10-16T16:54:08Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"<opublikowany i wysłany>\n\nDavide Libenzi wrote:\n\n> The test is fine as is. Only really bad hash collisions can show O(M*N). \n> Can I have the two sample files to test?\n\nJim Meyering wrote:\n\n>   http://meyering.net/code/git-perf/configure.gz\n>   http://meyering.net/code/git-perf/configure-curr.gz\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"28856","messageId":"Pine.LNX.4.64.0610160948450.3962@g5.osdl.org","threadId":"5940","inReplyTo":"87mz7wp6ek.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T16:54:11Z","receivedAt":"2006-10-16T16:54:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Oct 2006, Jim Meyering wrote:\n\n> Linus Torvalds <torvalds@osdl.org> wrote:\n> > On Mon, 16 Oct 2006, Linus Torvalds wrote:\n> ...\n> > So I think xdiff has chosen too small a hash. Can you try what happens if\n> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return\n> > a bigger value (for example, by initializing \"bits\" to 2 instead of 0),\n> > and see if that makes a difference.\n> \n> It makes no difference.\n> \n> Bear in mind that there are a *lot* of duplicate lines in the files\n> being compared: filtering each through \"sort -u\" removes 40-50k lines.\n\nIt can't be due to duplicate lines. If the lines are truly duplicate, then \nthey'd get the same 32-bit hash value, and then the first conditional in \nthe expression would always be true, and then it wouldn't _matter_ if it's \na \"&&\" or a \"||\".\n\nSee?\n\nSo as far as I can tell it has to be some kind of collission on the hash \nqueue with _different_ hash values being queued on the same hash queue.\n\nNow, it could be that there's a bad hash algorithm somewhere (eg if \nXDL_HASHLONG() just does horribly badly in distributing the hash values \nonto the hash queues, you'd see this _regardless_ of how many bits you \nhave, just because it clumps).\n\nOr there could be something else that I'm just missing..\n\nIt would probably be nice to just get a sampling of what the hash-queue \nlooks like for the bad case? Maybe it would be obvious that certain \ndifferent hash values then get the same XDL_HASHLONG() thing..\n\n\t\tLinus\n"},{"id":"28857","messageId":"Pine.LNX.4.64.0610160953480.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"87ejt8p5l9.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T16:54:46Z","receivedAt":"2006-10-16T16:54:46Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Jim Meyering wrote:\n\n> Davide Libenzi <davidel@xmailserver.org> wrote:\n> > On Mon, 16 Oct 2006, Jim Meyering wrote:\n> >\n> >> Linus Torvalds <torvalds@osdl.org> wrote:\n> >> > On Mon, 16 Oct 2006, Linus Torvalds wrote:\n> >> ...\n> >> > So I think xdiff has chosen too small a hash. Can you try what happens if\n> >> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return\n> >> > a bigger value (for example, by initializing \"bits\" to 2 instead of 0),\n> >> > and see if that makes a difference.\n> >>\n> >> It makes no difference.\n> >>\n> >> Bear in mind that there are a *lot* of duplicate lines in the files\n> >> being compared: filtering each through \"sort -u\" removes 40-50k lines.\n> >\n> > Ok, try to bring down XDL_MAX_EQLIMIT to something like 8 or 16 ...\n> \n> That helps a little.\n> Now, instead of taking 63s, my test takes ~30s.\n> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n\nThat's too much still. May I have the offending files?\n\n\n\n- Davide\n"},{"id":"28858","messageId":"878xjgp5az.fsf@rho.meyering.net","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160953480.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jim Meyering","fromEmail":"jim@meyering.net","sentAt":"2006-10-16T16:57:08Z","receivedAt":"2006-10-16T16:57:08Z","isPatch":false,"sender":{"key":"jim@meyering.net","avatar":"https://avatars.githubusercontent.com/u/710630?v=4"},"body":"Davide Libenzi <davidel@xmailserver.org> wrote:\n>> That helps a little.\n>> Now, instead of taking 63s, my test takes ~30s.\n>> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n>\n> That's too much still. May I have the offending files?\n\nThese URLs were in at least one of the messages to which\nyou've replied.  Would you like me to send them instead?\n\n>   http://meyering.net/code/git-perf/configure.gz\n>   http://meyering.net/code/git-perf/configure-curr.gz\n"},{"id":"28859","messageId":"Pine.LNX.4.64.0610160956360.3962@g5.osdl.org","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610160932100.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T16:57:25Z","receivedAt":"2006-10-16T16:57:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Oct 2006, Davide Libenzi wrote:\n>\n> I think the xdl_hashbits() picks up the hash table size \"almost\" \n> correctly. I think we're looking at some bad hash *collisions* (not \n> records with same hash value, that'd be stopped by the mlim check). \n> Send me the files and I'll take a look ...\n\nDavide, they were mentioned in the original report:\n\n\thttp://meyering.net/code/git-perf/configure.gz\n\thttp://meyering.net/code/git-perf/configure-curr.gz\n\nI'd take a look myself, but I need to run..\n\n\t\tLinus\n"},{"id":"28860","messageId":"Pine.LNX.4.64.0610161001200.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"878xjgp5az.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T17:02:03Z","receivedAt":"2006-10-16T17:02:03Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Jim Meyering wrote:\n\n> Davide Libenzi <davidel@xmailserver.org> wrote:\n> >> That helps a little.\n> >> Now, instead of taking 63s, my test takes ~30s.\n> >> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n> >\n> > That's too much still. May I have the offending files?\n> \n> These URLs were in at least one of the messages to which\n> you've replied.  Would you like me to send them instead?\n> \n> >   http://meyering.net/code/git-perf/configure.gz\n> >   http://meyering.net/code/git-perf/configure-curr.gz\n\nThanks, those are fine.\n\n\n\n- Davide\n"},{"id":"28861","messageId":"Pine.LNX.4.64.0610161038200.3962@g5.osdl.org","threadId":"5940","inReplyTo":"87ejt8p5l9.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T17:56:14Z","receivedAt":"2006-10-16T17:56:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Oct 2006, Jim Meyering wrote:\n> \n> That helps a little.\n> Now, instead of taking 63s, my test takes ~30s.\n> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n\nBtw, what architecture is this on?\n\nI'm testing those two files, and I get much more reasonable numbers with \nboth ppc32 and x86. Both 32-bit:\n\n\t[torvalds@macmini test-perf]$ time git show | wc -l\n\t25221\n\n\treal    0m1.437s\n\tuser    0m1.436s\n\tsys     0m0.012s\n\nie it generated the diff in less than a second and a half. Not wonderful, \nbut certainly not your 63s either.\n\nHOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes \n17 seconds on my 2GHz merom machine).\n\nSo I think there's something seriously broken with hashing on 64-bit. \n\nAnd I think I know what it is.\n\nTry this patch. And make sure to do a \"make clean\" first, since I think \nthe dependencies on xdiff may be broken.\n\nDavide: there's two things wrong with your old XDL_HASHLONG():\n\n - the GR_PRIME was just 32-bit, so it wouldn't shift low bits up far \n   enough on a 64-bit architecture, so then shifting things down caused \n   pretty much everything to be very small.\n\n - The whole idea of shifting up by multiplying and then shifting down to \n   get the high bits is _broken_. Even on 32-bit architectures. Think \n   about what happens when \"hashbits\" is 16 on a 32-bit architecture: the \n   multiply moves the low bits _up_, but it doesn't move the high bits \n   _down_. And with hashbits being a large fraction of the whole word, you \n   need to shift things down, not up.\n\nSo just making GR_PRIME be a bigger value on a 64-bit architecture would \nnot have fixed it. The whole hash was simply broken. Do it the sane and \nobvious way instead: always pick the low bits, but mix in upper bits there \ntoo..\n\nThis patch brings the time down from 17 seconds to 0.8 seconds for me.\n\n\t\tLinus\n\n---\ndiff --git a/xdiff/xmacros.h b/xdiff/xmacros.h\nindex 4c2fde8..bb4830b 100644\n--- a/xdiff/xmacros.h\n+++ b/xdiff/xmacros.h\n@@ -24,14 +24,27 @@ #if !defined(XMACROS_H)\n #define XMACROS_H\n \n \n-#define GR_PRIME 0x9e370001UL\n+static inline unsigned long xdl_hashlong(unsigned long val, unsigned int bits)\n+{\n+\tunsigned long shift = val >> bits;\n+\n+\t/* Shift in the upper bits too */\n+\tval += shift;\n+\n+\t/* Do it twice for small values of bits */\n+\tif (bits < 4*sizeof(unsigned long))\n+\t\tval += shift >> bits;\n+\n+\t/* Return the resulting low bits */\n+\treturn val & ((1ul << bits)-1);\n+}\n \n \n #define XDL_MIN(a, b) ((a) < (b) ? (a): (b))\n #define XDL_MAX(a, b) ((a) > (b) ? (a): (b))\n #define XDL_ABS(v) ((v) >= 0 ? (v): -(v))\n #define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')\n-#define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b)))\n+#define XDL_HASHLONG(v, b) xdl_hashlong(v,b)\n #define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)\n #define XDL_LE32_PUT(p, v) \\\n do { \\\n"},{"id":"28862","messageId":"Pine.LNX.4.64.0610161100070.3962@g5.osdl.org","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161038200.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T18:03:41Z","receivedAt":"2006-10-16T18:03:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Oct 2006, Linus Torvalds wrote:\n> \n> So just making GR_PRIME be a bigger value on a 64-bit architecture would \n> not have fixed it.\n\nSide note: in _practice_ I think it would have fixed it. The \"not mixing \nin high bits\" is not a real problem if the original hash-value has a good \ndistribution of bits, which I think we do have. So it's unclear whether we \neven need any mixing in of bits at all, and it's possible that it would be \nfine to just have\n\n\t#define XDL_HASHLONG(v,b) ((unsigned long)(v) & ((1ul << (b))-1))\n\nwhich is simpler than my patch.\n\nI prefer the mixing in of high bits just because it can help if the \noriginal hash was bad (or had a tendency to have patterns in the low bits, \nwhich could be the case). But I'm not sure xdiff actually needs it in this \ncase.\n\n\t\t\tLinus\n"},{"id":"28863","messageId":"Pine.LNX.4.64.0610161109430.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161038200.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T18:18:22Z","receivedAt":"2006-10-16T18:18:22Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Linus Torvalds wrote:\n\n> On Mon, 16 Oct 2006, Jim Meyering wrote:\n> > \n> > That helps a little.\n> > Now, instead of taking 63s, my test takes ~30s.\n> > (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n> \n> Btw, what architecture is this on?\n> \n> I'm testing those two files, and I get much more reasonable numbers with \n> both ppc32 and x86. Both 32-bit:\n> \n> \t[torvalds@macmini test-perf]$ time git show | wc -l\n> \t25221\n> \n> \treal    0m1.437s\n> \tuser    0m1.436s\n> \tsys     0m0.012s\n> \n> ie it generated the diff in less than a second and a half. Not wonderful, \n> but certainly not your 63s either.\n> \n> HOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes \n> 17 seconds on my 2GHz merom machine).\n> \n> So I think there's something seriously broken with hashing on 64-bit. \n> \n> And I think I know what it is.\n> \n> Try this patch. And make sure to do a \"make clean\" first, since I think \n> the dependencies on xdiff may be broken.\n> \n> Davide: there's two things wrong with your old XDL_HASHLONG():\n> \n>  - the GR_PRIME was just 32-bit, so it wouldn't shift low bits up far \n>    enough on a 64-bit architecture, so then shifting things down caused \n>    pretty much everything to be very small.\n> \n>  - The whole idea of shifting up by multiplying and then shifting down to \n>    get the high bits is _broken_. Even on 32-bit architectures. Think \n>    about what happens when \"hashbits\" is 16 on a 32-bit architecture: the \n>    multiply moves the low bits _up_, but it doesn't move the high bits \n>    _down_. And with hashbits being a large fraction of the whole word, you \n>    need to shift things down, not up.\n> \n> So just making GR_PRIME be a bigger value on a 64-bit architecture would \n> not have fixed it. The whole hash was simply broken. Do it the sane and \n> obvious way instead: always pick the low bits, but mix in upper bits there \n> too..\n\nYeah, using an appropriate golden ratio prime for 64 bits fixes it. I \nthink it's the best/minimal fix (use 0x9e37fffffffc0001UL, like the \nkernel does).\nI'm also looking into optimizing the multi-match discard loop, that \nactually loses the classifier informations collected in the context \nprepare phase.\n\n\n\n\n- Davide\n"},{"id":"28864","messageId":"873b9op19n.fsf@rho.meyering.net","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161038200.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jim Meyering","fromEmail":"jim@meyering.net","sentAt":"2006-10-16T18:24:20Z","receivedAt":"2006-10-16T18:24:20Z","isPatch":false,"sender":{"key":"jim@meyering.net","avatar":"https://avatars.githubusercontent.com/u/710630?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> wrote:\n> On Mon, 16 Oct 2006, Jim Meyering wrote:\n>>\n>> That helps a little.\n>> Now, instead of taking 63s, my test takes ~30s.\n>> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)\n>\n> Btw, what architecture is this on?\n>\n> I'm testing those two files, and I get much more reasonable numbers with\n> both ppc32 and x86. Both 32-bit:\n>\n> \t[torvalds@macmini test-perf]$ time git show | wc -l\n> \t25221\n>\n> \treal    0m1.437s\n> \tuser    0m1.436s\n> \tsys     0m0.012s\n>\n> ie it generated the diff in less than a second and a half. Not wonderful,\n> but certainly not your 63s either.\n>\n> HOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes\n> 17 seconds on my 2GHz merom machine).\n>\n> So I think there's something seriously broken with hashing on 64-bit.\n\namd_64 @ 2.0GHz\n\n> Try this patch. And make sure to do a \"make clean\" first, since I think\n> the dependencies on xdiff may be broken.\n\nYep.  Dependencies are definitely broken.\nApplied your patch.  No improvement after a plain \"make\",\nbut doing \"make clean && make\" solved the problem.\n\nNow, my diff-tree takes 2s (it's comparing other files, too).\nThank you!\n\nIMHO, my \"&& vs. ||\" patch is still worth applying.\nIf not, then the existing code doesn't make sense, and\nthere can be significant simplification in the affected loops.\nWith my patch, I get an additional 3x speed-up: diff-tree takes 0.7s\n"},{"id":"28865","messageId":"Pine.LNX.4.64.0610161129350.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"873b9op19n.fsf@rho.meyering.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T18:30:59Z","receivedAt":"2006-10-16T18:30:59Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Jim Meyering wrote:\n\n> IMHO, my \"&& vs. ||\" patch is still worth applying.\n> If not, then the existing code doesn't make sense, and\n> there can be significant simplification in the affected loops.\n> With my patch, I get an additional 3x speed-up: diff-tree takes 0.7s\n\nNo, the patch is broken. It will discard *any* line seen at least two \ntimes, that is an extremely low threashold.\n\n\n\n- Davide\n"},{"id":"28867","messageId":"Pine.LNX.4.64.0610161138140.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161100070.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T18:41:55Z","receivedAt":"2006-10-16T18:41:55Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Linus Torvalds wrote:\n\n> On Mon, 16 Oct 2006, Linus Torvalds wrote:\n> > \n> > So just making GR_PRIME be a bigger value on a 64-bit architecture would \n> > not have fixed it.\n> \n> Side note: in _practice_ I think it would have fixed it. The \"not mixing \n> in high bits\" is not a real problem if the original hash-value has a good \n> distribution of bits, which I think we do have. So it's unclear whether we \n> even need any mixing in of bits at all, and it's possible that it would be \n> fine to just have\n> \n> \t#define XDL_HASHLONG(v,b) ((unsigned long)(v) & ((1ul << (b))-1))\n> \n> which is simpler than my patch.\n> \n> I prefer the mixing in of high bits just because it can help if the \n> original hash was bad (or had a tendency to have patterns in the low bits, \n> which could be the case). But I'm not sure xdiff actually needs it in this \n> case.\n\nATM, I added AC_CHECK_SIZEOF(long) inside libxdiff's configure.in, and I \nhave (inside xmacros.h):\n\n#if SIZEOF_LONG == 4\n#define GR_PRIME 0x9e370001UL\n#else\n#define GR_PRIME 0x9e37fffffffc0001UL\n#endif\n\nI'm also looking into streamlining the discard loop to reuse information \ncollected during the context-setup phase ...\n\n\n\n\n- Davide\n"},{"id":"28868","messageId":"87wt70nlth.fsf@rho.meyering.net","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161129350.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jim Meyering","fromEmail":"jim@meyering.net","sentAt":"2006-10-16T18:43:22Z","receivedAt":"2006-10-16T18:43:22Z","isPatch":false,"sender":{"key":"jim@meyering.net","avatar":"https://avatars.githubusercontent.com/u/710630?v=4"},"body":"Davide Libenzi <davidel@xmailserver.org> wrote:\n...\n> No, the patch is broken. It will discard *any* line seen at least two\n> times, that is an extremely low threashold.\n\nOh!  I see it now.  Thanks.\n"},{"id":"28869","messageId":"Pine.LNX.4.64.0610161130090.3962@g5.osdl.org","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161109430.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T18:51:17Z","receivedAt":"2006-10-16T18:51:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nJunio, I think this is worthy to go in before a 1.4.3 release. Possibly \neven back-ported to earlier trees. Anything that causes an almost two \norders of magnitude slowdown (even if it's just on 64-bit architectures \nand most people won't necessarily compile git that way) is worth fixing \npronto.\n\nOn Mon, 16 Oct 2006, Davide Libenzi wrote:\n> \n> Yeah, using an appropriate golden ratio prime for 64 bits fixes it. I \n> think it's the best/minimal fix (use 0x9e37fffffffc0001UL, like the \n> kernel does).\n\nOk. But then you need something like the appended to avoid warnings..\n\n(This is the only nice portable way to figure out at compile-time whether \n\"unsigned long\" is more than 32 bits that I can come up with: everything \nthat uses actual C expressions ends up warning about integers not fitting \netc)\n\nQuite frankly, I prefer my previous patch more, it just avoids that whole \nproblem, and two shifts and adds (even with a conditional) are often \nfaster than a full 64-bit multiply.\n\n\t\tLinus\n---\ndiff --git a/xdiff/xmacros.h b/xdiff/xmacros.h\nindex 4c2fde8..38f8f93 100644\n--- a/xdiff/xmacros.h\n+++ b/xdiff/xmacros.h\n@@ -23,8 +23,13 @@\n #if !defined(XMACROS_H)\n #define XMACROS_H\n \n+#include <limits.h>\n \n+#if LONG_MAX > 2147483647ul\n+#define GR_PRIME 0x9e37fffffffc0001UL\n+#else\n #define GR_PRIME 0x9e370001UL\n+#endif\n \n \n #define XDL_MIN(a, b) ((a) < (b) ? (a): (b))\n"},{"id":"28870","messageId":"Pine.LNX.4.64.0610161225470.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161130090.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T19:44:52Z","receivedAt":"2006-10-16T19:44:52Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Linus Torvalds wrote:\n\n> \n> Junio, I think this is worthy to go in before a 1.4.3 release. Possibly \n> even back-ported to earlier trees. Anything that causes an almost two \n> orders of magnitude slowdown (even if it's just on 64-bit architectures \n> and most people won't necessarily compile git that way) is worth fixing \n> pronto.\n\nI ended up using this one:\n\n#define XDL_HASHLONG(v, b) ((((unsigned long) (v) >> ((CHAR_BIT * sizeof(unsigned long)) - (b))) + \\\n                            (unsigned long) (v)) & ((1UL << (b)) - 1))\n\nThe GR_PRIME selection does not make me feel good, and the 'static inline' \nis puked-over by certain C compilers. It'd be probably fine to just use a \nsimple function, though the above should work just fine.\n\nreal    0m0.665s\nuser    0m0.655s\nsys     0m0.010s\n\n(Opteron 252)\n\n\n\n- Davide\n"},{"id":"28871","messageId":"eh0q39$mb$1@sea.gmane.org","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161225470.7697@alien.or.mcafeemobile.com","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-10-16T20:29:57Z","receivedAt":"2006-10-16T20:29:57Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Davide Libenzi wrote:\n\n> I ended up using this one:\n> \n> #define XDL_HASHLONG(v, b) ((((unsigned long) (v) >> ((CHAR_BIT *\nsizeof(unsigned long)) - (b))) + \\\n>                             (unsigned long) (v)) & ((1UL << (b)) - 1))\n> \n> The GR_PRIME selection does not make me feel good, and the 'static inline' \n> is puked-over by certain C compilers. It'd be probably fine to just use a \n> simple function, though the above should work just fine.\n> \n> real    0m0.665s\n> user    0m0.655s\n> sys     0m0.010s\n> \n> (Opteron 252)\n\nCould you please do and post benchmarks for other solutions?\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"28876","messageId":"7vy7rfub36.fsf@assigned-by-dhcp.cox.net","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161130090.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-16T22:53:17Z","receivedAt":"2006-10-16T22:53:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Junio, I think this is worthy to go in before a 1.4.3 release. Possibly \n> even back-ported to earlier trees.\n\nThanks for resolving this quickly; I was (am still somewhat)\ndown sick today and missed all the excitement.\n\n> Quite frankly, I prefer my previous patch more, it just avoids that whole \n> problem, and two shifts and adds (even with a conditional) are often \n> faster than a full 64-bit multiply.\n\nI agree (although I am not sure about the \"do it twice for\nsmall\" bit), and I think Davide agrees with you in his reply:\n\nDavide Libenzi <davidel@xmailserver.org> writes:\n> On Mon, 16 Oct 2006, Linus Torvalds wrote:\n> ...\n> I ended up using this one:\n>\n> #define XDL_HASHLONG(v, b) ((((unsigned long) (v) >> ((CHAR_BIT * sizeof(unsigned long)) - (b))) + \\\n>                              (unsigned long) (v)) & ((1UL << (b)) - 1))\n\nso I am inclined to apply Davide's version, but I am going to\nbed again now...\n"},{"id":"28878","messageId":"Pine.LNX.4.64.0610161604360.3962@g5.osdl.org","threadId":"5940","inReplyTo":"7vy7rfub36.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-16T23:24:05Z","receivedAt":"2006-10-16T23:24:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Oct 2006, Junio C Hamano wrote:\n> \n> I agree (although I am not sure about the \"do it twice for\n> small\" bit), and I think Davide agrees with you in his reply:\n\nSure. Davide's all-macro version is fine. I don't like re-using the same \nvalue twice even in a ALL-CAPS macro, so I'm used to inline functions, but \nall the uses of XDL_HASHLONG() are fine with multiple uses of the \narguments.\n\nSomebody should just double-check that all the parentheses ended up being \nright ;)\n\nIt might be easier to read if you write it as\n\n\t#define BITS_IN_LONG\t(CHAR_BIT * sizeof(unsigned long))\n\t#define XDL_HIGHBITS(v,b) ((v) >> (BITS_IN_LONG - (b)))\n\t#define XDL_MASKBITS(b) ((1UL << (b)) - 1)\n\t#define XDL_HASHBITS(v,b) (((v) + XDL_HIGHBITS(v,b)) & XDL_MASKBITS(b))\n\t#define XDL_HASHLONG(v,b) XDL_HASHBITS( (unsigned long)(v) , b )\n\njust to avoid one huge #define.\n\nThat said, it unnecessarily calculates \"BITS_IN_LONG - (b)\" to shift with, \nbecause it really shouldn't matter _which_ high bits you use for hashing, \nso you might as well just use the \"next\" b bits, and have\n\n\t#define XDL_ADDBITS(v,b)\t((v) + ((v) >> (b)))\n\t#define XDL_MASKBITS(b)\t\t((1UL << (b)) - 1)\n\t#define XDL_HASHLONG(v,b)\t(XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))\n\nwhich generates better code at least on x86 (and x86-64), because the \nshift count stays the same for all shifts and can thus be kept in %ecx. \nFor example, on x86-64, you get\n\n\tmovq    %rdi, %rax\t\t# copy 'val'\n\tmovl    $1, %edx\t\t# const 1: start generating (1 << b) - 1\n\tshrq    %cl, %rax\t\t# val >> b\n\tsalq    %cl, %rdx\t\t# 1 << b\n\tleaq    (%rdi,%rax), %rax\t# val + (val >> b)\n\tsubq    $1, %rdx\t\t# (1 << b) -1\n\tandq    %rdx, %rax\t\t# final hash\n\nwhich is short and sweet. And on ppc32 (or ppc64) you get\n\n\tli 9,1\t\t\t# const 1: start generating (1 << b) - 1\n\tsrw 0,3,4\t\t# val >> b\n\tslw 9,9,4\t\t# 1 << b\n\tadd 0,0,3\t\t# val + (val >> b)\n\taddi 9,9,-1\t\t# (1 << b) - 1\n\tand 3,0,9\t\t# final hash\n\nin other words, apart from having two shifts (which you can't really \navoid, although a multiply can do one of them) it's just a very efficient \nway to mix together (2*b) bits into a (b)-bit hash.\n\nBut taking the high bits from the \"unsigned long\" doesn't add _that_ much \ncost. I just suspect that it's a good way to continue to get different \nanswers on 32-bit and 64-bit architectures. \n\n\t\tLinus\n"},{"id":"28883","messageId":"Pine.LNX.4.64.0610161651010.7697@alien.or.mcafeemobile.com","threadId":"5940","inReplyTo":"Pine.LNX.4.64.0610161604360.3962@g5.osdl.org","subject":"Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-16T23:52:00Z","receivedAt":"2006-10-16T23:52:00Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 16 Oct 2006, Linus Torvalds wrote:\n\n> That said, it unnecessarily calculates \"BITS_IN_LONG - (b)\" to shift with, \n> because it really shouldn't matter _which_ high bits you use for hashing, \n> so you might as well just use the \"next\" b bits, and have\n> \n> \t#define XDL_ADDBITS(v,b)\t((v) + ((v) >> (b)))\n> \t#define XDL_MASKBITS(b)\t\t((1UL << (b)) - 1)\n> \t#define XDL_HASHLONG(v,b)\t(XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))\n\nOk, I'm fine with this. And my Opteron agrees too:\n\nreal    0m0.283s\nuser    0m0.267s\nsys     0m0.016s\n\n\n\n- Davide\n"}]}