swh:1:snp:bb8853bfef8fcf2b1d37fd6404912c7606c98e48
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
Tip revision: 19981daefd7c147444462739375462b49412ce33 authored by Junio C Hamano on 05 April 2024, 17:49:37 UTC
The fifteenth batch
The fifteenth batch
Tip revision: 19981da
File | Mode | Size |
---|---|---|
Documentation | ||
block-sha1 | ||
builtin | ||
compat | ||
contrib | ||
git-gui | ||
git_remote_helpers | ||
gitk-git | ||
gitweb | ||
perl | ||
ppc | ||
t | ||
templates | ||
xdiff | ||
.gitattributes | -rw-r--r-- | 105 bytes |
.gitignore | -rw-r--r-- | 2.8 KB |
.mailmap | -rw-r--r-- | 2.7 KB |
COPYING | -rw-r--r-- | 18.3 KB |
GIT-VERSION-GEN | -rwxr-xr-x | 752 bytes |
INSTALL | -rw-r--r-- | 6.3 KB |
Makefile | -rw-r--r-- | 62.1 KB |
README | -rw-r--r-- | 2.4 KB |
RelNotes | l--------- | 32 bytes |
abspath.c | -rw-r--r-- | 2.8 KB |
advice.c | -rw-r--r-- | 1.4 KB |
advice.h | -rw-r--r-- | 432 bytes |
alias.c | -rw-r--r-- | 1.4 KB |
alloc.c | -rw-r--r-- | 1.7 KB |
archive-tar.c | -rw-r--r-- | 6.3 KB |
archive-zip.c | -rw-r--r-- | 7.3 KB |
archive.c | -rw-r--r-- | 10.2 KB |
archive.h | -rw-r--r-- | 927 bytes |
attr.c | -rw-r--r-- | 16.1 KB |
attr.h | -rw-r--r-- | 973 bytes |
base85.c | -rw-r--r-- | 2.7 KB |
bisect.c | -rw-r--r-- | 23.9 KB |
bisect.h | -rw-r--r-- | 820 bytes |
blob.c | -rw-r--r-- | 565 bytes |
blob.h | -rw-r--r-- | 664 bytes |
branch.c | -rw-r--r-- | 5.4 KB |
branch.h | -rw-r--r-- | 1.0 KB |
builtin.h | -rw-r--r-- | 8.6 KB |
bundle.c | -rw-r--r-- | 10.2 KB |
bundle.h | -rw-r--r-- | 627 bytes |
cache-tree.c | -rw-r--r-- | 15.6 KB |
cache-tree.h | -rw-r--r-- | 1.4 KB |
cache.h | -rw-r--r-- | 37.1 KB |
check-builtins.sh | -rwxr-xr-x | 588 bytes |
check-racy.c | -rw-r--r-- | 538 bytes |
check_bindir | -rwxr-xr-x | 369 bytes |
color.c | -rw-r--r-- | 4.6 KB |
color.h | -rw-r--r-- | 2.3 KB |
combine-diff.c | -rw-r--r-- | 27.9 KB |
command-list.txt | -rw-r--r-- | 7.7 KB |
commit.c | -rw-r--r-- | 17.5 KB |
commit.h | -rw-r--r-- | 5.0 KB |
config.c | -rw-r--r-- | 29.8 KB |
config.mak.in | -rw-r--r-- | 1.4 KB |
configure.ac | -rw-r--r-- | 24.6 KB |
connect.c | -rw-r--r-- | 13.8 KB |
convert.c | -rw-r--r-- | 14.1 KB |
copy.c | -rw-r--r-- | 1.6 KB |
csum-file.c | -rw-r--r-- | 2.5 KB |
csum-file.h | -rw-r--r-- | 761 bytes |
ctype.c | -rw-r--r-- | 874 bytes |
daemon.c | -rw-r--r-- | 25.3 KB |
date.c | -rw-r--r-- | 22.2 KB |
decorate.c | -rw-r--r-- | 1.8 KB |
decorate.h | -rw-r--r-- | 400 bytes |
delta.h | -rw-r--r-- | 3.4 KB |
diff-delta.c | -rw-r--r-- | 15.3 KB |
diff-lib.c | -rw-r--r-- | 14.0 KB |
diff-no-index.c | -rw-r--r-- | 6.0 KB |
diff.c | -rw-r--r-- | 101.7 KB |
diff.h | -rw-r--r-- | 9.3 KB |
diffcore-break.c | -rw-r--r-- | 8.7 KB |
diffcore-delta.c | -rw-r--r-- | 5.4 KB |
diffcore-order.c | -rw-r--r-- | 2.2 KB |
diffcore-pickaxe.c | -rw-r--r-- | 3.2 KB |
diffcore-rename.c | -rw-r--r-- | 16.9 KB |
diffcore.h | -rw-r--r-- | 4.2 KB |
dir.c | -rw-r--r-- | 24.8 KB |
dir.h | -rw-r--r-- | 2.8 KB |
editor.c | -rw-r--r-- | 1.1 KB |
entry.c | -rw-r--r-- | 6.0 KB |
environment.c | -rw-r--r-- | 5.3 KB |
exec_cmd.c | -rw-r--r-- | 3.3 KB |
exec_cmd.h | -rw-r--r-- | 487 bytes |
fast-import.c | -rw-r--r-- | 74.6 KB |
fetch-pack.h | -rw-r--r-- | 479 bytes |
fixup-builtins | -rwxr-xr-x | 432 bytes |
fsck.c | -rw-r--r-- | 8.0 KB |
fsck.h | -rw-r--r-- | 1.0 KB |
generate-cmdlist.sh | -rwxr-xr-x | 443 bytes |
git-add--interactive.perl | -rwxr-xr-x | 34.8 KB |
git-am.sh | -rwxr-xr-x | 18.6 KB |
git-archimport.perl | -rwxr-xr-x | 36.0 KB |
git-bisect.sh | -rwxr-xr-x | 9.8 KB |
git-compat-util.h | -rw-r--r-- | 11.8 KB |
git-cvsexportcommit.perl | -rwxr-xr-x | 12.4 KB |
git-cvsimport.perl | -rwxr-xr-x | 28.5 KB |
git-cvsserver.perl | -rwxr-xr-x | 114.9 KB |
git-difftool--helper.sh | -rwxr-xr-x | 1.7 KB |
git-difftool.perl | -rwxr-xr-x | 2.6 KB |
git-filter-branch.sh | -rwxr-xr-x | 11.9 KB |
git-instaweb.sh | -rwxr-xr-x | 10.9 KB |
git-lost-found.sh | -rwxr-xr-x | 554 bytes |
git-merge-octopus.sh | -rwxr-xr-x | 2.0 KB |
git-merge-one-file.sh | -rwxr-xr-x | 3.7 KB |
git-merge-resolve.sh | -rwxr-xr-x | 944 bytes |
git-mergetool--lib.sh | -rw-r--r-- | 8.8 KB |
git-mergetool.sh | -rwxr-xr-x | 6.0 KB |
git-parse-remote.sh | -rw-r--r-- | 1.9 KB |
git-pull.sh | -rwxr-xr-x | 7.8 KB |
git-quiltimport.sh | -rwxr-xr-x | 3.3 KB |
git-rebase--interactive.sh | -rwxr-xr-x | 24.3 KB |
git-rebase.sh | -rwxr-xr-x | 14.3 KB |
git-relink.perl | -rwxr-xr-x | 4.0 KB |
git-repack.sh | -rwxr-xr-x | 4.4 KB |
git-request-pull.sh | -rwxr-xr-x | 1.6 KB |
git-send-email.perl | -rwxr-xr-x | 35.5 KB |
git-sh-setup.sh | -rw-r--r-- | 3.9 KB |
git-stash.sh | -rwxr-xr-x | 8.6 KB |
git-submodule.sh | -rwxr-xr-x | 17.3 KB |
git-svn.perl | -rwxr-xr-x | 171.2 KB |
git-web--browse.sh | -rwxr-xr-x | 3.9 KB |
git.c | -rw-r--r-- | 15.0 KB |
git.spec.in | -rw-r--r-- | 10.3 KB |
graph.c | -rw-r--r-- | 34.6 KB |
graph.h | -rw-r--r-- | 2.5 KB |
grep.c | -rw-r--r-- | 22.3 KB |
grep.h | -rw-r--r-- | 2.5 KB |
hash.c | -rw-r--r-- | 2.5 KB |
hash.h | -rw-r--r-- | 1.1 KB |
help.c | -rw-r--r-- | 8.4 KB |
help.h | -rw-r--r-- | 751 bytes |
hex.c | -rw-r--r-- | 2.1 KB |
http-backend.c | -rw-r--r-- | 14.2 KB |
http-fetch.c | -rw-r--r-- | 2.3 KB |
http-push.c | -rw-r--r-- | 54.2 KB |
http-walker.c | -rw-r--r-- | 13.9 KB |
http.c | -rw-r--r-- | 31.0 KB |
http.h | -rw-r--r-- | 5.1 KB |
ident.c | -rw-r--r-- | 6.1 KB |
imap-send.c | -rw-r--r-- | 35.2 KB |
levenshtein.c | -rw-r--r-- | 2.5 KB |
levenshtein.h | -rw-r--r-- | 203 bytes |
list-objects.c | -rw-r--r-- | 4.6 KB |
list-objects.h | -rw-r--r-- | 422 bytes |
ll-merge.c | -rw-r--r-- | 9.1 KB |
ll-merge.h | -rw-r--r-- | 365 bytes |
lockfile.c | -rw-r--r-- | 6.3 KB |
log-tree.c | -rw-r--r-- | 14.4 KB |
log-tree.h | -rw-r--r-- | 783 bytes |
mailmap.c | -rw-r--r-- | 6.5 KB |
mailmap.h | -rw-r--r-- | 263 bytes |
match-trees.c | -rw-r--r-- | 8.7 KB |
merge-file.c | -rw-r--r-- | 2.6 KB |
merge-recursive.c | -rw-r--r-- | 38.7 KB |
merge-recursive.h | -rw-r--r-- | 1.5 KB |
name-hash.c | -rw-r--r-- | 2.5 KB |
notes.c | -rw-r--r-- | 33.4 KB |
notes.h | -rw-r--r-- | 9.8 KB |
object.c | -rw-r--r-- | 5.8 KB |
object.h | -rw-r--r-- | 2.5 KB |
pack-check.c | -rw-r--r-- | 4.5 KB |
pack-refs.c | -rw-r--r-- | 2.8 KB |
pack-refs.h | -rw-r--r-- | 465 bytes |
pack-revindex.c | -rw-r--r-- | 4.0 KB |
pack-revindex.h | -rw-r--r-- | 223 bytes |
pack-write.c | -rw-r--r-- | 8.0 KB |
pack.h | -rw-r--r-- | 2.2 KB |
pager.c | -rw-r--r-- | 2.2 KB |
parse-options.c | -rw-r--r-- | 16.2 KB |
parse-options.h | -rw-r--r-- | 7.4 KB |
patch-delta.c | -rw-r--r-- | 2.1 KB |
patch-ids.c | -rw-r--r-- | 2.5 KB |
patch-ids.h | -rw-r--r-- | 490 bytes |
path.c | -rw-r--r-- | 16.6 KB |
pkt-line.c | -rw-r--r-- | 3.3 KB |
pkt-line.h | -rw-r--r-- | 589 bytes |
preload-index.c | -rw-r--r-- | 2.3 KB |
pretty.c | -rw-r--r-- | 27.4 KB |
progress.c | -rw-r--r-- | 6.5 KB |
progress.h | -rw-r--r-- | 504 bytes |
quote.c | -rw-r--r-- | 10.2 KB |
quote.h | -rw-r--r-- | 2.5 KB |
reachable.c | -rw-r--r-- | 5.6 KB |
reachable.h | -rw-r--r-- | 127 bytes |
read-cache.c | -rw-r--r-- | 44.2 KB |
reflog-walk.c | -rw-r--r-- | 7.7 KB |
reflog-walk.h | -rw-r--r-- | 664 bytes |
refs.c | -rw-r--r-- | 43.6 KB |
refs.h | -rw-r--r-- | 4.0 KB |
remote-curl.c | -rw-r--r-- | 19.4 KB |
remote.c | -rw-r--r-- | 41.1 KB |
remote.h | -rw-r--r-- | 4.2 KB |
replace_object.c | -rw-r--r-- | 2.6 KB |
rerere.c | -rw-r--r-- | 14.3 KB |
rerere.h | -rw-r--r-- | 505 bytes |
resolve-undo.c | -rw-r--r-- | 4.0 KB |
resolve-undo.h | -rw-r--r-- | 546 bytes |
revision.c | -rw-r--r-- | 53.5 KB |
revision.h | -rw-r--r-- | 4.5 KB |
run-command.c | -rw-r--r-- | 12.6 KB |
run-command.h | -rw-r--r-- | 2.8 KB |
send-pack.h | -rw-r--r-- | 389 bytes |
server-info.c | -rw-r--r-- | 5.2 KB |
setup.c | -rw-r--r-- | 13.8 KB |
sha1-lookup.c | -rw-r--r-- | 7.8 KB |
sha1-lookup.h | -rw-r--r-- | 403 bytes |
sha1_file.c | -rw-r--r-- | 63.3 KB |
sha1_name.c | -rw-r--r-- | 25.8 KB |
shallow.c | -rw-r--r-- | 2.3 KB |
shell.c | -rw-r--r-- | 2.2 KB |
shortlog.h | -rw-r--r-- | 450 bytes |
show-index.c | -rw-r--r-- | 2.2 KB |
sideband.c | -rw-r--r-- | 3.4 KB |
sideband.h | -rw-r--r-- | 326 bytes |
sigchain.c | -rw-r--r-- | 969 bytes |
sigchain.h | -rw-r--r-- | 215 bytes |
strbuf.c | -rw-r--r-- | 8.0 KB |
strbuf.h | -rw-r--r-- | 5.0 KB |
string-list.c | -rw-r--r-- | 4.4 KB |
string-list.h | -rw-r--r-- | 1.8 KB |
submodule.c | -rw-r--r-- | 5.4 KB |
submodule.h | -rw-r--r-- | 308 bytes |
symlinks.c | -rw-r--r-- | 7.9 KB |
tag.c | -rw-r--r-- | 2.7 KB |
tag.h | -rw-r--r-- | 471 bytes |
tar.h | -rw-r--r-- | 644 bytes |
test-chmtime.c | -rw-r--r-- | 2.6 KB |
test-ctype.c | -rw-r--r-- | 1.4 KB |
test-date.c | -rw-r--r-- | 1.3 KB |
test-delta.c | -rw-r--r-- | 1.8 KB |
test-dump-cache-tree.c | -rw-r--r-- | 1.5 KB |
test-genrandom.c | -rw-r--r-- | 722 bytes |
test-index-version.c | -rw-r--r-- | 264 bytes |
test-match-trees.c | -rw-r--r-- | 588 bytes |
test-parse-options.c | -rw-r--r-- | 3.0 KB |
test-path-utils.c | -rw-r--r-- | 872 bytes |
test-run-command.c | -rw-r--r-- | 774 bytes |
test-sha1.c | -rw-r--r-- | 816 bytes |
test-sha1.sh | -rwxr-xr-x | 1.9 KB |
test-sigchain.c | -rw-r--r-- | 344 bytes |
thread-utils.c | -rw-r--r-- | 965 bytes |
thread-utils.h | -rw-r--r-- | 109 bytes |
trace.c | -rw-r--r-- | 3.5 KB |
transport-helper.c | -rw-r--r-- | 17.3 KB |
transport.c | -rw-r--r-- | 30.6 KB |
transport.h | -rw-r--r-- | 5.5 KB |
tree-diff.c | -rw-r--r-- | 11.9 KB |
tree-walk.c | -rw-r--r-- | 10.1 KB |
tree-walk.h | -rw-r--r-- | 1.7 KB |
tree.c | -rw-r--r-- | 7.0 KB |
tree.h | -rw-r--r-- | 883 bytes |
unimplemented.sh | -rw-r--r-- | 100 bytes |
unpack-trees.c | -rw-r--r-- | 35.9 KB |
unpack-trees.h | -rw-r--r-- | 1.6 KB |
upload-pack.c | -rw-r--r-- | 17.6 KB |
usage.c | -rw-r--r-- | 2.4 KB |
userdiff.c | -rw-r--r-- | 6.0 KB |
userdiff.h | -rw-r--r-- | 477 bytes |
utf8.c | -rw-r--r-- | 12.8 KB |
utf8.h | -rw-r--r-- | 537 bytes |
walker.c | -rw-r--r-- | 7.2 KB |
walker.h | -rw-r--r-- | 1.1 KB |
wrap-for-bin.sh | -rw-r--r-- | 610 bytes |
wrapper.c | -rw-r--r-- | 6.6 KB |
write_or_die.c | -rw-r--r-- | 2.0 KB |
ws.c | -rw-r--r-- | 8.2 KB |
wt-status.c | -rw-r--r-- | 20.0 KB |
wt-status.h | -rw-r--r-- | 1.4 KB |
xdiff-interface.c | -rw-r--r-- | 8.2 KB |
xdiff-interface.h | -rw-r--r-- | 1.1 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...