summaryrefslogtreecommitdiff
path: root/diff-lib.c
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2018-08-28 21:22:35 (GMT)
committerJunio C Hamano <gitster@pobox.com>2018-08-29 18:32:49 (GMT)
commit14438c4497c3ab3988cf50ebd504acef3735953c (patch)
tree60417c66f63858cb1af75cebf3f2ab26915aa438 /diff-lib.c
parent4d168e742a39b5e647ab8d2408cd5c0062ac35f4 (diff)
downloadgit-14438c4497c3ab3988cf50ebd504acef3735953c.zip
git-14438c4497c3ab3988cf50ebd504acef3735953c.tar.gz
git-14438c4497c3ab3988cf50ebd504acef3735953c.tar.bz2
introduce hasheq() and oideq()
The main comparison functions we provide for comparing object ids are hashcmp() and oidcmp(). These are more flexible than a strict equality check, since they also express ordering. That makes them useful for sorting and binary searching. However, it also makes them potentially slower than a strict equality check. Consider this C code, which is traditionally what our hashcmp has looked like: #include <string.h> int hashcmp(const unsigned char *a, const unsigned char *b) { return memcmp(a, b, 20); } Compiling with "gcc -O2 -S -fverbose-asm", the generated assembly shows that we actually call memcmp(). But if we change this to a strict equality check: return !memcmp(a, b, 20); we get a faster inline version: movq (%rdi), %rax # MEM[(void *)a_4(D)], MEM[(void *)a_4(D)] movq 8(%rdi), %rdx # MEM[(void *)a_4(D)], tmp101 xorq (%rsi), %rax # MEM[(void *)b_5(D)], tmp94 xorq 8(%rsi), %rdx # MEM[(void *)b_5(D)], tmp93 orq %rax, %rdx # tmp94, tmp93 jne .L2 #, movl 16(%rsi), %eax # MEM[(void *)b_5(D)], tmp104 cmpl %eax, 16(%rdi) # tmp104, MEM[(void *)a_4(D)] je .L5 #, Obviously our hashcmp() doesn't include the "!". But because it's an inline function, optimizing compilers are able to see "!hashcmp(a,b)" in calling code and take advantage of this case. So there has been no value thus far in introducing a more restricted interface for doing strict equality checks. But as Git learns about more values for the_hash_algo, our hashcmp() will grow more complicated and may even delegate at runtime to functions optimized specifically for that hash size. That breaks the inline connection we have, and the compiler will have to assume that the caller really cares about the sign and magnitude of the memcmp() result, even though the vast majority don't. We can solve that by introducing a hasheq() function (and matching oideq() wrapper), which callers can use to make it clear that they only care about equality. For now, the implementation will literally be "!hashcmp()", but it frees us up later to introduce code optimized specifically for the equality check. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'diff-lib.c')
0 files changed, 0 insertions, 0 deletions