{"thread":{"id":"30173","subject":"[PATCH v2] xdiff: load full words in the inner loop of xdl_hash_record","startedAt":"2012-04-06T21:01:23Z","lastAt":"2012-04-09T23:03:38Z","messageCount":2,"participants":["Thomas Rast","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"188689","messageId":"e0f938e9b849108e958da2e45e177f6f33d1118d.1333745883.git.trast@student.ethz.ch","threadId":"30173","inReplyTo":null,"subject":"[PATCH v2] xdiff: load full words in the inner loop of xdl_hash_record","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-04-06T21:01:23Z","receivedAt":"2012-04-06T21:01:23Z","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_64, where it provides nice speedup\nfor diff-related work:\n\n  Test                                  origin/next      tr/xdiff-fast-hash\n  -----------------------------------------------------------------------------\n  4000.1: log -3000 (baseline)          0.07(0.05+0.02)  0.08(0.06+0.02) +14.3%\n  4000.2: log --raw -3000 (tree-only)   0.37(0.33+0.04)  0.37(0.32+0.04) +0.0%\n  4000.3: log -p -3000 (Myers)          1.75(1.65+0.09)  1.60(1.49+0.10) -8.6%\n  4000.4: log -p -3000 --histogram      1.73(1.62+0.09)  1.58(1.49+0.08) -8.7%\n  4000.5: log -p -3000 --patience       2.11(2.00+0.10)  1.94(1.80+0.11) -8.1%\n\nPerhaps other platforms could also benefit.  However it does NOT work\non big-endian systems!\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n\nResending this now that 1.7.10 has been released.  There is one change\ncompared to the earlier version: the loading of the final partial word\nused\n\n  a = (a << 8) + *p\n\nwhere p is 'char *'.  This broke if *p has a high bit, because 'char'\nis signed here.  It now uses an unsigned char.\n\nI have verified that in both the git and linux repositories, all\npatch-ids are the same with the old and new hashing.\n\n\n Makefile       |   12 ++++++\n xdiff/xutils.c |  111 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 123 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..b198488 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -20,6 +20,8 @@\n  *\n  */\n \n+#include <limits.h>\n+#include <assert.h>\n #include \"xinclude.h\"\n \n \n@@ -276,6 +278,114 @@ 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\t * To avoid problems with masking in a signed value,\n+\t\t * we use an unsigned char here.\n+\t\t */\n+\t\tunsigned char 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 +403,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.241.g545e6\n"},{"id":"188824","messageId":"7viph8tsmt.fsf@alter.siamese.dyndns.org","threadId":"30173","inReplyTo":"e0f938e9b849108e958da2e45e177f6f33d1118d.1333745883.git.trast@student.ethz.ch","subject":"Re: [PATCH v2] xdiff: load full words in the inner loop of xdl_hash_record","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-09T23:03:38Z","receivedAt":"2012-04-09T23:03:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\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\nOk, because end is sufficiently below \"top\" and because you know \"top-1\"\nshould be a mapped byte, the \"ptr >= end\" check in the above loop ensures\nthat reading ul at ptr will stay within the range of mapped pages.\n\nCute but ugly ;-)\n"}]}