From: Jakub Narebski <email@example.com> To: Derrick Stolee <firstname.lastname@example.org> Cc: "Mike Hommey" <email@example.com>, "SZEDER Gábor" <firstname.lastname@example.org>, email@example.com Subject: Re: Revision walking, commit dates, slop Date: Thu, 23 May 2019 23:04:49 +0200 [thread overview] Message-ID: <firstname.lastname@example.org> (raw) In-Reply-To: <email@example.com> (Derrick Stolee's message of "Wed, 22 May 2019 15:06:32 -0400") Derrick Stolee <firstname.lastname@example.org> writes: > On 5/22/2019 2:29 PM, Jakub Narebski wrote: >> Derrick Stolee <email@example.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
next prev parent 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 \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.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).