From: Stefan Beller <firstname.lastname@example.org>
To: Derrick Stolee <email@example.com>
Cc: git <firstname.lastname@example.org>, "Jeff King" <email@example.com>,
"Junio C Hamano" <firstname.lastname@example.org>,
"Jakub Narębski" <email@example.com>,
"Derrick Stolee" <firstname.lastname@example.org>,
"Ævar Arnfjörð Bjarmason" <email@example.com>
Subject: Re: [RFC] Generation Number v2
Date: Mon, 29 Oct 2018 12:22:03 -0700 [thread overview]
Message-ID: <CAGZ79ka-FTqaXdrMixjUp2THJ3L0YvEnkKxs3XFgB3WEEy2-Tg@mail.gmail.com> (raw)
> Based on the performance results alone, we should remove minimum
> generation numbers, (epoch, date) pairs, and FELINE index from
> consideration. There are enough examples of these indexes performing
> In contrast, maximum generation numbers and corrected commit
> dates both performed quite well. They are frequently the top
> two performing indexes, and rarely significantly different.
> The trade-off here now seems to be: which _property_ is more important,
> locally-computable or backwards-compatible?
> * Maximum generation number is backwards-compatible but not
> locally-computable or immutable.
These maximum generation numbers sound like the reverse of
the generation numbers as they are currently implemented, i.e.
we count all commits between the commit A and all heads.
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).
Are there ways out by deferring the computation of maximum
generation numbers while still being able to work with some
commits that are un-accounted for?
When recomputing these numbers, the current generation number
(V0) has the property that already existing numbers can be re-used
as-is. We only need to compute the numbers for new commits,
and then insert this to the appropriate data structures (which is
a separate problem, one could imagine a split generation
numbers file like the split index)
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.
(Note: The table as read in
seems line broken, using gmails web interface is not good
for ASCII art and patches, git-send-email would fare better)
> * Corrected commit-date is locally-computable and immutable,
> but not backwards-compatible.
How are these dates not backwards incompatible?
We don't have to expose these dates to the user, but
- just like generation numbers - could store them and use them
but not tell the user about it.
We would need to be really careful to not expose them at all
as they look like the real dates, so that could make for an
awkward bug report.
The approach of "corrected commit date" sounds like we could
have a very lazy approach, i.e. no extra data structures needed
for many commits (as the corrected date equals the real date)
and only need to store the corrections for some commits.
Such an approach however would not make it easy to know
if we operate on corrected dates, or if we even checked them
for correctness before.
So if we'd have an additional row in the generation numbers file
telling the corrected date, then we should be able to be backwards
next prev parent reply other threads:[~2018-10-29 19:22 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-29 16:55 [RFC] Generation Number v2 Derrick Stolee
2018-10-29 19:22 ` Stefan Beller [this message]
2018-10-29 20:06 ` Derrick Stolee
2018-11-01 20:06 ` Jakub Narebski
2018-11-02 9:30 ` Jakub Narebski
2018-11-03 17:27 ` Jakub Narebski
2018-10-29 20:25 ` Derrick Stolee
2018-11-01 22:13 ` Jakub Narebski
2018-10-30 3:59 ` Junio C Hamano
2018-10-31 12:30 ` Derrick Stolee
2018-11-02 13:33 ` Jakub Narebski
2018-10-31 12:54 ` Ævar Arnfjörð Bjarmason
2018-10-31 13:04 ` Derrick Stolee
2018-11-02 17:44 ` Jakub Narebski
2018-11-01 12:27 ` Jakub Narebski
2018-11-01 13:29 ` Derrick Stolee
2018-11-03 12:33 ` Jakub Narebski
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:
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 \
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
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).