Alexander Monakov a4bbe8af0b xdiff: optimize xdl_hash_record_verbatim ... xdl_hash_record_verbatim uses modified djb2 hash with XOR instead of ADD for combining. The ADD-based variant is used as the basis of the modern ("GNU") symbol lookup scheme in ELF. Glibc dynamic loader received an optimized version of this hash function thanks to Noah Goldstein [1]. Switch xdl_hash_record_verbatim to additive hashing and implement an optimized loop following the scheme suggested by Noah. Timing 'git log --oneline --shortstat v2.0.0..v2.5.0' under perf, I got version | cycles, bn | instructions, bn --------------------------------------- A 6.38 11.3 B 6.21 10.89 C 5.80 9.95 D 5.83 8.74 --------------------------------------- A: baseline (git master at e4ef0485fd) B: plus 'xdiff: refactor xdl_hash_record()' C: and plus this patch D: with 'xdiff: use xxhash' by Phillip Wood The resulting speedup for xdl_hash_record_verbatim itself is about 1.5x. [1] https://inbox.sourceware.org/libc-alpha/20220519221803.57957-6-goldstein.w.n@gmail.com/ Signed-off-by: Alexander Monakov <amonakov@ispras.ru> Signed-off-by: Junio C Hamano <gitster@pobox.com>		2025-08-18 08:44:49 -07:00
..
xdiff.h	…
xdiffi.c	…
xdiffi.h	…
xemit.c	Merge branch 'rs/xdiff-context-length-fix'	2025-03-29 16:39:10 +09:00
xemit.h	…
xhistogram.c	…
xinclude.h	…
xmacros.h	…
xmerge.c	…
xpatience.c	…
xprepare.c	xdiff: disable cleanup_records heuristic with --minimal	2025-04-29 12:46:58 -07:00
xprepare.h	…
xtypes.h	…
xutils.c	xdiff: optimize xdl_hash_record_verbatim	2025-08-18 08:44:49 -07:00
xutils.h	xdiff: refactor xdl_hash_record()	2025-07-28 12:33:54 -07:00