summaryrefslogtreecommitdiff
path: root/mergesort.c
diff options
context:
space:
mode:
authorRené Scharfe <rene.scharfe@lsrfire.ath.cx>2012-03-31 22:11:01 (GMT)
committerJunio C Hamano <gitster@pobox.com>2012-04-11 15:50:54 (GMT)
commitfbc08ea177f8284d10c62ad39de51edb21af88b0 (patch)
treea9a6ae74936951f3e68c377ba590bb4ae6c8151f /mergesort.c
parent46905893b20ac2a044c06a0eecc12425a8405e69 (diff)
downloadgit-fbc08ea177f8284d10c62ad39de51edb21af88b0.zip
git-fbc08ea177f8284d10c62ad39de51edb21af88b0.tar.gz
git-fbc08ea177f8284d10c62ad39de51edb21af88b0.tar.bz2
revision: insert unsorted, then sort in prepare_revision_walk()
Speed up prepare_revision_walk() by adding commits without sorting to the commit_list and at the end sort the list in one go. Thanks to mergesort() working behind the scenes, this is a lot faster for large numbers of commits than the current insert sort. Also introduce and use commit_list_reverse(), to keep the ordering of commits sharing the same commit date unchanged. That's because commit_list_insert_by_date() sorts commits with descending date, but adds later entries with the same date entries last, while commit_list_insert() always inserts entries at the top. The following commit_list_sort_by_date() keeps the order of entries sharing the same date. Jeff's test case, in a repo with lots of refs, was to run: # make a new commit on top of HEAD, but not yet referenced sha1=`git commit-tree HEAD^{tree} -p HEAD </dev/null` # now do the same "connected" test that receive-pack would do git rev-list --objects $sha1 --not --all With a git.git with a ref for each revision, master needs (best of five): real 0m2.210s user 0m2.188s sys 0m0.016s And with this patch: real 0m0.480s user 0m0.456s sys 0m0.020s Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'mergesort.c')
0 files changed, 0 insertions, 0 deletions