Jakub Narebski <jna...@gmail.com> writes:
> Stefan Beller <sbel...@google.com> writes:
[...]
>> How would this impact creation of a commit?
>>
>> The current generation numbers can be lazily updated or not
>> updated at all. In my understanding of the maximum generation
>> numbers, a new commit would make these maximum generation
>> numbers invalid (i.e. they have to be recomputed).
[...]
>> For the V2 maximum generation numbers, would we need to
>> rewrite the numbers for all commits once we recompute them?
>> Assuming that is true, it sounds like the benchmark doesn't
>> cover the whole costs associated with V2, which is why the
>> exceptional performance can be explained.
>
> Let's check it using a simple example
>
> First, (minimum) parent-based generation numbers before and after
> extending the commit graph:
>
> 1 2 3 4 5 6 7 new
> 1 2 3 4 5 - - old
> .---.-----.---.-----.---*---*
> \
> \ 3 4 5 6 new
> \ 3 4 5 6 old
> \-.---.-----.---.
> \
> \ 5 new
> \ - old
> \-*
Let me check yet another idea, using (minimum) parent-based V0 generation
numbers (counting distance from the sink / root) as a starting number
for source / heads commits.
1 2 3 4 5 6 7 new
1 2 3 4 5 - - old
.---.-----.---.-----.---*---*
\
\ 3 4 5 6 new
\ 3 4 5 6 old
\-.---.-----.---.
\
\ 5 new
\ - old
\-*
Well, on this example it looks like this variant of maximum generation
numbers can be done incrementally, but let's check another example
1 2 3 4 5 6 7 8 9 new
1 2 3 4 5 6 7 8 - old
.---.-----.---.---.---.-----.---.---*
\ /
\ 3 4 / 5 6 7 8 new
\ 5 6 / - - - - old
\-.---.---------/---*---*---*---*
It looks like it doesn; give as good results as I thought. Less values
are changed, but you would still need to recalculate them, unless it can
be proven that they do not need it.
>
> Next, maximum generation numbers. We start with 9 commits, and we end
> up with 12 commits after the change
>
> 6 7 8 9 10 11 12 new
> 4 5 7 8 9 - - old
> .---.-----.---.-----.---*---*
> \
> \ 9 10 11 12 new
> \ 6 7 8 9 old
> \-.---.-----.---.
> \
> \ 12 new
> \ - old
> \-*
>
>
> As you can see all maximum generation numbers got rewritten.
>
> Though if instead using the number of commits, we use the maximum
> generation number, or in other words the length of the longest path, we
> get the following:
>
> 1 2 3 4 5 6 7 new
> 1 2 4 5 6 - - old
> .---.-----.---.-----.---*---*
> \
> \ 4 5 6 7 new
> \ 3 4 5 6 old
> \-.---.-----.---.
> \
> \ 7 new
> \ - old
> \-*
>
> A bit better, but still much change in numbers.
--
Jakub Narębski
