Revision e53e6b4433f264250c2e586167caf61721b0185c authored by Brian Downing on 11 June 2010, 02:59:07 UTC, committed by Junio C Hamano on 18 June 2010, 15:06:18 UTC
When traversing trees with an index, the current index pointer (o->cache_bottom) occasionally has to be temporarily advanced forwards to match the traversal order of the tree, which is not the same as the sort order of the index. The existing algorithm that did this (introduced in 730f72840cc50c523fe4cdd796ea2d2fc4571a28) would get "stuck" when the cache_bottom was popped and then repeatedly check the same index entries over and over. This represents a serious performance regression for large repositories compared to the old "broken" traversal order. This commit makes a simple change to mitigate this. Whenever find_cache_pos sees that the current pos is also the cache_bottom, and it has already been unpacked, it advances the cache_bottom as well as the current pos. This prevents the above "sticking" behavior without dramatically changing the algorithm. In addition, this commit moves the unpacked check above the ce_in_traverse_path() check. The simple bitmask check is cheaper, and in the case described above will be firing quite a bit to advance the cache_bottom after a tree pop. This yields considerable performance improvements for large trees. The following are the number of function calls for "git diff HEAD" on the Linux kernel tree, with 33,307 files: Symbol Calls Before Calls After ------------------- ------------ ----------- unpack_callback 35,332 35,332 find_cache_pos 37,357 37,357 ce_in_traverse_path 4,979,473 37,357 do_compare_entry 6,828,181 251,925 df_name_compare 6,828,181 251,925 And on a repository of 187,456 files: Symbol Calls Before Calls After ------------------- ------------ ----------- unpack_callback 197,958 197,958 find_cache_pos 208,460 208,460 ce_in_traverse_path 37,308,336 208,460 do_compare_entry 156,950,469 2,690,626 df_name_compare 156,950,469 2,690,626 On the latter repository, user time for "git diff HEAD" was reduced from 5.58 to 0.42 seconds. This is compared to 0.30 seconds before the traversal order fix was implemented. Signed-off-by: Brian Downing <bdowning@lavos.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent 2543d9b
sha1.h
/*
* SHA-1 implementation.
*
* Copyright (C) 2005 Paul Mackerras <paulus@samba.org>
*/
#include <stdint.h>
typedef struct {
uint32_t hash[5];
uint32_t cnt;
uint64_t len;
union {
unsigned char b[64];
uint64_t l[8];
} buf;
} ppc_SHA_CTX;
int ppc_SHA1_Init(ppc_SHA_CTX *c);
int ppc_SHA1_Update(ppc_SHA_CTX *c, const void *p, unsigned long n);
int ppc_SHA1_Final(unsigned char *hash, ppc_SHA_CTX *c);
#define git_SHA_CTX ppc_SHA_CTX
#define git_SHA1_Init ppc_SHA1_Init
#define git_SHA1_Update ppc_SHA1_Update
#define git_SHA1_Final ppc_SHA1_Final
Computing file changes ...
