git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Abhishek Kumar <abhishekkumar8222@gmail.com>
To: git@vger.kernel.org
Cc: stolee@gmail.com, jnareb@gmail.com
Subject: [RFC] Metadata vs Generation Data Chunk
Date: Mon, 22 Jun 2020 15:04:51 +0530	[thread overview]
Message-ID: <20200622093451.GA1719@Abhishek-Arch> (raw)

One of the remaining pre-requisites for implementing generation number
v2 was distinguishing between corrected commit dates with monotonically
increasing offsets and topological level without incrementing generation
number version.

Two approaches were proposed [1]:
1. New chunk for commit data (generation data chunk, "GDAT")
2. Metadata/versioning chunk

Since both approaches have their advantages and disadvantages, I wrote
up a prototype [2] to investigate their performance.

[1]: https://lore.kernel.org/git/86mu87qj92.fsf@gmail.com/ 
[2]: https://github.com/abhishekkumar2718/git/pull/1

TL;DR: I recommend we should use generation data chunk approach.

Generation Data Chunk
=====================

We could move the generation number v2 into a separate chunk, storing
topological levels in CDAT and the corrected commit date into a new,
"GDAT" chunk.  Thus, old Git would use generation number v1, and
new Git would use corrected commit dates from GDAT.

Using generation data chunk has the advantage that we would no longer
be restricted to using 30 bits for generation number. It also works
well for commit-graph chains with a mix of v1 and v2 generation numbers.

However, it increases the time required for I/O as commit data and
generation numbers are no longer contiguous.

Note: While it also increases disk space required for storing
commit-graph files by 8 bytes per commit, I don't consider it relevant,
especially on modern systems. A repo of the size of Linux repo would be
larger by a mere 7.2 Mb.

Metadata / Versioning Chunk
===========================

We could also introduce an optional metadata chunk to store generation
number version and store corrected date offsets in CDAT. Since the
offsets are backward compatible, Old Git would still yield correct
results by assuming the offsets to be topological levels. New Git would
correctly use the offsets to create corrected commit dates.

It works just as well as generation number v1 in parsing and writing
commit-graph files.

However, the generation numbers are still restricted to 30 bits in CDAT
chunk and it does not work well with commit-graph chains with a mix of
v1 and v2 generation numbers.

Performance
===========

| Command                        | Master | Metadata | Generation Data |
|--------------------------------|--------|----------|-----------------|
| git commit-graph write         | 14.45s | 14.28s   | 14.63s          |
| git log --topo-order -10000    | 0.211s | 0.206s   | 0.208s          |
| git log --topo-order -100 A..B | 0.019s | 0.015s   | 0.015s          |
| git merge-base A..B            | 0.137s | 0.137s   | 0.137s          |

- Metadata and generation data chunks perform better than master on
  using commit-graph files since they use corrected commit dates.

- The increased I/O time for parsing GDAT does not affect performance as
  much as expected.

- Generation data commit-graph takes longer to write since more
  information is written into the file.

As using the commit-graph is much more frequent than writing, we can
consider both approaches to perform equally well.

I prefer generation data chunk approach as it also removes 30-bit length
restriction on generation numbers.

Thanks
Abhishek

             reply	other threads:[~2020-06-22  9:36 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-06-22  9:34 Abhishek Kumar [this message]
2020-06-22 13:40 ` [RFC] Metadata vs Generation Data Chunk Jakub Narębski
2020-06-22 14:46 ` Derrick Stolee
  -- strict thread matches above, loose matches on Subject: below --
2020-06-26 13:44 Abhishek Kumar
2020-06-26 14:40 ` Derrick Stolee
2020-06-30 15:00 Abhishek Kumar
2020-06-30 20:46 ` Derrick Stolee
2020-07-03  8:29   ` Abhishek Kumar

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=20200622093451.GA1719@Abhishek-Arch \
    --to=abhishekkumar8222@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=jnareb@gmail.com \
    --cc=stolee@gmail.com \
    /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
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

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