On 4/11/2018 3:32 PM, Jakub Narebski wrote:
What would you suggest as a good test that could imply performance? The
Google Colab notebook linked to above includes a function to count
number of commits (nodes / vertices in the commit graph) walked,
currently in the worst case scenario.
The two main questions to consider are:
1. Can X reach Y?
2. What is the set of merge-bases between X and Y?
And the thing to measure is a commit count. If possible, it would be
good to count commits walked (commits whose parent list is enumerated)
and commits inspected (commits that were listed as a parent of some
walked commit). Walked commits require a commit parse -- albeit from the
commit-graph instead of the ODB now -- while inspected commits only
check the in-memory cache.
For git.git and Linux, I like to use the release tags as tests. They
provide a realistic view of the linear history, and maintenance releases
have their own history from the major releases.
I have tried finding number of false positives for level (generation
number) filter and for FELINE index, and number of false negatives for
min-post intervals in the spanning tree (for DFS tree) for 10000
randomly selected pairs of commits... but I don't think this is a good
benchmark.
What is a false-positive? A case where gen(X) < gen(Y) but Y cannot
reach X? I do not think that is a great benchmark, but I guess it is
something to measure.
I Linux kernel sources
(https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git)
that has 750832 nodes and 811733 edges, and 563747941392 possible
directed pairs, we have for 10000 randomly selected pairs of commits:
level-filter has 91 = 0.91% [all] false positives
FELINE index has 78 = 0.78% [all] false positives
FELINE index has 1.16667 less false positives than level filter
min-post spanning-tree intervals has 3641 = 36.41% [all] false
negatives
Perhaps something you can do instead of sampling from N^2 commits in
total is to select a pair of generations (say, G = 20000, G' = 20100) or
regions of generations ( 20000 <= G <= 20050, 20100 <= G' <= 20150) and
see how many false positives you see by testing all pairs (one from each
level). The delta between the generations may need to be smaller to
actually have a large proportion of unreachable pairs. Try different
levels, since major version releases tend to "pinch" the commit graph to
a common history.
For git.git repository (https://github.com/git/git.git) that has 52950
nodes and 65887 edges the numbers are slighly more in FELINE index
favor (also out of 10000 random pairs):
level-filter has 504 = 9.11% false positives
FELINE index has 125 = 2.26% false positives
FELINE index has 4.032 less false positives than level filter
This is for FELINE which does not use level / generatio-numbers filter.
Thanks,
-Stolee
