Subject: Re: [PATCH v5 00/11] Compute and consume generation numbers

From: Jakub Narebski <[email-masked]>
Date: Thu, 03 May 2018 13:18:24 +0200

Derrick Stolee <[email-masked]> writes:

> Most of the changes from v4 are cosmetic, but there is one new commit:
>
> 	commit: use generation number in remove_redundant()
>
> Other changes are non-functional, but do clarify things.

I wonder if out perf framework in t/perf could help here to show
performance gains for the whole series.  Though it may not include
operations that are most helped by this one.

For commit-graph feature if would be nice, if feasible, to see changes
in performance from before version, checking both state where feature is
enabled to see the gains, and state where feature is disabled to see if
there are no performance regressions.

> Inter-diff from v4:

O.K., now to commenting on inter-changes.

> diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt
> index d9f2713efa..e1a883eb46 100644
> --- a/Documentation/technical/commit-graph.txt
> +++ b/Documentation/technical/commit-graph.txt
> @@ -125,9 +125,10 @@ Future Work
>    walks aware of generation numbers to gain the performance benefits they
>    enable. This will mostly be accomplished by swapping a commit-date-ordered
>    priority queue with one ordered by generation number. The following
> -  operation is an important candidate:
> +  operations are important candidates:
>
>      - 'log --topo-order'
> +    - 'tag --merged'
>
>  - Currently, parse_commit_gently() requires filling in the root tree
>    object for a commit. This passes through lookup_tree() and consequently

O.K., this is about discussion in "branch --contains / tag --merged
inconsistency" thread:

  https://public-inbox.org/git/[email-masked]/t/#u

> diff --git a/commit-graph.c b/commit-graph.c
> index aebd242def..a8c337dd77 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -248,6 +248,7 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,
>  static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
>  {
>         const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
> +       item->graph_pos = pos;
>         item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
>  }
>

Minor bugfix.

> @@ -454,8 +455,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
>                 else
>                         packedDate[0] = 0;
>
> -               if ((*list)->generation != GENERATION_NUMBER_INFINITY)
> -                       packedDate[0] |= htonl((*list)->generation << 2);
> +               packedDate[0] |= htonl((*list)->generation << 2);
>
>                 packedDate[1] = htonl((*list)->date);
>                 hashwrite(f, packedDate, 8);

Minor bugfix.

> @@ -589,18 +589,17 @@ static void close_reachable(struct packed_oid_list *oids)
>         }
>  }
>
> -static void compute_generation_numbers(struct commit** commits,
> -                                      int nr_commits)
> +static void compute_generation_numbers(struct packed_commit_list* commits)
>  {
>         int i;
>         struct commit_list *list = NULL;
>
> -       for (i = 0; i < nr_commits; i++) {
> -               if (commits[i]->generation != GENERATION_NUMBER_INFINITY &&
> -                   commits[i]->generation != GENERATION_NUMBER_ZERO)
> +       for (i = 0; i < commits->nr; i++) {
> +               if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
> +                   commits->list[i]->generation != GENERATION_NUMBER_ZERO)
>                         continue;
>
> -               commit_list_insert(commits[i], &list);
> +               commit_list_insert(commits->list[i], &list);
>                 while (list) {
>                         struct commit *current = list->item;
>                         struct commit_list *parent;

Refactoring: signature change from pair of struct commit** + int to
struct packed_commit_list*.

I think that it makes code a bit uglier for no gain, but that is just my
personal opinion; it is a matter of taste.

> @@ -621,10 +620,10 @@ static void compute_generation_numbers(struct commit** commits,
>                         if (all_parents_computed) {
>                                 current->generation = max_generation + 1;
>                                 pop_commit(&list);
> -                       }
>
> -                       if (current->generation > GENERATION_NUMBER_MAX)
> -                               current->generation = GENERATION_NUMBER_MAX;
> +                               if (current->generation > GENERATION_NUMBER_MAX)
> +                                       current->generation = GENERATION_NUMBER_MAX;
> +                       }
>                 }
>         }
>  }

Bugfix (though it didn't result in wrong information writen out, just in
inconsistent state in the middle of computation).

> @@ -752,7 +751,7 @@ void write_commit_graph(const char *obj_dir,
>         if (commits.nr >= GRAPH_PARENT_MISSING)
>                 die(_("too many commits to write graph"));
>
> -       compute_generation_numbers(commits.list, commits.nr);
> +       compute_generation_numbers(&commits);
>
>         graph_name = get_commit_graph_filename(obj_dir);
>         fd = hold_lock_file_for_update(&lk, graph_name, 0);

The other side of signature change.

> diff --git a/commit.c b/commit.c
> index e2e16ea1a7..5064db4e61 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -835,7 +835,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,
>                 int flags;
>
>                 if (commit->generation > last_gen)
> -                       BUG("bad generation skip");
> +                       BUG("bad generation skip %8x > %8x at %s",
> +                           commit->generation, last_gen,
> +                           oid_to_hex(&commit->object.oid));
>                 last_gen = commit->generation;
>
>                 if (commit->generation < min_generation)

More detailed BUG() message, always nice to have.

> @@ -947,6 +949,7 @@ static int remove_redundant(struct commit **array, int cnt)
>                 parse_commit(array[i]);
>         for (i = 0; i < cnt; i++) {
>                 struct commit_list *common;
> +               uint32_t min_generation = GENERATION_NUMBER_INFINITY;
>
>                 if (redundant[i])
>                         continue;
> @@ -955,8 +958,12 @@ static int remove_redundant(struct commit **array, int cnt)
>                                 continue;
>                         filled_index[filled] = j;
>                         work[filled++] = array[j];
> +
> +                       if (array[j]->generation < min_generation)
> +                               min_generation = array[j]->generation;
>                 }
> -               common = paint_down_to_common(array[i], filled, work, 0);
> +               common = paint_down_to_common(array[i], filled, work,
> +                                             min_generation);
>                 if (array[i]->object.flags & PARENT2)
>                         redundant[i] = 1;
>                 for (j = 0; j < filled; j++)

New commit in series.  Change looks quite short, gives measurable
performance gains (in appropriate case).

> @@ -1073,7 +1080,7 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
>         for (i = 0; i < nr_reference; i++) {
>                 if (parse_commit(reference[i]))
>                         return ret;
> -               if (min_generation > reference[i]->generation)
> +               if (reference[i]->generation < min_generation)
>                         min_generation = reference[i]->generation;
>         }
>
>

Style change.

> -- >8 --
>
> Derrick Stolee (11):
>   ref-filter: fix outdated comment on in_commit_list
>   commit: add generation number to struct commmit
>   commit-graph: compute generation numbers
>   commit: use generations in paint_down_to_common()
>   commit-graph: always load commit-graph information
>   ref-filter: use generation number for --contains
>   commit: use generation numbers for in_merge_bases()
>   commit: add short-circuit to paint_down_to_common()
>   commit: use generation number in remove_redundant()
>   merge: check config before loading commits
>   commit-graph.txt: update design document

It looks like the series is maturing nicely.

Best,
-- 
Jakub Narębski