Re: Revision walking, commit dates, slop

From: Jakub Narebski <jnareb@gmail.com>
Date: May 22, 2019, 18:29 UTC
Message-ID: <86lfyyny0p.fsf@gmail.com>
In-Reply-To: <88662e18-db51-cb48-3307-0ea2a91c4ebe@gmail.com>

Derrick Stolee <stolee@gmail.com> writes:

Show 27 quoted lines

> On 5/20/2019 7:27 PM, Jakub Narebski wrote:
>> Jakub Narebski <jnareb@gmail.com> writes:
>>> Derrick Stolee <stolee@gmail.com> writes:
>>>> On 5/20/2019 7:02 AM, Jakub Narebski wrote:
>>>>>
>>>>> Are there any blockers that prevent the switch to this
>>>>> "generation number v2"?
>> [...]
>> 
>>>>                      Using the generation number column for the corrected
>>>> commit-date offsets (assuming we also guarantee the offset is strictly
>>>> increasing from parent to child), these new values will be backwards-
>>>> compatible _except_ for 'git commit-graph verify'.
>>>
>>> O.K., so the "generation number v2 (legacy)" would be incremental and
>>> backward-compatibile in use (though not in generation and validation).
>>>
>>> Do I understand it correctly how it is calculated:
>>>
>>>   corrected_date(C) = max(committer_date(C),
>>>                           max_{P ∈ parents(C)}(corrected_date(P)) + 1)
>> 
>> This should probably read
>> 
>>     offset_date(P) = committer_date(P) + gen_v2(P)
>>     corrected_date(C) = max(committer_date(C),
>>                             max_{P ∈ parents(C)}(offset_date(P)) + 1)

Restating it yet again:

   A.  corrected_date(C) = max(committer_date(C),
                               max_P(committer_date(P) + offset(P)) + 1)

   B.  offset(C) = max(corrected_date(C) - committer_date(C),
                       max_P(offset(P)) + 1)

Show 5 quoted lines

> The final definition needs two conditions on the offset of a commit C for
> every parent P:
>
>  1. committer_date(C) + offset(C) > committer_date(P) + offset(P)
>  2. offset(C) > offset(P)

The equation (B) ensures the (2) condition, i.e offset(C) > offset(P). The equation (A) ensures that condition (1) is fulfulled, because from (B) we have

   corrected_date(C) <= committer_date(C) + offset(C)

This from (B) and (A( we get:

   committer_date(C) + offset(C) >= corrected_date(C) >
                                 >  committer_date(P) + offset(P)

> Condition (1) will give us the performance benefits related to the
> committer-date heuristic. Condition (2) will give us backwards-compatibility
> with generation numbers.

Well, we should check/test if performance benefits of "offset date" ("corrected date with rising offset") truly holds.

Best, -- Jakub Narębski