Re: [RFC] Generation Number v2

From: Jakub Narebski <jnareb@gmail.com>
Date: Nov 2, 2018, 09:30 UTC
Message-ID: <86ftwjzv1h.fsf@gmail.com>
In-Reply-To: <86tvl0zhos.fsf@gmail.com>

Jakub Narebski <jnareb@gmail.com> writes:

> Stefan Beller <sbeller@google.com> writes:

[...]

Show 6 quoted lines

>> 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).

[...]

Show 22 quoted lines

>> 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.

Show 36 quoted lines

>
> 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