{"thread":{"id":"63866","subject":"[PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","startedAt":"2025-07-28T19:05:34Z","lastAt":"2025-09-08T21:04:19Z","messageCount":22,"participants":["Alexander Monakov","Junio C Hamano","Eli Schwartz","Phillip Wood","Jacob Keller","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"522875","messageId":"20250728190520.10962-3-amonakov@ispras.ru","threadId":"63866","inReplyTo":"20250728190520.10962-1-amonakov@ispras.ru","subject":"[PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-07-28T19:05:20Z","receivedAt":"2025-07-28T19:05:34Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"xdl_hash_record_verbatim uses modified djb2 hash with XOR instead of ADD\nfor combining. The ADD-based variant is used as the basis of the modern\n(\"GNU\") symbol lookup scheme in ELF. Glibc dynamic loader received an\noptimized version of this hash function thanks to Noah Goldstein [1].\n\nSwitch xdl_hash_record_verbatim to additive hashing and implement\nan optimized loop following the scheme suggested by Noah.\n\nTiming 'git log --oneline --shortstat v2.0.0..v2.5.0' under perf, I got\n\nversion | cycles, bn | instructions, bn\n---------------------------------------\nA 6.38 11.3\nB 6.21 10.89\nC 5.80 9.95\nD 5.83 8.74\n---------------------------------------\n\nA: baseline (git master at e4ef0485fd78)\nB: plus 'xdiff: refactor xdl_hash_record()'\nC: and plus this patch\nD: with 'xdiff: use xxhash' by Phillip Wood\n\nThe resulting speedup for xdl_hash_record_verbatim itself is about 1.5x.\n\n[1] https://inbox.sourceware.org/libc-alpha/20220519221803.57957-6-goldstein.w.n@gmail.com/\n\nSigned-off-by: Alexander Monakov \n---\n xdiff/xutils.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 55 insertions(+), 4 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex e070ed649f..b1f8273f0f 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -294,16 +294,67 @@ unsigned long xdl_hash_record_with_whitespace(char const **data,\n \treturn ha;\n }\n \n+/*\n+ * Compiler reassociation barrier: pretend to modify X and Y to disallow\n+ * changing evaluation order with respect to following uses of X and Y.\n+ */\n+#ifdef __GNUC__\n+#define REASSOC_FENCE(x, y) asm(\"\" : \"+r\"(x), \"+r\"(y))\n+#else\n+#define REASSOC_FENCE(x, y)\n+#endif\n+\n unsigned long xdl_hash_record_verbatim(char const **data, char const *top) {\n-\tunsigned long ha = 5381;\n+\tunsigned long ha = 5381, c0, c1;\n \tchar const *ptr = *data;\n-\n+#if 0\n+\t/*\n+\t * The baseline form of the optimized loop below. This is the djb2\n+\t * hash (the above function uses a variant with XOR instead of ADD).\n+\t */\n \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n \t\tha += (ha << 5);\n-\t\tha ^= (unsigned long) *ptr;\n+\t\tha += (unsigned long) *ptr;\n \t}\n \t*data = ptr < top ? ptr + 1: ptr;\n-\n+#else\n+\t/* Process two characters per iteration. */\n+\tif (top - ptr >= 2) do {\n+\t\tif ((c0 = ptr[0]) == '\\n') {\n+\t\t\t*data = ptr + 1;\n+\t\t\treturn ha;\n+\t\t}\n+\t\tif ((c1 = ptr[1]) == '\\n') {\n+\t\t\t*data = ptr + 2;\n+\t\t\tc0 += ha;\n+\t\t\tREASSOC_FENCE(c0, ha);\n+\t\t\tha = ha * 32 + c0;\n+\t\t\treturn ha;\n+\t\t}\n+\t\t/*\n+\t\t * Combine characters C0 and C1 into the hash HA. We have\n+\t\t * HA = (HA * 33 + C0) * 33 + C1, and we want to ensure\n+\t\t * that dependency chain over HA is just one multiplication\n+\t\t * and one addition, i.e. we want to evaluate this as\n+\t\t * HA = HA * 33 * 33 + (C0 * 33 + C1), and likewise prefer\n+\t\t * (C0 * 32 + (C0 + C1)) for the expression in parenthesis.\n+\t\t */\n+\t\tha *= 33 * 33;\n+\t\tc1 += c0;\n+\t\tREASSOC_FENCE(c1, c0);\n+\t\tc1 += c0 * 32;\n+\t\tREASSOC_FENCE(c1, ha);\n+\t\tha += c1;\n+\n+\t\tptr += 2;\n+\t} while (ptr < top - 1);\n+\t*data = top;\n+\tif (ptr < top && (c0 = ptr[0]) != '\\n') {\n+\t\tc0 += ha;\n+\t\tREASSOC_FENCE(c0, ha);\n+\t\tha = ha * 32 + c0;\n+\t}\n+#endif\n \treturn ha;\n }\n \n-- \n2.44.2\n\n"},{"id":"522877","messageId":"20250728190520.10962-1-amonakov@ispras.ru","threadId":"63866","inReplyTo":null,"subject":"[PATCH 0/2] optimize string hashing in xdiff","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-07-28T19:05:18Z","receivedAt":"2025-07-28T19:12:33Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"Hello world,\n\nI've noticed the work by Phillip Wood regarding hash optimization for xdiff.\nI want to point out that it is possible to speed up the existing hash by 1.5x\nmatching the peformance of xxhash (but without introducing a dependendency).\n\nThe additive variant of the djb2 hash is used in ELF symbol lookup, and\nNoah Goldstein contributed a well-optimized implementation to Glibc.\n\nI'm taking the refactoring patch from Phillip and building on top of it.\n\nAlexander Monakov (1):\n xdiff: optimize xdl_hash_record_verbatim\n\nPhillip Wood (1):\n xdiff: refactor xdl_hash_record()\n\n xdiff/xutils.c | 66 +++++++++++++++++++++++++++++++++++++++++++-------\n xdiff/xutils.h | 10 +++++++-\n 2 files changed, 66 insertions(+), 10 deletions(-)\n\n-- \n2.44.2\n\n"},{"id":"522878","messageId":"20250728190520.10962-2-amonakov@ispras.ru","threadId":"63866","inReplyTo":"20250728190520.10962-1-amonakov@ispras.ru","subject":"[PATCH 1/2] xdiff: refactor xdl_hash_record()","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-07-28T19:05:19Z","receivedAt":"2025-07-28T19:12:33Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"From: Phillip Wood \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 \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.44.2\n\n"},{"id":"522879","messageId":"xmqqa54oun5w.fsf@gitster.g","threadId":"63866","inReplyTo":"20250728190520.10962-1-amonakov@ispras.ru","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-28T19:32:11Z","receivedAt":"2025-07-28T19:32:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Monakov writes:\n\n> I've noticed the work by Phillip Wood regarding hash optimization for xdiff.\n> I want to point out that it is possible to speed up the existing hash by 1.5x\n> matching the peformance of xxhash (but without introducing a dependendency).\n\nUsing xxhash() was merely a sample code path for technology\ndemonstration, so the Rust adoption topic may want to pick a\ndifferent code path to do its thing.\n\n> The additive variant of the djb2 hash is used in ELF symbol lookup, and\n> Noah Goldstein contributed a well-optimized implementation to Glibc.\n\nWhat is the licensing terms for that code you are proposing us to\nborrow? If it is anything recent in GNU, I'd expect that it would\nbe GPLv3, which would be incompatible with our code base?\n\n> I'm taking the refactoring patch from Phillip and building on top of it.\n\nIt is an obviously good approach to do this.\n\n"},{"id":"522883","messageId":"2e70fce9-1779-4d35-ae65-42792e710054@gentoo.org","threadId":"63866","inReplyTo":"xmqqa54oun5w.fsf@gitster.g","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Eli Schwartz","fromEmail":"eschwartz@gentoo.org","sentAt":"2025-07-28T19:56:21Z","receivedAt":"2025-07-28T19:56:30Z","isPatch":true,"sender":{"key":"eschwartz@gentoo.org","avatar":"https://avatars.githubusercontent.com/u/6551424?v=4"},"body":"On 7/28/25 3:32 PM, Junio C Hamano wrote:\n\n>> The additive variant of the djb2 hash is used in ELF symbol lookup, and\n>> Noah Goldstein contributed a well-optimized implementation to Glibc.\n> \n> What is the licensing terms for that code you are proposing us to\n> borrow? If it is anything recent in GNU, I'd expect that it would\n> be GPLv3, which would be incompatible with our code base?\n\n\nThat feels like a quite surprising assessment. Many GNU projects make\nspecific calculations here. See:\n\nhttps://www.gnu.org/licenses/gpl-faq.html#DoesAllGNUSoftwareUseTheGNUGPLAsItsLicense\n\nhttps://www.gnu.org/licenses/why-not-lgpl.html\n\n\nAt any rate, quite untrue. Glibc's wikipedia page -- and also its source\ncode, luckily -- documents \"LGPL-2.1-or-later\", which is more permissive\nthan git (and equally as permissive as xdiff).\n\nReason is documented in the second link. :)\n\n\n-- \nEli Schwartz\n"},{"id":"522894","messageId":"43459416-ced2-d551-40e3-6db594ca4520@ispras.ru","threadId":"63866","inReplyTo":"xmqqa54oun5w.fsf@gitster.g","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-07-28T20:25:07Z","receivedAt":"2025-07-28T20:25:14Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"On Mon, 28 Jul 2025, Junio C Hamano wrote:\n\n> Alexander Monakov writes:\n> \n> > I've noticed the work by Phillip Wood regarding hash optimization for xdiff.\n> > I want to point out that it is possible to speed up the existing hash by 1.5x\n> > matching the peformance of xxhash (but without introducing a dependendency).\n> \n> Using xxhash() was merely a sample code path for technology\n> demonstration, so the Rust adoption topic may want to pick a\n> different code path to do its thing.\n\nMy interest here is just speeding up xdiff in C, is that a welcome topic?\n\n> > The additive variant of the djb2 hash is used in ELF symbol lookup, and\n> > Noah Goldstein contributed a well-optimized implementation to Glibc.\n> \n> What is the licensing terms for that code you are proposing us to\n> borrow? If it is anything recent in GNU, I'd expect that it would\n> be GPLv3, which would be incompatible with our code base?\n\nNoah's code is not usable in xdiff due to different context (mainly the need\nto limit iteration by length — ELF hashing iterates until the NUL character).\n\nI have participated in review of Noah's patches and he kindly listed me as\na co-author in the final revision of his patchset. So while I'm aware of how\nhis code is structured, I had to write a new implementation in order to meet\nthe contract of xdl_hash_record_verbatim. Therefore I think I can contribute\nthis code on GPLv2 terms with my sign-off.\n\nMaybe someone would be willing to look at patch 2 and compare against Noah's\npatch (linked in the commit message)?\n\nThank you.\nAlexander"},{"id":"522896","messageId":"xmqq5xfcujjn.fsf@gitster.g","threadId":"63866","inReplyTo":"20250728190520.10962-3-amonakov@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-28T20:50:20Z","receivedAt":"2025-07-28T20:50:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Monakov writes:\n\n> +/*\n> + * Compiler reassociation barrier: pretend to modify X and Y to disallow\n> + * changing evaluation order with respect to following uses of X and Y.\n> + */\n> +#ifdef __GNUC__\n> +#define REASSOC_FENCE(x, y) asm(\"\" : \"+r\"(x), \"+r\"(y))\n> +#else\n> +#define REASSOC_FENCE(x, y)\n> +#endif\n\nWith gcc we can build, but with clang, we unfortunately get this:\n\n $ make CC=clang DEVELOPER=YesPlease\n xdiff/xutils.c:330:4: error: extension used [-Werror,-Wlanguage-extension-token]\n 330 | REASSOC_FENCE(c0, ha);\n | ^\n xdiff/xutils.c:302:29: note: expanded from macro 'REASSOC_FENCE'\n 302 | #define REASSOC_FENCE(x, y) asm(\"\" : \"+r\"(x), \"+r\"(y))\n | ^\n\n"},{"id":"522899","messageId":"xmqqseigt4sp.fsf@gitster.g","threadId":"63866","inReplyTo":"2e70fce9-1779-4d35-ae65-42792e710054@gentoo.org","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-07-28T20:54:14Z","receivedAt":"2025-07-28T20:54:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eli Schwartz writes:\n\n> At any rate, quite untrue. Glibc's wikipedia page -- and also its source\n> code, luckily -- documents \"LGPL-2.1-or-later\", which is more permissive\n> than git (and equally as permissive as xdiff).\n\nAh, OK. That sound very nice. Thanks for correcting me.\n"},{"id":"522900","messageId":"3405f274-cef1-b361-7424-840dc55b48a1@ispras.ru","threadId":"63866","inReplyTo":"xmqq5xfcujjn.fsf@gitster.g","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-07-28T20:57:18Z","receivedAt":"2025-07-28T20:57:21Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"On Mon, 28 Jul 2025, Junio C Hamano wrote:\n\n> Alexander Monakov writes:\n> \n> > +/*\n> > + * Compiler reassociation barrier: pretend to modify X and Y to disallow\n> > + * changing evaluation order with respect to following uses of X and Y.\n> > + */\n> > +#ifdef __GNUC__\n> > +#define REASSOC_FENCE(x, y) asm(\"\" : \"+r\"(x), \"+r\"(y))\n> > +#else\n> > +#define REASSOC_FENCE(x, y)\n> > +#endif\n> \n> With gcc we can build, but with clang, we unfortunately get this:\n> \n> $ make CC=clang DEVELOPER=YesPlease\n> xdiff/xutils.c:330:4: error: extension used [-Werror,-Wlanguage-extension-token]\n> 330 | REASSOC_FENCE(c0, ha);\n> | ^\n> xdiff/xutils.c:302:29: note: expanded from macro 'REASSOC_FENCE'\n> 302 | #define REASSOC_FENCE(x, y) asm(\"\" : \"+r\"(x), \"+r\"(y))\n> | ^\n\nSorry, wasn't aware that Clang would warn. The solution is to spell 'asm' with\ndouble underscores, __asm__. I'll make this change if I post a v2.\n\nThanks.\nAlexander\n"},{"id":"523441","messageId":"aedb1be1-3151-421e-94ce-27bc77d80b83@gmail.com","threadId":"63866","inReplyTo":"20250728190520.10962-3-amonakov@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-08-04T13:49:41Z","receivedAt":"2025-08-04T13:49:47Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Alexander\n\nOn 28/07/2025 20:05, Alexander Monakov wrote:\n> xdl_hash_record_verbatim uses modified djb2 hash with XOR instead of ADD\n> for combining. The ADD-based variant is used as the basis of the modern\n> (\"GNU\") symbol lookup scheme in ELF. Glibc dynamic loader received an\n> optimized version of this hash function thanks to Noah Goldstein [1].\n\nInteresting\n\n> Switch xdl_hash_record_verbatim to additive hashing and implement\n> an optimized loop following the scheme suggested by Noah.\n> \n> Timing 'git log --oneline --shortstat v2.0.0..v2.5.0' under perf, I got\n> \n> version | cycles, bn | instructions, bn\n> ---------------------------------------\n> A 6.38 11.3\n> B 6.21 10.89\n> C 5.80 9.95\n> D 5.83 8.74\n> ---------------------------------------\n> \n> A: baseline (git master at e4ef0485fd78)\n> B: plus 'xdiff: refactor xdl_hash_record()'\n> C: and plus this patch\n> D: with 'xdiff: use xxhash' by Phillip Wood\n\nI think it would be helpful to say that B is the previous patch and \nprovide a link for D.\n> The resulting speedup for xdl_hash_record_verbatim itself is about 1.5x.\n\nWhile that's interesting it does not tell us how much this speeds up \ndiff generation. Running the command above under hyperfine it is 1.02 ± \n0.01 times faster than the previous patch and 1.11 ± 0.01 times faster \nthan master. Using xxhash (D above) is 1.03 ± 0.01 times faster than \nthis patch. How do the changes below affect compilers other than gcc and \nclang than do not see the re-association barrier? We'd want to make sure \nthat it does not result in slower diffs. Can we use \natomic_signal_fence() on compilers that support C11? (we don't require \nC11 so we'd have to make it optional but it is supported by things like \nMSVC)\n\nThanks\n\nPhillip\n> \n> [1] https://inbox.sourceware.org/libc-alpha/20220519221803.57957-6-goldstein.w.n@gmail.com/\n> \n> Signed-off-by: Alexander Monakov \n> ---\n> xdiff/xutils.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++----\n> 1 file changed, 55 insertions(+), 4 deletions(-)\n> \n> diff --git a/xdiff/xutils.c b/xdiff/xutils.c\n> index e070ed649f..b1f8273f0f 100644\n> --- a/xdiff/xutils.c\n> +++ b/xdiff/xutils.c\n> @@ -294,16 +294,67 @@ unsigned long xdl_hash_record_with_whitespace(char const **data,\n> \treturn ha;\n> }\n> \n> +/*\n> + * Compiler reassociation barrier: pretend to modify X and Y to disallow\n> + * changing evaluation order with respect to following uses of X and Y.\n> + */\n> +#ifdef __GNUC__\n> +#define REASSOC_FENCE(x, y) asm(\"\" : \"+r\"(x), \"+r\"(y))\n> +#else\n> +#define REASSOC_FENCE(x, y)\n> +#endif\n> +\n> unsigned long xdl_hash_record_verbatim(char const **data, char const *top) {\n> -\tunsigned long ha = 5381;\n> +\tunsigned long ha = 5381, c0, c1;\n> \tchar const *ptr = *data;\n> -\n> +#if 0\n> +\t/*\n> +\t * The baseline form of the optimized loop below. This is the djb2\n> +\t * hash (the above function uses a variant with XOR instead of ADD).\n> +\t */\n> \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n> \t\tha += (ha << 5);\n> -\t\tha ^= (unsigned long) *ptr;\n> +\t\tha += (unsigned long) *ptr;\n> \t}\n> \t*data = ptr < top ? ptr + 1: ptr;\n> -\n> +#else\n> +\t/* Process two characters per iteration. */\n> +\tif (top - ptr >= 2) do {\n> +\t\tif ((c0 = ptr[0]) == '\\n') {\n> +\t\t\t*data = ptr + 1;\n> +\t\t\treturn ha;\n> +\t\t}\n> +\t\tif ((c1 = ptr[1]) == '\\n') {\n> +\t\t\t*data = ptr + 2;\n> +\t\t\tc0 += ha;\n> +\t\t\tREASSOC_FENCE(c0, ha);\n> +\t\t\tha = ha * 32 + c0;\n> +\t\t\treturn ha;\n> +\t\t}\n> +\t\t/*\n> +\t\t * Combine characters C0 and C1 into the hash HA. We have\n> +\t\t * HA = (HA * 33 + C0) * 33 + C1, and we want to ensure\n> +\t\t * that dependency chain over HA is just one multiplication\n> +\t\t * and one addition, i.e. we want to evaluate this as\n> +\t\t * HA = HA * 33 * 33 + (C0 * 33 + C1), and likewise prefer\n> +\t\t * (C0 * 32 + (C0 + C1)) for the expression in parenthesis.\n> +\t\t */\n> +\t\tha *= 33 * 33;\n> +\t\tc1 += c0;\n> +\t\tREASSOC_FENCE(c1, c0);\n> +\t\tc1 += c0 * 32;\n> +\t\tREASSOC_FENCE(c1, ha);\n> +\t\tha += c1;\n> +\n> +\t\tptr += 2;\n> +\t} while (ptr < top - 1);\n> +\t*data = top;\n> +\tif (ptr < top && (c0 = ptr[0]) != '\\n') {\n> +\t\tc0 += ha;\n> +\t\tREASSOC_FENCE(c0, ha);\n> +\t\tha = ha * 32 + c0;\n> +\t}\n> +#endif\n> \treturn ha;\n> }\n> \n\n"},{"id":"523449","messageId":"353c7865-d9b5-2a1c-4d71-cd1136581f01@ispras.ru","threadId":"63866","inReplyTo":"aedb1be1-3151-421e-94ce-27bc77d80b83@gmail.com","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-08-04T14:39:37Z","receivedAt":"2025-08-04T14:39:53Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"\nOn Mon, 4 Aug 2025, Phillip Wood wrote:\n\n> > Switch xdl_hash_record_verbatim to additive hashing and implement\n> > an optimized loop following the scheme suggested by Noah.\n> > \n> > Timing 'git log --oneline --shortstat v2.0.0..v2.5.0' under perf, I got\n> > \n> > version | cycles, bn | instructions, bn\n> > ---------------------------------------\n> > A 6.38 11.3\n> > B 6.21 10.89\n> > C 5.80 9.95\n> > D 5.83 8.74\n> > ---------------------------------------\n> > \n> > A: baseline (git master at e4ef0485fd78)\n> > B: plus 'xdiff: refactor xdl_hash_record()'\n> > C: and plus this patch\n> > D: with 'xdiff: use xxhash' by Phillip Wood\n> \n> I think it would be helpful to say that B is the previous patch and provide a\n> link for D.\n\nOk, reworded locally, will appear in v2.\n\n> > The resulting speedup for xdl_hash_record_verbatim itself is about 1.5x.\n> \n> While that's interesting it does not tell us how much this speeds up diff\n> generation.\n\nThat's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)\n\n> Running the command above under hyperfine it is 1.02 ± 0.01 times\n> faster than the previous patch and 1.11 ± 0.01 times faster than master.\n\nThen you get 9% from the inlining patch and only 2% from the faster hash\nfunction? That's a bit surprising, which compiler and CPU you used? Is it\nwith default optimization (-O2)?\n\n> Using\n> xxhash (D above) is 1.03 ± 0.01 times faster than this patch. How do the\n> changes below affect compilers other than gcc and clang than do not see the\n> re-association barrier?\n\nI'd say under reasonable assumptions (e.g. a not too ancient CPU with 3-cycle\ninteger multiplication) the new scheme is generally faster even without asm.\n\nBut Git can certainly follow Glibc's choice and employ this only on x86_64\n(and only with GCC or Clang).\n\n> We'd want to make sure that it does not result in\n> slower diffs. Can we use atomic_signal_fence() on compilers that support C11?\n\nNo, what we need to do here is outside of the abstract machine's view, standard\nfunctions are not going to help.\n\nAlexander\n\n> (we don't require C11 so we'd have to make it optional but it is supported by\n> things like MSVC)\n> \n> Thanks\n> \n> Phillip"},{"id":"523931","messageId":"5cf47722-7073-4761-8698-090af840d0c4@gmail.com","threadId":"63866","inReplyTo":"353c7865-d9b5-2a1c-4d71-cd1136581f01@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-08-11T13:13:26Z","receivedAt":"2025-08-11T13:13:03Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 04/08/2025 15:39, Alexander Monakov wrote:\n> On Mon, 4 Aug 2025, Phillip Wood wrote:\n> \n>>> Switch xdl_hash_record_verbatim to additive hashing and implement\n>>> an optimized loop following the scheme suggested by Noah.\n>>>\n>>> Timing 'git log --oneline --shortstat v2.0.0..v2.5.0' under perf, I got\n>>>\n>>> version | cycles, bn | instructions, bn\n>>> ---------------------------------------\n>>> A 6.38 11.3\n>>> B 6.21 10.89\n>>> C 5.80 9.95\n>>> D 5.83 8.74\n>>> ---------------------------------------\n>>>\n>>> A: baseline (git master at e4ef0485fd78)\n>>> B: plus 'xdiff: refactor xdl_hash_record()'\n>>> C: and plus this patch\n>>> D: with 'xdiff: use xxhash' by Phillip Wood\n>>\n>> I think it would be helpful to say that B is the previous patch and provide a\n>> link for D.\n> \n> Ok, reworded locally, will appear in v2.\n\nThanks\n\n>>> The resulting speedup for xdl_hash_record_verbatim itself is about 1.5x.\n>>\n>> While that's interesting it does not tell us how much this speeds up diff\n>> generation.\n> \n> That's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)\n\nIt would be helpful to add a column with those calculations in it rather \nthan forcing the reader to calculate the speed up for themselves. Also \nwhat is the cycles column measuring? What is it that takes 6.21 cycles \nfor B and only 5.8 cycles for C?\n\n>> Running the command above under hyperfine it is 1.02 ± 0.01 times\n>> faster than the previous patch and 1.11 ± 0.01 times faster than master.\n> \n> Then you get 9% from the inlining patch and only 2% from the faster hash\n> function? That's a bit surprising, which compiler and CPU you used? Is it\n> with default optimization (-O2)?\n\nI used gcc with -O2 -march=native on an i5-8500. I saw a similar \nimprovement from the inlining when I was playing with xxhash.\n\n>> Using\n>> xxhash (D above) is 1.03 ± 0.01 times faster than this patch. How do the\n>> changes below affect compilers other than gcc and clang than do not see the\n>> re-association barrier?\n> \n> I'd say under reasonable assumptions (e.g. a not too ancient CPU with 3-cycle\n> integer multiplication) the new scheme is generally faster even without asm.\n\nThanks, fwiw I don't see a measurable difference in the timings with and \nwithout the asm on my machine - sometimes one is faster, sometimes the \nother, any difference is within the noise.\n\n> But Git can certainly follow Glibc's choice and employ this only on x86_64\n> (and only with GCC or Clang).\n> \n>> We'd want to make sure that it does not result in\n>> slower diffs. Can we use atomic_signal_fence() on compilers that support C11?\n> \n> No, what we need to do here is outside of the abstract machine's view, standard\n> functions are not going to help.\n\nThat's a shame. I'd hoped that stopping the compiler reorder the code \nwould do the same thing - what is the asm doing that's different?\n\nThanks\n\nPhillip\n"},{"id":"523945","messageId":"c2fe3b69-8436-af46-c47d-dde5bb037227@ispras.ru","threadId":"63866","inReplyTo":"5cf47722-7073-4761-8698-090af840d0c4@gmail.com","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-08-11T14:14:39Z","receivedAt":"2025-08-11T14:14:50Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"\nOn Mon, 11 Aug 2025, Phillip Wood wrote:\n\n> > That's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)\n> \n> It would be helpful to add a column with those calculations in it rather than\n> forcing the reader to calculate the speed up for themselves.\n\nOk, will change it to\n\nversion | speedup over (A) | cycles, bn | instructions, bn\n----------------------------------------------------------\nA 6.38 11.3\nB 1.027 6.21 10.89\nC 1.1 5.80 9.95\nD 1.094 5.83 8.74\n----------------------------------------------------------\n\n> Also what is the cycles column measuring? What is it that takes 6.21 cycles\n> for B and only 5.8 cycles for C?\n\nBillions of cycles, e.g. in C the entire command completes in 5.8e9 CPU cycles.\n\n> > Then you get 9% from the inlining patch and only 2% from the faster hash\n> > function? That's a bit surprising, which compiler and CPU you used? Is it\n> > with default optimization (-O2)?\n> \n> I used gcc with -O2 -march=native on an i5-8500. I saw a similar improvement\n> from the inlining when I was playing with xxhash.\n\nThanks, I'll see if I can benchmark it on a Skylake in the coming days. That\nsaid, I think most users will get Git from their distro, without -march=native,\nright? So I'd suggest looking at plain -O2, especially for xxhash, which\nselects hashing primitives based on CPU-indicating predefined macros.\n\n> > I'd say under reasonable assumptions (e.g. a not too ancient CPU with\n> > 3-cycle integer multiplication) the new scheme is generally faster even\n> > without asm.\n> \n> Thanks, fwiw I don't see a measurable difference in the timings with and\n> without the asm on my machine -\n\nTo be clear, by \"without asm\" you mean forcing the !__GNUC__ branch where\nREASSOC_FENCE macro is empty?\n\n> sometimes one is faster, sometimes the other, any difference is within the\n> noise.\n\nWould you mind showing your 'gcc --version'? Also, I prefer 'perf stat' for\nsuch measurements, because its measurements are not so sensitive to frequency\nscaling (plus, you can compare my cycles/instructions counts with yours if you\nrun 'perf stat', but I cannot compare your seconds from hyperfine with mine\nbecause of course my CPU runs at a different frequency than yours).\n\n'perf stat -r 5' runs the workload 5 times and prints averages and deviation.\n\n> > No, what we need to do here is outside of the abstract machine's view,\n> > standard functions are not going to help.\n> \n> That's a shame. I'd hoped that stopping the compiler reorder the code would do\n> the same thing - what is the asm doing that's different?\n\natomic_signal_fence only blocks reordering of references to memory that can be\nobserved from a signal handler interrupting the current thread. It has no effect\non variables whose addresses do not escape (let alone never taken in the first\nplace). Here we want to force a particular evaluation order for variables that\nend up on registers and are not supposed to appear in memory at all.\n\nAlexander\n"},{"id":"524077","messageId":"0379ba2d-837b-761e-9d5a-d65ca9d051d6@ispras.ru","threadId":"63866","inReplyTo":"c2fe3b69-8436-af46-c47d-dde5bb037227@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-08-12T17:56:37Z","receivedAt":"2025-08-12T17:56:46Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"> On Mon, 11 Aug 2025, Phillip Wood wrote:\n> \n> > > That's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)\n> > \n> > It would be helpful to add a column with those calculations in it rather than\n> > forcing the reader to calculate the speed up for themselves.\n> \n> Ok, will change it to\n> \n> version | speedup over (A) | cycles, bn | instructions, bn\n> ----------------------------------------------------------\n> A 6.38 11.3\n> B 1.027 6.21 10.89\n> C 1.1 5.80 9.95\n> D 1.094 5.83 8.74\n> ----------------------------------------------------------\n\nOn my Skylake:\n\nversion | speedup over (A) | cycles, bn | instructions, bn\n----------------------------------------------------------\nA 5.77 10.96\nB 1.076 5.36 10.60\nC 1.12 5.16 9.66\n----------------------------------------------------------\n\nA is today's master, B and C are patch 1 and 1+2 like before.\n\nAlexander\n"},{"id":"524120","messageId":"b118903c-a50a-4ae4-b41e-1c47c37218c4@gmail.com","threadId":"63866","inReplyTo":"c2fe3b69-8436-af46-c47d-dde5bb037227@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-08-13T13:10:56Z","receivedAt":"2025-08-13T13:11:01Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Alexander\n\nOn 11/08/2025 15:14, Alexander Monakov wrote:\n> \n> On Mon, 11 Aug 2025, Phillip Wood wrote:\n> \n>>> That's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)\n>>\n>> It would be helpful to add a column with those calculations in it rather than\n>> forcing the reader to calculate the speed up for themselves.\n> \n> Ok, will change it to\n> \n> version | speedup over (A) | cycles, bn | instructions, bn\n> ----------------------------------------------------------\n> A 6.38 11.3\n> B 1.027 6.21 10.89\n> C 1.1 5.80 9.95\n> D 1.094 5.83 8.74\n> ----------------------------------------------------------\n\nThat looks good, thanks\n\n>> Also what is the cycles column measuring? What is it that takes 6.21 cycles\n>> for B and only 5.8 cycles for C?\n> \n> Billions of cycles, e.g. in C the entire command completes in 5.8e9 CPU cycles.\n\nAh, for some reason I'd not realized than bn was short for billion\n>>> Then you get 9% from the inlining patch and only 2% from the faster hash\n>>> function? That's a bit surprising, which compiler and CPU you used? Is it\n>>> with default optimization (-O2)?\n>>\n>> I used gcc with -O2 -march=native on an i5-8500. I saw a similar improvement\n>> from the inlining when I was playing with xxhash.\n> \n> Thanks, I'll see if I can benchmark it on a Skylake in the coming days. That\n> said, I think most users will get Git from their distro, without -march=native,\n> right? So I'd suggest looking at plain -O2, especially for xxhash, which\n> selects hashing primitives based on CPU-indicating predefined macros.\n\nFor xxhash I was using the system library rather than compiling it myself\n>>> I'd say under reasonable assumptions (e.g. a not too ancient CPU with\n>>> 3-cycle integer multiplication) the new scheme is generally faster even\n>>> without asm.\n>>\n>> Thanks, fwiw I don't see a measurable difference in the timings with and\n>> without the asm on my machine -\n> \n> To be clear, by \"without asm\" you mean forcing the !__GNUC__ branch where\n> REASSOC_FENCE macro is empty?\n\nExactly\n\n>> sometimes one is faster, sometimes the other, any difference is within the\n>> noise.\n> \n> Would you mind showing your 'gcc --version'?\n\ngcc (Debian 12.2.0-14+deb12u1) 12.2.0\n\n> Also, I prefer 'perf stat' for\n> such measurements, because its measurements are not so sensitive to frequency\n> scaling (plus, you can compare my cycles/instructions counts with yours if you\n> run 'perf stat', but I cannot compare your seconds from hyperfine with mine\n> because of course my CPU runs at a different frequency than yours).\n> \n> 'perf stat -r 5' runs the workload 5 times and prints averages and deviation.\n\nI'll try and take a look at that though I'm off line next week and I'm \nnot sure I'll have time before then.\n>>> No, what we need to do here is outside of the abstract machine's view,\n>>> standard functions are not going to help.\n>>\n>> That's a shame. I'd hoped that stopping the compiler reorder the code would do\n>> the same thing - what is the asm doing that's different?\n> \n> atomic_signal_fence only blocks reordering of references to memory that can be\n> observed from a signal handler interrupting the current thread. It has no effect\n> on variables whose addresses do not escape (let alone never taken in the first\n> place). Here we want to force a particular evaluation order for variables that\n> end up on registers and are not supposed to appear in memory at all.\n\nAh, that makes sense\n\nThanks\n\nPhillip\n"},{"id":"524176","messageId":"xmqqqzxe6j83.fsf@gitster.g","threadId":"63866","inReplyTo":"43459416-ced2-d551-40e3-6db594ca4520@ispras.ru","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-14T15:01:00Z","receivedAt":"2025-08-14T15:01:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Monakov writes:\n\n>> Using xxhash() was merely a sample code path for technology\n>> demonstration, so the Rust adoption topic may want to pick a\n>> different code path to do its thing.\n>\n> My interest here is just speeding up xdiff in C, is that a welcome topic?\n\nI missed this question. It is very much welcome.\n\nIt is not like Rust-minded folks licked this corner of the system\nand others cannot touch it ;-)\n\n>> What is the licensing terms for that code you are proposing us to\n>> borrow? If it is anything recent in GNU, I'd expect that it would\n>> be GPLv3, which would be incompatible with our code base?\n> ...\n> I have participated in review of Noah's patches and he kindly listed me as\n> a co-author in the final revision of his patchset. So while I'm aware of how\n> his code is structured, I had to write a new implementation in order to meet\n> the contract of xdl_hash_record_verbatim. Therefore I think I can contribute\n> this code on GPLv2 terms with my sign-off.\n\nThanks for a wonderfully clear description.\n\nI obviously misread the log message of [2/2] and misunderstood that\nthis was a borrowed code.\n\n"},{"id":"524579","messageId":"xmqq7byx8yo3.fsf@gitster.g","threadId":"63866","inReplyTo":"0379ba2d-837b-761e-9d5a-d65ca9d051d6@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-20T21:34:52Z","receivedAt":"2025-08-20T21:34:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Monakov writes:\n\n>> On Mon, 11 Aug 2025, Phillip Wood wrote:\n>> \n>> > > That's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)\n>> > \n>> > It would be helpful to add a column with those calculations in it rather than\n>> > forcing the reader to calculate the speed up for themselves.\n>> \n>> Ok, will change it to\n>> \n>> version | speedup over (A) | cycles, bn | instructions, bn\n>> ----------------------------------------------------------\n>> A 6.38 11.3\n>> B 1.027 6.21 10.89\n>> C 1.1 5.80 9.95\n>> D 1.094 5.83 8.74\n>> ----------------------------------------------------------\n>\n> On my Skylake:\n>\n> version | speedup over (A) | cycles, bn | instructions, bn\n> ----------------------------------------------------------\n> A 5.77 10.96\n> B 1.076 5.36 10.60\n> C 1.12 5.16 9.66\n> ----------------------------------------------------------\n>\n> A is today's master, B and C are patch 1 and 1+2 like before.\n\nThe thread has gone quiet. I assume everybody is happy with the\nresult? Can we have a hopefully final v2 iteration of these\npatches, to address the updated to the table (this thread), to\nsquelch the __asm__() issue [*asm*], and a reword you mentioned\n[*reword*] against Phillip's review?\n\nThanks.\n\n\n*asm*\nhttps://lore.kernel.org/git/3405f274-cef1-b361-7424-840dc55b48a1@ispras.ru/\n\n*reword*\nhttps://lore.kernel.org/git/353c7865-d9b5-2a1c-4d71-cd1136581f01@ispras.ru/\n"},{"id":"525171","messageId":"xmqqecsvqal6.fsf@gitster.g","threadId":"63866","inReplyTo":"43459416-ced2-d551-40e3-6db594ca4520@ispras.ru","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-28T23:40:21Z","receivedAt":"2025-08-28T23:40:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Monakov writes:\n\n>> Using xxhash() was merely a sample code path for technology\n>> demonstration, so the Rust adoption topic may want to pick a\n>> different code path to do its thing.\n>\n> My interest here is just speeding up xdiff in C, is that a welcome topic?\n\nIt seems that the (side) discussion on the performance has\nconcluded, and Ezekiel's new iteration of the Rust thing moved to a\nnon-overlapping part of the system, so I do not see any reason to\nkeep this topic out of 'next'.\n\nIs everybody OK for me to mark the topic for 'next' soonish? Any\nobjections I overlooked?\n\nThanks.\n"},{"id":"525176","messageId":"CA+P7+xqn6hbahTAbLcnDspz-LHFrkFVMq_o8on4Hmez9HUiNxQ@mail.gmail.com","threadId":"63866","inReplyTo":"xmqqecsvqal6.fsf@gitster.g","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2025-08-29T01:13:07Z","receivedAt":"2025-08-29T01:13:17Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Thu, Aug 28, 2025 at 4:52 PM Junio C Hamano wrote:\n>\n> Alexander Monakov writes:\n>\n> >> Using xxhash() was merely a sample code path for technology\n> >> demonstration, so the Rust adoption topic may want to pick a\n> >> different code path to do its thing.\n> >\n> > My interest here is just speeding up xdiff in C, is that a welcome topic?\n>\n> It seems that the (side) discussion on the performance has\n> concluded, and Ezekiel's new iteration of the Rust thing moved to a\n> non-overlapping part of the system, so I do not see any reason to\n> keep this topic out of 'next'.\n>\n> Is everybody OK for me to mark the topic for 'next' soonish? Any\n> objections I overlooked?\n>\n> Thanks.\n>\n\nThat seems reasonable to me.\n"},{"id":"525183","messageId":"CABPp-BGo17qAicW0C3o6eURfTvGjXTN9EbTzokcmmTCd_bzpWg@mail.gmail.com","threadId":"63866","inReplyTo":"xmqqecsvqal6.fsf@gitster.g","subject":"Re: [PATCH 0/2] optimize string hashing in xdiff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-08-29T03:09:16Z","receivedAt":"2025-08-29T03:09:28Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Aug 28, 2025 at 4:41 PM Junio C Hamano wrote:\n>\n> Alexander Monakov writes:\n>\n> >> Using xxhash() was merely a sample code path for technology\n> >> demonstration, so the Rust adoption topic may want to pick a\n> >> different code path to do its thing.\n> >\n> > My interest here is just speeding up xdiff in C, is that a welcome topic?\n>\n> It seems that the (side) discussion on the performance has\n> concluded, and Ezekiel's new iteration of the Rust thing moved to a\n> non-overlapping part of the system, so I do not see any reason to\n> keep this topic out of 'next'.\n>\n> Is everybody OK for me to mark the topic for 'next' soonish? Any\n> objections I overlooked?\n\nSounds good to me.\n"},{"id":"525875","messageId":"abb2bc1a-e68b-85a3-2562-53328fb502c6@ispras.ru","threadId":"63866","inReplyTo":"xmqq7byx8yo3.fsf@gitster.g","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Alexander Monakov","fromEmail":"amonakov@ispras.ru","sentAt":"2025-09-08T19:06:56Z","receivedAt":"2025-09-08T19:06:59Z","isPatch":true,"sender":{"key":"amonakov@ispras.ru","avatar":"https://avatars.githubusercontent.com/u/1997391?v=4"},"body":"\nOn Wed, 20 Aug 2025, Junio C Hamano wrote:\n\n> The thread has gone quiet. I assume everybody is happy with the\n> result? Can we have a hopefully final v2 iteration of these\n> patches, to address the updated to the table (this thread), to\n> squelch the __asm__() issue [*asm*], and a reword you mentioned\n> [*reword*] against Phillip's review?\n\nI was expecting that Phillip would come back to the question of underwhelming\nperformance improvement he was seeing on his CPU. I was working on an\nalternative approach to speed up that function, which I just sent in the v2\nthread: https://lore.kernel.org/git/20250908184939.16338-4-amonakov@ispras.ru/\nIt does not depend on the performance of integer multiplication anymore,\nso it should work better from architecture neutrality point of view.\n\nI'm not sure what's the current status though, it seems nobody gave the original\ntwo patches a Reviewed-by?\n\nIf the proposed changes in v2 are too sudden, what happens now?\n\nThanks.\nAlexander\n"},{"id":"525879","messageId":"xmqq8qiowt9r.fsf@gitster.g","threadId":"63866","inReplyTo":"abb2bc1a-e68b-85a3-2562-53328fb502c6@ispras.ru","subject":"Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-09-08T21:04:16Z","receivedAt":"2025-09-08T21:04:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexander Monakov writes:\n\n> On Wed, 20 Aug 2025, Junio C Hamano wrote:\n>\n>> The thread has gone quiet. I assume everybody is happy with the\n>> result? Can we have a hopefully final v2 iteration of these\n>> patches, to address the updated to the table (this thread), to\n>> squelch the __asm__() issue [*asm*], and a reword you mentioned\n>> [*reword*] against Phillip's review?\n>\n> I was expecting that Phillip would come back to the question of underwhelming\n> performance improvement he was seeing on his CPU. I was working on an\n> alternative approach to speed up that function, which I just sent in the v2\n> thread: https://lore.kernel.org/git/20250908184939.16338-4-amonakov@ispras.ru/\n> It does not depend on the performance of integer multiplication anymore,\n> so it should work better from architecture neutrality point of view.\n>\n> I'm not sure what's the current status though, it seems nobody gave the original\n> two patches a Reviewed-by?\n>\n> If the proposed changes in v2 are too sudden, what happens now?\n\nWell, it has been quite a while since I asked, and the last round,\nwhich looked reasonably well done, is now in 'next' and is about to\ngraduate to 'master'. So, if there are further good changes on top,\ncan you make them incremental on top of 'master' after I push out\ntoday's integration result?\n\nThanks.\n"}]}