git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
* [PATCH 00/16] Consolidate reachability logic
@ 2018-07-16 13:00 Derrick Stolee via GitGitGadget
  2018-06-19 20:25 ` [PATCH 04/16] upload-pack: make reachable() more generic Derrick Stolee via GitGitGadget
                   ` (17 more replies)
  0 siblings, 18 replies; 118+ messages in thread
From: Derrick Stolee via GitGitGadget @ 2018-07-16 13:00 UTC (permalink / raw)
  To: git; +Cc: Junio C Hamano

There are many places in Git that use a commit walk to determine
reachability between commits and/or refs. A lot of this logic is
duplicated.

I wanted to achieve the following:

1. Consolidate several different commit walks into one file
2. Reduce duplicate reachability logic
3. Increase testability (correctness and performance)
4. Improve performance of reachability queries

My approach is mostly in three parts:

  I. Move code to a new commit-reach.c file.
 II. Add a 'test-tool reach' command to test these methods directly.
III. Modify the logic by improving performance and calling methods with
     similar logic but different prototypes.

The 'test-tool reach' command is helpful to make sure I don't break
anything as I change the logic, but also so I can test methods that are
normally only exposed by other more complicated commands. For instance,
ref_newer() is part of 'git push -f' and ok_to_give_up() is buried deep
within fetch negotiation. Both of these methods have some problematic
performance issues that are corrected by this series. As I discovered
them, it was clear that it would be better to consolidate walk logic
instead of discovering a new walk in another file hidden somewhere.

For the ok_to_give_up() method, I refactored the method so I could pull
the logic out of the depths of fetch negotiation. In the commit
"commit-reach: make can_all_from_reach... linear" I discuss how the
existing algorithm is quadratic and how we can make it linear. Also, we
can use heuristic knowledge about the shape of the commit graph and the
usual haves/wants to get some extra performance bonus. (The heuristic is
to do a DFS with first-parents first, and stop on first found result. We
expect haves/wants to include ref tips, which typically have their
previous values in their first-parent history.)

One major difference in this series versus the RFC is that I added a new
method 'generation_numbers_enabled()' to detect if we have a commit-graph
file with non-zero generation numbers. Using can_all_from_reach in
is_descendant_of is only faster if we have generation numbers as a cutoff.

Thanks,
-Stolee

This series is based on jt/commit-graph-per-object-store

CC: sbeller@google.com

Derrick Stolee (16):
  commit-reach: move walk methods from commit.c
  commit-reach: move ref_newer from remote.c
  commit-reach: move commit_contains from ref-filter
  upload-pack: make reachable() more generic
  upload-pack: refactor ok_to_give_up()
  upload-pack: generalize commit date cutoff
  commit-reach: move can_all_from_reach_with_flags
  test-reach: create new test tool for ref_newer
  test-reach: test in_merge_bases
  test-reach: test is_descendant_of
  test-reach: test get_merge_bases_many
  test-reach: test reduce_heads
  test-reach: test can_all_from_reach_with_flags
  commit-reach: replace ref_newer logic
  commit-reach: make can_all_from_reach... linear
  commit-reach: use can_all_from_reach

 Makefile              |   2 +
 builtin/remote.c      |   1 +
 commit-graph.c        |  18 ++
 commit-graph.h        |   6 +
 commit-reach.c        | 662 ++++++++++++++++++++++++++++++++++++++++++
 commit-reach.h        |  76 +++++
 commit.c              | 358 -----------------------
 fast-import.c         |   1 +
 http-push.c           |   1 +
 ref-filter.c          | 147 +---------
 remote.c              |  50 +---
 remote.h              |   1 -
 t/helper/test-reach.c | 104 +++++++
 t/helper/test-tool.c  |   1 +
 t/helper/test-tool.h  |   1 +
 t/t6600-test-reach.sh | 208 +++++++++++++
 upload-pack.c         |  58 +---
 17 files changed, 1095 insertions(+), 600 deletions(-)
 create mode 100644 commit-reach.c
 create mode 100644 commit-reach.h
 create mode 100644 t/helper/test-reach.c
 create mode 100755 t/t6600-test-reach.sh


base-commit: 596e28576ef3ca69432dbe5953b7bdcd18a32876
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-10%2Fderrickstolee%2Freach%2Frefactor-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-10/derrickstolee/reach/refactor-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/10
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 118+ messages in thread

end of thread, other threads:[~2020-11-18 17:54 UTC | newest]

Thread overview: 118+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-07-16 13:00 [PATCH 00/16] Consolidate reachability logic Derrick Stolee via GitGitGadget
2018-06-19 20:25 ` [PATCH 04/16] upload-pack: make reachable() more generic Derrick Stolee via GitGitGadget
2018-06-19 20:35 ` [PATCH 05/16] upload-pack: refactor ok_to_give_up() Derrick Stolee via GitGitGadget
2018-06-25 17:16 ` [PATCH 01/16] commit-reach: move walk methods from commit.c Derrick Stolee via GitGitGadget
2018-07-16 18:57   ` Stefan Beller
2018-07-16 21:31   ` Jonathan Tan
2018-06-25 17:35 ` [PATCH 02/16] commit-reach: move ref_newer from remote.c Derrick Stolee via GitGitGadget
2018-07-16 19:10   ` Stefan Beller
2018-06-25 18:01 ` [PATCH 03/16] commit-reach: move commit_contains from ref-filter Derrick Stolee via GitGitGadget
2018-07-16 19:14   ` Stefan Beller
2018-06-28 12:31 ` [PATCH 15/16] commit-reach: make can_all_from_reach... linear Derrick Stolee via GitGitGadget
2018-07-16 22:37   ` Stefan Beller
2018-07-17  1:16   ` Jonathan Tan
2018-10-01 19:16   ` René Scharfe
2018-10-01 19:26     ` Derrick Stolee
2018-10-01 20:37       ` René Scharfe
2018-10-04 22:59         ` René Scharfe
2018-10-05 12:15           ` Derrick Stolee
2018-10-05 16:51           ` Jeff King
2018-10-05 18:48             ` René Scharfe
2018-10-05 19:08               ` Jeff King
2018-10-05 19:36                 ` René Scharfe
2018-10-05 19:42                   ` Jeff King
2018-10-14 14:29                     ` René Scharfe
2018-10-15 15:31                       ` Derrick Stolee
2018-10-15 16:26                         ` René Scharfe
2018-10-16 23:09                       ` Junio C Hamano
2018-10-17  8:33                       ` Jeff King
2020-11-18  2:16                         ` Jonathan Nieder
2020-11-18  6:54                           ` Jeff King
2020-11-18 17:47                             ` René Scharfe
2018-10-05 19:12             ` Ævar Arnfjörð Bjarmason
2018-10-05 19:28               ` Jeff King
2018-10-05 19:42                 ` Ævar Arnfjörð Bjarmason
2018-10-05 19:44                   ` Jeff King
2018-07-12 20:47 ` [PATCH 06/16] upload-pack: generalize commit date cutoff Derrick Stolee via GitGitGadget
2018-07-16 19:38   ` Stefan Beller
2018-07-18 16:04     ` Derrick Stolee
2018-07-12 20:52 ` [PATCH 07/16] commit-reach: move can_all_from_reach_with_flags Derrick Stolee via GitGitGadget
2018-07-16 22:37   ` Jonathan Tan
2018-07-13 14:06 ` [PATCH 08/16] test-reach: create new test tool for ref_newer Derrick Stolee via GitGitGadget
2018-07-16 23:00   ` Jonathan Tan
2018-07-18 16:14     ` Derrick Stolee
2018-07-13 14:28 ` [PATCH 09/16] test-reach: test in_merge_bases Derrick Stolee via GitGitGadget
2018-07-13 14:38 ` [PATCH 10/16] test-reach: test is_descendant_of Derrick Stolee via GitGitGadget
2018-07-13 14:51 ` [PATCH 11/16] test-reach: test get_merge_bases_many Derrick Stolee via GitGitGadget
2018-07-16 21:24   ` Stefan Beller
2018-07-16 23:08   ` Jonathan Tan
2018-07-13 16:51 ` [PATCH 12/16] test-reach: test reduce_heads Derrick Stolee via GitGitGadget
2018-07-16 21:30   ` Stefan Beller
2018-07-16 21:59     ` Eric Sunshine
2018-07-13 17:22 ` [PATCH 13/16] test-reach: test can_all_from_reach_with_flags Derrick Stolee via GitGitGadget
2018-07-16 21:54   ` Stefan Beller
2018-07-18 16:54     ` Derrick Stolee
2018-07-17  0:10   ` Jonathan Tan
2018-07-13 18:37 ` [PATCH 14/16] commit-reach: replace ref_newer logic Derrick Stolee via GitGitGadget
2018-07-16 22:16   ` Stefan Beller
2018-07-13 19:25 ` [PATCH 16/16] commit-reach: use can_all_from_reach Derrick Stolee via GitGitGadget
2018-07-16 22:47   ` Stefan Beller
2018-07-16 13:54 ` [PATCH 00/16] Consolidate reachability logic Ramsay Jones
2018-07-16 16:18   ` Jeff King
2018-07-16 18:40     ` Eric Sunshine
2018-07-16 18:56       ` Jeff King
2018-07-16 18:59         ` Eric Sunshine
2018-07-18 12:32           ` Johannes Schindelin
2018-07-18 12:23     ` Johannes Schindelin
2018-07-18 19:21       ` Jeff King
2018-07-19 16:34         ` Johannes Schindelin
2018-07-16 17:26   ` Stefan Beller
2018-07-16 18:44     ` Eric Sunshine
2018-07-16 18:47       ` Derrick Stolee
2018-07-18 12:28         ` Johannes Schindelin
2018-07-18 15:01           ` Duy Nguyen
2018-07-18 17:01             ` Junio C Hamano
2018-07-18 17:11               ` Derrick Stolee
2018-07-19 16:37                 ` Johannes Schindelin
2018-07-19 16:32               ` Johannes Schindelin
2018-07-20 16:33 ` [PATCH v2 00/18] " Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 01/18] commit-reach: move walk methods from commit.c Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 02/18] commit.h: remove method declarations Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 03/18] commit-reach: move ref_newer from remote.c Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 04/18] commit-reach: move commit_contains from ref-filter Derrick Stolee
2018-08-28 21:24     ` Jonathan Nieder
2018-08-28 21:33       ` Derrick Stolee
2018-08-28 21:36       ` [PATCH] commit-reach: correct accidental #include of C file Jonathan Nieder
2018-08-28 21:39         ` Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 05/18] upload-pack: make reachable() more generic Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 06/18] upload-pack: refactor ok_to_give_up() Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 07/18] upload-pack: generalize commit date cutoff Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 08/18] commit-reach: move can_all_from_reach_with_flags Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 09/18] test-reach: create new test tool for ref_newer Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 10/18] test-reach: test in_merge_bases Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 11/18] test-reach: test is_descendant_of Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 12/18] test-reach: test get_merge_bases_many Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 13/18] test-reach: test reduce_heads Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 14/18] test-reach: test can_all_from_reach_with_flags Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 15/18] test-reach: test commit_contains Derrick Stolee
2018-07-23 20:35     ` Jonathan Tan
2018-07-25 18:08       ` Junio C Hamano
2018-07-25 18:30         ` Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 16/18] commit-reach: replace ref_newer logic Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear Derrick Stolee
2018-07-23 20:41     ` Jonathan Tan
2018-08-01 20:41       ` Derrick Stolee
2018-09-12  4:14     ` Jeff King
2018-09-12  4:29       ` Jeff King
2018-09-12 13:08         ` Derrick Stolee
2018-07-20 16:33   ` [PATCH v2 18/18] commit-reach: use can_all_from_reach Derrick Stolee
2018-07-20 17:10   ` [PATCH v2 00/18] Consolidate reachability logic Stefan Beller
2018-07-20 17:15     ` Derrick Stolee
2018-07-20 22:16       ` Stefan Beller
2018-08-01 20:33         ` Derrick Stolee
2018-07-20 17:18   ` Derrick Stolee
2018-07-20 18:09     ` Eric Sunshine
2018-07-20 19:14       ` Derrick Stolee
2018-07-20 17:41   ` Duy Nguyen
2018-07-20 19:09     ` Derrick Stolee
2018-07-20 22:45   ` Junio C Hamano

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