Revision 8518ff8fabc43aa96f1d8c8cd3de7f399d51d11e authored by Kirill Smelkov on 20 January 2014, 16:20:40 UTC, committed by Junio C Hamano on 24 February 2014, 22:44:57 UTC
When generating combined diff, for each commit, we intersect diff paths from diff(parent_0,commit) to diff(parent_i,commit) comparing all paths pairs, i.e. doing it the quadratic way. That is correct, but could be optimized. Paths come from trees in sorted (= tree) order, and so does diff_tree() emits resulting paths in that order too. Now if we look at diffcore transformations, all of them, except diffcore_order, preserve resulting path ordering: - skip_stat_unmatch, grep, pickaxe, filter -- just skip elements -> order stays preserved - break -- just breaks diff for a path, adding path dup after the path -> order stays preserved - detect rename/copy -- resulting paths are emitted sorted (verified empirically) So only diffcore_order changes diff paths ordering. But diffcore_order meaning affects only presentation - i.e. only how to show the diff, so we could do all the internal computations without paths reordering, and order only resultant paths set. This is faster, since, if we know two paths sets are all ordered, their intersection could be done in linear time. This patch does just that. Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log") and with `-c` ("git log -c") before and after the patch are as follows: linux.git v3.10..v3.11 log log -c before 1.9s 20.4s after 1.9s 16.6s navy.git (private repo) log log -c before 0.83s 15.6s after 0.83s 2.1s P.S. I think linux.git case is sped up not so much as the second one, since in navy.git, there are more exotic (subtree, etc) merges. P.P.S. My tracing showed that the rest of the time (16.6s vs 1.9s) is usually spent in computing huge diffs from commit to second parent. Will try to deal with it, if I'll have time. P.P.P.S. For combine_diff_path, ->len is not needed anymore - will remove it in the next noisy cleanup path, to maintain good signal/noise ratio here. Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru> Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent 91921ce
File | Mode | Size |
---|---|---|
Documentation | ||
block-sha1 | ||
builtin | ||
compat | ||
contrib | ||
git-gui | ||
gitk-git | ||
gitweb | ||
mergetools | ||
perl | ||
po | ||
ppc | ||
t | ||
templates | ||
vcs-svn | ||
xdiff | ||
.gitattributes | -rw-r--r-- | 105 bytes |
.gitignore | -rw-r--r-- | 3.5 KB |
.mailmap | -rw-r--r-- | 13.5 KB |
COPYING | -rw-r--r-- | 18.3 KB |
GIT-VERSION-GEN | -rwxr-xr-x | 766 bytes |
INSTALL | -rw-r--r-- | 8.5 KB |
LGPL-2.1 | -rw-r--r-- | 26.2 KB |
Makefile | -rw-r--r-- | 74.8 KB |
README | -rw-r--r-- | 2.6 KB |
RelNotes | l--------- | 30 bytes |
abspath.c | -rw-r--r-- | 5.8 KB |
aclocal.m4 | -rw-r--r-- | 1.4 KB |
advice.c | -rw-r--r-- | 3.3 KB |
advice.h | -rw-r--r-- | 966 bytes |
alias.c | -rw-r--r-- | 1.7 KB |
alloc.c | -rw-r--r-- | 1.6 KB |
archive-tar.c | -rw-r--r-- | 11.0 KB |
archive-zip.c | -rw-r--r-- | 12.1 KB |
archive.c | -rw-r--r-- | 12.0 KB |
archive.h | -rw-r--r-- | 1.3 KB |
argv-array.c | -rw-r--r-- | 1.8 KB |
argv-array.h | -rw-r--r-- | 696 bytes |
attr.c | -rw-r--r-- | 19.2 KB |
attr.h | -rw-r--r-- | 1.6 KB |
base85.c | -rw-r--r-- | 2.8 KB |
bisect.c | -rw-r--r-- | 23.5 KB |
bisect.h | -rw-r--r-- | 644 bytes |
blob.c | -rw-r--r-- | 565 bytes |
blob.h | -rw-r--r-- | 664 bytes |
branch.c | -rw-r--r-- | 8.4 KB |
branch.h | -rw-r--r-- | 1.9 KB |
builtin.h | -rw-r--r-- | 8.5 KB |
bulk-checkin.c | -rw-r--r-- | 7.0 KB |
bulk-checkin.h | -rw-r--r-- | 343 bytes |
bundle.c | -rw-r--r-- | 11.0 KB |
bundle.h | -rw-r--r-- | 707 bytes |
cache-tree.c | -rw-r--r-- | 16.6 KB |
cache-tree.h | -rw-r--r-- | 1.5 KB |
cache.h | -rw-r--r-- | 48.8 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-- | 5.2 KB |
color.h | -rw-r--r-- | 3.1 KB |
column.c | -rw-r--r-- | 10.2 KB |
column.h | -rw-r--r-- | 1.4 KB |
combine-diff.c | -rw-r--r-- | 37.1 KB |
command-list.txt | -rw-r--r-- | 7.9 KB |
commit-slab.h | -rw-r--r-- | 3.7 KB |
commit.c | -rw-r--r-- | 38.0 KB |
commit.h | -rw-r--r-- | 10.2 KB |
config.c | -rw-r--r-- | 43.2 KB |
config.mak.in | -rw-r--r-- | 540 bytes |
config.mak.uname | -rw-r--r-- | 15.4 KB |
configure.ac | -rw-r--r-- | 32.1 KB |
connect.c | -rw-r--r-- | 17.5 KB |
connect.h | -rw-r--r-- | 596 bytes |
connected.c | -rw-r--r-- | 3.3 KB |
connected.h | -rw-r--r-- | 930 bytes |
convert.c | -rw-r--r-- | 29.2 KB |
convert.h | -rw-r--r-- | 2.2 KB |
copy.c | -rw-r--r-- | 1.6 KB |
credential-cache--daemon.c | -rw-r--r-- | 5.9 KB |
credential-cache.c | -rw-r--r-- | 2.9 KB |
credential-store.c | -rw-r--r-- | 4.0 KB |
credential.c | -rw-r--r-- | 7.6 KB |
credential.h | -rw-r--r-- | 822 bytes |
csum-file.c | -rw-r--r-- | 4.1 KB |
csum-file.h | -rw-r--r-- | 1.1 KB |
ctype.c | -rw-r--r-- | 2.6 KB |
daemon.c | -rw-r--r-- | 30.5 KB |
date.c | -rw-r--r-- | 25.0 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.4 KB |
diff-lib.c | -rw-r--r-- | 14.0 KB |
diff-no-index.c | -rw-r--r-- | 5.7 KB |
diff.c | -rw-r--r-- | 134.8 KB |
diff.h | -rw-r--r-- | 11.4 KB |
diffcore-break.c | -rw-r--r-- | 8.8 KB |
diffcore-delta.c | -rw-r--r-- | 5.4 KB |
diffcore-order.c | -rw-r--r-- | 2.4 KB |
diffcore-pickaxe.c | -rw-r--r-- | 6.4 KB |
diffcore-rename.c | -rw-r--r-- | 18.6 KB |
diffcore.h | -rw-r--r-- | 4.6 KB |
dir.c | -rw-r--r-- | 40.6 KB |
dir.h | -rw-r--r-- | 6.3 KB |
editor.c | -rw-r--r-- | 1.5 KB |
entry.c | -rw-r--r-- | 7.3 KB |
environment.c | -rw-r--r-- | 7.6 KB |
exec_cmd.c | -rw-r--r-- | 3.2 KB |
exec_cmd.h | -rw-r--r-- | 509 bytes |
fast-import.c | -rw-r--r-- | 87.7 KB |
fetch-pack.c | -rw-r--r-- | 26.1 KB |
fetch-pack.h | -rw-r--r-- | 1.0 KB |
fmt-merge-msg.h | -rw-r--r-- | 187 bytes |
fsck.c | -rw-r--r-- | 10.1 KB |
fsck.h | -rw-r--r-- | 1.0 KB |
generate-cmdlist.sh | -rwxr-xr-x | 433 bytes |
gettext.c | -rw-r--r-- | 4.3 KB |
gettext.h | -rw-r--r-- | 1.4 KB |
git-add--interactive.perl | -rwxr-xr-x | 35.9 KB |
git-am.sh | -rwxr-xr-x | 22.5 KB |
git-archimport.perl | -rwxr-xr-x | 36.0 KB |
git-bisect.sh | -rwxr-xr-x | 11.7 KB |
git-compat-util.h | -rw-r--r-- | 18.2 KB |
git-cvsexportcommit.perl | -rwxr-xr-x | 12.6 KB |
git-cvsimport.perl | -rwxr-xr-x | 31.3 KB |
git-cvsserver.perl | -rwxr-xr-x | 158.6 KB |
git-difftool--helper.sh | -rwxr-xr-x | 1.9 KB |
git-difftool.perl | -rwxr-xr-x | 13.3 KB |
git-filter-branch.sh | -rwxr-xr-x | 11.4 KB |
git-instaweb.sh | -rwxr-xr-x | 17.8 KB |
git-merge-octopus.sh | -rwxr-xr-x | 2.2 KB |
git-merge-one-file.sh | -rwxr-xr-x | 3.4 KB |
git-merge-resolve.sh | -rwxr-xr-x | 944 bytes |
git-mergetool--lib.sh | -rw-r--r-- | 7.4 KB |
git-mergetool.sh | -rwxr-xr-x | 8.2 KB |
git-p4.py | -rwxr-xr-x | 119.3 KB |
git-parse-remote.sh | -rw-r--r-- | 2.3 KB |
git-pull.sh | -rwxr-xr-x | 8.3 KB |
git-quiltimport.sh | -rwxr-xr-x | 3.3 KB |
git-rebase--am.sh | -rw-r--r-- | 1.5 KB |
git-rebase--interactive.sh | -rw-r--r-- | 26.6 KB |
git-rebase--merge.sh | -rw-r--r-- | 3.1 KB |
git-rebase.sh | -rwxr-xr-x | 15.2 KB |
git-relink.perl | -rwxr-xr-x | 4.0 KB |
git-remote-testgit.sh | -rwxr-xr-x | 2.5 KB |
git-request-pull.sh | -rwxr-xr-x | 3.7 KB |
git-send-email.perl | -rwxr-xr-x | 43.0 KB |
git-sh-i18n.sh | -rw-r--r-- | 2.0 KB |
git-sh-setup.sh | -rw-r--r-- | 8.0 KB |
git-stash.sh | -rwxr-xr-x | 13.1 KB |
git-submodule.sh | -rwxr-xr-x | 31.3 KB |
git-svn.perl | -rwxr-xr-x | 60.0 KB |
git-web--browse.sh | -rwxr-xr-x | 4.3 KB |
git.c | -rw-r--r-- | 17.8 KB |
git.rc | -rw-r--r-- | 566 bytes |
git.spec.in | -rw-r--r-- | 11.1 KB |
gpg-interface.c | -rw-r--r-- | 3.7 KB |
gpg-interface.h | -rw-r--r-- | 721 bytes |
graph.c | -rw-r--r-- | 34.8 KB |
graph.h | -rw-r--r-- | 3.9 KB |
grep.c | -rw-r--r-- | 40.6 KB |
grep.h | -rw-r--r-- | 4.7 KB |
hash.c | -rw-r--r-- | 2.5 KB |
hash.h | -rw-r--r-- | 1.4 KB |
help.c | -rw-r--r-- | 11.1 KB |
help.h | -rw-r--r-- | 1.1 KB |
hex.c | -rw-r--r-- | 2.3 KB |
http-backend.c | -rw-r--r-- | 13.9 KB |
http-fetch.c | -rw-r--r-- | 2.3 KB |
http-push.c | -rw-r--r-- | 50.4 KB |
http-walker.c | -rw-r--r-- | 14.0 KB |
http.c | -rw-r--r-- | 38.4 KB |
http.h | -rw-r--r-- | 5.8 KB |
ident.c | -rw-r--r-- | 10.4 KB |
imap-send.c | -rw-r--r-- | 32.9 KB |
kwset.c | -rw-r--r-- | 20.5 KB |
kwset.h | -rw-r--r-- | 2.6 KB |
levenshtein.c | -rw-r--r-- | 2.5 KB |
levenshtein.h | -rw-r--r-- | 203 bytes |
line-log.c | -rw-r--r-- | 30.7 KB |
line-log.h | -rw-r--r-- | 1.8 KB |
line-range.c | -rw-r--r-- | 6.5 KB |
line-range.h | -rw-r--r-- | 1.3 KB |
list-objects.c | -rw-r--r-- | 6.0 KB |
list-objects.h | -rw-r--r-- | 407 bytes |
ll-merge.c | -rw-r--r-- | 10.2 KB |
ll-merge.h | -rw-r--r-- | 567 bytes |
lockfile.c | -rw-r--r-- | 6.3 KB |
log-tree.c | -rw-r--r-- | 22.1 KB |
log-tree.h | -rw-r--r-- | 1015 bytes |
mailmap.c | -rw-r--r-- | 9.1 KB |
mailmap.h | -rw-r--r-- | 271 bytes |
match-trees.c | -rw-r--r-- | 8.2 KB |
merge-blobs.c | -rw-r--r-- | 2.6 KB |
merge-blobs.h | -rw-r--r-- | 194 bytes |
merge-recursive.c | -rw-r--r-- | 58.1 KB |
merge-recursive.h | -rw-r--r-- | 1.6 KB |
merge.c | -rw-r--r-- | 2.8 KB |
mergesort.c | -rw-r--r-- | 1.5 KB |
mergesort.h | -rw-r--r-- | 574 bytes |
name-hash.c | -rw-r--r-- | 7.6 KB |
notes-cache.c | -rw-r--r-- | 2.2 KB |
notes-cache.h | -rw-r--r-- | 500 bytes |
notes-merge.c | -rw-r--r-- | 22.6 KB |
notes-merge.h | -rw-r--r-- | 2.9 KB |
notes-utils.c | -rw-r--r-- | 4.4 KB |
notes-utils.h | -rw-r--r-- | 1.1 KB |
notes.c | -rw-r--r-- | 36.1 KB |
notes.h | -rw-r--r-- | 11.2 KB |
object.c | -rw-r--r-- | 8.6 KB |
object.h | -rw-r--r-- | 3.7 KB |
pack-check.c | -rw-r--r-- | 5.0 KB |
pack-revindex.c | -rw-r--r-- | 7.0 KB |
pack-revindex.h | -rw-r--r-- | 223 bytes |
pack-write.c | -rw-r--r-- | 10.2 KB |
pack.h | -rw-r--r-- | 3.2 KB |
pager.c | -rw-r--r-- | 3.6 KB |
parse-options-cb.c | -rw-r--r-- | 2.7 KB |
parse-options.c | -rw-r--r-- | 16.9 KB |
parse-options.h | -rw-r--r-- | 9.0 KB |
patch-delta.c | -rw-r--r-- | 2.2 KB |
patch-ids.c | -rw-r--r-- | 2.5 KB |
patch-ids.h | -rw-r--r-- | 490 bytes |
path.c | -rw-r--r-- | 18.1 KB |
pathspec.c | -rw-r--r-- | 14.2 KB |
pathspec.h | -rw-r--r-- | 3.2 KB |
pkt-line.c | -rw-r--r-- | 4.5 KB |
pkt-line.h | -rw-r--r-- | 3.0 KB |
preload-index.c | -rw-r--r-- | 2.4 KB |
pretty.c | -rw-r--r-- | 43.0 KB |
prio-queue.c | -rw-r--r-- | 1.9 KB |
prio-queue.h | -rw-r--r-- | 1.4 KB |
progress.c | -rw-r--r-- | 6.1 KB |
progress.h | -rw-r--r-- | 504 bytes |
prompt.c | -rw-r--r-- | 1.4 KB |
prompt.h | -rw-r--r-- | 207 bytes |
quote.c | -rw-r--r-- | 10.2 KB |
quote.h | -rw-r--r-- | 2.8 KB |
reachable.c | -rw-r--r-- | 6.1 KB |
reachable.h | -rw-r--r-- | 163 bytes |
read-cache.c | -rw-r--r-- | 52.9 KB |
reflog-walk.c | -rw-r--r-- | 8.3 KB |
reflog-walk.h | -rw-r--r-- | 773 bytes |
refs.c | -rw-r--r-- | 93.0 KB |
refs.h | -rw-r--r-- | 8.6 KB |
remote-curl.c | -rw-r--r-- | 24.3 KB |
remote-testsvn.c | -rw-r--r-- | 8.5 KB |
remote.c | -rw-r--r-- | 52.9 KB |
remote.h | -rw-r--r-- | 7.0 KB |
replace_object.c | -rw-r--r-- | 2.6 KB |
rerere.c | -rw-r--r-- | 18.1 KB |
rerere.h | -rw-r--r-- | 800 bytes |
resolve-undo.c | -rw-r--r-- | 4.3 KB |
resolve-undo.h | -rw-r--r-- | 612 bytes |
revision.c | -rw-r--r-- | 86.6 KB |
revision.h | -rw-r--r-- | 7.6 KB |
run-command.c | -rw-r--r-- | 16.7 KB |
run-command.h | -rw-r--r-- | 2.9 KB |
send-pack.c | -rw-r--r-- | 8.3 KB |
send-pack.h | -rw-r--r-- | 395 bytes |
sequencer.c | -rw-r--r-- | 32.2 KB |
sequencer.h | -rw-r--r-- | 1020 bytes |
server-info.c | -rw-r--r-- | 5.1 KB |
setup.c | -rw-r--r-- | 20.9 KB |
sh-i18n--envsubst.c | -rw-r--r-- | 10.7 KB |
sha1-array.c | -rw-r--r-- | 1.2 KB |
sha1-array.h | -rw-r--r-- | 583 bytes |
sha1-lookup.c | -rw-r--r-- | 9.3 KB |
sha1-lookup.h | -rw-r--r-- | 403 bytes |
sha1_file.c | -rw-r--r-- | 80.6 KB |
sha1_name.c | -rw-r--r-- | 35.8 KB |
shallow.c | -rw-r--r-- | 17.2 KB |
shell.c | -rw-r--r-- | 5.2 KB |
shortlog.h | -rw-r--r-- | 463 bytes |
show-index.c | -rw-r--r-- | 2.2 KB |
sideband.c | -rw-r--r-- | 3.4 KB |
sideband.h | -rw-r--r-- | 262 bytes |
sigchain.c | -rw-r--r-- | 969 bytes |
sigchain.h | -rw-r--r-- | 215 bytes |
strbuf.c | -rw-r--r-- | 11.9 KB |
strbuf.h | -rw-r--r-- | 6.1 KB |
streaming.c | -rw-r--r-- | 11.7 KB |
streaming.h | -rw-r--r-- | 504 bytes |
string-list.c | -rw-r--r-- | 7.4 KB |
string-list.h | -rw-r--r-- | 4.9 KB |
submodule.c | -rw-r--r-- | 32.7 KB |
submodule.h | -rw-r--r-- | 1.9 KB |
symlinks.c | -rw-r--r-- | 9.4 KB |
tag.c | -rw-r--r-- | 3.9 KB |
tag.h | -rw-r--r-- | 576 bytes |
tar.h | -rw-r--r-- | 644 bytes |
test-chmtime.c | -rw-r--r-- | 2.6 KB |
test-ctype.c | -rw-r--r-- | 918 bytes |
test-date.c | -rw-r--r-- | 1.4 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-- | 258 bytes |
test-line-buffer.c | -rw-r--r-- | 2.1 KB |
test-match-trees.c | -rw-r--r-- | 590 bytes |
test-mergesort.c | -rw-r--r-- | 924 bytes |
test-mktemp.c | -rw-r--r-- | 269 bytes |
test-parse-options.c | -rw-r--r-- | 3.5 KB |
test-path-utils.c | -rw-r--r-- | 3.5 KB |
test-prio-queue.c | -rw-r--r-- | 621 bytes |
test-read-cache.c | -rw-r--r-- | 202 bytes |
test-regex.c | -rw-r--r-- | 534 bytes |
test-revision-walking.c | -rw-r--r-- | 1.4 KB |
test-run-command.c | -rw-r--r-- | 840 bytes |
test-scrap-cache-tree.c | -rw-r--r-- | 395 bytes |
test-sha1.c | -rw-r--r-- | 941 bytes |
test-sha1.sh | -rwxr-xr-x | 1.9 KB |
test-sigchain.c | -rw-r--r-- | 344 bytes |
test-string-list.c | -rw-r--r-- | 2.5 KB |
test-subprocess.c | -rw-r--r-- | 401 bytes |
test-svn-fe.c | -rw-r--r-- | 1.3 KB |
test-urlmatch-normalization.c | -rw-r--r-- | 1.2 KB |
test-wildmatch.c | -rw-r--r-- | 2.7 KB |
thread-utils.c | -rw-r--r-- | 1.3 KB |
thread-utils.h | -rw-r--r-- | 209 bytes |
trace.c | -rw-r--r-- | 4.7 KB |
transport-helper.c | -rw-r--r-- | 33.7 KB |
transport.c | -rw-r--r-- | 35.0 KB |
transport.h | -rw-r--r-- | 6.8 KB |
tree-diff.c | -rw-r--r-- | 8.5 KB |
tree-walk.c | -rw-r--r-- | 21.6 KB |
tree-walk.h | -rw-r--r-- | 2.2 KB |
tree.c | -rw-r--r-- | 6.3 KB |
tree.h | -rw-r--r-- | 945 bytes |
unimplemented.sh | -rw-r--r-- | 100 bytes |
unix-socket.c | -rw-r--r-- | 2.4 KB |
unix-socket.h | -rw-r--r-- | 158 bytes |
unpack-trees.c | -rw-r--r-- | 48.2 KB |
unpack-trees.h | -rw-r--r-- | 2.2 KB |
upload-pack.c | -rw-r--r-- | 20.0 KB |
url.c | -rw-r--r-- | 2.8 KB |
url.h | -rw-r--r-- | 492 bytes |
urlmatch.c | -rw-r--r-- | 16.6 KB |
urlmatch.h | -rw-r--r-- | 2.0 KB |
usage.c | -rw-r--r-- | 3.3 KB |
userdiff.c | -rw-r--r-- | 9.2 KB |
userdiff.h | -rw-r--r-- | 646 bytes |
utf8.c | -rw-r--r-- | 16.4 KB |
utf8.h | -rw-r--r-- | 1.4 KB |
varint.c | -rw-r--r-- | 631 bytes |
varint.h | -rw-r--r-- | 198 bytes |
version.c | -rw-r--r-- | 651 bytes |
version.h | -rw-r--r-- | 180 bytes |
walker.c | -rw-r--r-- | 7.2 KB |
walker.h | -rw-r--r-- | 1.1 KB |
wildmatch.c | -rw-r--r-- | 7.8 KB |
wildmatch.h | -rw-r--r-- | 346 bytes |
wrap-for-bin.sh | -rw-r--r-- | 707 bytes |
wrapper.c | -rw-r--r-- | 9.7 KB |
write_or_die.c | -rw-r--r-- | 1.9 KB |
ws.c | -rw-r--r-- | 9.6 KB |
wt-status.c | -rw-r--r-- | 42.6 KB |
wt-status.h | -rw-r--r-- | 2.6 KB |
xdiff-interface.c | -rw-r--r-- | 7.0 KB |
xdiff-interface.h | -rw-r--r-- | 944 bytes |
zlib.c | -rw-r--r-- | 6.1 KB |
Computing file changes ...