git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Jakub Narebski <jnareb@gmail.com>
To: Derrick Stolee <stolee@gmail.com>
Cc: "Mike Hommey" <mh@glandium.org>,
	"SZEDER Gábor" <szeder.dev@gmail.com>,
	git@vger.kernel.org
Subject: Re: Revision walking, commit dates, slop
Date: Thu, 23 May 2019 23:04:49 +0200	[thread overview]
Message-ID: <8636l4rifi.fsf@gmail.com> (raw)
In-Reply-To: <f1f2c7f5-9b78-8404-2738-ab895a06c133@gmail.com> (Derrick Stolee's message of "Wed, 22 May 2019 15:06:32 -0400")

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

For me equation (A) was just an intermediate step; we might call it
adjusted_date(C) or temp_date(C) instead.

Note that with the following adjustment

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

it is +1 corrected "V3: Corrected Commit Date" from gen-test.

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

I think it is easier to prove the conditions (1) and (2) using two-step
definition (A) + (B), as I have shown in previous email.

Also, what we need to calculate and store is offset(C), not
offset_date(C) (i.e. corrected_date(C), if you prefer).

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

That assumes that max_P(function(P)) over empty set of P is taken to be
zero.  Also, I think two step definition has the same property.

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

I worry that monotonic offset corrected date would behave like
topological levels (i.e. like current generation number v1) in more
cases rather than like commit date heuristics.

P.S. there is _theoretical_ problem with all date-offset based
generation numbers (slightly more likely to occur for monotonical
offset), namely that in the commit-graph format v1 we have 34 bits for
commit date timestamp, but only 30 bits for offset; and there might be
the case where offset do not fit in 30 bits.  It would be however very
unlikely, e.g. commit date of 2028, then commit date of 1970 (timestamp
equal to zero).

Regards,
--
Jakub Narębski

  reply	other threads:[~2019-05-23 21:04 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-05-18  0:54 Mike Hommey
2019-05-18  1:50 ` SZEDER Gábor
2019-05-18  3:58   ` Mike Hommey
2019-05-18  4:17     ` Mike Hommey
2019-05-18 12:01       ` SZEDER Gábor
2019-05-19 22:28         ` Jakub Narebski
2019-05-20  1:33       ` Derrick Stolee
2019-05-20 11:02         ` Jakub Narebski
2019-05-20 11:20           ` Derrick Stolee
2019-05-20 13:42             ` Jakub Narebski
2019-05-20 23:27               ` Jakub Narebski
2019-05-21  1:20                 ` Derrick Stolee
2019-05-22 18:29                   ` Jakub Narebski
2019-05-22 19:06                     ` Derrick Stolee
2019-05-23 21:04                       ` Jakub Narebski [this message]
2019-06-25  7:51               ` Jakub Narebski
2019-06-25 10:54                 ` Derrick Stolee
2019-09-18  8:43                   ` [RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling) Jakub Narebski
2019-09-18 12:26                     ` Derrick Stolee
2019-05-21 13:14         ` [PATCH] revision: use generation for A..B --topo-order queries Derrick Stolee
2019-05-21 13:59           ` [PATCH 2/2] revision: keep topo-walk free of unintersting commits Derrick Stolee
2019-05-22  2:19             ` Mike Hommey
2019-05-21  2:00   ` Revision walking, commit dates, slop Jonathan Nieder

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=8636l4rifi.fsf@gmail.com \
    --to=jnareb@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=mh@glandium.org \
    --cc=stolee@gmail.com \
    --cc=szeder.dev@gmail.com \
    --subject='Re: Revision walking, commit dates, slop' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).