git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Derrick Stolee <stolee@gmail.com>
To: git@vger.kernel.org
Cc: gitster@pobox.com, sbeller@google.com, szeder.dev@gmail.com,
	ramsay@ramsayjones.plus.com, git@jeffhostetler.com,
	peff@peff.net, Derrick Stolee <dstolee@microsoft.com>
Subject: [PATCH v7 00/14] Serialized Git Commit Graph
Date: Mon,  2 Apr 2018 16:34:13 -0400
Message-ID: <20180402203427.170177-1-dstolee@microsoft.com> (raw)
In-Reply-To: <20180314192736.70602-1-dstolee@microsoft.com>

This patch has only a few changes since v6:

* Fixed whitespace issues using 'git rebase --whitespace=fix'

* The --stdin-packs docs now refer to "pack-indexes" insead of "packs"

* Modified description of --object-dir option to warn use is rare

* Replaced '--additive' with '--append'

* In "commit-graph: close under reachability" I greatly simplified
  the check that every reachable commit is included. While running
  tests I noticed that the revision walk machinery could not keep up
  with a very large queue created when combined with the '--append'
  option that added all commits from the existing file as starting
  points for the walk. The new algorithm simply appends missing commits
  to the end of the list, which are then iterated to ensure their
  parents are in the list.

I have a few patch series prepared that provide further performance
improvments following this patch.

-- >8 --

This patch contains a way to serialize the commit graph.

The current implementation defines a new file format to store the graph
structure (parent relationships) and basic commit metadata (commit date,
root tree OID) in order to prevent parsing raw commits while performing
basic graph walks. For example, we do not need to parse the full commit
when performing these walks:

* 'git log --topo-order -1000' walks all reachable commits to avoid
  incorrect topological orders, but only needs the commit message for
  the top 1000 commits.

* 'git merge-base <A> <B>' may walk many commits to find the correct
  boundary between the commits reachable from A and those reachable
  from B. No commit messages are needed.

* 'git branch -vv' checks ahead/behind status for all local branches
  compared to their upstream remote branches. This is essentially as
  hard as computing merge bases for each.

The current patch speeds up these calculations by injecting a check in
parse_commit_gently() to check if there is a graph file and using that
to provide the required metadata to the struct commit.

The file format has room to store generation numbers, which will be
provided as a patch after this framework is merged. Generation numbers
are referenced by the design document but not implemented in order to
make the current patch focus on the graph construction process. Once
that is stable, it will be easier to add generation numbers and make
graph walks aware of generation numbers one-by-one.

By loading commits from the graph instead of parsing commit buffers, we
save a lot of time on long commit walks. Here are some performance
results for a copy of the Linux repository where 'master' has 678,653
reachable commits and is behind 'origin/master' by 59,929 commits.

| Command                          | Before | After  | Rel % |
|----------------------------------|--------|--------|-------|
| log --oneline --topo-order -1000 |  8.31s |  0.94s | -88%  |
| branch -vv                       |  1.02s |  0.14s | -86%  |
| rev-list --all                   |  5.89s |  1.07s | -81%  |
| rev-list --all --objects         | 66.15s | 58.45s | -11%  |

To test this yourself, run the following on your repo:

  git config core.commitGraph true
  git show-ref -s | git commit-graph write --stdin-commits

The second command writes a commit graph file containing every commit
reachable from your refs. Now, all git commands that walk commits will
check your graph first before consulting the ODB. You can run your own
performance comparisons by toggling the 'core.commitGraph' setting.

[1] https://github.com/derrickstolee/git/pull/2
    A GitHub pull request containing the latest version of this patch.

Derrick Stolee (14):
  csum-file: rename hashclose() to finalize_hashfile()
  csum-file: refactor finalize_hashfile() method
  commit-graph: add format document
  graph: add commit graph design document
  commit-graph: create git-commit-graph builtin
  commit-graph: implement write_commit_graph()
  commit-graph: implement git-commit-graph write
  commit-graph: implement git commit-graph read
  commit-graph: add core.commitGraph setting
  commit-graph: close under reachability
  commit: integrate commit graph with commit parsing
  commit-graph: read only from specific pack-indexes
  commit-graph: build graph from starting commits
  commit-graph: implement "--additive" option

 .gitignore                                    |   1 +
 Documentation/config.txt                      |   4 +
 Documentation/git-commit-graph.txt            |  94 +++
 .../technical/commit-graph-format.txt         |  97 +++
 Documentation/technical/commit-graph.txt      | 163 ++++
 Makefile                                      |   2 +
 alloc.c                                       |   1 +
 builtin.h                                     |   1 +
 builtin/commit-graph.c                        | 171 ++++
 builtin/index-pack.c                          |   2 +-
 builtin/pack-objects.c                        |   6 +-
 bulk-checkin.c                                |   4 +-
 cache.h                                       |   1 +
 command-list.txt                              |   1 +
 commit-graph.c                                | 738 ++++++++++++++++++
 commit-graph.h                                |  46 ++
 commit.c                                      |   3 +
 commit.h                                      |   3 +
 config.c                                      |   5 +
 contrib/completion/git-completion.bash        |   2 +
 csum-file.c                                   |  10 +-
 csum-file.h                                   |   9 +-
 environment.c                                 |   1 +
 fast-import.c                                 |   2 +-
 git.c                                         |   1 +
 pack-bitmap-write.c                           |   2 +-
 pack-write.c                                  |   5 +-
 packfile.c                                    |   4 +-
 packfile.h                                    |   2 +
 t/t5318-commit-graph.sh                       | 224 ++++++
 30 files changed, 1584 insertions(+), 21 deletions(-)
 create mode 100644 Documentation/git-commit-graph.txt
 create mode 100644 Documentation/technical/commit-graph-format.txt
 create mode 100644 Documentation/technical/commit-graph.txt
 create mode 100644 builtin/commit-graph.c
 create mode 100644 commit-graph.c
 create mode 100644 commit-graph.h
 create mode 100755 t/t5318-commit-graph.sh


base-commit: 468165c1d8a442994a825f3684528361727cd8c0
-- 
2.17.0.14.gba1221a8ce


  parent reply index

Thread overview: 109+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-02-27  2:32 [PATCH v5 00/13] " Derrick Stolee
2018-02-27  2:32 ` [PATCH v5 01/13] commit-graph: add format document Derrick Stolee
2018-02-27  2:32 ` [PATCH v5 02/13] graph: add commit graph design document Derrick Stolee
2018-02-27  2:32 ` [PATCH v5 03/13] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-02-27  2:32 ` [PATCH v5 04/13] csum-file: add CSUM_KEEP_OPEN flag Derrick Stolee
2018-03-12 13:55   ` Derrick Stolee
2018-03-13 21:42     ` Junio C Hamano
2018-03-14  2:26       ` Derrick Stolee
2018-03-14 17:00         ` Junio C Hamano
2018-02-27  2:32 ` [PATCH v5 05/13] commit-graph: implement write_commit_graph() Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 06/13] commit-graph: implement 'git-commit-graph write' Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 07/13] commit-graph: implement git commit-graph read Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 08/13] commit-graph: add core.commitGraph setting Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 09/13] commit-graph: close under reachability Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 10/13] commit: integrate commit graph with commit parsing Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 11/13] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-02-27 20:15   ` Stefan Beller
2018-02-27  2:33 ` [PATCH v5 12/13] commit-graph: build graph from starting commits Derrick Stolee
2018-02-27  2:33 ` [PATCH v5 13/13] commit-graph: implement "--additive" option Derrick Stolee
2018-02-27 18:50 ` [PATCH v5 00/13] Serialized Git Commit Graph Stefan Beller
2018-03-14 19:27 ` [PATCH v6 00/14] " Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 01/14] csum-file: rename hashclose() to finalize_hashfile() Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 02/14] csum-file: refactor finalize_hashfile() method Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 03/14] commit-graph: add format document Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 04/14] graph: add commit graph design document Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 05/14] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 06/14] commit-graph: implement write_commit_graph() Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 07/14] commit-graph: implement 'git-commit-graph write' Derrick Stolee
2018-03-18 13:25     ` Ævar Arnfjörð Bjarmason
2018-03-19 13:12       ` Derrick Stolee
2018-03-19 14:36         ` Ævar Arnfjörð Bjarmason
2018-03-19 18:27           ` Derrick Stolee
2018-03-19 18:48             ` Ævar Arnfjörð Bjarmason
2018-03-14 19:27   ` [PATCH v6 08/14] commit-graph: implement git commit-graph read Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 09/14] commit-graph: add core.commitGraph setting Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 10/14] commit-graph: close under reachability Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 11/14] commit: integrate commit graph with commit parsing Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 12/14] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-03-15 22:50     ` SZEDER Gábor
2018-03-19 13:13       ` Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 13/14] commit-graph: build graph from starting commits Derrick Stolee
2018-03-14 19:27   ` [PATCH v6 14/14] commit-graph: implement "--additive" option Derrick Stolee
2018-03-14 20:10   ` [PATCH v6 00/14] Serialized Git Commit Graph Ramsay Jones
2018-03-14 20:43   ` Junio C Hamano
2018-03-15 17:23     ` Johannes Schindelin
2018-03-15 18:41       ` Junio C Hamano
2018-03-15 21:51         ` Ramsay Jones
2018-03-16 11:50         ` Johannes Schindelin
2018-03-16 17:27           ` Junio C Hamano
2018-03-19 11:41             ` Johannes Schindelin
2018-03-16 16:28     ` Lars Schneider
2018-03-19 13:10       ` Derrick Stolee
2018-03-16 15:06   ` Ævar Arnfjörð Bjarmason
2018-03-16 16:38     ` SZEDER Gábor
2018-03-16 18:33       ` Junio C Hamano
2018-03-16 19:48         ` SZEDER Gábor
2018-03-16 20:06           ` Jeff King
2018-03-16 20:19             ` Jeff King
2018-03-19 12:55               ` Derrick Stolee
2018-03-20  1:17                 ` Derrick Stolee
2018-03-16 20:49         ` Jeff King
2018-04-02 20:34   ` Derrick Stolee [this message]
2018-04-02 20:34     ` [PATCH v7 01/14] csum-file: rename hashclose() to finalize_hashfile() Derrick Stolee
2018-04-02 20:34     ` [PATCH v7 02/14] csum-file: refactor finalize_hashfile() method Derrick Stolee
2018-04-07 22:59       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 03/14] commit-graph: add format document Derrick Stolee
2018-04-07 23:49       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 04/14] graph: add commit graph design document Derrick Stolee
2018-04-08 11:06       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 05/14] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-04-02 20:34     ` [PATCH v7 06/14] commit-graph: implement write_commit_graph() Derrick Stolee
2018-04-02 20:34     ` [PATCH v7 07/14] commit-graph: implement git-commit-graph write Derrick Stolee
2018-04-08 11:59       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 08/14] commit-graph: implement git commit-graph read Derrick Stolee
2018-04-02 21:33       ` Junio C Hamano
2018-04-03 11:49         ` Derrick Stolee
2018-04-08 12:59       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 09/14] commit-graph: add core.commitGraph setting Derrick Stolee
2018-04-08 13:39       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 10/14] commit-graph: close under reachability Derrick Stolee
2018-04-02 20:34     ` [PATCH v7 11/14] commit: integrate commit graph with commit parsing Derrick Stolee
2018-04-02 20:34     ` [PATCH v7 12/14] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-04-02 20:34     ` [PATCH v7 13/14] commit-graph: build graph from starting commits Derrick Stolee
2018-04-08 13:50       ` Jakub Narebski
2018-04-02 20:34     ` [PATCH v7 14/14] commit-graph: implement "--additive" option Derrick Stolee
2018-04-05  8:27       ` SZEDER Gábor
2018-04-10 12:55     ` [PATCH v8 00/14] Serialized Git Commit Graph Derrick Stolee
2018-04-10 12:55       ` [PATCH v8 01/14] csum-file: rename hashclose() to finalize_hashfile() Derrick Stolee
2018-04-10 12:55       ` [PATCH v8 02/14] csum-file: refactor finalize_hashfile() method Derrick Stolee
2018-04-10 12:55       ` [PATCH v8 03/14] commit-graph: add format document Derrick Stolee
2018-04-10 19:10         ` Stefan Beller
2018-04-10 19:18           ` Derrick Stolee
2018-04-11 20:58         ` Jakub Narebski
2018-04-12 11:28           ` Derrick Stolee
2018-04-13 22:07             ` Jakub Narebski
2018-04-10 12:55       ` [PATCH v8 04/14] graph: add commit graph design document Derrick Stolee
2018-04-15 22:48         ` Jakub Narebski
2018-04-10 12:55       ` [PATCH v8 05/14] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 06/14] commit-graph: implement write_commit_graph() Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 07/14] commit-graph: implement git-commit-graph write Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 08/14] commit-graph: implement git commit-graph read Derrick Stolee
2018-04-14 22:15         ` Jakub Narebski
2018-04-15  3:26           ` Eric Sunshine
2018-04-10 12:56       ` [PATCH v8 09/14] commit-graph: add core.commitGraph setting Derrick Stolee
2018-04-14 18:33         ` Jakub Narebski
2018-04-10 12:56       ` [PATCH v8 10/14] commit-graph: close under reachability Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 11/14] commit: integrate commit graph with commit parsing Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 12/14] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 13/14] commit-graph: build graph from starting commits Derrick Stolee
2018-04-10 12:56       ` [PATCH v8 14/14] commit-graph: implement "--append" option Derrick Stolee

Reply instructions:

You may reply publically 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=20180402203427.170177-1-dstolee@microsoft.com \
    --to=stolee@gmail.com \
    --cc=dstolee@microsoft.com \
    --cc=git@jeffhostetler.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=peff@peff.net \
    --cc=ramsay@ramsayjones.plus.com \
    --cc=sbeller@google.com \
    --cc=szeder.dev@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

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox