git/xdiff/xutils.c, branch jch

xdiff: use unambiguous types in xdl_bogo_sqrt()

2026-04-08T20:57:45Z

There is no real square root for a negative number and size_t may not be large enough for certain applications, replace long with uint64_t. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: use unambiguous types in xdl_hash_record()

2025-11-18T22:53:10Z

Convert the function signature and body to use unambiguous types. char is changed to uint8_t because this function processes bytes in memory. unsigned long to uint64_t so that the hash output is consistent across platforms. `flags` was changed from long to uint64_t to ensure the high order bits are not dropped on platforms that treat long as 32 bits. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: make xrecord_t.ptr a uint8_t instead of char

2025-11-18T22:53:10Z

Make xrecord_t.ptr uint8_t because it's referring to bytes in memory. In order to avoid a refactor avalanche, many uses of this field were cast to char* or similar. Places where casting was unnecessary: xemit.c:156 xmerge.c:124 xmerge.c:127 xmerge.c:164 xmerge.c:169 xmerge.c:172 xmerge.c:178 Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

Merge branch 'en/xdiff-cleanup'

2025-10-14T19:56:09Z

A lot of code clean-up of xdiff. Split out of a larger topic. * en/xdiff-cleanup: xdiff: change type of xdfile_t.changed from char to bool xdiff: add macros DISCARD(0), KEEP(1), INVESTIGATE(2) in xprepare.c xdiff: rename rchg -> changed in xdfile_t xdiff: delete chastore from xdfile_t xdiff: delete fields ha, line, size in xdlclass_t in favor of an xrecord_t xdiff: delete redundant array xdfile_t.ha xdiff: delete struct diffdata_t xdiff: delete local variables that alias fields in xrecord_t xdiff: delete superfluous function xdl_get_rec() in xemit xdiff: delete unnecessary fields from xrecord_t and xdfile_t xdiff: delete local variables and initialize/free xdfile_t directly xdiff: delete static forward declarations in xprepare

xdiff: rename rchg -> changed in xdfile_t

2025-09-30T21:12:46Z

The field rchg (now 'changed') declares if a line in a file is changed or not. A later commit will change it's type from 'char' to 'bool' to make its purpose even more clear. Best-viewed-with: --color-words Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: delete chastore from xdfile_t

2025-09-30T21:12:46Z

xdfile_t currently uses chastore_t which is an arena allocator. I think that xrecord_t used to be a linked list and recs didn't exist originally. When recs was added I think they forgot to remove xdfile_t.next, but was overlooked. This dual data structure setup makes the code somewhat confusing. Additionally the C type chastore_t isn't FFI friendly, and provides little to no performance benefit over using realloc to grow an array. Performance impact of deleting fields from xdfile_t: Deleting ha is about 5% slower. Deleting cha is about 5% faster. Delete ha, but keep cha time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_ha/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Time (mean ± σ): 1.269 s ± 0.017 s [User: 1.135 s, System: 0.128 s] Range (min … max): 1.249 s … 1.286 s 10 runs Benchmark 2: build_delete_ha/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Time (mean ± σ): 1.339 s ± 0.017 s [User: 1.234 s, System: 0.099 s] Range (min … max): 1.320 s … 1.358 s 10 runs Summary build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran 1.06 ± 0.02 times faster than build_delete_ha/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Delete cha, but keep ha time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_chastore/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Time (mean ± σ): 1.290 s ± 0.001 s [User: 1.154 s, System: 0.130 s] Range (min … max): 1.288 s … 1.292 s 10 runs Benchmark 2: build_delete_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Time (mean ± σ): 1.232 s ± 0.017 s [User: 1.105 s, System: 0.121 s] Range (min … max): 1.205 s … 1.249 s 10 runs Summary build_delete_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran 1.05 ± 0.01 times faster than build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Delete ha AND chastore time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_ha_and_chastore/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Time (mean ± σ): 1.291 s ± 0.002 s [User: 1.156 s, System: 0.129 s] Range (min … max): 1.287 s … 1.295 s 10 runs Benchmark 2: build_delete_ha_and_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Time (mean ± σ): 1.306 s ± 0.001 s [User: 1.195 s, System: 0.105 s] Range (min … max): 1.305 s … 1.308 s 10 runs Summary build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran 1.01 ± 0.00 times faster than build_delete_ha_and_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null Best-viewed-with: --color-words Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: optimize xdl_hash_record_verbatim

2025-08-18T15:44:49Z

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 e4ef0485fd78) 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 Signed-off-by: Junio C Hamano

xdiff: refactor xdl_hash_record()

2025-07-28T19:33:54Z

Inline the check for whitespace flags so that the compiler can hoist it out of the loop in xdl_prepare_ctx(). This improves the performance by 8%. $ 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' Benchmark 1: : HEAD; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0 Time (mean ± σ): 1.670 s ± 0.044 s [User: 1.473 s, System: 0.196 s] Range (min … max): 1.619 s … 1.754 s 10 runs Benchmark 2: : HEAD^; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0 Time (mean ± σ): 1.801 s ± 0.021 s [User: 1.605 s, System: 0.192 s] Range (min … max): 1.766 s … 1.831 s 10 runs Summary ': HEAD^; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0' ran 1.08 ± 0.03 times faster than ': HEAD^^; GIT_CONFIG_GLOBAL=/dev/null ./git log --oneline --shortstat v2.0.0..v2.5.0' Signed-off-by: Phillip Wood Signed-off-by: Junio C Hamano

xdiff: avoid signed vs. unsigned comparisons in xutils.c

2025-02-12T17:41:17Z

The comparisons all involve comparisons against unsigned values. Signed-off-by: David Aguilar Signed-off-by: Junio C Hamano

xdiff: move sign comparison warning guard into each file

2025-02-12T17:41:15Z

Allow each file to fix the warnings guarded by the macro separately by moving the definition from the shared xinclude.h into each file that needs it. xmerge.c and xprepare.c do not contain any signed vs. unsigned comparisons so the definition was not included in these files. Signed-off-by: David Aguilar Signed-off-by: Junio C Hamano