commit: convert pop_most_recent_commit() to prio_queue
cover commit: convert pop_most_recent_commit() to prio_queue
Use prio_queue to improve worst-case performance at the cost of slightly worse best-case performance. Then add and use prio_queue_replace() to recover that loss.
commit: convert pop_most_recent_commit() to prio_queue
prio-queue: add prio_queue_replace()
commit: use prio_queue_replace() in pop_most_recent_commit()
commit.c | 14 ++++++-- commit.h | 8 ++--- fetch-pack.c | 13 +++++--- object-name.c | 10 +++--- prio-queue.c | 45 +++++++++++++++++-------- prio-queue.h | 8 +++++ t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++ t/unit-tests/u-prio-queue.c | 23 +++++++++++++ walker.c | 11 ++++--- 9 files changed, 153 insertions(+), 34 deletions(-) create mode 100755 t/perf/p1501-rev-parse-oneline.sh
Signature · 1 line
2.50.1
PATCH 1/3 commit: convert pop_most_recent_commit() to prio_queue
pop_most_recent_commit() calls commit_list_insert_by_date(), which and is itself called in a loop, which can lead to quadratic complexity. Replace the commit_list with a prio_queue to ensure logarithmic worst case complexity and convert all three users.
Add a performance test that exercises one of them using a pathological history that consists of 50% merges and 50% root commits to demonstrate the speedup:
Test v2.50.1 HEAD
----------------------------------------------------------------------
1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%
Alas, sane histories don't benefit from the conversion much, and traversing Git's own history takes a 1% performance hit on my machine:
$ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'
Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]
Range (min … max): 1.067 s … 1.078 s 10 runsBenchmark 2: ./git rev-parse :/^Initial.revision
Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]
Range (min … max): 1.074 s … 1.083 s 10 runs Summary
./git_2.50.1 rev-parse :/^Initial.revision ran
1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision
--- commit.c | 7 ++-- commit.h | 8 ++--- fetch-pack.c | 13 +++++--- object-name.c | 10 +++--- t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++ walker.c | 11 ++++--- 6 files changed, 83 insertions(+), 21 deletions(-) create mode 100755 t/perf/p1501-rev-parse-oneline.sh
commit.c +4 -3
@@ -31,6 +31,7 @@#include "parse.h" #include "object-file.h" #include "object-file-convert.h" +#include "prio-queue.h" static struct commit_extra_header *read_commit_extra_header_lines (const char *buf,size_t len,const char **);
@@ -738,17 +739,17 @@ void commit_list_sort_by_date(struct commit_list **list)commit_list_sort (list, commit_list_compare_by_date); } -struct commit *pop_most_recent_commit (struct commit_list **list, +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =pop_commit (list); +struct commit *ret =prio_queue_get (queue);struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -commit_list_insert_by_date (commit, list); +prio_queue_put (queue, commit); } parents = parents->next; }
commit.h +4 -4
@@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,const char *skip_blank_lines (const char *msg); -/** Removes the first commit from a list sorted by date, and adds all -* of its parents. -**/ -struct commit *pop_most_recent_commit (struct commit_list **list, +struct prio_queue ; + +/* Removes the first commit from a prio_queue and adds its parents. */ +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark);struct commit *pop_commit (struct commit_list **stack);
fetch-pack.c +8 -5
@@ -34,6 +34,7 @@#include "commit-graph.h" #include "sigchain.h" #include "mergesort.h" +#include "prio-queue.h" static int transfer_unpack_limit =-1 ;static int fetch_unpack_limit =-1 ;
@@ -600,7 +601,7 @@ static int find_common(struct fetch_negotiator *negotiator,return count ? retval :0 ; } -static struct commit_list *complete; +static struct prio_queue complete = { compare_commits_by_commit_date };static int mark_complete (const struct object_id *oid) {
@@ -608,7 +609,7 @@ static int mark_complete(const struct object_id *oid)if (commit && !(commit->object.flags &COMPLETE )) { commit->object.flags |=COMPLETE ; -commit_list_insert (commit, &complete); +prio_queue_put (&complete, commit); }return 0 ; }
@@ -625,9 +626,12 @@ static int mark_complete_oid(const char *refname UNUSED,static void mark_recent_complete_commits (struct fetch_pack_args *args,timestamp_t cutoff) { -while (complete && cutoff <= complete->item->date) { +while (complete.nr) { +struct commit *item =prio_queue_peek (&complete); +if (item->date < cutoff) +break ;print_verbose (args,_ ("Marking %s as complete" ), -oid_to_hex (&complete->item->object.oid)); +oid_to_hex (&item->object.oid));pop_most_recent_commit (&complete,COMPLETE ); } }
@@ -797,7 +801,6 @@ static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator,refs_for_each_rawref (get_main_ref_store (the_repository), mark_complete_oid,NULL );for_each_cached_alternate (NULL , mark_alternate_complete); -commit_list_sort_by_date (&complete);if (cutoff)mark_recent_complete_commits (args, cutoff); }
object-name.c +5 -5
@@ -28,6 +28,7 @@#include "commit-reach.h" #include "date.h" #include "object-file-convert.h" +#include "prio-queue.h" static int get_oid_oneline (struct repository *r,const char *,struct object_id *,const struct commit_list *);
@@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r, const char *prefix, struct object_id *oid, const struct commit_list *list) { - struct commit_list *copy = NULL, **copy_tail = © + struct prio_queue copy = { compare_commits_by_commit_date };const struct commit_list *l;int found =0 ;int negative =0 ;
@@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,for (l = list; l; l = l->next) { l->item->object.flags |=ONELINE_SEEN ; - copy_tail = &commit_list_insert (l->item, copy_tail)->next; +prio_queue_put (©, l->item); } -while (copy) { +while (copy.nr) {const char *p, *buf;struct commit *commit;int matches;
@@ -1507,7 +1508,7 @@ static int get_oid_oneline(struct repository *r,regfree (®ex);for (l = list; l; l = l->next)clear_commit_marks (l->item,ONELINE_SEEN ); -free_commit_list (copy); +clear_prio_queue (©);return found ?0 :-1 ; }
@@ -2061,7 +2062,6 @@ static enum get_oid_result get_oid_with_context_1(struct repository *repo, cb.list = &list;refs_for_each_ref (get_main_ref_store (repo), handle_one_ref, &cb);refs_head_ref (get_main_ref_store (repo), handle_one_ref, &cb); -commit_list_sort_by_date (&list); ret =get_oid_oneline (repo, name +2 , oid, list);free_commit_list (list);
t/perf/p1501-rev-parse-oneline.sh new file +55 -0
55 lines not on this page · raw message
walker.c +7 -4
@@ -14,6 +14,7 @@#include "blob.h" #include "refs.h" #include "progress.h" +#include "prio-queue.h" static struct object_id current_commit_oid;
@@ -78,7 +79,7 @@ static int process_tree(struct walker *walker, struct tree *tree)#define SEEN (1U << 1)#define TO_SCAN (1U << 2) -static struct commit_list *complete =NULL ; +static struct prio_queue complete = { compare_commits_by_commit_date };static int process_commit (struct walker *walker,struct commit *commit) {
@@ -87,7 +88,10 @@ static int process_commit(struct walker *walker, struct commit *commit)if (repo_parse_commit (the_repository, commit))return -1 ; -while (complete && complete->item->date >= commit->date) { +while (complete.nr) { +struct commit *item =prio_queue_peek (&complete); +if (item->date < commit->date) +break ;pop_most_recent_commit (&complete,COMPLETE ); }
@@ -233,7 +237,7 @@ static int mark_complete(const char *path UNUSED,if (commit) { commit->object.flags |=COMPLETE ; -commit_list_insert (commit, &complete); +prio_queue_put (&complete, commit); }return 0 ; }
@@ -302,7 +306,6 @@ int walker_fetch(struct walker *walker, int targets, char **target,if (!walker->get_recover) {refs_for_each_ref (get_main_ref_store (the_repository), mark_complete,NULL ); -commit_list_sort_by_date (&complete); }for (i =0 ; i < targets; i++) {
Signature · 1 line
2.50.1
Quoted 9 lines · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which and is itself called in a loop, which can lead to quadratic complexity. Replace thecommit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.Add a performance test that exercises one of them using a pathological history that consists of 50% merges and 50% root commits to demonstrate the speedup:
Quoted 6 lines
Test v2.50.1 HEAD ---------------------------------------------------------------------- 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%Alas, sane histories don't benefit from the conversion much, and traversing Git's own history takes a 1% performance hit on my machine:
;-)
Quoted 12 lines
$ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision' Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s] Range (min … max): 1.067 s … 1.078 s 10 runsBenchmark 2: ./git rev-parse :/^Initial.revision Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s] Range (min … max): 1.074 s … 1.083 s 10 runs Summary ./git_2.50.1 rev-parse :/^Initial.revision ran 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision
Quoted 1 line · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which and
Did you mean?
s/which and/which/
Quoted 3 lines
is itself called in a loop, which can lead to quadratic complexity. Replace the
commit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.
If I understand correctly, pop_most_recent_commit() removes the most recent commit from a list of commits sorted by date and then inserts each of the removed commit's parents into the list while maintaining date order. Iterating through struct commit_list every time to find where to insert each parent parent leads to quadratic complexity. For repositories with many merge commits, this could scale poorly.
Quoted 10 lines
Add a performance test that exercises one of them using a pathological history that consists of 50% merges and 50% root commits to demonstrate the speedup:
Test v2.50.1 HEAD ---------------------------------------------------------------------- 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%Alas, sane histories don't benefit from the conversion much, and traversing Git's own history takes a 1% performance hit on my machine:
As "normal" repositories don't benefit here, it might be nice to more explicitly mention the the types of repositories that do benefit.
Quoted 64 lines
$ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision' Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s] Range (min … max): 1.067 s … 1.078 s 10 runsBenchmark 2: ./git rev-parse :/^Initial.revision Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s] Range (min … max): 1.074 s … 1.083 s 10 runs Summary ./git_2.50.1 rev-parse :/^Initial.revision ran 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revisionSigned-off-by René Scharfe <[email protected]>--- commit.c | 7 ++-- commit.h | 8 ++--- fetch-pack.c | 13 +++++--- object-name.c | 10 +++--- t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++ walker.c | 11 ++++--- 6 files changed, 83 insertions(+), 21 deletions(-) create mode 100755 t/perf/p1501-rev-parse-oneline.shcommit.c +4
-3@@ -31,6 +31,7 @@#include "parse.h" #include "object-file.h" #include "object-file-convert.h" +#include "prio-queue.h" static struct commit_extra_header *read_commit_extra_header_lines (const char *buf,size_t len,const char **);@@ -738,17 +739,17 @@ void commit_list_sort_by_date(struct commit_list **list)commit_list_sort (list, commit_list_compare_by_date); } -struct commit *pop_most_recent_commit (struct commit_list **list, +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =pop_commit (list); +struct commit *ret =prio_queue_get (queue);struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -commit_list_insert_by_date (commit, list); +prio_queue_put (queue, commit); } parents = parents->next; }commit.h +0
-0@@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,const char *skip_blank_lines (const char *msg);
commit.h const char *repo_logmsg_reencode(struct repository *r, · line 208
Quoted 10 lines
commit.h +4
-4-/** Removes the first commit from a list sorted by date, and adds all -* of its parents. -**/ -struct commit *pop_most_recent_commit (struct commit_list **list, +struct prio_queue ; + +/* Removes the first commit from a prio_queue and adds its parents. */ +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark);
Previously, pop_most_recent_commit() would ensure commits inserted in the list were done it date order. Now this depends on how the caller has configured the struct prio_queue. This is fine though as previously the caller was required to ensure the list was sorted to begin with otherwise it wouldn't work properly.
-Justin
Quoted 6 lines · Justin Tobler
Quoted 1 line · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which andDid you mean?
s/which and/which/
Oh, yes.
Quoted 10 lines
Quoted 3 lines
is itself called in a loop, which can lead to quadratic complexity. Replace the
commit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.If I understand correctly,
pop_most_recent_commit()removes the most recent commit from a list of commits sorted by date and then inserts each of the removed commit's parents into the list while maintaining date order. Iterating throughstruct commit_listevery time to find where to insert each parent parent leads to quadratic complexity. For repositories with many merge commits, this could scale poorly.
Right.
Quoted 8 lines
Quoted 8 lines
Add a performance test that exercises one of them using a pathological history that consists of 50% merges and 50% root commits to demonstrate the speedup:
Test v2.50.1 HEAD ---------------------------------------------------------------------- 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%
Quoted 5 lines
Quoted 2 lines
Alas, sane histories don't benefit from the conversion much, and traversing Git's own history takes a 1% performance hit on my machine:
As "normal" repositories don't benefit here, it might be nice to more explicitly mention the the types of repositories that do benefit.
Good idea.
Quoted 8 lines
Quoted 8 lines
commit.h +0
-0@@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,const char *skip_blank_lines (const char *msg);
Quoted 15 lines
commit.h const char *repo_logmsg_reencode(struct repository *r, · line 208
Quoted 9 lines
commit.h +4
-4-/** Removes the first commit from a list sorted by date, and adds all -* of its parents. -**/ -struct commit *pop_most_recent_commit (struct commit_list **list, +struct prio_queue ; + +/* Removes the first commit from a prio_queue and adds its parents. */ +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark);Previously,
pop_most_recent_commit()would ensure commits inserted in the list were done it date order. Now this depends on how the caller has configured thestruct prio_queue. This is fine though as previously the caller was required to ensure the list was sorted to begin with otherwise it wouldn't work properly.
Indeed.
René
Quoted 4 lines · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which and is itself called in a loop, which can lead to quadratic complexity. Replace thecommit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.
I guess I'm cc'd because of my frequent complains about the quadratic nature of our commit lists? :)
Mostly I asked because I had to look at pop_most_recent_commit() to see what operation would be made faster here. Looks like it's mostly ":/", but maybe also fetch's mark_recent_complete_commits()? I guess we might hit that if you have a huge number of refs?
Anyway, I am in support of the direction regardless.
I actually have a series turning rev_info.commits into a prio_queue which I need to polish up (mostly just writing commit messages; I've been running with it for almost 2 years without trouble). Ironically it does not touch this spot, as these commit lists are formed on their own.
The patch itself looks reasonable. I think here:
Quoted 11 lines
object-name.c +1
-1@@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r, const char *prefix, struct object_id *oid, const struct commit_list *list) { - struct commit_list *copy = NULL, **copy_tail = © + struct prio_queue copy = { compare_commits_by_commit_date };const struct commit_list *l;int found =0 ;int negative =0 ;@@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,
object-name.c static int get_oid_oneline(struct repository *r, · line 1492
Quoted 10 lines
object-name.c +2
-2for (l = list; l; l = l->next) { l->item->object.flags |=ONELINE_SEEN ; - copy_tail = &commit_list_insert (l->item, copy_tail)->next; +prio_queue_put (©, l->item); } -while (copy) { +while (copy.nr) {const char *p, *buf;struct commit *commit;int matches;
our callers are always generating and passing in a list. So we could avoid the overhead of allocating the list in the first place by just taking a prio_queue. But maybe it gets weird with clearing the ONELINE_SEEN marks? We make a copy even in the current code so that we can call clear_commit_marks() on the complete set.
I guess we could add them to an array or something, but that probably ends up being roughly the same amount of work.
Quoted 20 lines
t/perf/p1501-rev-parse-oneline.sh new file +20
-0+build_history () { + local max_level="$1" && + local level="${2:-1}" && + local mark="${3:-1}" && + if test $level -eq $max_level + then + echo "reset refs/heads/master" && + echo "from $ZERO_OID" && + echo "commit refs/heads/master" && + echo "mark :$mark" && + echo "committer C <[email protected]> 1234567890 +0000" && + echo "data <<EOF" && + echo "$mark" && + echo "EOF" + else + local level1=$((level+1)) && + local mark1=$((2*mark)) && + local mark2=$((2*mark+1)) && + build_history $max_level $level1 $mark1 && + build_history $max_level $level1 $mark2 &&
t/perf/p1501-rev-parse-oneline.sh line 38
Quoted 10 lines
t/perf/p1501-rev-parse-oneline.sh new file +10
-0+ echo "commit refs/heads/master" && + echo "mark :$mark" && + echo "committer C <[email protected]> 1234567890 +0000" && + echo "data <<EOF" && + echo "$mark" && + echo "EOF" && + echo "from :$mark1" && + echo "merge :$mark2" + fi +}
This took some brain cycles to decipher. It looks like we'll make 2^$level commits in a filled tree? It might be worth a brief comment describing the goal (and maybe even giving an example graph drawing for N=3 or something, though it gets out of hand quickly).
t/perf/p1501-rev-parse-oneline.sh line 49
Quoted 3 lines
t/perf/p1501-rev-parse-oneline.sh new file +3
-0+test_perf "rev-parse ':/$(cat needle)'" " + git rev-parse ':/$(cat needle)' >actual +"
Hmm, usually we frown on putting snippets inside double-quotes because it's so easy to accidentally interpolate outside of the test_eval. But maybe this is short enough to be OK. I guess you did it here especially so that the title is a nice ":/65535" and not the opaque "$(cat needle)".
-Peff
Quoted 9 lines · Jeff King
Quoted 4 lines · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which and is itself called in a loop, which can lead to quadratic complexity. Replace thecommit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.I guess I'm cc'd because of my frequent complains about the quadratic nature of our commit lists? :)
And because you introduced prio_queue.
Quoted 4 lines
Mostly I asked because I had to look at
pop_most_recent_commit()to see what operation would be made faster here. Looks like it's mostly ":/", but maybe also fetch'smark_recent_complete_commits()? I guess we might hit that if you have a huge number of refs?
The :/ handling was the easiest to test for me. fetch_pack() and walker_fetch() require some server side to set up, which seems not worth it just to demonstrate quadratic behavior. Having thousands of refs would make the list long enough to notice, as would having lots of merges.
My general idea is to get rid of commit_list_insert_by_date() eventually to avoid quadratic complexity.
Quoted 4 lines
I actually have a series turning rev_info.commits into a
prio_queuewhich I need to polish up (mostly just writing commit messages; I've been running with it for almost 2 years without trouble). Ironically it does not touch this spot, as these commit lists are formed on their own.
That is not a coincidence. I had a look at that series and tried to reach its goals while keeping rev_info.commits a commit_list. Why? Mostly being vaguely uncomfortable with prio_queue' memory overhead, lack of type safety and dual use as a stack. I still used it, but only as local variable, not in the central struct rev_info.
Anyway, I failed; revision.c::get_revision_1() took an 8% performance hit in my versions and none in yours, and I couldn't figure out why. Perhaps I should revisit it with the new prio_queue_replace() in hand, hmm.. For now I try to salvage the commit_list_insert_by_date() replacement work outside of revision.c from that effort.
Quoted 30 lines
The patch itself looks reasonable. I think here:
Quoted 11 lines
object-name.c +1
-1@@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r, const char *prefix, struct object_id *oid, const struct commit_list *list) { - struct commit_list *copy = NULL, **copy_tail = © + struct prio_queue copy = { compare_commits_by_commit_date };const struct commit_list *l;int found =0 ;int negative =0 ;@@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,object-name.c static int get_oid_oneline(struct repository *r, · line 1492
Quoted 10 lines
object-name.c +2
-2for (l = list; l; l = l->next) { l->item->object.flags |=ONELINE_SEEN ; - copy_tail = &commit_list_insert (l->item, copy_tail)->next; +prio_queue_put (©, l->item); } -while (copy) { +while (copy.nr) {const char *p, *buf;struct commit *commit;int matches;our callers are always generating and passing in a list. So we could avoid the overhead of allocating the list in the first place by just taking a
prio_queue. But maybe it gets weird with clearing theONELINE_SEENmarks? We make a copy even in the current code so that we can callclear_commit_marks()on the complete set.
Quoted 2 lines
I guess we could add them to an array or something, but that probably ends up being roughly the same amount of work.
Right, if get_oid_oneline() gets handed a prio_queue, it would need to copy all commits to a list or array for marks clearing at the end. I don't see a way around having both. And I doubt there would be much of a difference between list and array here, but could be convinced by numbers. ;)
Quoted 27 lines
Quoted 27 lines
t/perf/p1501-rev-parse-oneline.sh new file +27
-0+build_history () { + local max_level="$1" && + local level="${2:-1}" && + local mark="${3:-1}" && + if test $level -eq $max_level + then + echo "reset refs/heads/master" && + echo "from $ZERO_OID" && + echo "commit refs/heads/master" && + echo "mark :$mark" && + echo "committer C <[email protected]> 1234567890 +0000" && + echo "data <<EOF" && + echo "$mark" && + echo "EOF" + else + local level1=$((level+1)) && + local mark1=$((2*mark)) && + local mark2=$((2*mark+1)) && + build_history $max_level $level1 $mark1 && + build_history $max_level $level1 $mark2 && + echo "commit refs/heads/master" && + echo "mark :$mark" && + echo "committer C <[email protected]> 1234567890 +0000" && + echo "data <<EOF" && + echo "$mark" && + echo "EOF" && + echo "from :$mark1" &&
Quoted 8 lines
t/perf/p1501-rev-parse-oneline.sh line 38
Quoted 3 lines
t/perf/p1501-rev-parse-oneline.sh new file +3
-0+ echo "merge :$mark2" + fi +}This took some brain cycles to decipher. It looks like we'll make 2^$level commits in a filled tree? It might be worth a brief comment describing the goal (and maybe even giving an example graph drawing for N=3 or something, though it gets out of hand quickly).
The goal is to have lots of merges, to make the list that pop_most_recent_commit() works on long (each pop adds back two parents).
The script builds a binary tree of merges, with root commits (without parents) as leaf nodes. (The nomenclature is a bit weird because we call the child nodes parent commits.) So it creates 2^($level-1) root commits and 2^($level-1)-1 two-way merges stacked on top.
_1_
/ \
2 3
/ \ / \
4 5 6 7
The numbers are the marks; 1 to 3 are merges (have two parents), 4 to 7 are root commits.
Quoted 9 lines
t/perf/p1501-rev-parse-oneline.sh line 49
Quoted 3 lines
t/perf/p1501-rev-parse-oneline.sh new file +3
-0+test_perf "rev-parse ':/$(cat needle)'" " + git rev-parse ':/$(cat needle)' >actual +"Hmm, usually we frown on putting snippets inside double-quotes because it's so easy to accidentally interpolate outside of the
test_eval. But maybe this is short enough to be OK. I guess you did it here especially so that the title is a nice ":/65535" and not the opaque "$(cat needle)".
The first one allowed me to check whether the setup step created the expected number of commits and seems kind of interesting for people running the test. The second one could be switched to be evaluated at test_eval time, but that would make it harder to see that title and test do the same. We could strip out the quotes:
test_perf "rev-parse :/$(cat needle)" '
git rev-parse :/$(cat needle) >actual
'René
Quoted 13 lines · René Scharfe
Quoted 4 lines · Jeff King
I actually have a series turning rev_info.commits into a
prio_queuewhich I need to polish up (mostly just writing commit messages; I've been running with it for almost 2 years without trouble). Ironically it does not touch this spot, as these commit lists are formed on their own.That is not a coincidence. I had a look at that series and tried to reach its goals while keeping rev_info.commits a
commit_list. Why? Mostly being vaguely uncomfortable withprio_queue' memory overhead, lack of type safety and dual use as a stack. I still used it, but only as local variable, not in the central structrev_info.
Quoted 4 lines
Anyway, I failed;
revision.c::get_revision_1()took an 8% performance hit in my versions and none in yours, and I couldn't figure out why. Perhaps I should revisit it with the newprio_queue_replace()in hand, hmm..
Checked now, and it's still slower. So I don't see an alternative to making rev_info.commits a prio_queue.
René
Quoted 8 lines · René Scharfe
Quoted 7 lines · Jeff King
Quoted 4 lines · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which and is itself called in a loop, which can lead to quadratic complexity. Replace thecommit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.
Quoted 4 lines
Quoted 2 lines
I guess I'm cc'd because of my frequent complains about the quadratic nature of our commit lists? :)
And because you introduced
prio_queue.
I think that was Junio, but I think I can be counted as a cheerleader for the topic. :)
Quoted 10 lines
Quoted 4 lines
Mostly I asked because I had to look at
pop_most_recent_commit()to see what operation would be made faster here. Looks like it's mostly ":/", but maybe also fetch'smark_recent_complete_commits()? I guess we might hit that if you have a huge number of refs?The :/ handling was the easiest to test for me.
fetch_pack()andwalker_fetch()require some server side to set up, which seems not worth it just to demonstrate quadratic behavior. Having thousands of refs would make the list long enough to notice, as would having lots of merges.
OK, that makes sense. Just making sure I understand the benefits.
Quoted 2 lines
My general idea is to get rid of
commit_list_insert_by_date()eventually to avoid quadratic complexity.
Yeah, it's certainly at the root of many such problems we've seen over the years.
Quoted 10 lines
Quoted 4 lines
I actually have a series turning rev_info.commits into a
prio_queuewhich I need to polish up (mostly just writing commit messages; I've been running with it for almost 2 years without trouble). Ironically it does not touch this spot, as these commit lists are formed on their own.That is not a coincidence. I had a look at that series and tried to reach its goals while keeping rev_info.commits a
commit_list. Why? Mostly being vaguely uncomfortable withprio_queue' memory overhead, lack of type safety and dual use as a stack. I still used it, but only as local variable, not in the central structrev_info.
Hmm, I would have thought prio_queue had less memory overhead. You're spending one pointer per entry in a packed array, versus list nodes. But it's true that it doesn't shrink as items are removed (though that is something we _could_ implement).
The dual use as a stack actually came in handy for my series, IIRC. There are spots which use a commit_list but care about a specific order, and my list/prio_queue conversion helpers use that to create a non-heap prio_queue that just returns the items in the original order (it's actually FIFO, but we can get that by reversing).
I dunno. That's kind of horrible when I say it out loud, but it did make things work. I'm surprised that your attempt ended up with a performance hit when mine did not. Mine tried not to be clever, and even leaves in place a few spots where we convert between the two representations to satisfy various interfaces (with the goal that we'd probably eventually switch to prio_queue everywhere).
-Peff
Quoted 17 lines · Jeff King
Quoted 5 lines
That is not a coincidence. I had a look at that series and tried to reach its goals while keeping rev_info.commits a
commit_list. Why? Mostly being vaguely uncomfortable withprio_queue' memory overhead, lack of type safety and dual use as a stack. I still used it, but only as local variable, not in the central structrev_info.Hmm, I would have thought
prio_queuehad less memory overhead. You're spending one pointer per entry in a packed array, versus list nodes. But it's true that it doesn't shrink as items are removed (though that is something we _could_ implement).The dual use as a stack actually came in handy for my series, IIRC. There are spots which use a
commit_listbut care about a specific order, and my list/prio_queue conversion helpers use that to create a non-heapprio_queuethat just returns the items in the original order (it's actually FIFO, but we can get that by reversing).
Quoted 6 lines
I dunno. That's kind of horrible when I say it out loud, but it did make things work. I'm surprised that your attempt ended up with a performance hit when mine did not. Mine tried not to be clever, and even leaves in place a few spots where we convert between the two representations to satisfy various interfaces (with the goal that we'd probably eventually switch to
prio_queueeverywhere).
Oh, re-reading what you wrote again: you left rev_info.commits as a list, so presumably you were paying more conversion overhead as you walked (whereas I think in mine the prio_queue becomes the data structure for the hot path during traversal).
-Peff
Quoted 10 lines · Jeff King
Quoted 8 lines · René Scharfe
Quoted 7 lines · Jeff King
Quoted 4 lines · René Scharfe
pop_most_recent_commit()callscommit_list_insert_by_date(), which and is itself called in a loop, which can lead to quadratic complexity. Replace thecommit_listwith aprio_queueto ensure logarithmic worst case complexity and convert all three users.
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
I guess I'm cc'd because of my frequent complains about the quadratic nature of our commit lists? :)
And because you introduced
prio_queue.I think that was Junio, but I think I can be counted as a cheerleader for the topic. :)
Ah, sorry. You did make it stable, though, which allows using it for backward-compatible history traversal.
Quoted 11 lines
Quoted 10 lines
Quoted 4 lines
I actually have a series turning rev_info.commits into a
prio_queuewhich I need to polish up (mostly just writing commit messages; I've been running with it for almost 2 years without trouble). Ironically it does not touch this spot, as these commit lists are formed on their own.That is not a coincidence. I had a look at that series and tried to reach its goals while keeping rev_info.commits a
commit_list. Why? Mostly being vaguely uncomfortable withprio_queue' memory overhead, lack of type safety and dual use as a stack. I still used it, but only as local variable, not in the central structrev_info.
Quoted 4 lines
Hmm, I would have thought
prio_queuehad less memory overhead. You're spending one pointer per entry in a packed array, versus list nodes. But it's true that it doesn't shrink as items are removed (though that is something we _could_ implement).
If we just count the net data then a commit_list item has two pointers and a prio_queue_entry has a pointer and an ID for stability. That's a tie. ALLOC_GROW overallocates by ca. 50%, so that's 25% more on average for the prio_queue. No idea what overhead malloc() needs per allocation, but I guess it's enough to tilt the scale back against commit_lists.
However, a prio_queue without a comparison function acts as a FIFO stack, but needs double the amount of memory than a pointer array without the stability ID would, for the same behavior.
I don't think lack of shrinking causes much of an issue. I did stumble over at least one place where using a prio_queue in FIFO mode made the code slightly but measurably slower than using a commit_list, though, which could be rectified by using a raw array of pointers.
René
Quoted 11 lines · René Scharfe
Quoted 4 lines
Hmm, I would have thought
prio_queuehad less memory overhead. You're spending one pointer per entry in a packed array, versus list nodes. But it's true that it doesn't shrink as items are removed (though that is something we _could_ implement).If we just count the net data then a
commit_listitem has two pointers and aprio_queue_entryhas a pointer and an ID for stability. That's a tie.ALLOC_GROWoverallocates by ca. 50%, so that's 25% more on average for theprio_queue. No idea what overheadmalloc()needs per allocation, but I guess it's enough to tilt the scale back againstcommit_lists.
Oh right, I totally forgot about the extra counter.
-Peff
Quoted 7 lines · Jeff King
Quoted 5 lines · René Scharfe
Quoted 4 lines
Hmm, I would have thought
prio_queuehad less memory overhead. You're spending one pointer per entry in a packed array, versus list nodes. But it's true that it doesn't shrink as items are removed (though that is something we _could_ implement).
Quoted 8 lines
Quoted 6 lines
If we just count the net data then a
commit_listitem has two pointers and aprio_queue_entryhas a pointer and an ID for stability. That's a tie.ALLOC_GROWoverallocates by ca. 50%, so that's 25% more on average for theprio_queue. No idea what overheadmalloc()needs per allocation, but I guess it's enough to tilt the scale back againstcommit_lists.Oh right, I totally forgot about the extra counter.
Don't feel bad. I forgot about it, too, when I gave my "is it stable?" comment to René's patch. ;-)
Quoted 2 lines · René Scharfe
t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++ create mode 100755 t/perf/p1501-rev-parse-oneline.sh
This unfortunately calls for something like.
Tonight's integration cycle I have this on top of your series in 'seen'.
Subject: [PATCH] fixup! commit: convert pop_most_recent_commit() to prio_queue
t/meson.build | 1 + 1 file changed, 1 insertion(+)
t/meson.build +1 -0
@@ -1117,6 +1117,7 @@ benchmarks = [ 'perf/p1450-fsck.sh', 'perf/p1451-fsck-skip-list.sh', 'perf/p1500-graph-walks.sh', + 'perf/p1501-rev-parse-oneline.sh', 'perf/p2000-sparse-operations.sh', 'perf/p3400-rebase.sh', 'perf/p3404-rebase-interactive.sh',
Signature · 1 line
2.50.1-447-g1e759a1f67
Quoted 20 lines · Junio C Hamano
Quoted 2 lines · René Scharfe
t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++ create mode 100755 t/perf/p1501-rev-parse-oneline.shThis unfortunately calls for something like.
Tonight's integration cycle I have this on top of your series in 'seen'.
Subject: [PATCH] fixup! commit: convert
pop_most_recent_commit()toprio_queuet/meson.build | 1 + 1 file changed, 1 insertion(+)t/meson.build +0
-0
t/meson.build benchmarks = [ · line 1123
Quoted 7 lines
t/meson.build +1
-0@@ -1117,6 +1117,7 @@ benchmarks = [ 'perf/p1450-fsck.sh', 'perf/p1451-fsck-skip-list.sh', 'perf/p1500-graph-walks.sh', + 'perf/p1501-rev-parse-oneline.sh', 'perf/p2000-sparse-operations.sh', 'perf/p3400-rebase.sh', 'perf/p3404-rebase-interactive.sh',
Oh, OK, thanks. Will include it in v2.
René
PATCH 2/3 prio-queue: add prio_queue_replace()
In reply to René ScharfeAdd a function to replace the top element of the queue that basically does the same as prio_queue_get() followed by prio_queue_put(), but without the work by prio_queue_get() to rebalance the heap. It can be used to optimize loops that get one element and then immediately add another one. That's common e.g., with commit history traversal, where we get out a commit and then put in its parents.
--- prio-queue.c | 45 ++++++++++++++++++++++++++----------- prio-queue.h | 8 +++++++ t/unit-tests/u-prio-queue.c | 23 +++++++++++++++++++ 3 files changed, 63 insertions(+), 13 deletions(-)
prio-queue.c +32 -13
@@ -58,22 +58,10 @@ void prio_queue_put(struct prio_queue *queue, void *thing) } } -void *prio_queue_get (struct prio_queue *queue) +static void sift_down_root (struct prio_queue *queue) { -void *result;size_t ix, child; -if (!queue->nr) -return NULL ; -if (!queue->compare) -return queue->array[--queue->nr].data;/* LIFO */ - - result = queue->array[0 ].data; -if (!--queue->nr) -return result; - - queue->array[0 ] = queue->array[queue->nr]; -/* Push down the one at the root */ for (ix =0 ; ix *2 +1 < queue->nr; ix = child) { child = ix *2 +1 ;/* left */
@@ -86,6 +74,23 @@ void *prio_queue_get(struct prio_queue *queue)swap (queue, child, ix); } +} + +void *prio_queue_get (struct prio_queue *queue) +{ +void *result; + +if (!queue->nr) +return NULL ; +if (!queue->compare) +return queue->array[--queue->nr].data;/* LIFO */ + + result = queue->array[0 ].data; +if (!--queue->nr) +return result; + + queue->array[0 ] = queue->array[queue->nr]; +sift_down_root (queue);return result; }
@@ -97,3 +102,17 @@ void *prio_queue_peek(struct prio_queue *queue)return queue->array[queue->nr -1 ].data;return queue->array[0 ].data; } + +void prio_queue_replace (struct prio_queue *queue,void *thing) +{ +if (!queue->nr) { +prio_queue_put (queue, thing); + }else if (!queue->compare) { + queue->array[queue->nr -1 ].ctr = queue->insertion_ctr++; + queue->array[queue->nr -1 ].data = thing; + }else { + queue->array[0 ].ctr = queue->insertion_ctr++; + queue->array[0 ].data = thing; +sift_down_root (queue); + } +}
prio-queue.h +8 -0
@@ -52,6 +52,14 @@ void *prio_queue_get(struct prio_queue *);*/ void *prio_queue_peek (struct prio_queue *); +/* +* Replace the "thing" that compares the smallest with a new "thing", +* like prio_queue_get()+prio_queue_put() would do, but in a more +* efficient way. Does the same as prio_queue_put() if the queue is +* empty. +*/ +void prio_queue_replace (struct prio_queue *queue,void *thing); +void clear_prio_queue (struct prio_queue *);/* Reverse the LIFO elements */
t/unit-tests/u-prio-queue.c +23 -0
@@ -13,6 +13,7 @@ static int intcmp(const void *va, const void *vb, void *data UNUSED)#define STACK -3#define GET -4#define REVERSE -5 +#define REPLACE -6static int show (int *v) {
@@ -51,6 +52,15 @@ static void test_prio_queue(int *input, size_t input_size,case REVERSE :prio_queue_reverse (&pq);break ; +case REPLACE : + peek =prio_queue_peek (&pq); +cl_assert (i +1 < input_size); +cl_assert (input[i +1 ] >=0 ); +cl_assert (j < result_size); +cl_assert_equal_i (result[j],show (peek)); + j++; +prio_queue_replace (&pq, &input[++i]); +break ;default :prio_queue_put (&pq, &input[i]);break ;
@@ -81,6 +91,13 @@ void test_prio_queue__empty(void) ((int []){ 1, 2, MISSING, 1, 2, MISSING })); } +void test_prio_queue__replace (void ) +{ +TEST_INPUT (((int []){REPLACE ,6 ,2 ,4 ,REPLACE ,5 ,7 ,GET , +REPLACE ,1 ,DUMP }), + ((int []){MISSING ,2 ,4 ,5 ,1 ,6 ,7 })); +} +void test_prio_queue__stack (void ) { TEST_INPUT(((int []){ STACK, 8, 1, 5, 4, 6, 2, 3, DUMP }),
@@ -92,3 +109,9 @@ void test_prio_queue__reverse_stack(void)TEST_INPUT (((int []){STACK ,1 ,2 ,3 ,4 ,5 ,6 ,REVERSE ,DUMP }), ((int []){1 ,2 ,3 ,4 ,5 ,6 })); } + +void test_prio_queue__replace_stack (void ) +{ +TEST_INPUT (((int []){STACK ,8 ,1 ,5 ,REPLACE ,4 ,6 ,2 ,3 ,DUMP }), + ((int []){5 ,3 ,2 ,6 ,4 ,1 ,8 })); +}
Signature · 1 line
2.50.1
Re: [PATCH 2/3] prio-queue: add prio_queue_replace()
Quoted 6 lines · René Scharfe
Add a function to replace the top element of the queue that basically does the same as
prio_queue_get()followed byprio_queue_put(), but without the work byprio_queue_get()to rebalance the heap. It can be used to optimize loops that get one element and then immediately add another one. That's common e.g., with commit history traversal, where we get out a commit and then put in its parents.
Hmm. But surely we still need to rebalance the heap after adding an element? And indeed, we still call the new sift_down_root() function.
But I guess we are getting away without the "bubble up" operation that put would do? So we are doing half as much work (but still big-O the same)?
-Peff
Re: [PATCH 2/3] prio-queue: add prio_queue_replace()
Quoted 11 lines · Jeff King
Quoted 6 lines · René Scharfe
Add a function to replace the top element of the queue that basically does the same as
prio_queue_get()followed byprio_queue_put(), but without the work byprio_queue_get()to rebalance the heap. It can be used to optimize loops that get one element and then immediately add another one. That's common e.g., with commit history traversal, where we get out a commit and then put in its parents.Hmm. But surely we still need to rebalance the heap after adding an element? And indeed, we still call the new
sift_down_root()function.
Yes.
Quoted 3 lines
But I guess we are getting away without the "bubble up" operation that put would do? So we are doing half as much work (but still big-O the same)?
Yes.
I thought about building this optimization into prio_queue_get(), but that would require prio_queue_peek() and prio_queue_put() to be adjusted as well and all prio_queue users would have to be either made aware of the not-fully-heapified state, or prevented from accessing prio_queue properties like .nr and .array. Adding a new function seemed like the simplest and safest way for now.
René
Re: [PATCH 2/3] prio-queue: add prio_queue_replace()
Quoted 19 lines · René Scharfe
Quoted 11 lines · Jeff King
Quoted 6 lines · René Scharfe
Add a function to replace the top element of the queue that basically does the same as
prio_queue_get()followed byprio_queue_put(), but without the work byprio_queue_get()to rebalance the heap. It can be used to optimize loops that get one element and then immediately add another one. That's common e.g., with commit history traversal, where we get out a commit and then put in its parents.Hmm. But surely we still need to rebalance the heap after adding an element? And indeed, we still call the new
sift_down_root()function.Yes.
Quoted 3 lines
But I guess we are getting away without the "bubble up" operation that put would do? So we are doing half as much work (but still big-O the same)?
Quoted 7 lines
Yes.
I thought about building this optimization into
prio_queue_get(), but that would requireprio_queue_peek()andprio_queue_put()to be adjusted as well and allprio_queueusers would have to be either made aware of the not-fully-heapified state, or prevented from accessingprio_queueproperties like .nr and .array.
Here's what that would like like. .nr and .array elements are kept consistent at all times, but the root item is not in heap order after a prio_queue_get(). That's good enough to enumerate all prio_queue items like commit-reach.c::queue_has_nonstale() or negotiator/skipping.c::push_parent() do.
Not sure what other weird patterns people might come up with that require touching the innards of a prio_queue directly. I don't even understand why negotiator/skipping.c::push_parent() does a linear search for each parent -- isn't that expensive? Setting an object flag on prio_queue_put() and clearing it on prio_queue_get() or a using a commit_slab seem to be better options from a very cursory glance.
Anyway, here's what doing prio_queue_replace() automatically could look like. I almost talked myself into using it now. Any objections, ideas on how to make it safer or clearer, other thoughts?
René
--- prio-queue.c | 52 +++++++++++++++++++++++++++++++++++++++------------- prio-queue.h | 1 + 2 files changed, 40 insertions(+), 13 deletions(-)
prio-queue.c +39 -13
@@ -34,12 +34,46 @@ void clear_prio_queue(struct prio_queue *queue) queue->nr =0 ; queue->alloc =0 ; queue->insertion_ctr =0 ; + queue->sift_down_root_pending = false; +} + +static void sift_down_root (struct prio_queue *queue) +{ +size_t ix, child; + +/* Push down the one at the root */ +for (ix =0 ; ix *2 +1 < queue->nr; ix = child) { + child = ix *2 +1 ;/* left */ +if (child +1 < queue->nr && +compare (queue, child, child +1 ) >=0 ) + child++;/* use right child */ + +if (compare (queue, ix, child) <=0 ) +break ; + +swap (queue, child, ix); + } + queue->sift_down_root_pending = false; }void prio_queue_put (struct prio_queue *queue,void *thing) {size_t ix, parent; +if (queue->sift_down_root_pending) { +/* +* Restore the original heap size. The last item is +* still in the right place. +*/ + queue->nr++; + +/* Now fill the hole at the root with the new item. */ + queue->array[0 ].ctr = queue->insertion_ctr++; + queue->array[0 ].data = thing; +sift_down_root (queue); +return ; + } +/* Append at the end */ ALLOC_GROW (queue->array, queue->nr +1 , queue->alloc); queue->array[queue->nr].ctr = queue->insertion_ctr++;
@@ -61,31 +95,21 @@ void prio_queue_put(struct prio_queue *queue, void *thing)void *prio_queue_get (struct prio_queue *queue) {void *result; -size_t ix, child;if (!queue->nr)return NULL ;if (!queue->compare)return queue->array[--queue->nr].data;/* LIFO */ +if (queue->sift_down_root_pending) +sift_down_root (queue); result = queue->array[0 ].data;if (!--queue->nr)return result; queue->array[0 ] = queue->array[queue->nr]; -/* Push down the one at the root */ -for (ix =0 ; ix *2 +1 < queue->nr; ix = child) { - child = ix *2 +1 ;/* left */ -if (child +1 < queue->nr && -compare (queue, child, child +1 ) >=0 ) - child++;/* use right child */ - -if (compare (queue, ix, child) <=0 ) -break ; - -swap (queue, child, ix); - } + queue->sift_down_root_pending = true;return result; }
@@ -95,5 +119,7 @@ void *prio_queue_peek(struct prio_queue *queue)return NULL ;if (!queue->compare)return queue->array[queue->nr -1 ].data; +if (queue->sift_down_root_pending) +sift_down_root (queue);return queue->array[0 ].data; }
prio-queue.h +1 -0
@@ -32,6 +32,7 @@ struct prio_queue {void *cb_data;size_t alloc, nr;struct prio_queue_entry *array; +bool sift_down_root_pending; };/*
Signature · 1 line
2.50.1
Re: [PATCH 2/3] prio-queue: add prio_queue_replace()
Quoted 11 lines · René Scharfe
Quoted 5 lines
I thought about building this optimization into
prio_queue_get(), but that would requireprio_queue_peek()andprio_queue_put()to be adjusted as well and allprio_queueusers would have to be either made aware of the not-fully-heapified state, or prevented from accessingprio_queueproperties like .nr and .array.Here's what that would like like. .nr and .array elements are kept consistent at all times, but the root item is not in heap order after a
prio_queue_get(). That's good enough to enumerate allprio_queueitems like commit-reach.c::queue_has_nonstale() or negotiator/skipping.c::push_parent() do.
Hmm, I agree that _probably_ we'd be fine as long as .nr and .array were always consistent. It does make me feel a bit dirty to violate the heap property in a way that callers can see. I guess the argument in favor of it would be:
- if you are directly walking over all elements, then almost all ordering is out the window. Yes, the root item is supposed to be the min, but in a heap the rest of the elements won't be sorted.
- if you really want things in order from a heap, you'll be calling the get() or peek() accessors. And that gives us an opportunity to lazily put things in order.
I guess one alternative would be to make the array private and require some kind of foreach accessor. True struct-field privacy in C sucks. You have to hide behind a pointer, so there's runtime cost, plus iteration requires a clunky callback rather than a loop. I guess we could call it "array_" or something, and provide a foreach macro.
I dunno. I'm on the fence.
-Peff
PATCH 3/3 commit: use prio_queue_replace() in pop_most_recent_commit()
In reply to René ScharfeOptimize pop_most_recent_commit() by adding the first parent using the more efficient prio_queue_peek() and prio_queue_replace() instead of prio_queue_get() and prio_queue_put().
On my machine this neutralizes the performance hit it took in Git's own repository when we converted it to prio_queue two patches ago (git_pq):
$ hyperfine -w3 -L git ./git_2.50.1,./git_pq,./git '{git} rev-parse :/^Initial.revision'
Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
Time (mean ± σ): 1.073 s ± 0.003 s [User: 1.053 s, System: 0.019 s]
Range (min … max): 1.069 s … 1.078 s 10 runsBenchmark 2: ./git_pq rev-parse :/^Initial.revision
Time (mean ± σ): 1.077 s ± 0.002 s [User: 1.057 s, System: 0.018 s]
Range (min … max): 1.072 s … 1.079 s 10 runsBenchmark 3: ./git rev-parse :/^Initial.revision
Time (mean ± σ): 1.069 s ± 0.003 s [User: 1.049 s, System: 0.018 s]
Range (min … max): 1.065 s … 1.074 s 10 runs Summary
./git rev-parse :/^Initial.revision ran
1.00 ± 0.00 times faster than ./git_2.50.1 rev-parse :/^Initial.revision 1.01 ± 0.00 times faster than ./git_pq rev-parse :/^Initial.revision
--- commit.c | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-)
commit.c +9 -2
@@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =prio_queue_get (queue); +struct commit *ret =prio_queue_peek (queue); +int delete_pending =1 ;struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -prio_queue_put (queue, commit); +if (delete_pending) +prio_queue_replace (queue, commit); +else +prio_queue_put (queue, commit); + delete_pending =0 ; } parents = parents->next; } +if (delete_pending) +prio_queue_get (queue);return ret; }
Signature · 1 line
2.50.1
Re: [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()
Quoted 6 lines · René Scharfe
Optimize
pop_most_recent_commit()by adding the first parent using the more efficientprio_queue_peek()andprio_queue_replace()instead ofprio_queue_get()andprio_queue_put().On my machine this neutralizes the performance hit it took in Git's own repository when we converted it to
prio_queuetwo patches ago (git_pq):
Given that our history has more merges than other projects, and the _replace() optimization would help primarily single-strand-of-pearls (and the first parent of a merge), that result is very good.
commit.c void commit_list_sort_by_date(struct commit_list **list) · line 746
Quoted 11 lines
commit.c +2
-1@@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =prio_queue_get (queue); +struct commit *ret =prio_queue_peek (queue); +int delete_pending =1 ;
Briefly I was puzzled by the name (I would have called first-parent since the logic was "we treat first parent specially by using replace instead of get/put"), but the variable signals "instead of get to remove the item from the queue, we just peeked, so we need to remove it later" with its name, which is understandable.
Quoted 19 lines
commit.c +7
-1struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -prio_queue_put (queue, commit); +if (delete_pending) +prio_queue_replace (queue, commit); +else +prio_queue_put (queue, commit); + delete_pending =0 ; } parents = parents->next; } +if (delete_pending) +prio_queue_get (queue);return ret; }
Re: [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()
Quoted 11 lines · Junio C Hamano
Quoted 9 lines · René Scharfe
commit.c +0
-1@@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =prio_queue_get (queue);
Quoted 8 lines
commit.c void commit_list_sort_by_date(struct commit_list **list) · line 746
Quoted 2 lines
commit.c +2
-0+struct commit *ret =prio_queue_peek (queue); +int delete_pending =1 ;Briefly I was puzzled by the name (I would have called first-parent since the logic was "we treat first parent specially by using replace instead of get/put"), but the variable signals "instead of get to remove the item from the queue, we just peeked, so we need to remove it later" with its name, which is understandable.
Indeed, we're just interested in the removal part of prio_queue_get() here, as we have done the cheap half (the peeking) already. We don't have a prio_queue_delete(). Adding one would perhaps add some clarity here, but also widen the interface and probably not bring much of a performance gain.
So perhaps calling the variable get_pending like the prio_queue_get() that we end up invoking would reduce the initial puzzlement?
Quoted 20 lines
Quoted 20 lines
commit.c +7
-1struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -prio_queue_put (queue, commit); +if (delete_pending) +prio_queue_replace (queue, commit); +else +prio_queue_put (queue, commit); + delete_pending =0 ; } parents = parents->next; } +if (delete_pending) +prio_queue_get (queue);return ret; }
Quoted 3 lines · René Scharfe
Use
prio_queueto improve worst-case performance at the cost of slightly worse best-case performance. Then add and useprio_queue_replace()to recover that loss.
Would change in the tiebreaking behaviour (aka sort stability) also a cost of this change, as this swaps use of sorted linearly linked list with priority queue?
Quoted 9 lines · Junio C Hamano
Quoted 3 lines · René Scharfe
Use
prio_queueto improve worst-case performance at the cost of slightly worse best-case performance. Then add and useprio_queue_replace()to recover that loss.Would change in the tiebreaking behaviour (aka sort stability) also a cost of this change, as this swaps use of sorted linearly linked list with priority queue?
The prio_queue uses insertion order as a tie-breaker for stability (with earlier entries coming first). For building the initial queue from the list, I think that is obviously fine (we feed them in sorted order, which the prio queue will retain). For inserting while we walk the list, we'll produce the same results as long as the original code always inserted new entries after existing ones (in the case of a tie on commit date, that is).
And I think that is the case, since commit_list_insert_by_date() does this:
while ((p = *pp) != NULL) {
if (p->item->date < item->date) {
break;
}
pp = &p->next;
}
return commit_list_insert(item, pp);So we only insert once we have found an item in the list _after_ us, retaining the same order.
But hopefully somebody can double check my logic, as it is quite possible I got something reversed above. ;)
-Peff
Quoted 31 lines · Jeff King
Quoted 9 lines · Junio C Hamano
Quoted 3 lines · René Scharfe
Use
prio_queueto improve worst-case performance at the cost of slightly worse best-case performance. Then add and useprio_queue_replace()to recover that loss.Would change in the tiebreaking behaviour (aka sort stability) also a cost of this change, as this swaps use of sorted linearly linked list with priority queue?
The
prio_queueuses insertion order as a tie-breaker for stability (with earlier entries coming first). For building the initial queue from the list, I think that is obviously fine (we feed them in sorted order, which the prio queue will retain). For inserting while we walk the list, we'll produce the same results as long as the original code always inserted new entries after existing ones (in the case of a tie on commit date, that is).And I think that is the case, since
commit_list_insert_by_date()does this:while ((p = *pp) != NULL) { if (p->item->date < item->date) { break; } pp = &p->next; } return commit_list_insert(item, pp);
Quoted 5 lines
So we only insert once we have found an item in the list _after_ us, retaining the same order.
But hopefully somebody can double check my logic, as it is quite possible I got something reversed above. ;)
Yes, commit_list_insert_by_date() is stable, as it inserts commits after ones with the same date. Items are popped from the top, so this ensures FIFO behavior for commits with the same date.
prio_queue ensures stability using an ID and favors lower ones, so it provides the same order.
We should add unit tests for that, no?
René
Quoted 8 lines · René Scharfe
Yes,
commit_list_insert_by_date()is stable, as it inserts commits after ones with the same date. Items are popped from the top, so this ensures FIFO behavior for commits with the same date.
prio_queueensures stability using an ID and favors lower ones, so it provides the same order.We should add unit tests for that, no?
Probably wouldn't hurt to do so, but I don't think doing so needs to hold up your series.
-Peff
Quoted 8 lines · Jeff King
Quoted 6 lines · Junio C Hamano
Quoted 3 lines · René Scharfe
Use
prio_queueto improve worst-case performance at the cost of slightly worse best-case performance. Then add and useprio_queue_replace()to recover that loss.
Quoted 8 lines
Quoted 3 lines
Would change in the tiebreaking behaviour (aka sort stability) also a cost of this change, as this swaps use of sorted linearly linked list with priority queue?
The
prio_queueuses insertion order as a tie-breaker for stability (with earlier entries coming first). For building the initial queue from the list, I think that is obviously fine (we feed them in sorted order, which the prio queue will retain).
OK, then everything looks great. Thanks.
v2 cover commit: convert pop_most_recent_commit() to prio_queue
In reply to René ScharfeUse prio_queue to improve worst-case performance at the cost of slightly worse best-case performance. Then add and use prio_queue_replace() to recover that loss.
Changes since v2:
- Mention that a prio_queue improves performance for merge-heavy histories in the commit message.
- Add the new perf script to Meson build file.
- Mention which kind of history we are aiming for and show its shape in a comment in the perf script.
- Remove unnecessary quotes and use single quotes for the perf test code.
- Rename the variable delete_pending to get_pending to align it with the concrete function prio_queue_get() instead of referring to the abstract concept of deletion, to improve readability.
commit: convert pop_most_recent_commit() to prio_queue
prio-queue: add prio_queue_replace()
commit: use prio_queue_replace() in pop_most_recent_commit()
commit.c | 14 ++++-- commit.h | 8 ++-- fetch-pack.c | 13 +++--- object-name.c | 10 ++--- prio-queue.c | 45 ++++++++++++++------ prio-queue.h | 8 ++++ t/meson.build | 1 + t/perf/p1501-rev-parse-oneline.sh | 71 +++++++++++++++++++++++++++++++ t/unit-tests/u-prio-queue.c | 23 ++++++++++ walker.c | 11 +++-- 10 files changed, 170 insertions(+), 34 deletions(-) create mode 100755 t/perf/p1501-rev-parse-oneline.sh
Range-diff against v1:
1: d9c0d13801 ! 1: 5bff885d0f commit: convert pop_most_recent_commit() to prio_queue
@@ Metadata
## Commit message ##
commit: convert pop_most_recent_commit() to prio_queue
- pop_most_recent_commit() calls commit_list_insert_by_date(), which and
- is itself called in a loop, which can lead to quadratic complexity.
- Replace the commit_list with a prio_queue to ensure logarithmic worst
- case complexity and convert all three users.
+ pop_most_recent_commit() calls commit_list_insert_by_date() for parent
+ commits, which is itself called in a loop. This can lead to quadratic
+ complexity if there are many merges. Replace the commit_list with a
+ prio_queue to ensure logarithmic worst case complexity and convert all
+ three users.
Add a performance test that exercises one of them using a pathological
history that consists of 50% merges and 50% root commits to demonstrate
@@ object-name.c: static enum get_oid_result get_oid_with_context_1(struct reposito
free_commit_list(list);
+ ## t/meson.build ##
+@@ t/meson.build: benchmarks = [
+ 'perf/p1450-fsck.sh',
+ 'perf/p1451-fsck-skip-list.sh',
+ 'perf/p1500-graph-walks.sh',
++ 'perf/p1501-rev-parse-oneline.sh',
+ 'perf/p2000-sparse-operations.sh',
+ 'perf/p3400-rebase.sh',
+ 'perf/p3404-rebase-interactive.sh',
+
## t/perf/p1501-rev-parse-oneline.sh (new) ##
@@
+#!/bin/sh
@@ t/perf/p1501-rev-parse-oneline.sh (new)
+
+test_perf_fresh_repo
+
++#
++# Creates lots of merges to make history traversal costly. In
++# particular it creates 2^($max_level-1)-1 2-way merges on top of
++# 2^($max_level-1) root commits. E.g., the commit history looks like
++# this for a $max_level of 3:
++#
++# _1_
++# / \
++# 2 3
++# / \ / \
++# 4 5 6 7
++#
++# The numbers are the fast-import marks, which also are the commit
++# messages. 1 is the HEAD commit and a merge, 2 and 3 are also merges,
++# 4-7 are the root commits.
++#
+build_history () {
+ local max_level="$1" &&
+ local level="${2:-1}" &&
@@ t/perf/p1501-rev-parse-oneline.sh (new)
+ sed -n -e "s/^.* //p" -e "q" <commits >needle
+'
+
-+test_perf "rev-parse ':/$(cat needle)'" "
-+ git rev-parse ':/$(cat needle)' >actual
-+"
++test_perf "rev-parse :/$(cat needle)" '
++ git rev-parse :/$(cat needle) >actual
++'
+
+test_expect_success 'verify result' '
+ test_cmp expect actual
2: a4011d850c = 2: a2e57ca443 prio-queue: add prio_queue_replace()
3: dc535e8b64 ! 3: 1cbea38524 commit: use prio_queue_replace() in pop_most_recent_commit()
@@ commit.c: void commit_list_sort_by_date(struct commit_list **list)
{
- struct commit *ret = prio_queue_get(queue);
+ struct commit *ret = prio_queue_peek(queue);
-+ int delete_pending = 1;
++ int get_pending = 1;
struct commit_list *parents = ret->parents;
while (parents) {
@@ commit.c: void commit_list_sort_by_date(struct commit_list **list)
if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
commit->object.flags |= mark;
- prio_queue_put(queue, commit);
-+ if (delete_pending)
++ if (get_pending)
+ prio_queue_replace(queue, commit);
+ else
+ prio_queue_put(queue, commit);
-+ delete_pending = 0;
++ get_pending = 0;
}
parents = parents->next;
}
-+ if (delete_pending)
++ if (get_pending)
+ prio_queue_get(queue);
return ret;
}Signature · 1 line
2.50.1
PATCH v2 1/3 commit: convert pop_most_recent_commit() to prio_queue
pop_most_recent_commit() calls commit_list_insert_by_date() for parent commits, which is itself called in a loop. This can lead to quadratic complexity if there are many merges. Replace the commit_list with a prio_queue to ensure logarithmic worst case complexity and convert all three users.
Add a performance test that exercises one of them using a pathological history that consists of 50% merges and 50% root commits to demonstrate the speedup:
Test v2.50.1 HEAD
----------------------------------------------------------------------
1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%
Alas, sane histories don't benefit from the conversion much, and traversing Git's own history takes a 1% performance hit on my machine:
$ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'
Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]
Range (min … max): 1.067 s … 1.078 s 10 runsBenchmark 2: ./git rev-parse :/^Initial.revision
Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]
Range (min … max): 1.074 s … 1.083 s 10 runs Summary
./git_2.50.1 rev-parse :/^Initial.revision ran
1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision
--- commit.c | 7 +-- commit.h | 8 ++-- fetch-pack.c | 13 +++--- object-name.c | 10 ++--- t/meson.build | 1 + t/perf/p1501-rev-parse-oneline.sh | 71 +++++++++++++++++++++++++++++++ walker.c | 11 +++-- 7 files changed, 100 insertions(+), 21 deletions(-) create mode 100755 t/perf/p1501-rev-parse-oneline.sh
commit.c +4 -3
@@ -31,6 +31,7 @@#include "parse.h" #include "object-file.h" #include "object-file-convert.h" +#include "prio-queue.h" static struct commit_extra_header *read_commit_extra_header_lines (const char *buf,size_t len,const char **);
@@ -739,17 +740,17 @@ void commit_list_sort_by_date(struct commit_list **list)commit_list_sort (list, commit_list_compare_by_date); } -struct commit *pop_most_recent_commit (struct commit_list **list, +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =pop_commit (list); +struct commit *ret =prio_queue_get (queue);struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -commit_list_insert_by_date (commit, list); +prio_queue_put (queue, commit); } parents = parents->next; }
commit.h +4 -4
@@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,const char *skip_blank_lines (const char *msg); -/** Removes the first commit from a list sorted by date, and adds all -* of its parents. -**/ -struct commit *pop_most_recent_commit (struct commit_list **list, +struct prio_queue ; + +/* Removes the first commit from a prio_queue and adds its parents. */ +struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark);struct commit *pop_commit (struct commit_list **stack);
fetch-pack.c +8 -5
@@ -34,6 +34,7 @@#include "commit-graph.h" #include "sigchain.h" #include "mergesort.h" +#include "prio-queue.h" static int transfer_unpack_limit =-1 ;static int fetch_unpack_limit =-1 ;
@@ -601,7 +602,7 @@ static int find_common(struct fetch_negotiator *negotiator,return count ? retval :0 ; } -static struct commit_list *complete; +static struct prio_queue complete = { compare_commits_by_commit_date };static int mark_complete (const struct object_id *oid) {
@@ -609,7 +610,7 @@ static int mark_complete(const struct object_id *oid)if (commit && !(commit->object.flags &COMPLETE )) { commit->object.flags |=COMPLETE ; -commit_list_insert (commit, &complete); +prio_queue_put (&complete, commit); }return 0 ; }
@@ -626,9 +627,12 @@ static int mark_complete_oid(const char *refname UNUSED,static void mark_recent_complete_commits (struct fetch_pack_args *args,timestamp_t cutoff) { -while (complete && cutoff <= complete->item->date) { +while (complete.nr) { +struct commit *item =prio_queue_peek (&complete); +if (item->date < cutoff) +break ;print_verbose (args,_ ("Marking %s as complete" ), -oid_to_hex (&complete->item->object.oid)); +oid_to_hex (&item->object.oid));pop_most_recent_commit (&complete,COMPLETE ); } }
@@ -798,7 +802,6 @@ static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator,refs_for_each_rawref (get_main_ref_store (the_repository), mark_complete_oid,NULL );for_each_cached_alternate (NULL , mark_alternate_complete); -commit_list_sort_by_date (&complete);if (cutoff)mark_recent_complete_commits (args, cutoff); }
object-name.c +5 -5
@@ -28,6 +28,7 @@#include "commit-reach.h" #include "date.h" #include "object-file-convert.h" +#include "prio-queue.h" static int get_oid_oneline (struct repository *r,const char *,struct object_id *,const struct commit_list *);
@@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r, const char *prefix, struct object_id *oid, const struct commit_list *list) { - struct commit_list *copy = NULL, **copy_tail = © + struct prio_queue copy = { compare_commits_by_commit_date };const struct commit_list *l;int found =0 ;int negative =0 ;
@@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,for (l = list; l; l = l->next) { l->item->object.flags |=ONELINE_SEEN ; - copy_tail = &commit_list_insert (l->item, copy_tail)->next; +prio_queue_put (©, l->item); } -while (copy) { +while (copy.nr) {const char *p, *buf;struct commit *commit;int matches;
@@ -1507,7 +1508,7 @@ static int get_oid_oneline(struct repository *r,regfree (®ex);for (l = list; l; l = l->next)clear_commit_marks (l->item,ONELINE_SEEN ); -free_commit_list (copy); +clear_prio_queue (©);return found ?0 :-1 ; }
@@ -2061,7 +2062,6 @@ static enum get_oid_result get_oid_with_context_1(struct repository *repo, cb.list = &list;refs_for_each_ref (get_main_ref_store (repo), handle_one_ref, &cb);refs_head_ref (get_main_ref_store (repo), handle_one_ref, &cb); -commit_list_sort_by_date (&list); ret =get_oid_oneline (repo, name +2 , oid, list);free_commit_list (list);
t/meson.build +1 -0
@@ -1116,6 +1116,7 @@ benchmarks = [ 'perf/p1450-fsck.sh', 'perf/p1451-fsck-skip-list.sh', 'perf/p1500-graph-walks.sh', + 'perf/p1501-rev-parse-oneline.sh', 'perf/p2000-sparse-operations.sh', 'perf/p3400-rebase.sh', 'perf/p3404-rebase-interactive.sh',
t/perf/p1501-rev-parse-oneline.sh new file +71 -0
71 lines not on this page · raw message
walker.c +7 -4
@@ -14,6 +14,7 @@#include "blob.h" #include "refs.h" #include "progress.h" +#include "prio-queue.h" static struct object_id current_commit_oid;
@@ -78,7 +79,7 @@ static int process_tree(struct walker *walker, struct tree *tree)#define SEEN (1U << 1)#define TO_SCAN (1U << 2) -static struct commit_list *complete =NULL ; +static struct prio_queue complete = { compare_commits_by_commit_date };static int process_commit (struct walker *walker,struct commit *commit) {
@@ -87,7 +88,10 @@ static int process_commit(struct walker *walker, struct commit *commit)if (repo_parse_commit (the_repository, commit))return -1 ; -while (complete && complete->item->date >= commit->date) { +while (complete.nr) { +struct commit *item =prio_queue_peek (&complete); +if (item->date < commit->date) +break ;pop_most_recent_commit (&complete,COMPLETE ); }
@@ -233,7 +237,7 @@ static int mark_complete(const char *path UNUSED,if (commit) { commit->object.flags |=COMPLETE ; -commit_list_insert (commit, &complete); +prio_queue_put (&complete, commit); }return 0 ; }
@@ -302,7 +306,6 @@ int walker_fetch(struct walker *walker, int targets, char **target,if (!walker->get_recover) {refs_for_each_ref (get_main_ref_store (the_repository), mark_complete,NULL ); -commit_list_sort_by_date (&complete); }for (i =0 ; i < targets; i++) {
Signature · 1 line
2.50.1
Quoted 7 lines · René Scharfe
t/perf/p1501-rev-parse-oneline.sh new file +6
-0+# +# Creates lots of merges to make history traversal costly. In +# particular it creates 2^($max_level-1)-1 2-way merges on top of +# 2^($max_level-1) root commits. E.g., the commit history looks like +# this for a $max_level of 3: +#
t/perf/p1501-rev-parse-oneline.sh line 24
Quoted 10 lines
t/perf/p1501-rev-parse-oneline.sh new file +10
-0+# _1_ +# / \ +# 2 3 +# / \ / \ +# 4 5 6 7 +# +# The numbers are the fast-import marks, which also are the commit +# messages. 1 is the HEAD commit and a merge, 2 and 3 are also merges, +# 4-7 are the root commits. +#
I feel that the reason there's no significant performance improvement is probably because mostly we are using the priority queue to sort O(siblings) nodes. For example, in this case, the most time-consuming operation is when the priority queue or commit list contains 4 and 5, and we then need to insert 6 and 7.
Assuming the maximum number of siblings is W and the number of nodes is N, the time complexity with a commit list is O(W² × N), while using a priority queue gives O(W log W × N). Perhaps in many projects, W isn't particularly large, which results in the performance improvement not being very significant.
- Lidong
Quoted 24 lines · Lidong Yan
Quoted 7 lines · René Scharfe
t/perf/p1501-rev-parse-oneline.sh new file +6
-0+# +# Creates lots of merges to make history traversal costly. In +# particular it creates 2^($max_level-1)-1 2-way merges on top of +# 2^($max_level-1) root commits. E.g., the commit history looks like +# this for a $max_level of 3: +#t/perf/p1501-rev-parse-oneline.sh line 24
Quoted 10 lines
t/perf/p1501-rev-parse-oneline.sh new file +10
-0+# _1_ +# / \ +# 2 3 +# / \ / \ +# 4 5 6 7 +# +# The numbers are the fast-import marks, which also are the commit +# messages. 1 is the HEAD commit and a merge, 2 and 3 are also merges, +# 4-7 are the root commits. +#I feel that the reason there's no significant performance improvement is probably because mostly we are using the priority queue to sort O(siblings) nodes. For example, in this case, the most time-consuming operation is when the priority queue or commit list contains 4 and 5, and we then need to insert 6 and 7.
Quoted 4 lines
Assuming the maximum number of siblings is W and the number of nodes is N, the time complexity with a commit list is O(W² × N), while using a priority queue gives O(W log W × N). Perhaps in many projects, W isn't particularly large, which results in the performance improvement not being very significant.
Kinda. While traversing the history we take a commit from to the commit_list or prio_queue and put back its parents. For single-parent commits this sequence keeps the number of stored items the same. Merges increase that number.
We add and retrieve each commit in the (relevant part of) history. That takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for the prio_queue, where N is the length of the list.
So the best-case history is a string of single-parent commits, keeping only a single item on the list/queue throughout. That requires no sorting or heaping, making the additions and retrievals O(1). The overall complexity is then O(N) for both variants, N being the number of commits in the history.
Worst-case history might be a single merge of all commits -- a centipede or myriapod? With all commits on the sorted list we get a complexity of O(N²) for the traversal, and O(N log N) with a prio_queue.
René
Quoted 10 lines · René Scharfe
We add and retrieve each commit in the (relevant part of) history. That takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for the
prio_queue, where N is the length of the list.So the best-case history is a string of single-parent commits, keeping only a single item on the list/queue throughout. That requires no sorting or heaping, making the additions and retrievals O(1). The overall complexity is then O(N) for both variants, N being the number of commits in the history.
Quoted 3 lines
Worst-case history might be a single merge of all commits -- a centipede or myriapod? With all commits on the sorted list we get a complexity of O(N²) for the traversal, and O(N log N) with a
prio_queue.
In other words, for a typical two-parent merge, we peek the current one, "replace" it with its first parent and then do the usual "put and sift it down into place" for the second one.
I am wondering if there is a more optimization opportunity if we allowed "put more than one, and then sift all of them down into place". In other words, if I told the machinery:
I am doing this put. I promise I won't do get until I say "now I'll start doing get's, so you are free to delay your internal state maintenance and do so immediately before my next 'get'".
and did such put's a few times before I do a 'get', would there be a way to teach the machinery to take advantage of the promise?
In any case, it is very much welcome to speed up "describe" with a better data structure and algorithm. Will queue.
Thanks.
Quoted 24 lines · Junio C Hamano
Quoted 10 lines · René Scharfe
We add and retrieve each commit in the (relevant part of) history. That takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for the
prio_queue, where N is the length of the list.So the best-case history is a string of single-parent commits, keeping only a single item on the list/queue throughout. That requires no sorting or heaping, making the additions and retrievals O(1). The overall complexity is then O(N) for both variants, N being the number of commits in the history.
Quoted 3 lines
Worst-case history might be a single merge of all commits -- a centipede or myriapod? With all commits on the sorted list we get a complexity of O(N²) for the traversal, and O(N log N) with a
prio_queue.In other words, for a typical two-parent merge, we peek the current one, "replace" it with its first parent and then do the usual "put and sift it down into place" for the second one.
I am wondering if there is a more optimization opportunity if we allowed "put more than one, and then sift all of them down into place". In other words, if I told the machinery:
Quoted 6 lines
I am doing this put. I promise I won't do get until I say "now I'll start doing get's, so you are free to delay your internal state maintenance and do so immediately before my next 'get'".
and did such put's a few times before I do a 'get', would there be a way to teach the machinery to take advantage of the promise?
Well, we could reestablish the heap at a cost of O(N), which only pays off if it's less than the O(P log N) needed for regular puts of P parents, with N being the number of queue elements. This starts to lose once queues become too long -- just when an optimization would be most welcome. So it seems impractical.
We could replace our binary heap with an algorithm that has O(1) inserts, like a pairing heap, though.
René
PATCH v2 2/3 prio-queue: add prio_queue_replace()
In reply to René ScharfeAdd a function to replace the top element of the queue that basically does the same as prio_queue_get() followed by prio_queue_put(), but without the work by prio_queue_get() to rebalance the heap. It can be used to optimize loops that get one element and then immediately add another one. That's common e.g., with commit history traversal, where we get out a commit and then put in its parents.
--- prio-queue.c | 45 ++++++++++++++++++++++++++----------- prio-queue.h | 8 +++++++ t/unit-tests/u-prio-queue.c | 23 +++++++++++++++++++ 3 files changed, 63 insertions(+), 13 deletions(-)
prio-queue.c +32 -13
@@ -58,22 +58,10 @@ void prio_queue_put(struct prio_queue *queue, void *thing) } } -void *prio_queue_get (struct prio_queue *queue) +static void sift_down_root (struct prio_queue *queue) { -void *result;size_t ix, child; -if (!queue->nr) -return NULL ; -if (!queue->compare) -return queue->array[--queue->nr].data;/* LIFO */ - - result = queue->array[0 ].data; -if (!--queue->nr) -return result; - - queue->array[0 ] = queue->array[queue->nr]; -/* Push down the one at the root */ for (ix =0 ; ix *2 +1 < queue->nr; ix = child) { child = ix *2 +1 ;/* left */
@@ -86,6 +74,23 @@ void *prio_queue_get(struct prio_queue *queue)swap (queue, child, ix); } +} + +void *prio_queue_get (struct prio_queue *queue) +{ +void *result; + +if (!queue->nr) +return NULL ; +if (!queue->compare) +return queue->array[--queue->nr].data;/* LIFO */ + + result = queue->array[0 ].data; +if (!--queue->nr) +return result; + + queue->array[0 ] = queue->array[queue->nr]; +sift_down_root (queue);return result; }
@@ -97,3 +102,17 @@ void *prio_queue_peek(struct prio_queue *queue)return queue->array[queue->nr -1 ].data;return queue->array[0 ].data; } + +void prio_queue_replace (struct prio_queue *queue,void *thing) +{ +if (!queue->nr) { +prio_queue_put (queue, thing); + }else if (!queue->compare) { + queue->array[queue->nr -1 ].ctr = queue->insertion_ctr++; + queue->array[queue->nr -1 ].data = thing; + }else { + queue->array[0 ].ctr = queue->insertion_ctr++; + queue->array[0 ].data = thing; +sift_down_root (queue); + } +}
prio-queue.h +8 -0
@@ -52,6 +52,14 @@ void *prio_queue_get(struct prio_queue *);*/ void *prio_queue_peek (struct prio_queue *); +/* +* Replace the "thing" that compares the smallest with a new "thing", +* like prio_queue_get()+prio_queue_put() would do, but in a more +* efficient way. Does the same as prio_queue_put() if the queue is +* empty. +*/ +void prio_queue_replace (struct prio_queue *queue,void *thing); +void clear_prio_queue (struct prio_queue *);/* Reverse the LIFO elements */
t/unit-tests/u-prio-queue.c +23 -0
@@ -13,6 +13,7 @@ static int intcmp(const void *va, const void *vb, void *data UNUSED)#define STACK -3#define GET -4#define REVERSE -5 +#define REPLACE -6static int show (int *v) {
@@ -51,6 +52,15 @@ static void test_prio_queue(int *input, size_t input_size,case REVERSE :prio_queue_reverse (&pq);break ; +case REPLACE : + peek =prio_queue_peek (&pq); +cl_assert (i +1 < input_size); +cl_assert (input[i +1 ] >=0 ); +cl_assert (j < result_size); +cl_assert_equal_i (result[j],show (peek)); + j++; +prio_queue_replace (&pq, &input[++i]); +break ;default :prio_queue_put (&pq, &input[i]);break ;
@@ -81,6 +91,13 @@ void test_prio_queue__empty(void) ((int []){ 1, 2, MISSING, 1, 2, MISSING })); } +void test_prio_queue__replace (void ) +{ +TEST_INPUT (((int []){REPLACE ,6 ,2 ,4 ,REPLACE ,5 ,7 ,GET , +REPLACE ,1 ,DUMP }), + ((int []){MISSING ,2 ,4 ,5 ,1 ,6 ,7 })); +} +void test_prio_queue__stack (void ) { TEST_INPUT(((int []){ STACK, 8, 1, 5, 4, 6, 2, 3, DUMP }),
@@ -92,3 +109,9 @@ void test_prio_queue__reverse_stack(void)TEST_INPUT (((int []){STACK ,1 ,2 ,3 ,4 ,5 ,6 ,REVERSE ,DUMP }), ((int []){1 ,2 ,3 ,4 ,5 ,6 })); } + +void test_prio_queue__replace_stack (void ) +{ +TEST_INPUT (((int []){STACK ,8 ,1 ,5 ,REPLACE ,4 ,6 ,2 ,3 ,DUMP }), + ((int []){5 ,3 ,2 ,6 ,4 ,1 ,8 })); +}
Signature · 1 line
2.50.1
PATCH v2 3/3 commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0
In reply to René ScharfeOptimize pop_most_recent_commit() by adding the first parent using the more efficient prio_queue_peek() and prio_queue_replace() instead of prio_queue_get() and prio_queue_put().
On my machine this neutralizes the performance hit it took in Git's own repository when we converted it to prio_queue two patches ago (git_pq):
$ hyperfine -w3 -L git ./git_2.50.1,./git_pq,./git '{git} rev-parse :/^Initial.revision'
Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
Time (mean ± σ): 1.073 s ± 0.003 s [User: 1.053 s, System: 0.019 s]
Range (min … max): 1.069 s … 1.078 s 10 runsBenchmark 2: ./git_pq rev-parse :/^Initial.revision
Time (mean ± σ): 1.077 s ± 0.002 s [User: 1.057 s, System: 0.018 s]
Range (min … max): 1.072 s … 1.079 s 10 runsBenchmark 3: ./git rev-parse :/^Initial.revision
Time (mean ± σ): 1.069 s ± 0.003 s [User: 1.049 s, System: 0.018 s]
Range (min … max): 1.065 s … 1.074 s 10 runs Summary
./git rev-parse :/^Initial.revision ran
1.00 ± 0.00 times faster than ./git_2.50.1 rev-parse :/^Initial.revision 1.01 ± 0.00 times faster than ./git_pq rev-parse :/^Initial.revision
--- commit.c | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-)
commit.c +9 -2
@@ -743,17 +743,24 @@ void commit_list_sort_by_date(struct commit_list **list)struct commit *pop_most_recent_commit (struct prio_queue *queue,unsigned int mark) { -struct commit *ret =prio_queue_get (queue); +struct commit *ret =prio_queue_peek (queue); +int get_pending =1 ;struct commit_list *parents = ret->parents;while (parents) {struct commit *commit = parents->item;if (!repo_parse_commit (the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; -prio_queue_put (queue, commit); +if (get_pending) +prio_queue_replace (queue, commit); +else +prio_queue_put (queue, commit); + get_pending =0 ; } parents = parents->next; } +if (get_pending) +prio_queue_get (queue);return ret; }
Signature · 1 line
2.50.1
Re: [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0
Hi René,
Quoted 5 lines · René Scharfe
Optimize
pop_most_recent_commit()by adding the first parent using the more efficientprio_queue_peek()andprio_queue_replace()instead ofprio_queue_get()andprio_queue_put().[... clipped ...]
I noticed that v2 of this patch not only made it into next, but it also introduced a commit subject suffix (likely unintended?):
[PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0
Maybe that is something you want to look into?
Ciao,
Johannes
Re: [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0
Quoted 8 lines · Johannes Schindelin
Hi René,
Quoted 4 lines · René Scharfe
Optimize
pop_most_recent_commit()by adding the first parent using the more efficientprio_queue_peek()andprio_queue_replace()instead ofprio_queue_get()andprio_queue_put().
Quoted 8 lines
Quoted 1 line
[... clipped ...]
I noticed that v2 of this patch not only made it into
next, but it also introduced a commit subject suffix (likely unintended?):[PATCH v2 3/3] commit: use
prio_queue_replace()in pop_most_recent_commit(),MIME-Version: 1.0Maybe that is something you want to look into?
My bad, copy+paste error. A fixed version made it into master in the meantime. Sorry about that, and thanks a lot for correcting it, Junio!
René
Quoted 6 lines · René Scharfe
Use
prio_queueto improve worst-case performance at the cost of slightly worse best-case performance. Then add and useprio_queue_replace()to recover that loss.Changes since v2:
[...]
Thanks for fleshing out the test script. This version looks good to me.
-Peff
Quoted 16 lines · René Scharfe
Use
prio_queueto improve worst-case performance at the cost of slightly worse best-case performance. Then add and useprio_queue_replace()to recover that loss.Changes since v2:
- Mention that aprio_queueimproves performance for merge-heavy histories in the commit message.
- Add the new perf script to Meson build file.
- Mention which kind of history we are aiming for and show its shape in a comment in the perf script.
- Remove unnecessary quotes and use single quotes for the perf test code.
- Rename the variabledelete_pendingtoget_pendingto align it with the concrete functionprio_queue_get()instead of referring to the abstract concept of deletion, to improve readability.
Quoted 3 lines
commit: convert
pop_most_recent_commit()toprio_queue
prio-queue: addprio_queue_replace()
commit: useprio_queue_replace()inpop_most_recent_commit()
The patches in this series were picked up in the wrong order:
$ git log --topo-order --reverse --oneline -3 e436bc94f3 36554bf51a commit: convert pop_most_recent_commit() to prio_queue 304f06e0c0 commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0 e436bc94f3 prio-queue: add prio_queue_replace()
Note that the order of the second and third patches is reversed.
Since the second patch/third commit introduces a new function used by the third patch/second commit, this leads to build failure of 304f06e0c0:
CC commit.o
commit.c: In function ‘pop_most_recent_commit’:
commit.c:754:33: error: implicit declaration of function ‘prio_queue_replace’; did you mean ‘prio_queue_reverse’? [-Werror=implicit-function-declaration]
754 | prio_queue_replace(queue, commit);
| ^~~~~~~~~~~~~~~~~~
| prio_queue_reverse cc1: all warnings being treated as errors
make: *** [Makefile:2821: commit.o] Error 1
(And there's that MIME-Version thing at the end of 304f06e0c0's subject line as well.)
Quoted 4 lines · SZEDER Gábor
$ git log --topo-order --reverse --oneline -3 e436bc94f3 36554bf51a commit: convert pop_most_recent_commit() to prio_queue 304f06e0c0 commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0 e436bc94f3 prio-queue: add prio_queue_replace()
Funny. Thanks for spotting.