Re: Revision walking, commit dates, slop

From: Derrick Stolee <stolee@gmail.com>
Date: May 22, 2019, 19:06 UTC
Message-ID: <f1f2c7f5-9b78-8404-2738-ab895a06c133@gmail.com>
In-Reply-To: <86lfyyny0p.fsf@gmail.com>

On 5/22/2019 2:29 PM, Jakub Narebski wrote:

Show 9 quoted lines

> Derrick Stolee <stolee@gmail.com> writes:
>> On 5/20/2019 7:27 PM, Jakub Narebski wrote:
> 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)

The problem with this definition is that it "defines" the corrected date, and then _adjusts_ it by updating the offset. I consider

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

to be part of the definition. You could restate the definition as follows:

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

or, equivalently

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

This definition, in a single step, satisfies the conditions below:

Show 6 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)

Plus, the "+ 1" in the first step takes into account that "0" is a special offset value in the commit-graph file format meaning "not computed".

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

Yes, a full performance test will be required. I have full confidence that the monotonic offset requirement will have only positive effect. That is, it will not affect the case where committer-date was better than generation number, but will help the cases where all the committer-dates are equal.

Thanks, -Stolee