Derrick Stolee [off-list ref] writes:

On 3/30/2018 7:10 AM, Jakub Narebski wrote:

quoted

I hope that I am addressing the most recent version of this series.

Hi Jakub. Thanks for the interest in this patch series.

The most-recent version is v6 [1], but I will re-roll to v7 soon
(after v2.17.0 is marked).

[1] https://public-inbox.org/git/20180314192736.70602-1-dstolee@microsoft.com/T/#u

Ooops.  Sorry about that.

quoted

Derrick Stolee [off-list ref] writes:

[...]

quoted

What are the assumptions about the serialized commit graph format? Does
it need to be:
  - extensible without rewriting (e.g. append-only)?
  - like the above, but may need rewriting for optimal performance?
  - extending it needs to rewrite whole file?

Excuse me if it waas already asked and answered.

It is not extensible without rewriting. Reducing write time was not a
main goal, since the graph will be written only occasionally during
data management phases (like 'gc' or 'repack'; this integration is not
implemented yet).

Ah.  I thought that it could be something easily extensible in-place,
and thus easy to keep up to date on each commit.

Recalculating it on 'gc' or 'repack' is still good, especially that it
works even when there are come commits outside commit-graph, without
this information.

quoted

quoted

The file format has room to store generation numbers, which will be
provided as a patch after this framework is merged. Generation numbers
are referenced by the design document but not implemented in order to
make the current patch focus on the graph construction process. Once
that is stable, it will be easier to add generation numbers and make
graph walks aware of generation numbers one-by-one.

As the serialized commit graph format is versioned, I wonder if it would
be possible to speed up graph walks even more by adding to it FELINE
index (pair of numbers) from "Reachability Queries in Very Large Graphs:
A Fast Refined Olnine Search Approach" (2014) - available at
http://openproceedings.org/EDBT/2014/paper_166.pdf

The implementation would probably need adjustments to make it
unambiguous and unambiguously extensible; unless there is place for
indices that are local-only and need to be recalculated from scratch
when graph changes (to cover all graph).

The chunk-based format is intended to allow extra indexes like the one
you recommend, without needing to increase the version number. Using
an optional chunk allows older versions of Git to read the file
without error, since the data is "extra", and newer versions can take
advantage of the acceleration.

That's good.

At one point, I was investigating these reachability indexes (I read
"SCARAB: Scaling Reachability Computation on Large Graphs" by Jihn,
Ruan, Dey, and Xu [2]) but find the question that these indexes target
to be lacking for most of the Git uses. That is, they ask the boolean
question "Can X reach Y?". More often, Git needs to answer "What is
the set of commits reachable from X but not from Y" or "Topologically
sort commits reachable from X" or "How many commits are in each part
of the symmetric difference between reachable from X or reachable from
Y?"

In the "Reachability Queries in Very Large Graphs..." by Veloso, Cerf,
Meira and Zaki FELINE-index work, authors mention SCARAB as something
that can be used in addition to FELINE-index, as a complementary data
(FELINE-SCARAB in the work, section 4.4).

I see the FELINE-index as a stronger form of generation numbers (called
also level of the vertex / node), in that it allows to negative-cut even
more, pruning paths that are known to be unreachable (or marking nodes
known to be unreachable in the "calculate difference" scenario). 

Also, FELINE-index uses two integer numbers (coordinates in 2d space);
one of those indices can be the topological numbering (topological
sorting order) of nodes in the commit graph.  That would help to answer
even more Git questions.

The case for "Can X reach Y?" is mostly for commands like 'git branch
--contains', when 'git fetch' checks for forced-updates of branches,
or when the server decides enough negotiation has occurred during a
'git fetch'. While these may be worth investigating, they also benefit
greatly from the accelerated graph walk introduced in the current
format.

I would be happy to review any effort to extend the commit-graph
format to include such indexes, as long as the performance benefits
outweigh the complexity to create them.

[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.719.8396&rep=rep1&type=pdf

The complexity of calculating FELINE index is O(|V| log(|V|) + |E|), the
storage complexity is 2*|V|.

quoted

quoted

Here are some performance results for a copy of the Linux repository
where 'master' has 704,766 reachable commits and is behind 'origin/master'
by 19,610 commits.

| Command                          | Before | After  | Rel % |
|----------------------------------|--------|--------|-------|
| log --oneline --topo-order -1000 |  5.9s  |  0.7s  | -88%  |
| branch -vv                       |  0.42s |  0.27s | -35%  |
| rev-list --all                   |  6.4s  |  1.0s  | -84%  |
| rev-list --all --objects         | 32.6s  | 27.6s  | -15%  |

That's the "Rel %" of "Before", that is delta/before, isn't it?

I do mean the relative change.

But is it relative to the state before, or relative to the state after?

[...]

quoted

I just wonder what happens in the (rare) presence of grafts (old
mechanism), or "git replace"-d commits...

In the design document, I mention that the current implementation does
not work with grafts (it will ignore them). A later patch will
refactor the graft code so we can access it from the commit-graph
parsing of a commit without copy-pasting the code out of
parse_commit_gently().

The commit-graph is only a compact representation of the object
database. If a commit is replaced with 'git replace' before 'git
commit-graph write' then the commit-graph write will write the
replaced object. I haven't tested what happens when a commit-graph is
written and then a commit is replaced, but my guess is that the
replacement does not occur until a full parse is attempted (i.e. when
reading author or commit message information). This will lead to
unknown results.

Thanks for pointing out the interaction with 'git replace'. I have
items to fix grafts and replaced commits before integrating
commit-graph writes into automatic actions like 'gc.auto'.

Note that you can make Git ignore replacements with appropriate command
line option for "git" wrapper; the transfer mechanism can safely
ignore replacements (treating refs/replacements just like it would any
other refs/).

Best regards,
--
Jakub Narębski