{"thread":{"id":"29917","subject":"[PATCH] xdiff: load full words in the inner loop of xdl_hash_record","startedAt":"2012-03-12T15:10:13Z","lastAt":"2012-03-12T20:59:08Z","messageCount":4,"participants":["Thomas Rast","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"186711","messageId":"1e11b1466ea3209cfe74e1dd8dff45f8666e942b.1331564754.git.trast@student.ethz.ch","threadId":"29917","inReplyTo":null,"subject":"[PATCH] xdiff: load full words in the inner loop of xdl_hash_record","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-12T15:10:13Z","receivedAt":"2012-03-12T15:10:13Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Redo the hashing loop in xdl_hash_record in a way that loads an entire\n'long' at a time, using masking tricks to see when and where we found\nthe terminating '\\n'.\n\nI stole inspiration and code from the posts by Linus Torvalds around\n\n https://lkml.org/lkml/2012/3/2/452\n https://lkml.org/lkml/2012/3/5/6\n\nHis method reads the buffers in sizeof(long) increments, and may thus\noverrun it by at most sizeof(long)-1 bytes before it sees the final\nnewline (or hits the buffer length check). I considered padding out\nall buffers by a suitable amount to \"catch\" the overrun, but\n\n* this does not work for mmap()'d buffers: if you map 4096+8 bytes\n from a 4096 byte file, accessing the last 8 bytes results in a\n SIGBUS on my machine; and\n\n* it would also be extremely ugly because it intrudes deep into the\n unpacking machinery.\n\nSo I adapted it to not read beyond the buffer at all. Instead, it\nreads the final partial word byte-by-byte and strings it together.\nThen it can use the same logic as before to finish the hashing.\n\nSo far we enable this only on x86; perhaps other platforms could also\nbenefit. However it does NOT work on big-endian systems!\n\nThe resulting speedup is about 7% in 'log -p' workloads:\n\n Test t/proper-xdl-speedup origin/master \n -------------------------------------------------------------------------------------\n 4000.1: log -3000 (baseline) 0.08(0.06+0.01) 0.08(0.07+0.01) +3.0% \n 4000.2: log --raw -3000 (tree-only) 0.40(0.34+0.04) 0.40(0.34+0.05) -1.6% \n 4000.3: log -p -3000 (Myers) 1.63(1.51+0.10) 1.75(1.64+0.10) +7.4%*** \n 4000.4: log -p -3000 --histogram 1.60(1.50+0.09) 1.73(1.63+0.08) +8.4%*** \n 4000.5: log -p -3000 --patience 1.95(1.83+0.10) 2.07(1.96+0.10) +6.5%*** \n -------------------------------------------------------------------------------------\n Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n\nSigned-off-by: Thomas Rast \n---\n\nAlso definitely post-v1.7.10 material, but I figure many people will\nbe interested. Since it's such a central part of much of git, it's\nalso quite important that it gets tested heavily.\n\nFor blame I get the following speedups:\n\n Test t/proper-xdl-speedup origin/master \n ---------------------------------------------------------------------------------------\n 8002.2: blame 1.93(1.80+0.12) 1.92(1.79+0.12) -0.8%* \n 8002.3: blame -M 2.05(1.91+0.12) 2.04(1.90+0.12) -0.4% \n 8002.4: blame -C 2.26(2.11+0.13) 2.24(2.10+0.12) -1.0%* \n 8002.5: blame -C -C 3.34(3.15+0.18) 3.47(3.28+0.18) +3.9%*** \n 8002.6: blame -C -C -C 13.76(13.29+0.42) 14.72(14.27+0.41) +7.0%***\n ---------------------------------------------------------------------------------------\n Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n\nThis is using p8002 and the t-test from the perf series I am sending\nout in parallel. It strikes me as odd that blame does not benefit\nunless it uses at least -C -C; my understanding is that blame consists\nlargely of diffing. Apparently there's more to it...\n\n\n Makefile | 12 +++++++\n xdiff/xutils.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 120 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex be1957a..13ed1b1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -288,6 +288,11 @@ all::\n # dependency rules.\n #\n # Define NATIVE_CRLF if your platform uses CRLF for line endings.\n+#\n+# Define XDL_FAST_HASH to use an alternative line-hashing method in\n+# the diff algorithm. It gives a nice speedup if your processor has\n+# fast unaligned word loads. Does NOT work on big-endian systems!\n+# Enabled by default on x86_64.\n \n GIT-VERSION-FILE: FORCE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -864,6 +869,9 @@ EXTLIBS =\n # because maintaining the nesting to match is a pain. If\n # we had \"elif\" things would have been much nicer...\n \n+ifeq ($(uname_M),x86_64)\n+\tXDL_FAST_HASH = YesPlease\n+endif\n ifeq ($(uname_S),OSF1)\n \t# Need this for u_short definitions et al\n \tBASIC_CFLAGS += -D_OSF_SOURCE\n@@ -1737,6 +1745,10 @@ ifndef NO_MSGFMT_EXTENDED_OPTIONS\n \tMSGFMT += --check --statistics\n endif\n \n+ifneq (,$(XDL_FAST_HASH))\n+\tBASIC_CFLAGS += -DXDL_FAST_HASH\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n endif\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 0de084e..415e08a 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -20,6 +20,8 @@\n *\n */\n \n+#include \n+#include \n #include \"xinclude.h\"\n \n \n@@ -276,6 +278,111 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n \treturn ha;\n }\n \n+#ifdef XDL_FAST_HASH\n+\n+#define ONEBYTES\t0x0101010101010101ul\n+#define NEWLINEBYTES\t0x0a0a0a0a0a0a0a0aul\n+#define HIGHBITS\t0x8080808080808080ul\n+\n+/* Return the high bit set in the first byte that is a zero */\n+static inline unsigned long has_zero(unsigned long a)\n+{\n+\treturn ((a - ONEBYTES) & ~a) & HIGHBITS;\n+}\n+\n+#if __WORDSIZE == 64\n+\n+/*\n+ * Jan Achrenius on G+: microoptimized version of\n+ * the simpler \"(mask & ONEBYTES) * ONEBYTES >> 56\"\n+ * that works for the bytemasks without having to\n+ * mask them first.\n+ */\n+static inline long count_masked_bytes(unsigned long mask)\n+{\n+\treturn mask*0x0001020304050608 >> 56;\n+}\n+\n+#else\t/* 32-bit case */\n+\n+/* Modified Carl Chatfield G+ version for 32-bit */\n+static inline long count_masked_bytes(long mask)\n+{\n+\t/*\n+\t * (a) gives us\n+\t * -1 (0, ff), 0 (ffff) or 1 (ffffff)\n+\t * (b) gives us\n+\t * 0 for 0, 1 for (ff ffff ffffff)\n+\t * (a+b+1) gives us\n+\t * correct 0-3 bytemask count result\n+\t */\n+\tlong a = (mask-256) >> 23;\n+\tlong b = mask & 1;\n+\treturn a + b + 1;\n+}\n+\n+#endif\n+\n+unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n+\tunsigned long hash = 5381;\n+\tunsigned long a = 0, mask = 0;\n+\tchar const *ptr = *data;\n+\tchar const *end = top-sizeof(unsigned long)+1;\n+\n+\tif (flags & XDF_WHITESPACE_FLAGS)\n+\t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n+\n+\tptr -= sizeof(unsigned long);\n+\tdo {\n+\t\thash += hash << 5;\n+\t\thash ^= a;\n+\t\tptr += sizeof(unsigned long);\n+\t\tif (ptr >= end)\n+\t\t\tbreak;\n+\t\ta = *(unsigned long *)ptr;\n+\t\t/* Do we have any '\\n' bytes in this word? */\n+\t\tmask = has_zero(a ^ NEWLINEBYTES);\n+\t} while (!mask);\n+\n+\tif (ptr >= end) {\n+\t\t/*\n+\t\t * There is only a partial word left at the end of the\n+\t\t * buffer. Because we may work with a memory mapping,\n+\t\t * we have to grab the rest byte by byte instead of\n+\t\t * blindly reading it.\n+\t\t */\n+\t\tchar const *p;\n+\t\tfor (p = top-1; p >= ptr; p--)\n+\t\t\ta = (a << 8) + *p;\n+\t\tmask = has_zero(a ^ NEWLINEBYTES);\n+\t\tif (!mask)\n+\t\t\t/*\n+\t\t\t * No '\\n' found in the partial word. Make a\n+\t\t\t * mask that matches what we read.\n+\t\t\t */\n+\t\t\tmask = 1UL << (8*(top-ptr)+7);\n+\t}\n+\n+\t/* The mask *below* the first high bit set */\n+\tmask = (mask - 1) & ~mask;\n+\tmask >>= 7;\n+\thash += hash << 5;\n+\thash ^= a & mask;\n+\n+\t/* Advance past the last (possibly partial) word */\n+\tptr += count_masked_bytes(mask);\n+\n+\tif (ptr < top) {\n+\t\tassert (*ptr == '\\n');\n+\t\tptr++;\n+\t}\n+\n+\t*data = ptr;\n+\n+\treturn hash;\n+}\n+\n+#else /* XDL_FAST_HASH */\n \n unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n \tunsigned long ha = 5381;\n@@ -293,6 +400,7 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n \treturn ha;\n }\n \n+#endif /* XDL_FAST_HASH */\n \n unsigned int xdl_hashbits(unsigned int size) {\n \tunsigned int val = 1, bits = 0;\n-- \n1.7.10.rc0.230.g16d90\n"},{"id":"186754","messageId":"7vmx7lsmjd.fsf@alter.siamese.dyndns.org","threadId":"29917","inReplyTo":"1e11b1466ea3209cfe74e1dd8dff45f8666e942b.1331564754.git.trast@student.ethz.ch","subject":"Re: [PATCH] xdiff: load full words in the inner loop of xdl_hash_record","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-12T18:26:46Z","receivedAt":"2012-03-12T18:26:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Also definitely post-v1.7.10 material, but I figure many people will\n> be interested. Since it's such a central part of much of git, it's\n> also quite important that it gets tested heavily.\n\nI am interested but this is a material not beyond 'pu'. Until it\nlearns to be nice on platforms that do not like unaligned accesses\nor use big endian, that is.\n\nThanks for a fun read, though.\n"},{"id":"186773","messageId":"877gypr319.fsf@thomas.inf.ethz.ch","threadId":"29917","inReplyTo":"7vmx7lsmjd.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] xdiff: load full words in the inner loop of xdl_hash_record","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-03-12T20:13:22Z","receivedAt":"2012-03-12T20:13:22Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> Also definitely post-v1.7.10 material, but I figure many people will\n>> be interested. Since it's such a central part of much of git, it's\n>> also quite important that it gets tested heavily.\n>\n> I am interested but this is a material not beyond 'pu'. Until it\n> learns to be nice on platforms that do not like unaligned accesses\n> or use big endian, that is.\n\nUmm, nice how? It leaves in the old version for those platforms. I can\nperhaps make it #error if we are unhappy about the user's platform, but\nthat's about it. Testing for endianness is possible, but testing for\nunaligned access risks SIGBUS and thus requires spawning a helper\nprogram.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"186781","messageId":"7v62e9r0wz.fsf@alter.siamese.dyndns.org","threadId":"29917","inReplyTo":"877gypr319.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH] xdiff: load full words in the inner loop of xdl_hash_record","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-12T20:59:08Z","receivedAt":"2012-03-12T20:59:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Junio C Hamano writes:\n>\n>> Thomas Rast writes:\n>>\n>>> Also definitely post-v1.7.10 material, but I figure many people will\n>>> be interested. Since it's such a central part of much of git, it's\n>>> also quite important that it gets tested heavily.\n>>\n>> I am interested but this is a material not beyond 'pu'. Until it\n>> learns to be nice on platforms that do not like unaligned accesses\n>> or use big endian, that is.\n>\n> Umm, nice how? It leaves in the old version for those platforms.\n\nAh, I misread the patch and somehow thought you are unconditionally\nreplacing the code with the optimized one.\n\nNo, I didn't mean to suggest autodetection.\n"}]}