Re: [PATCH 4/6] commit: use generations in paint_down_to_common()

[Stefan Beller <sbeller@google.com>]

On Tue, Apr 3, 2018 at 9:51 AM, Derrick Stolee <dstolee@microsoft.com> wrote:
> 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_UNDEF.
>
> 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.


This patch (or later in this series) may want to touch
Documentation/technical/commit-graph.txt, that mentions this in
the section of Future Work:

- After computing and storing generation numbers, we must make graph
  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
  operations are important candidates:

    - paint_down_to_common()
    - 'log --topo-order'

The paint down to common is only internal, not exposed to the user
for ordering, i.e. the topological ordering is still ordering commits in
a branch adjacent?

Thanks,
Stefan