{"thread":{"id":"64113","subject":"[PATCH v2 1/4] xdiff: refactor xdl_hash_record()","startedAt":"2025-09-08T18:49:52Z","lastAt":"2025-09-08T18:49:57Z","messageCount":4,"participants":["Alexander Monakov"],"isPatch":true,"patchVersion":2,"patchTotal":4},"messages":[{"id":"525873","messageId":"20250908184939.16338-3-amonakov@ispras.ru","threadId":"64113","inReplyTo":"20250908184939.16338-1-amonakov@ispras.ru","subject":"[PATCH v2 3/4] xdiff: move hashing functions to a separate header","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-09-08T18:49:38Z","receivedAt":"2025-09-08T18:49:52Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"Move xdl_hash_record to a separate header file, and expose\nxdl_hash_record_verbatim as an inline function to avoid call overhead\nfor short strings.\n\nSigned-off-by: Alexander Monakov <amonakov@ispras.ru>\n---\n xdiff-interface.c |  1 +\n xdiff/xhash.h     | 52 +++++++++++++++++++++++++++++++++++++++++++++++\n xdiff/xinclude.h  |  1 +\n xdiff/xutils.c    | 13 ------------\n xdiff/xutils.h    |  9 --------\n 5 files changed, 54 insertions(+), 22 deletions(-)\n create mode 100644 xdiff/xhash.h\n\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 4971f722b3..e21a7aa0c9 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -12,6 +12,7 @@\n #include \"xdiff/xtypes.h\"\n #include \"xdiff/xdiffi.h\"\n #include \"xdiff/xutils.h\"\n+#include \"xdiff/xhash.h\"\n \n struct xdiff_emit_state {\n \txdiff_emit_hunk_fn hunk_fn;\ndiff --git a/xdiff/xhash.h b/xdiff/xhash.h\nnew file mode 100644\nindex 0000000000..27da4288c8\n--- /dev/null\n+++ b/xdiff/xhash.h\n@@ -0,0 +1,52 @@\n+/*\n+ *  LibXDiff by Davide Libenzi ( File Differential Library )\n+ *  Copyright (C) 2003  Davide Libenzi\n+ *\n+ *  This library is free software; you can redistribute it and/or\n+ *  modify it under the terms of the GNU Lesser General Public\n+ *  License as published by the Free Software Foundation; either\n+ *  version 2.1 of the License, or (at your option) any later version.\n+ *\n+ *  This library is distributed in the hope that it will be useful,\n+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\n+ *  Lesser General Public License for more details.\n+ *\n+ *  You should have received a copy of the GNU Lesser General Public\n+ *  License along with this library; if not, see\n+ *  <http://www.gnu.org/licenses/>.\n+ *\n+ *  Davide Libenzi <davidel@xmailserver.org>\n+ *\n+ */\n+\n+#if !defined(XHASH_H)\n+#define XHASH_H\n+\n+\n+\n+unsigned long xdl_hash_record_with_whitespace(char const **data, char const *top, long flags);\n+\n+static inline unsigned long xdl_hash_record_verbatim(char const **data, char const *top)\n+{\n+\tunsigned long ha = 5381;\n+\tchar const *ptr = *data;\n+\n+\tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n+\t\tha += (ha << 5);\n+\t\tha ^= (unsigned long) *ptr;\n+\t}\n+\t*data = ptr < top ? ptr + 1: ptr;\n+\n+\treturn ha;\n+}\n+\n+static inline unsigned long xdl_hash_record(char const **data, char const *top, long flags)\n+{\n+\tif (flags & XDF_WHITESPACE_FLAGS)\n+\t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n+\telse\n+\t\treturn xdl_hash_record_verbatim(data, top);\n+}\n+\n+#endif /* #if !defined(XHASH_H) */\ndiff --git a/xdiff/xinclude.h b/xdiff/xinclude.h\nindex a4285ac0eb..68b2d9f1f1 100644\n--- a/xdiff/xinclude.h\n+++ b/xdiff/xinclude.h\n@@ -31,6 +31,7 @@\n #include \"xprepare.h\"\n #include \"xdiffi.h\"\n #include \"xemit.h\"\n+#include \"xhash.h\"\n \n \n #endif /* #if !defined(XINCLUDE_H) */\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex e070ed649f..0fff5b26a0 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -294,19 +294,6 @@ unsigned long xdl_hash_record_with_whitespace(char const **data,\n \treturn ha;\n }\n \n-unsigned long xdl_hash_record_verbatim(char const **data, char const *top) {\n-\tunsigned long ha = 5381;\n-\tchar const *ptr = *data;\n-\n-\tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n-\t\tha += (ha << 5);\n-\t\tha ^= (unsigned long) *ptr;\n-\t}\n-\t*data = ptr < top ? ptr + 1: ptr;\n-\n-\treturn ha;\n-}\n-\n unsigned int xdl_hashbits(unsigned int size) {\n \tunsigned int val = 1, bits = 0;\n \ndiff --git a/xdiff/xutils.h b/xdiff/xutils.h\nindex 13f6831047..f51336fce1 100644\n--- a/xdiff/xutils.h\n+++ b/xdiff/xutils.h\n@@ -34,15 +34,6 @@ void *xdl_cha_alloc(chastore_t *cha);\n long xdl_guess_lines(mmfile_t *mf, long sample);\n int xdl_blankline(const char *line, long size, long flags);\n int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);\n-unsigned long xdl_hash_record_verbatim(char const **data, char const *top);\n-unsigned long xdl_hash_record_with_whitespace(char const **data, char const *top, long flags);\n-static inline unsigned long xdl_hash_record(char const **data, char const *top, long flags)\n-{\n-\tif (flags & XDF_WHITESPACE_FLAGS)\n-\t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n-\telse\n-\t\treturn xdl_hash_record_verbatim(data, top);\n-}\n unsigned int xdl_hashbits(unsigned int size);\n int xdl_num_out(char *out, long val);\n int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,\n-- \n2.49.1\n\n"},{"id":"525871","messageId":"20250908184939.16338-1-amonakov@ispras.ru","threadId":"64113","inReplyTo":null,"subject":"[PATCH v2 1/4] xdiff: refactor xdl_hash_record()","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-09-08T18:49:36Z","receivedAt":"2025-09-08T18:49:53Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nInline the check for whitespace flags so that the compiler can hoist\nit out of the loop in xdl_prepare_ctx(). This improves the performance\nby 8%.\n\n$ hyperfine --warmup=1 -L rev HEAD,HEAD^  --setup='git checkout {rev} -- :/ && make git' ': {rev}; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0'\nBenchmark 1: : HEAD; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0\n  Time (mean ± σ):      1.670 s ±  0.044 s    [User: 1.473 s, System: 0.196 s]\n  Range (min … max):    1.619 s …  1.754 s    10 runs\n\nBenchmark 2: : HEAD^; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0\n  Time (mean ± σ):      1.801 s ±  0.021 s    [User: 1.605 s, System: 0.192 s]\n  Range (min … max):    1.766 s …  1.831 s    10 runs\n\nSummary\n  ': HEAD^; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0' ran\n    1.08 ± 0.03 times faster than ': HEAD^^; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0'\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xutils.c |  7 ++-----\n xdiff/xutils.h | 10 +++++++++-\n 2 files changed, 11 insertions(+), 6 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 444a108f87..e070ed649f 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -249,7 +249,7 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n \treturn 1;\n }\n \n-static unsigned long xdl_hash_record_with_whitespace(char const **data,\n+unsigned long xdl_hash_record_with_whitespace(char const **data,\n \t\tchar const *top, long flags) {\n \tunsigned long ha = 5381;\n \tchar const *ptr = *data;\n@@ -294,13 +294,10 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n \treturn ha;\n }\n \n-unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n+unsigned long xdl_hash_record_verbatim(char const **data, char const *top) {\n \tunsigned long ha = 5381;\n \tchar const *ptr = *data;\n \n-\tif (flags & XDF_WHITESPACE_FLAGS)\n-\t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n-\n \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n \t\tha += (ha << 5);\n \t\tha ^= (unsigned long) *ptr;\ndiff --git a/xdiff/xutils.h b/xdiff/xutils.h\nindex fd0bba94e8..13f6831047 100644\n--- a/xdiff/xutils.h\n+++ b/xdiff/xutils.h\n@@ -34,7 +34,15 @@ void *xdl_cha_alloc(chastore_t *cha);\n long xdl_guess_lines(mmfile_t *mf, long sample);\n int xdl_blankline(const char *line, long size, long flags);\n int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);\n-unsigned long xdl_hash_record(char const **data, char const *top, long flags);\n+unsigned long xdl_hash_record_verbatim(char const **data, char const *top);\n+unsigned long xdl_hash_record_with_whitespace(char const **data, char const *top, long flags);\n+static inline unsigned long xdl_hash_record(char const **data, char const *top, long flags)\n+{\n+\tif (flags & XDF_WHITESPACE_FLAGS)\n+\t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n+\telse\n+\t\treturn xdl_hash_record_verbatim(data, top);\n+}\n unsigned int xdl_hashbits(unsigned int size);\n int xdl_num_out(char *out, long val);\n int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,\n-- \n2.49.1\n\n"},{"id":"525872","messageId":"20250908184939.16338-4-amonakov@ispras.ru","threadId":"64113","inReplyTo":"20250908184939.16338-1-amonakov@ispras.ru","subject":"[PATCH v2 4/4] xdiff: use a faster hash in xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-09-08T18:49:39Z","receivedAt":"2025-09-08T18:49:54Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"Reimplement xdl_hash_record_verbatim such that it computes two djb2\nhashes for even and odd characters independently, each at latency two\nper character. The new loop is expected to be issue and execution\nport throughput bound at three cycles per a pair of characters. The\nmore efficient ways to evaluate such hashes involve use of\nmultiplication and higher interleaving factors. The scheme used here\nis expected to be a reasonable compromise for lines of source code\n(i.e. not very long strings).\n\nDue to interleaving, the new function does not produce the same hash\nvalues as the original. Given values H0 for even characters and H1\nfor odd characters, we combine them to produce the final hash value\nas 'H1 * 257 + H0'. The factor 257 is chosen to approximately match\nthe original in quality (collision count in xdiff hashtable).\n\nSigned-off-by: Alexander Monakov <amonakov@ispras.ru>\n---\n xdiff/xhash.h | 62 +++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 55 insertions(+), 7 deletions(-)\n\ndiff --git a/xdiff/xhash.h b/xdiff/xhash.h\nindex 27da4288c8..1e9e13cc45 100644\n--- a/xdiff/xhash.h\n+++ b/xdiff/xhash.h\n@@ -29,16 +29,64 @@ unsigned long xdl_hash_record_with_whitespace(char const **data, char const *top\n \n static inline unsigned long xdl_hash_record_verbatim(char const **data, char const *top)\n {\n-\tunsigned long ha = 5381;\n \tchar const *ptr = *data;\n-\n-\tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n-\t\tha += (ha << 5);\n-\t\tha ^= (unsigned long) *ptr;\n+#if 0\n+\t/*\n+\t * djb2 hash (below) is latency-bound; on x86, this baseline form cannot\n+\t * run faster than two cycles per iteration, and to achieve that it is\n+\t * neccessary to arrange for 'ha * 32' to be computed in parallel with\n+\t * 'ha + ch'. To avoid being latency-bound, we run two independent djb2\n+\t * hashes over even and odd characters, then combine them in the end.\n+\t * The resulting hash is not equivalent to the original djb2.\n+\t */\n+\tunsigned long ha = 5381, ch;\n+\twhile (ptr < top) {\n+\t\tif ((ch = *ptr++) == '\\n')\n+\t\t\tbreak;\n+\t\tha = ha * 33 + ch;\n \t}\n-\t*data = ptr < top ? ptr + 1: ptr;\n-\n+\t*data = ptr;\n \treturn ha;\n+#else\n+#ifdef __GNUC__\n+/*\n+ * Compiler reassociation barrier: pretend to modify X and Y to disallow\n+ * changing evaluation order with respect to following uses of X or Y.\n+ */\n+#define REASSOC_FENCE(x, y) __asm__(\"\" : \"+r\"(x), \"+r\"(y))\n+#else\n+#define REASSOC_FENCE(x, y)\n+#endif\n+\tunsigned long h0 = 5381, h1 = 0, ch;\n+\t/* Process two characters per iteration. */\n+\tif (top - ptr >= 2) do {\n+\t\tif ((ch = *ptr++) == '\\n') {\n+\t\t\t*data = ptr;\n+\t\t\th0 += h1;\n+\t\t\tREASSOC_FENCE(h0, h1);\n+\t\t\treturn h1 * 256 + h0;\n+\t\t}\n+\t\tch += h0;\n+\t\tREASSOC_FENCE(ch, h0);\n+\t\th0 = h0 * 32 + ch;\n+\n+\t\tif ((ch = *ptr++) == '\\n') {\n+\t\t\t*data = ptr;\n+\t\t\th0 += h1;\n+\t\t\tREASSOC_FENCE(h0, h1);\n+\t\t\treturn h1 * 256 + h0;\n+\t\t}\n+\t\tch += h1;\n+\t\tREASSOC_FENCE(ch, h1);\n+\t\th1 = h1 * 32 + ch;\n+\n+\t} while (ptr < top - 1);\n+\t*data = top;\n+\tif (ptr < top && (ch = *ptr++) != '\\n')\n+\t\th0 = h0 * 33 + ch;\n+\treturn h1 * 257 + h0;\n+#undef REASSOC_FENCE\n+#endif\n }\n \n static inline unsigned long xdl_hash_record(char const **data, char const *top, long flags)\n-- \n2.49.1\n\n"},{"id":"525874","messageId":"20250908184939.16338-2-amonakov@ispras.ru","threadId":"64113","inReplyTo":"20250908184939.16338-1-amonakov@ispras.ru","subject":"[PATCH v2 2/4] xdiff: annotate unlikely branch","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-09-08T18:49:37Z","receivedAt":"2025-09-08T18:49:57Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"XDL_ALLOC_GROW is used in a hot loop in xdl_prepare_ctx. Inform the\ncompiler that branching to the reallocation helper happens rarely\nto improve code layout.\n\nSigned-off-by: Alexander Monakov <amonakov@ispras.ru>\n---\n xdiff/xmacros.h | 11 +++++++----\n 1 file changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/xdiff/xmacros.h b/xdiff/xmacros.h\nindex 8487bb396f..d892e022d4 100644\n--- a/xdiff/xmacros.h\n+++ b/xdiff/xmacros.h\n@@ -23,8 +23,11 @@\n #if !defined(XMACROS_H)\n #define XMACROS_H\n \n-\n-\n+#if __GNUC__ >= 3\n+#define XDL_LIKELY(e) __builtin_expect((e), 1)\n+#else\n+#define XDL_LIKELY(e) (e)\n+#endif\n \n #define XDL_MIN(a, b) ((a) < (b) ? (a): (b))\n #define XDL_MAX(a, b) ((a) > (b) ? (a): (b))\n@@ -64,8 +67,8 @@ do { \\\n  * elements) as necessary. Frees p and returns -1 on failure, returns\n  * 0 on success\n  */\n-#define XDL_ALLOC_GROW(p, nr, alloc)\t\\\n-\t(-!((nr) <= (alloc) ||\t\t\\\n+#define XDL_ALLOC_GROW(p, nr, alloc)\t    \\\n+\t(-!(XDL_LIKELY((nr) <= (alloc)) ||  \\\n \t    ((p) = xdl_alloc_grow_helper((p), (nr), &(alloc), sizeof(*(p))))))\n \n #endif /* #if !defined(XMACROS_H) */\n-- \n2.49.1\n\n"}]}