{"thread":{"id":"3632","subject":"git-diff-tree -M performance regression in 'next'","startedAt":"2006-03-11T17:28:18Z","lastAt":"2006-03-14T10:26:22Z","messageCount":17,"participants":["Fredrik Kuivinen","Junio C Hamano","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"17460","messageId":"20060311172818.GB32609@c165.ib.student.liu.se","threadId":"3632","inReplyTo":null,"subject":"git-diff-tree -M performance regression in 'next'","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-03-11T17:28:18Z","receivedAt":"2006-03-11T17:28:18Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Hi,\n\nI added some time logging code to git-merge-recursive to see exactly\nwhat we spend all the time on in merges which involves many changes,\nsuch as a merge of a slightly modified v2.6.12 and an unmodified\nv2.6.15.\n\nI turned out that the rename detection took almost 10 minutes on my\nmachine. More specifically,\n\n git-diff-tree -r -M --diff-filter=R v2.6.12 v2.6.14\n\ntakes ~9 minutes with the current 'next'.\n\nWith 65416758cd83772f2f3c69f1bd1f501608e64745, which uses the delta\ncode to compute the similarity measure, the above git-diff-tree\ninvocation takes 1.50 minutes.\n\n- Fredrik\n"},{"id":"17463","messageId":"7v7j70gxxw.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"20060311172818.GB32609@c165.ib.student.liu.se","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-12T03:10:35Z","receivedAt":"2006-03-12T03:10:35Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> I turned out that the rename detection took almost 10 minutes on my\n> machine.\n\nYes, that is one of the reasons why it still is in \"next\", not\nin \"master\".\n\nThe rename-detector change was done primarily to work around the\ncorrectness problem the finer-grained delta changes would have\nintroduced. The new delta code would have produced far more\ncopies from the source than the current xdelta code, but the\nnature of the new copies it would have found was quite different\nfrom what we would usually call \"file being renamed\". Now we\ndecided to shelve the finer-grained delta code for now, I do not\nsee a pressing reason to have the experimental rename detector\ngraduate to \"master\" until we resolve its performance issues.\n"},{"id":"17467","messageId":"7voe0bdeyr.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"20060311172818.GB32609@c165.ib.student.liu.se","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-12T12:28:44Z","receivedAt":"2006-03-12T12:28:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> I turned out that the rename detection took almost 10 minutes on my\n> machine. More specifically,\n>\n> git-diff-tree -r -M --diff-filter=R v2.6.12 v2.6.14\n>\n> takes ~9 minutes with the current 'next'.\n\nI have some updates to \"next\" tonight.\n\nOn my otherwise idle Duron 750 with slow disks, I am getting\nsomething like these:\n\n0.99.9m : 130m virtual, 40m resident, (0major+14205minor)\n 67.62user 0.08system 1:15.95elapsed\nmaster : 130m virtual, 40m resident, (0major+12510minor)\n 66.06user 0.07system 1:10.95elapsed\n\"next\" : 150m virtual, 65m resident, (0major+49858minor)\n 51.41user 0.45system 0.57.55elapsed\n\nThe result will _not_ exactly match, because the similarity\nestimation algorithms are different.\n\nJudging the differences objectively is a bit hard, but my\nimpression is that the \"next\" one tends to find more sensible\nrenames. To name a few:\n\n* Documentation/dvb/README.dibusb from v2.6.12 seems pretty\n similar to Documentation/dvb/README.dvb-usb from v2.6.14, and\n \"next\" finds them, but \"master\" does not.\n\n* \"master\" says arch/arm/configs/omnimeter_defconfig was\n copy-edited to produce arch/arm/configs/collie_defconfig; The\n diff output shows ~350 new lines and ~270 deleted lines, while\n these files are 800-900 lines long; \"next\" rejects them. I\n think this is a border-line case.\n\n* \"next\" finds Kconfig and Makefile in arch/arm/mach-omap-1/ are\n derived from arch/arm/mach-omap/; manual inspection of these\n files makes me feel that decision is sensible. \"master\" does\n not find them.\n\n* Same thing for config.c in arch/m68knommu/platform/68VZ328/;\n found to be derived from arch/m68knommu/platform/68VZ328/de2/ by\n \"next\" but not by \"master\".\n\n* Other examples \"next\" finds but \"master\" misses include:\n\n arch/um/kernel/process.c\tarch/um/os-Linux/start_up.c\n arch/um/kernel/tt/unmap.c\tarch/um/sys-x86_64/unmap.c\n drivers/ide/cris/ide-v10.c\tdrivers/ide/cris/ide-cris.c\n include/asm-ppc/cputime.h\tinclude/asm-xtensa/cputime.h\n include/asm-ppc64/ioctl.h\tinclude/asm-xtensa/ioctl.h\n include/asm-ppc64/ioctls.h\tinclude/asm-xtensa/ioctls.h\n include/asm-ppc64/mman.h\tinclude/asm-xtensa/mman.h\n include/asm-ppc64/poll.h\tinclude/asm-xtensa/poll.h\n include/asm-ppc64/shmbuf.h\tinclude/asm-xtensa/shmbuf.h\n include/asm-ppc64/socket.h\tinclude/asm-xtensa/socket.h\n include/asm-ppc64/termbits.h\tinclude/asm-xtensa/termbits.h\n\n* The \"next\" one is not perfect. There are some quite bad\n choices made by it:\n\n include/asm-ppc64/timex.h\tinclude/asm-powerpc/bugs.h\n include/asm-ppc64/iSeries/LparData.h\tinclude/linux/i2c-isa.h\n"},{"id":"17474","messageId":"Pine.LNX.4.64.0603120858230.3618@g5.osdl.org","threadId":"3632","inReplyTo":"7voe0bdeyr.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-12T17:00:13Z","receivedAt":"2006-03-12T17:00:13Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Junio C Hamano wrote:\n> \n> On my otherwise idle Duron 750 with slow disks, I am getting\n> something like these:\n> \n> 0.99.9m : 130m virtual, 40m resident, (0major+14205minor)\n> 67.62user 0.08system 1:15.95elapsed\n> master : 130m virtual, 40m resident, (0major+12510minor)\n> 66.06user 0.07system 1:10.95elapsed\n> \"next\" : 150m virtual, 65m resident, (0major+49858minor)\n> 51.41user 0.45system 0.57.55elapsed\n\nAny way to fix that \"4 times as many page misses, and 70% bigger rss?\" \nthing? It looks like you're not very careful about your memory use.\n\nI realize that git in general wants a lot of memory, but I see that as a \nfailure most of the time. I've got 2GB in most of my machines, but I \nshouldn't _need_ to have it..\n\n\t\t\tLinus\n"},{"id":"17480","messageId":"7vk6azcv9y.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603120858230.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-12T19:34:01Z","receivedAt":"2006-03-12T19:34:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 12 Mar 2006, Junio C Hamano wrote:\n>> \n>> master : 130m virtual, 40m resident, (0major+12510minor)\n>> 66.06user 0.07system 1:10.95elapsed\n>> \"next\" : 150m virtual, 65m resident, (0major+49858minor)\n>> 51.41user 0.45system 0.57.55elapsed\n>\n> Any way to fix that \"4 times as many page misses, and 70% bigger rss?\" \n> thing? It looks like you're not very careful about your memory use.\n\nI started from \"80 times as many page misses and 5 times bigger\nrss\", shrunk it down to the above after doing more careful\nmemory use, running out of ideas to shrink it more, and pushed\nit out. So...\n"},{"id":"17485","messageId":"7vwtezw4ye.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"7vk6azcv9y.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T00:42:17Z","receivedAt":"2006-03-13T00:42:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"> Linus Torvalds writes:\n>\n>> On Sun, 12 Mar 2006, Junio C Hamano wrote:\n>>> \n>>> master : 130m virtual, 40m resident, (0major+12510minor)\n>>> 66.06user 0.07system 1:10.95elapsed\n>>> \"next\" : 150m virtual, 65m resident, (0major+49858minor)\n>>> 51.41user 0.45system 0.57.55elapsed\n>>\n>> Any way to fix that \"4 times as many page misses, and 70% bigger rss?\" \n>> thing? It looks like you're not very careful about your memory use.\n\n\"this\" : 145m virtual, 57m resident, (0major+18855minor)\n 39.81user 0.28system 0:42.16elapsed\n\n50% more page misses, 45% bigger rss, 65% less usertime.\nSlowly getting there...\n\n-- >8 --\n[PATCH] diffcore-delta: make the hash a bit denser.\n\nTo reduce wasted memory, wait until the hash fills up more\ndensely before we rehash. This reduces the working set size a\nbit further.\n\nSigned-off-by: Junio C Hamano \n\n---\n\n diffcore-delta.c | 13 +++++++++----\n diffcore-rename.c | 4 +++-\n 2 files changed, 12 insertions(+), 5 deletions(-)\n\naf0b459589edaa77c51a892dd7dc44329634d253\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 471b98f..f8a7518 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -25,8 +25,12 @@\n */\n \n /* Wild guess at the initial hash size */\n-#define INITIAL_HASH_SIZE 10\n+#define INITIAL_HASH_SIZE 9\n #define HASHBASE 65537 /* next_prime(2^16) */\n+/* We leave more room in smaller hash but do not let it\n+ * grow to have unused hole too much.\n+ */\n+#define INITIAL_FREE(sz_log2) ((1<<(sz_log2))*(sz_log2-3)/(sz_log2))\n \n struct spanhash {\n \tunsigned long hashval;\n@@ -38,7 +42,8 @@ struct spanhash_top {\n \tstruct spanhash data[FLEX_ARRAY];\n };\n \n-static struct spanhash *spanhash_find(struct spanhash_top *top, unsigned long hashval)\n+static struct spanhash *spanhash_find(struct spanhash_top *top,\n+\t\t\t\t unsigned long hashval)\n {\n \tint sz = 1 << top->alloc_log2;\n \tint bucket = hashval & (sz - 1);\n@@ -62,7 +67,7 @@ static struct spanhash_top *spanhash_reh\n \n \tnew = xmalloc(sizeof(*orig) + sizeof(struct spanhash) * sz);\n \tnew->alloc_log2 = orig->alloc_log2 + 1;\n-\tnew->free = osz;\n+\tnew->free = INITIAL_FREE(new->alloc_log2);\n \tmemset(new->data, 0, sizeof(struct spanhash) * sz);\n \tfor (i = 0; i < osz; i++) {\n \t\tstruct spanhash *o = &(orig->data[i]);\n@@ -122,7 +127,7 @@ static struct spanhash_top *hash_chars(u\n \ti = INITIAL_HASH_SIZE;\n \thash = xmalloc(sizeof(*hash) + sizeof(struct spanhash) * (1<alloc_log2 = i;\n-\thash->free = (1<free = INITIAL_FREE(i);\n \tmemset(hash->data, 0, sizeof(struct spanhash) * (1<score = estimate_similarity(one, two,\n \t\t\t\t\t\t minimum_score);\n \t\t}\n+\t\t/* We do not need the text anymore */\n \t\tfree(two->cnt_data);\n-\t\ttwo->cnt_data = NULL;\n+\t\tfree(two->data);\n+\t\ttwo->data = two->cnt_data = NULL;\n \t\tdst_cnt++;\n \t}\n \t/* cost matrix sorted by most to least similar pair */\n-- \n1.2.4.g3dcf\n"},{"id":"17487","messageId":"Pine.LNX.4.64.0603121700410.3618@g5.osdl.org","threadId":"3632","inReplyTo":"7vwtezw4ye.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T01:09:47Z","receivedAt":"2006-03-13T01:09:47Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Junio C Hamano wrote:\n> \n> To reduce wasted memory, wait until the hash fills up more\n> densely before we rehash. This reduces the working set size a\n> bit further.\n\nUmm. Why do you rehash at all?\n\nJust take the size of the \"src\" file as the initial hash size. \n\nAlso, I think it is likely really wasteful to try to actually hash at \n_each_ character. Instead, let's say that the chunk-size is 8 bytes (like \nyou do now), and let's say that you have a 32-bit good hash of those 8 \nbytes. What you can do is:\n\n - for each 8 bytes in the source, hash those 8 bytes (not every byte)\n - for each byte in the other file, hash 8 next bytes. IF it matches a \n hash in the source with a non-zero count, subtract the count for that \n hash and move up by _eight_ characters! If it doesn't, add one to \n \"characters not matched\" counter, and move up _one_ character, and try \n again.\n\nAt the end of this, you have two counts: the count of characters that you \ncouldn't match in the other file, and the count of 8-byte hash-chunks that \nyou couldn't match in the first one. Use those two counts to decide if \nit's close or not.\n\nEspecially for good matches, this should basically cut your work into an \neight of what you do now.\n\nActually, even for bad matches, you cut the first source overhead into one \neight (the second file will obviously do the \"update by 1 byte\" most of \nthe time).\n\nDon't you think that would be as accurate as what you're doing now (it's \nthe same basic notion, after all), and noticeably faster?\n\n\t\t\tLinus\n"},{"id":"17488","messageId":"7vhd63w33n.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603121700410.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T01:22:20Z","receivedAt":"2006-03-13T01:22:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Umm. Why do you rehash at all?\n>\n> Just take the size of the \"src\" file as the initial hash size. \n\nThe code uses close to 16-bit hash and I had 65k flat array as a\nhashtable. That one was what you commented as \"4-times as many\npage misses\".\n\nInterestingly enough, that kind of flat array representation\nseems to be too sparse and gives very bad performance behaviour.\n\nThe improvement I mentioned in the message you are replying to\nis the result of making it into smaller (starting at (1<<9) or\nsomething like that) linear-overflowing hash.\n\nThe latter suggestion I need to think about it a bit more.\n"},{"id":"17489","messageId":"Pine.LNX.4.64.0603121710110.3618@g5.osdl.org","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603121700410.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T01:29:45Z","receivedAt":"2006-03-13T01:29:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Linus Torvalds wrote:\n> \n> Also, I think it is likely really wasteful to try to actually hash at \n> _each_ character. Instead, let's say that the chunk-size is 8 bytes (like \n> you do now), and let's say that you have a 32-bit good hash of those 8 \n> bytes. What you can do is:\n\nSide note: regardless, your new algorithm clearly does seem faster.\n\nHowever, it worries me a bit that you don't check the source strings, \nespecially since the hash you use seems somewhat suspect (why limit it to \nessentially just 16 bits? Wouldn't it be best to have the _biggest_ prime \nthat fits in the \"hashval\" thing, which is at least 32 bits? Also, \nshouldn't you make that spanhash thing use a \"unsigned int\" instead of \n\"unsigned long\"?)\n\nSo I would suggest instead the hash function to be:\n\n\ttypedef unsigned long long u64;\n\n\t/* Biggest prime in 32 bits */\n\t#define HASHVAL (4294967291u)\n\n\n\tu64 value = *(u64 *)src;\n\tsrc += 8;\n\thash = value % 4294967291u;\n\nwhich does a 64-bit modulus, but hey, 64-bit hw isn't _that_ uncommon any \nmore, and it's not _excessively_ slow on x86 (gcc doesn't generate good \ncode, but we could actually use the kernel \"do_div()\" routine for much \nfaster division of 64 % 32 than what gcc can do - since the dividend is \n32-bit, you actually only need to do one 32/32 division and one 64/32 \ndivision, so the optimized hash function on a good x86 will be just in \nthe teens of cycles for the 64-bit modulus).\n\n\t\tLinus\n"},{"id":"17490","messageId":"Pine.LNX.4.64.0603121730310.3618@g5.osdl.org","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603121710110.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T01:31:39Z","receivedAt":"2006-03-13T01:31:39Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Linus Torvalds wrote:\n>\n> \tu64 value = *(u64 *)src;\n> \tsrc += 8;\n> \thash = value % 4294967291u;\n\nBtw, this assumes the \"only hash every 8 bytes\" at the source, in which \ncase this is ok even on architectures that need aligned reads. For the \nnon-aligned reads, you'd need your \"shift the value\" approach.\n\n\t\tLinus\n"},{"id":"17491","messageId":"Pine.LNX.4.64.0603121733350.3618@g5.osdl.org","threadId":"3632","inReplyTo":"7vhd63w33n.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T01:39:20Z","receivedAt":"2006-03-13T01:39:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Junio C Hamano wrote:\n> \n> The code uses close to 16-bit hash and I had 65k flat array as a\n> hashtable. That one was what you commented as \"4-times as many\n> page misses\".\n\nAhh. That explains the limited bits in the hash function too. I only \nlooked at the current sources, not at the historic ones.\n\nBtw, the page misses may come from the fact that you allocated and \nre-allocated the flat array all the time. That can be very expensive for \nbig allocations, since most libraries may decide that it's a big enough \narea that it should be map/unmap'ed in order to give memory back to the \nsystem (without realizing that there's another allocation coming soon \nafterwards of the same size).\n\nIf you map/unmap, the kernel will end up having to not just use new pages, \nbut obviously also clear them for security reasons. So it ends up sucking \non many levels. In contrast, if you just have a 64k-entry array of \"int\", \nand allocate it _once_ (instead of once per file-pair) you'll still have \nto clear it in between file-pairs, but at least you won't have the \noverhead of mapping/unmapping it.\n\nThe clearing can still be pretty expensive (64k \"int\" entries is 256kB, \nand since most _files_ are just in the ~4-8kB range, you're spending a \n_lot_ of time just memset'ing). Which is why it's probably a good idea to \ninstead default to having just \"filesize / 8\" entries, but then you can \nobviously not use the hash as the index any more.\n\n\t\tLinus\n"},{"id":"17492","messageId":"Pine.LNX.4.64.0603121810140.3618@g5.osdl.org","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603121710110.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T02:29:15Z","receivedAt":"2006-03-13T02:29:15Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Linus Torvalds wrote:\n> \n> So I would suggest instead the hash function to be:\n> \n> \ttypedef unsigned long long u64;\n> \n> \t/* Biggest prime in 32 bits */\n> \t#define HASHVAL (4294967291u)\n> \n> \n> \tu64 value = *(u64 *)src;\n> \tsrc += 8;\n> \thash = value % 4294967291u;\n> \n> which does a 64-bit modulus, but hey, 64-bit hw isn't _that_ uncommon any \n> more, and it's not _excessively_ slow on x86 (gcc doesn't generate good \n> code, but we could actually use the kernel \"do_div()\" routine for much \n> faster division of 64 % 32 than what gcc can do - since the dividend is \n> 32-bit, you actually only need to do one 32/32 division and one 64/32 \n> division, so the optimized hash function on a good x86 will be just in \n> the teens of cycles for the 64-bit modulus).\n\nActually, on x86, where we can do the 64-by-32 division with a single \ninstruction, this seems to be the best possible code:\n\n\t#define HASH_VAL (4294967291u)\n\n\tstatic inline unsigned int hash64x32(unsigned long long a)\n\t{\n\t\tunsigned int high, low;\n\t\tunsigned int modulus;\n\n\t\tasm(\"\"\n\t\t\t:\"=a\" (low), \"=d\" (high)\n\t\t\t:\"A\" (a));\n\t\tif (high > HASH_VAL)\n\t\t\thigh -= HASH_VAL;\n\t\tasm(\"divl %2\"\n\t\t\t:\"=a\" (low), \"=d\" (modulus)\n\t\t\t:\"rm\" (HASH_VAL), \"0\" (low), \"1\" (high));\n\t\treturn modulus;\n\t}\n\nat least as far as I can think.\n\nThe magic is the reduction of the high 32 bits: for the general case you\nwant a modulus for that reduction, but since we're dividing with a\nreally big value, the modulus of the high bits really does end up\nbecoming just that simple\n\n\tif (high > HASH_VAL)\n\t\thigh -= HASH_VAL;\n\nand then we just need to do a single \"divl\" instruction.\n\nSo if you want a 32-bit hash of an 8-byte area, this should be a pretty\ngood and fast way to calculate it. \n\nOf course, maybe just doing an adler32() is simpler/better. But with\nthe above, at least on x86, I suspect you get an even better\ndistribution at a lower cost (of course, different coress do differently\nwell on large divisions, but integer division being pretty important for\nsome codes, modern cores actually tend to be pretty good at it). \n\n\t\t\tLinus\n"},{"id":"17493","messageId":"Pine.LNX.4.64.0603121852280.3618@g5.osdl.org","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603121810140.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T02:53:17Z","receivedAt":"2006-03-13T02:53:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Linus Torvalds wrote:\n>\n> \t\tif (high > HASH_VAL)\n> \t\t\thigh -= HASH_VAL;\n\nThat should be \">= HASH_VAL\", of course. I'm a retard. \n\n\t\tLinus\n"},{"id":"17498","messageId":"7vwtezt202.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603121710110.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T04:14:21Z","receivedAt":"2006-03-13T04:14:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> However, it worries me a bit that you don't check the source strings, \n> especially since the hash you use seems somewhat suspect (why limit it to \n> essentially just 16 bits? Wouldn't it be best to have the _biggest_ prime \n> that fits in the \"hashval\" thing, which is at least 32 bits? Also, \n> shouldn't you make that spanhash thing use a \"unsigned int\" instead of \n> \"unsigned long\"?)\n>\n> So I would suggest instead the hash function to be:\n>\n> \ttypedef unsigned long long u64;\n>\n> \t/* Biggest prime in 32 bits */\n> \t#define HASHVAL (4294967291u)\n\nActually what you are seeing is the best compromise I've come up\nwith. There were about a dozen crappoid that turned out to be\nsuboptimal I threw away.\n\nThe hashsize is an interesting example of such a compromise\nbetween precision and performance. It is true that full 32-bit\nhash gives us more precise match detection. If you change the\ncurrent hash function to divide with (4294967291u), the rename\nsimilarity score assigned to some (but not all) paths in the\nexample dataset we have been using (diff between v2.6.12 and\nv2.6.14) decreases by about 1% -- this comes from the fact that\nthe hashvalue capped to 16-bit gives some false hits that larger\nhashbase value can tell apart. Because of it, some paths near\nthe rename detection threshold stop being recognized as renames.\n\nHowever, the runtime of the same dataset increases quite a bit\nwhen we do this. I think this is because we need to keep more\ndifferent hash values in the hashtable and the cost to randomly\naccess into a huge table starts to hurt, unlike the 16-bit\ncapped version whose hash table never needs to grow beyond 65k\nentries.\n\n next 39.77user 0.22system 0:40.78elapsed\n 0inputs+0outputs (0major+18855minor)\n\n 32-bit 66.32user 0.15system 1:07.00elapsed\n 0inputs+0outputs (0major+21057minor)\n\nAdmittedly, we should not optimize for one particular test case,\nbut we should start from somewhere.\n\nDecreasing the hashsize to 14-bit or less had noticeable\ndegradation on the quality of renames the algorithm detects and\nmisses to detect, both in v2.6.12..v2.6.14 test and some tests\nin git.git repository.\n\nOne obvious change we could do is to make the hashsize to\n0x1800D (a prime halfway between 16- and 17-bit); currently the\nhashtable grows double every time when the table of the current\nsize fills up sufficiently, but the current hashbase cannot fit\nin 16-bit, so we _are_ already using a table with 128K entries\nin some cases.\n"},{"id":"17538","messageId":"7vveuhohve.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"7vwtezt202.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-14T02:55:01Z","receivedAt":"2006-03-14T02:55:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"While we are hacking away with weird ideas...\n\nHere is still an WIP but an insanely fast one (actually this is\na modified version of what once was in next). I haven't\nverified the sanity of its output fully, but from a cursory look\nwhat are found look sensible. The same v2.6.12..v2.6.14 test on\nmy Duron 750:\n\n master 64.65user 0.17system 1:05.42elapsed\n 0inputs+0outputs (0major+12511minor)\n\n next 40.69user 0.14system 0:40.98elapsed\n 0inputs+0outputs (0major+19471minor)\n\n \"this\" 5.59user 0.09system 0:05.68elapsed\n 0inputs+0outputs (0major+13015minor)\n\nThe hash used here is heavily optimized for handling text files\nand nothing else. Actually, it punts on a file that contains a\nNUL byte. The hash is computed by first skipping sequences of\nwhitespace letters (including LF); upon seeing a non whitespace,\nwe start hashing, while still ignoring whitespaces, until we hit\nthe next LF (or EOF). Then we store the real number of bytes\nalong with the hash. \n\nWhen we find the matching hash value in the destination, we say\nthat many bytes (including the whitespaces we ignored while\nhashing) were copied.\n\nThe patch should apply on top of the current \"next\".\n\n---\n\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 835d82c..0f4866e 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -3,25 +3,10 @@\n #include \"diffcore.h\"\n \n /*\n- * Idea here is very simple.\n- *\n- * We have total of (sz-N+1) N-byte overlapping sequences in buf whose\n- * size is sz. If the same N-byte sequence appears in both source and\n- * destination, we say the byte that starts that sequence is shared\n- * between them (i.e. copied from source to destination).\n- *\n- * For each possible N-byte sequence, if the source buffer has more\n- * instances of it than the destination buffer, that means the\n- * difference are the number of bytes not copied from source to\n- * destination. If the counts are the same, everything was copied\n- * from source to destination. If the destination has more,\n- * everything was copied, and destination added more.\n- *\n- * We are doing an approximation so we do not really have to waste\n- * memory by actually storing the sequence. We just hash them into\n- * somewhere around 2^16 hashbuckets and count the occurrences.\n- *\n- * The length of the sequence is arbitrarily set to 8 for now.\n+ * Record the hashes for \"extended lines\" in both source and destination,\n+ * and compare how similar they are. \"Extended lines\" hash is designed\n+ * to work well on text files -- leading whitespaces and tabs, and consecutive\n+ * LF characters are effectively ignored.\n */\n \n /* Wild guess at the initial hash size */\n@@ -40,8 +25,9 @@\n #define HASHBASE 107927\n \n struct spanhash {\n-\tunsigned long hashval;\n-\tunsigned long cnt;\n+\tunsigned long hashval; /* hash for the line */\n+\tunsigned bytes; /* real number of bytes in such a line */\n+\tunsigned long cnt; /* occurrences */\n };\n struct spanhash_top {\n \tint alloc_log2;\n@@ -87,6 +73,7 @@ static struct spanhash_top *spanhash_reh\n \t\t\tif (!h->cnt) {\n \t\t\t\th->hashval = o->hashval;\n \t\t\t\th->cnt = o->cnt;\n+\t\t\t\th->bytes = o->bytes;\n \t\t\t\tnew->free--;\n \t\t\t\tbreak;\n \t\t\t}\n@@ -99,7 +86,8 @@ static struct spanhash_top *spanhash_reh\n }\n \n static struct spanhash_top *add_spanhash(struct spanhash_top *top,\n-\t\t\t\t\t unsigned long hashval)\n+\t\t\t\t\t unsigned long hashval,\n+\t\t\t\t\t unsigned bytes)\n {\n \tint bucket, lim;\n \tstruct spanhash *h;\n@@ -110,6 +98,7 @@ static struct spanhash_top *add_spanhash\n \t\th = &(top->data[bucket++]);\n \t\tif (!h->cnt) {\n \t\t\th->hashval = hashval;\n+\t\t\th->bytes = bytes;\n \t\t\th->cnt = 1;\n \t\t\ttop->free--;\n \t\t\tif (top->free < 0)\n@@ -117,6 +106,14 @@ static struct spanhash_top *add_spanhash\n \t\t\treturn top;\n \t\t}\n \t\tif (h->hashval == hashval) {\n+\t\t\tif (h->bytes != bytes) {\n+\t\t\t\t/* avg of h->cnt instances were h->bytes\n+\t\t\t\t * now we are adding bytes\n+\t\t\t\t */\n+\t\t\t\th->bytes = ((h->cnt / 2 + bytes +\n+\t\t\t\t\t h->cnt * h->bytes) /\n+\t\t\t\t\t (h->cnt + 1));\n+\t\t\t}\n \t\t\th->cnt++;\n \t\t\treturn top;\n \t\t}\n@@ -125,11 +122,49 @@ static struct spanhash_top *add_spanhash\n \t}\n }\n \n-static struct spanhash_top *hash_chars(unsigned char *buf, unsigned long sz)\n+static unsigned long hash_extended_line(const unsigned char **buf_p,\n+\t\t\t\t\tunsigned long left)\n+{\n+\t/* An extended line is zero or more whitespace letters (including LF)\n+\t * followed by one non whitespace letter followed by zero or more\n+\t * non LF, and terminated with by a LF (or EOF).\n+\t */\n+\tconst unsigned char *bol = *buf_p;\n+\tconst unsigned char *buf = bol;\n+\tunsigned long hashval = 0;\n+\twhile (left) {\n+\t\tunsigned c = *buf++;\n+\t\tif (!c)\n+\t\t\tgoto binary;\n+\t\tleft--;\n+\t\tif (' ' < c) {\n+\t\t\thashval = c;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\twhile (left) {\n+\t\tunsigned c = *buf++;\n+\t\tif (!c)\n+\t\t\tgoto binary;\n+\t\tleft--;\n+\t\tif (c == '\\n')\n+\t\t\tbreak;\n+\t\tif (' ' < c)\n+\t\t\thashval = hashval * 11 + c;\n+\t}\n+\t*buf_p = buf;\n+\treturn hashval;\n+\n+ binary:\n+\t*buf_p = NULL;\n+\treturn 0;\n+}\n+\n+static struct spanhash_top *hash_lines(const unsigned char *buf, unsigned long sz)\n {\n \tint i;\n-\tunsigned long accum1, accum2, hashval;\n \tstruct spanhash_top *hash;\n+\tconst unsigned char *eobuf = buf + sz;\n \n \ti = INITIAL_HASH_SIZE;\n \thash = xmalloc(sizeof(*hash) + sizeof(struct spanhash) * (1<free = INITIAL_FREE(i);\n \tmemset(hash->data, 0, sizeof(struct spanhash) * (1<> 24);\n-\t\taccum2 = (accum2 << 8) | *buf++;\n-\t}\n-\twhile (sz) {\n-\t\taccum1 = (accum1 << 8) | (accum2 >> 24);\n-\t\taccum2 = (accum2 << 8) | *buf++;\n-\t\thashval = (accum1 + accum2 * 0x61) % HASHBASE;\n-\t\thash = add_spanhash(hash, hashval);\n-\t\tsz--;\n+\twhile (buf < eobuf) {\n+\t\tconst unsigned char *ptr = buf;\n+\t\tunsigned long hashval = hash_extended_line(&buf, eobuf-ptr);\n+\t\tif (!buf) {\n+\t\t\tfree(hash);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\thash = add_spanhash(hash, hashval, buf-ptr);\n \t}\n \treturn hash;\n }\n@@ -166,21 +196,18 @@ int diffcore_count_changes(void *src, un\n \tstruct spanhash_top *src_count, *dst_count;\n \tunsigned long sc, la;\n \n-\tif (src_size < 8 || dst_size < 8)\n-\t\treturn -1;\n-\n \tsrc_count = dst_count = NULL;\n \tif (src_count_p)\n \t\tsrc_count = *src_count_p;\n \tif (!src_count) {\n-\t\tsrc_count = hash_chars(src, src_size);\n+\t\tsrc_count = hash_lines(src, src_size);\n \t\tif (src_count_p)\n \t\t\t*src_count_p = src_count;\n \t}\n \tif (dst_count_p)\n \t\tdst_count = *dst_count_p;\n \tif (!dst_count) {\n-\t\tdst_count = hash_chars(dst, dst_size);\n+\t\tdst_count = hash_lines(dst, dst_size);\n \t\tif (dst_count_p)\n \t\t\t*dst_count_p = dst_count;\n \t}\n@@ -193,9 +220,9 @@ int diffcore_count_changes(void *src, un\n \t\tunsigned dst_cnt, src_cnt;\n \t\tif (!s->cnt)\n \t\t\tcontinue;\n-\t\tsrc_cnt = s->cnt;\n \t\td = spanhash_find(dst_count, s->hashval);\n-\t\tdst_cnt = d ? d->cnt : 0;\n+\t\tsrc_cnt = s->cnt * s->bytes;\n+\t\tdst_cnt = d ? (d->cnt * d->bytes) : 0;\n \t\tif (src_cnt < dst_cnt) {\n \t\t\tla += dst_cnt - src_cnt;\n \t\t\tsc += src_cnt;\n"},{"id":"17540","messageId":"Pine.LNX.4.64.0603131941260.3618@g5.osdl.org","threadId":"3632","inReplyTo":"7vveuhohve.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-14T03:47:41Z","receivedAt":"2006-03-14T03:47:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 13 Mar 2006, Junio C Hamano wrote:\n> \n> Here is still an WIP but an insanely fast one (actually this is\n> a modified version of what once was in next). I haven't\n> verified the sanity of its output fully, but from a cursory look\n> what are found look sensible. The same v2.6.12..v2.6.14 test on\n> my Duron 750:\n\nHeh. I did something similar, except I wanted mine to work with binary \ndata too. Not that I know how _well_ it works, but assuming you have \n_some_ '\\n' characters to fix up offset mismatches, it might do something.\n\nMine is a bit less hacky than yours, I believe. It doesn't skip \nwhitespace, instead it just maintains a rolling 64-bit number, where each \ncharacter shifts it left by 7 and then adds in the new character value \n(overflow in 32 bits just ignored).\n\nThen it uses your old hash function, except it hides the length in the top \nbyte.\n\nIt breaks the hashing on '\\n' or on hitting a 64-byte sequence, whichever \ncomes first.\n\nIt's fast and stupid, but doesn't seem to do any worse than your old one. \nThe speed comes from the fact that it only does the hash comparisons at \nthe \"block boundaries\", not at every byte.\n\nAnyway, I don't think something like this is really any good for rename \ndetection, but it might be good for deciding whether to do a real delta.\n\n\t\tLinus\n\n----\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 835d82c..4c6e512 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -127,7 +127,7 @@ static struct spanhash_top *add_spanhash\n \n static struct spanhash_top *hash_chars(unsigned char *buf, unsigned long sz)\n {\n-\tint i;\n+\tint i, n;\n \tunsigned long accum1, accum2, hashval;\n \tstruct spanhash_top *hash;\n \n@@ -137,19 +137,21 @@ static struct spanhash_top *hash_chars(u\n \thash->free = INITIAL_FREE(i);\n \tmemset(hash->data, 0, sizeof(struct spanhash) * (1<> 24);\n-\t\taccum2 = (accum2 << 8) | *buf++;\n-\t}\n+\tn = 0;\n+\taccum1 = accum2 = 0;\n \twhile (sz) {\n-\t\taccum1 = (accum1 << 8) | (accum2 >> 24);\n-\t\taccum2 = (accum2 << 8) | *buf++;\n+\t\tunsigned long c = *buf++;\n+\t\tsz--;\n+\t\taccum1 = (accum1 << 7) | (accum2 >> 25);\n+\t\taccum2 = (accum2 << 7) | (accum1 >> 25);\n+\t\taccum1 += c;\n+\t\tif (++n < 64 && c != '\\n')\n+\t\t\tcontinue;\n \t\thashval = (accum1 + accum2 * 0x61) % HASHBASE;\n+\t\thashval |= (n << 24);\n \t\thash = add_spanhash(hash, hashval);\n-\t\tsz--;\n+\t\tn = 0;\n+\t\taccum1 = accum2 = 0;\n \t}\n \treturn hash;\n }\n@@ -166,9 +168,6 @@ int diffcore_count_changes(void *src, un\n \tstruct spanhash_top *src_count, *dst_count;\n \tunsigned long sc, la;\n \n-\tif (src_size < 8 || dst_size < 8)\n-\t\treturn -1;\n-\n \tsrc_count = dst_count = NULL;\n \tif (src_count_p)\n \t\tsrc_count = *src_count_p;\n@@ -196,6 +195,8 @@ int diffcore_count_changes(void *src, un\n \t\tsrc_cnt = s->cnt;\n \t\td = spanhash_find(dst_count, s->hashval);\n \t\tdst_cnt = d ? d->cnt : 0;\n+\t\tdst_cnt *= (d->hashval >> 24);\n+\t\tsrc_cnt *= (d->hashval >> 24);\n \t\tif (src_cnt < dst_cnt) {\n \t\t\tla += dst_cnt - src_cnt;\n \t\t\tsc += src_cnt;\n"},{"id":"17541","messageId":"7v1wx5l3u9.fsf@assigned-by-dhcp.cox.net","threadId":"3632","inReplyTo":"Pine.LNX.4.64.0603131941260.3618@g5.osdl.org","subject":"Re: git-diff-tree -M performance regression in 'next'","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-14T10:26:22Z","receivedAt":"2006-03-14T10:26:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Mine is a bit less hacky than yours, I believe. It doesn't skip \n> whitespace, instead it just maintains a rolling 64-bit number, where each \n> character shifts it left by 7 and then adds in the new character value \n> (overflow in 32 bits just ignored).\n\nThat rolling register is a good idea. The \"whitespace hack\" was\ndone to recognize certain kind of changes that commonly appear\nin source code. For example, it will still recognize content\ncopies after you re-indent your code, or add an \"if (...) {\" and\n\"} else { ... }\" around an existing code block, or add extra\nblank lines.\n\nIt is still an inadequate hack. If you comment out a code block\nby adding \"#if 0\" and \"#endif\" around it, it notices the\nsurviving lines, but if instead you comment out a block by\nprefixing \"//\" in front of every line in the block, neither your\n64-byte-or-EOL or my extended line algorithm would notice that\nthe content copy anymore.\n\nAnyway, I did a bit of comparison and it appears that the\nwhitespace thing does not make much difference in practice.\n\n> It's fast and stupid, but doesn't seem to do any worse than your old one. \n\nComparing the \"next\" with your 64-byte-or-EOL and \"extended\nline\" on the v2.6.12..v2.6.14 test case shows:\n\n\t\t\t\t64-or-EOL\textended line\nrenames identically detected\t108\t\t110\nmatched differently\t\t2\t\t2\nfinds what\"next\" misses\t\t4\t\t4\nmisses what \"next\" finds\t23\t\t21\n\nWhat they find seem reasonable. What they reject are sometimes\ndebatable. For example, similarity between these two files does\nnot seem to be noticed by either.\n\n v2.6.12/drivers/media/dvb/dibusb/dvb-dibusb-firmware.c\n v2.6.14/drivers/media/dvb/dvb-usb/dvb-usb-firmware.c\n\nThe \"next\" algorithm gives 60% score while these two gives 45%\nor so to this pair.\n\nBut they both reject these bogus \"rename\" the \"next\" algorithm\nfinds:\n\n\tv2.6.12/drivers/char/drm/gamma_drv.c\n\tv2.6.14/drivers/char/drm/via_verifier.h\n\n(\"next\" 51% vs 37-40% with these algorithms). \n\n> Anyway, I don't think something like this is really any good for rename \n> detection, but it might be good for deciding whether to do a real delta.\n\nEither algorithm seem to have non-negligible false negative\nrates but their false positive rates are reasonably low. So we\ncould use these as a pre-filter and use real delta on pairs that\nthese quick and dirty algorithms say are too different.\n"}]}