On 4/18/2018 10:31 AM, Jakub Narebski wrote:
Derrick Stolee <dstolee@xxxxxxxxxxxxx> writes:
Define compare_commits_by_gen_then_commit_date(), which uses generation
numbers as a primary comparison and commit date to break ties (or as a
comparison when both commits do not have computed generation numbers).
Since the commit-graph file is closed under reachability, we know that
all commits in the file have generation at most GENERATION_NUMBER_MAX
which is less than GENERATION_NUMBER_INFINITY.
This change does not affect the number of commits that are walked during
the execution of paint_down_to_common(), only the order that those
commits are inspected. In the case that commit dates violate topological
order (i.e. a parent is "newer" than a child), the previous code could
walk a commit twice: if a commit is reached with the PARENT1 bit, but
later is re-visited with the PARENT2 bit, then that PARENT2 bit must be
propagated to its parents. Using generation numbers avoids this extra
effort, even if it is somewhat rare.
Does it mean that it gives no measureable performance improvements for
typical test cases?
Not in this commit. When we add the `min_generation` parameter in a
later commit, we do get a significant performance boost (when we can
supply a non-zero value to `min_generation`).
This step of using generation numbers for the priority is important for
that commit, but on its own has limited value outside of the clock-skew
case mentioned above.
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
---
commit.c | 20 +++++++++++++++++++-
commit.h | 1 +
2 files changed, 20 insertions(+), 1 deletion(-)
diff --git a/commit.c b/commit.c
index 711f674c18..a44899c733 100644
--- a/commit.c
+++ b/commit.c
@@ -640,6 +640,24 @@ static int compare_commits_by_author_date(const void *a_, const void *b_,
return 0;
}
+int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
+{
+ const struct commit *a = a_, *b = b_;
+
+ /* newer commits first */
+ if (a->generation < b->generation)
+ return 1;
+ else if (a->generation > b->generation)
+ return -1;
+
+ /* use date as a heuristic when generataions are equal */
Very minor typo in above comment:
s/generataions/generations/
Good catch!
+ if (a->date < b->date)
+ return 1;
+ else if (a->date > b->date)
+ return -1;
+ return 0;
+}
+
int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)
{
const struct commit *a = a_, *b = b_;
@@ -789,7 +807,7 @@ static int queue_has_nonstale(struct prio_queue *queue)
/* all input commits in one and twos[] must have been parsed! */
static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
{
- struct prio_queue queue = { compare_commits_by_commit_date };
+ struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
struct commit_list *result = NULL;
int i;
diff --git a/commit.h b/commit.h
index aac3b8c56f..64436ff44e 100644
--- a/commit.h
+++ b/commit.h
@@ -341,6 +341,7 @@ extern int remove_signature(struct strbuf *buf);
extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc);
int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);
+int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused);
LAST_ARG_MUST_BE_NULL
extern int run_commit_hook(int editor_is_used, const char *index_file, const char *name, ...);
