[PATCH v6 10/14] commit-graph: close under reachability

From: Derrick Stolee <dsto...@microsoft.com> Teach write_commit_graph() to walk all parents from the commits discovered in packfiles. This prevents gaps given by loose objects or previously-missed packfiles. Also automatically add commits from the existing graph file, if it exists. Sign

[PATCH v6 07/14] commit-graph: implement 'git-commit-graph write'

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to write graph files. Create new test script to verify this command succeeds without failure. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Documentation/git-commit-graph.txt | 39 bu

[PATCH v6 05/14] commit-graph: create git-commit-graph builtin

From: Derrick Stolee <dsto...@microsoft.com> Teach git the 'commit-graph' builtin that will be used for writing and reading packed graph files. The current implementation is mostly empty, except for an '--object-dir' option. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> ---

[PATCH v6 01/14] csum-file: rename hashclose() to finalize_hashfile()

From: Derrick Stolee <dsto...@microsoft.com> The hashclose() method behaves very differently depending on the flags parameter. In particular, the file descriptor is not always closed. Perform a simple rename of "hashclose()" to "finalize_hashfile()" in preparation for f

[PATCH v6 12/14] commit-graph: read only from specific pack-indexes

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to inspect the objects only in a certain list of pack-indexes within the given pack directory. This allows updating the commit graph iteratively. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Docum

[PATCH v6 13/14] commit-graph: build graph from starting commits

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to read commits from stdin when the --stdin-commits flag is specified. Commits reachable from these commits are added to the graph. This is a much faster way to construct the graph than inspecting all packed o

[PATCH v6 09/14] commit-graph: add core.commitGraph setting

From: Derrick Stolee <dsto...@microsoft.com> The commit graph feature is controlled by the new core.commitGraph config setting. This defaults to 0, so the feature is opt-in. The intention of core.commitGraph is that a user can always stop checking for or parsing commit graph

[PATCH v6 14/14] commit-graph: implement "--additive" option

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to add all commits from the existing commit-graph file to the file about to be written. This should be used when adding new commits without performing garbage collection. Signed-off-by: Derrick Stolee <dsto...@micr

[PATCH 1/3] commit: create get_commit_tree() method

/behind information. Create get_commit_tree() as a first step to removing direct references to the 'tree' member of struct commit. Create get_commit_tree_oid() as a shortcut for several references to ">tree->object.oid" in the codebase. Signed-off-by: Derrick Stolee <ds

[PATCH 3/3] commit-graph: lazy-load trees

--graph --oneline -1000 Before: 0.83s After: 0.65s Rel %: -21.6% Adding '-- kernel/' to the command requires loading the root tree for every commit that is walked. There was no measureable performance change as a result of this patch. Signed-off-by: Derrick Stolee <dsto...@microsoft.

Re: [PATCH v7 08/14] commit-graph: implement git commit-graph read

On 4/2/2018 5:33 PM, Junio C Hamano wrote: Derrick Stolee <sto...@gmail.com> writes: From: Derrick Stolee <dsto...@microsoft.com> ... +static int graph_read(int argc, const char **argv) +{ + struct commit_graph *graph = 0; The previous round said NULL above, not

[PATCH 2/3] treewide: use get_commit_tree() for tree access

ation demonstrated a correct transformation. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- blame.c | 18 +- builtin/checkout.c| 17 + builtin/diff.c| 2 +- builtin/fast-export.c | 6 +++--- builtin/log.c |

[PATCH 0/3] Lazy-load trees when reading commit-graph

depends on v7 of ds/commit-graph. Derrick Stolee (3): commit: create get_commit_tree() method treewide: use get_commit_tree() for tree access commit-graph: lazy-load trees blame.c | 18 +- builtin/checkout.c| 17 + builtin/diff.c| 2

Re: [PATCH v2 1/5] core.aheadbehind: add new config setting

On 4/3/2018 6:18 AM, Ævar Arnfjörð Bjarmason wrote: On Tue, Apr 03 2018, Lars Schneider wrote: What is the state of this series? I can't find it in git/git nor in git-for-windows/git. I think Stolee mentioned the config in his Git Merge talk [1] and I was about to test it/roll it out :-) It's

Re: [PATCH 0/3] Lazy-load trees when reading commit-graph

On 4/3/2018 8:00 AM, Derrick Stolee wrote: There are several commit-graph walks that require loading many commits but never walk the trees reachable from those commits. However, the current logic in parse_commit() requires the root tree to be loaded. This only uses lookup_tree(), but when

[PATCH v2 2/4] commit: create get_commit_tree() method

/behind information. Create get_commit_tree() as a first step to removing direct references to the 'maybe_tree' member of struct commit. Create get_commit_tree_oid() as a shortcut for several references to ">maybe_tree->object.oid" in the codebase. Signed-off-by: Derr

[PATCH v2 1/4] treewide: rename tree to maybe_tree

off-by: Derrick Stolee <dsto...@microsoft.com> --- blame.c | 18 +- builtin/checkout.c| 12 ++-- builtin/diff.c| 2 +- builtin/fast-export.c | 6 +++--- builtin/log.c | 4 ++-- builtin/reflog.c | 2 +- commit-graph.c| 4 ++--

[PATCH v2 0/4] Lazy-load trees when reading commit-graph

'-- kernel/' to the command requires loading the root tree for every commit that is walked. There was no measureable performance change as a result of this patch. This patch series depends on v7 of ds/commit-graph. Derrick Stolee (4): treewide: rename tree to maybe_tree commit: create get_commit_tree

Re: [PATCH 3/3] ref-filter: factor ref_array pushing into its own function

/ +struct ref_array_item *ref_array_push(struct ref_array *array, + const char *refname, + const struct object_id *oid); + #endif /* REF_FILTER_H */ The three patches in this series look good to me. Reviewed-by: Derrick Stolee <dsto...@microsoft.com>

Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph

On 4/6/2018 3:21 PM, Jeff King wrote: On Fri, Apr 06, 2018 at 07:09:30PM +, Derrick Stolee wrote: Derrick Stolee (4): treewide: rename tree to maybe_tree commit: create get_commit_tree() method treewide: replace maybe_tree with accessor methods commit-graph: lazy-load trees

[PATCH v2 4/4] commit-graph: lazy-load trees for commits

--graph --oneline -1000 Before: 0.92s After: 0.66s Rel %: -28.3% Adding '-- kernel/' to the command requires loading the root tree for every commit that is walked. There was no measureable performance change as a result of this patch. Signed-off-by: Derrick Stolee <dsto...@microsoft.

[PATCH v2 09/10] commit: use generation numbers for in_merge_bases()

--contains' was tested: Before: 60.0s After: 0.4s Rel %: -99.3% Reported-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 9 - 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index 00bdc2ab21

[PATCH v2 02/10] merge: check config before loading commits

a test to t5318-commit-graph.sh that exercises this code path to prevent a regression. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- builtin/merge.c | 5 +++-- t/t5318-commit-graph.sh | 9 + 2 files changed, 12 insertions(+), 2 deletions(-) diff --git a/builtin/mer

[PATCH v2 10/10] commit: add short-circuit to paint_down_to_common()

After: 0.13s Rel %: -38% Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 13 + 1 file changed, 9 insertions(+), 4 deletions(-) diff --git a/commit.c b/commit.c index 0b155dece8..7348075e38 100644 --- a/commit.c +++ b/commit.c @@ -796,7 +796,9 @@ static int

[PATCH v2 08/10] ref-filter: use generation number for --contains

is containd in v4.13 but no earlier tag, the command 'git tag --contains HEAD' had the following peformance improvement: Before: 0.81s After: 0.04s Rel %: -95% Helped-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- ref-filter.c | 24 +++

[PATCH v8 14/14] commit-graph: implement "--append" option

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to add all commits from the existing commit-graph file to the file about to be written. This should be used when adding new commits without performing garbage collection. Signed-off-by: Derrick Stolee <dsto...@micr

[PATCH v8 13/14] commit-graph: build graph from starting commits

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to read commits from stdin when the --stdin-commits flag is specified. Commits reachable from these commits are added to the graph. This is a much faster way to construct the graph than inspecting all packed o

[PATCH v8 11/14] commit: integrate commit graph with commit parsing

From: Derrick Stolee <dsto...@microsoft.com> Teach Git to inspect a commit graph file to supply the contents of a struct commit when calling parse_commit_gently(). This implementation satisfies all post-conditions on the struct commit, including loading parents, the root tree, and the commi

[PATCH v8 09/14] commit-graph: add core.commitGraph setting

From: Derrick Stolee <dsto...@microsoft.com> The commit graph feature is controlled by the new core.commitGraph config setting. This defaults to 0, so the feature is opt-in. The intention of core.commitGraph is that a user can always stop checking for or parsing commit graph

[PATCH v8 12/14] commit-graph: read only from specific pack-indexes

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to inspect the objects only in a certain list of pack-indexes within the given pack directory. This allows updating the commit graph iteratively. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Docum

Re: What's cooking in git.git (Apr 2018, #01; Mon, 9)

On 4/9/2018 6:08 PM, Junio C Hamano wrote: I guess we'd want a final cleaned-up round after all ;-) Thanks. v8 sent [1]. Thanks. -Stolee [1] https://public-inbox.org/git/20180410125608.39443-1-dsto...@microsoft.com/T/#u

[PATCH v8 10/14] commit-graph: close under reachability

From: Derrick Stolee <dsto...@microsoft.com> Teach write_commit_graph() to walk all parents from the commits discovered in packfiles. This prevents gaps given by loose objects or previously-missed packfiles. Also automatically add commits from the existing graph file, if it exists. Sign

[PATCH v8 07/14] commit-graph: implement git-commit-graph write

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to write graph files. Create new test script to verify this command succeeds without failure. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Documentation/git-commit-graph.txt | 41 ++ builtin/co

[PATCH v8 04/14] graph: add commit graph design document

From: Derrick Stolee <dsto...@microsoft.com> Add Documentation/technical/commit-graph.txt with details of the planned commit graph feature, including future plans. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Documentation/technical/commit-graph.txt | 163 ++

[PATCH v8 08/14] commit-graph: implement git commit-graph read

From: Derrick Stolee <dsto...@microsoft.com> Teach git-commit-graph to read commit graph files and summarize their contents. Use the read subcommand to verify the contents of a commit graph file in the tests. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Documentatio

[PATCH v8 06/14] commit-graph: implement write_commit_graph()

From: Derrick Stolee <dsto...@microsoft.com> Teach Git to write a commit graph file by checking all packed objects to see if they are commits, then store the file in the given object directory. Helped-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto..

[PATCH v8 02/14] csum-file: refactor finalize_hashfile() method

From: Derrick Stolee <dsto...@microsoft.com> If we want to use a hashfile on the temporary file for a lockfile, then we need finalize_hashfile() to fully write the trailing hash but also keep the file descriptor open. Do this by adding a new CSUM_HASH_IN_STREAM flag along with a func

[PATCH v8 03/14] commit-graph: add format document

From: Derrick Stolee <dsto...@microsoft.com> Add document specifying the binary format for commit graphs. This format allows for: * New versions. * New hash functions and hash lengths. * Optional extensions. Basic header information is followed by a binary table of contents into &

[PATCH v8 05/14] commit-graph: create git-commit-graph builtin

From: Derrick Stolee <dsto...@microsoft.com> Teach git the 'commit-graph' builtin that will be used for writing and reading packed graph files. The current implementation is mostly empty, except for an '--object-dir' option. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> ---

[PATCH v8 01/14] csum-file: rename hashclose() to finalize_hashfile()

From: Derrick Stolee <dsto...@microsoft.com> The hashclose() method behaves very differently depending on the flags parameter. In particular, the file descriptor is not always closed. Perform a simple rename of "hashclose()" to "finalize_hashfile()" in preparation for f

[PATCH v8 00/14] Serialized Git Commit Graph

raph' 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

Re: What's cooking in git.git (Apr 2018, #01; Mon, 9)

On 4/10/2018 3:21 PM, Ramsay Jones wrote: On 10/04/18 13:57, Derrick Stolee wrote: On 4/9/2018 6:08 PM, Junio C Hamano wrote: I guess we'd want a final cleaned-up round after all ;-)  Thanks. v8 sent [1]. Thanks. I just tried to 'git am' this series and I could not get it to apply cleanly

Re: [PATCH v8 03/14] commit-graph: add format document

On 4/10/2018 3:10 PM, Stefan Beller wrote: Hi Derrick, On Tue, Apr 10, 2018 at 5:55 AM, Derrick Stolee <sto...@gmail.com> wrote: + OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes) + The ith entry, F[i], stores the number of OIDs with first + byte at most i. Thus F[255]

Re: [PATCH 0/3] Lazy-load trees when reading commit-graph

On 4/3/2018 4:20 PM, Jeff King wrote: On Tue, Apr 03, 2018 at 09:14:50AM -0400, Derrick Stolee wrote: I'm not sure what the exact solution would be, but I imagine something like variable-sized "struct commit"s with the parent pointers embedded, with some kind of flag to indicate

Re: [PATCH 8/6] commit: use generation numbers for in_merge_bases()

On 4/4/2018 11:45 AM, Derrick Stolee wrote: The containment algorithm for 'git branch --contains' is different from that for 'git tag --contains' in that it uses is_descendant_of() instead of contains_tag_algo(). The expensive portion of the branch algorithm is computing merge bases. When

[PATCH 7/6] ref-filter: use generation number for --contains

is containd in v4.13 but no earlier tag, the command 'git tag --contains HEAD' had the following peformance improvement: Before: 0.81s After: 0.04s Rel %: -95% Helped-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- ref-f

[PATCH 8/6] commit: use generation numbers for in_merge_bases()

--contains' was tested: Before: 60.0s After: 0.4s Rel %: -99.3% Reported-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 9 - 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index 858f4fdbc9

Re: [PATCH 7/6] ref-filter: use generation number for --contains

On 4/4/2018 3:16 PM, Jeff King wrote: On Wed, Apr 04, 2018 at 03:06:26PM -0400, Derrick Stolee wrote: @@ -1615,8 +1619,20 @@ static enum contains_result contains_tag_algo(struct commit *candidate, struct contains_cache *cache) { struct

Re: [PATCH 8/6] commit: use generation numbers for in_merge_bases()

On 4/4/2018 2:24 PM, Jeff King wrote: On Wed, Apr 04, 2018 at 11:48:42AM -0400, Derrick Stolee wrote: diff --git a/commit.c b/commit.c index 858f4fdbc9..2566cba79f 100644 --- a/commit.c +++ b/commit.c @@ -1059,12 +1059,19 @@ int in_merge_bases_many(struct commit *commit, int nr_reference

Re: [PATCH 7/6] ref-filter: use generation number for --contains

On 4/4/2018 2:22 PM, Jeff King wrote: On Wed, Apr 04, 2018 at 11:45:53AM -0400, Derrick Stolee wrote: @@ -1615,8 +1619,20 @@ static enum contains_result contains_tag_algo(struct commit *candidate, struct contains_cache *cache) { struct

Re: [PATCH v2 04/10] commit-graph: compute generation numbers

On 4/10/2018 10:51 PM, Junio C Hamano wrote: Derrick Stolee <dsto...@microsoft.com> writes: + if ((*list)->generation != GENERATION_NUMBER_INFINITY) { + if ((*list)->generation > GENERATION_NUMBER_MAX) + die(&qu

Re: [PATCH v2 02/10] merge: check config before loading commits

On 4/10/2018 10:12 PM, Junio C Hamano wrote: Derrick Stolee <dsto...@microsoft.com> writes: diff --git a/builtin/merge.c b/builtin/merge.c index ee050a47f3..20897f8223 100644 --- a/builtin/merge.c +++ b/builtin/merge.c @@ -1183,13 +1183,14 @@ int cmd_merge(int argc, const char **argv,

Re: [PATCH v2 03/10] commit: add generation number to struct commmit

On 4/10/2018 10:31 PM, Junio C Hamano wrote: Derrick Stolee <dsto...@microsoft.com> writes: The generation number of a commit is defined recursively as follows: * If a commit A has no parents, then the generation number of A is one. * If a commit A has parents, then the generation

Re: [PATCH v2 06/10] commit.c: use generation to halt paint walk

On 4/10/2018 11:02 PM, Junio C Hamano wrote: Derrick Stolee <dsto...@microsoft.com> writes: @@ -800,17 +810,26 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc return result; } prio_queue_put(, one); + i

Re: [PATCH resend] SubmittingPatches: mention the git contacts command

On 4/11/2018 4:20 PM, Thomas Gummerer wrote: Instead of just mentioning 'git blame' and 'git shortlog', which make it quite hard for new contributors to pick out the appropriate list of people to cc on their patch series, mention the 'git contacts' utility, which makes it much easier to get a

Re: [PATCHv3 00/15] replace_object.c: rename to use dash in file name

On 4/11/2018 8:21 PM, Stefan Beller wrote: v3: * interdiff below, the only changes are renaming the variable - struct ref_store *main_ref_store; + struct ref_store *refs; in struct repository. as well as dropping the file rename patch. * improved commit messages from

Re: [PATCH v8 03/14] commit-graph: add format document

On 4/11/2018 4:58 PM, Jakub Narebski wrote: Derrick Stolee <sto...@gmail.com> writes: +CHUNK DATA: + + OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes) + The ith entry, F[i], stores the number of OIDs with first + byte at most i. Thus F[255] stores the total +

Re: [PATCH v2 07/10] commit-graph.txt: update future work

On 4/12/2018 5:12 AM, Junio C Hamano wrote: Derrick Stolee <dsto...@microsoft.com> writes: +Here is a diagram to visualize the shape of the full commit graph, and +how different generation numbers relate: + ++-+ +| GENERATION_NUMBER_IN

Re: [PATCH 0/6] Compute and consume generation numbers

On 4/11/2018 3:32 PM, Jakub Narebski wrote: What would you suggest as a good test that could imply performance? The Google Colab notebook linked to above includes a function to count number of commits (nodes / vertices in the commit graph) walked, currently in the worst case scenario. The two

[PATCH v2 04/10] commit-graph: compute generation numbers

commits to the commit-graph file. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit-graph.c | 46 ++ 1 file changed, 46 insertions(+) diff --git a/commit-graph.c b/commit-graph.c index d24b947525..5fd63acc31 100644 --- a/commit-g

[PATCH v2 07/10] commit-graph.txt: update future work

We now calculate generation numbers in the commit-graph file and use them in paint_down_to_common(). Expand the section on generation numbers to discuss how the two "special" generation numbers GENERATION_NUMBER_INFINITY and *_ZERO interact with other generation numbers. Signed-off-b

[PATCH v2 06/10] commit.c: use generation to halt paint walk

the minimum generation number of a commit that enters the queue with nonstale status. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 37 ++--- 1 file changed, 30 insertions(+), 7 deletions(-) diff --git a/commit.c b/commit.c index 95ae

[PATCH v2 05/10] commit: use generations in paint_down_to_common()

ers avoids this extra effort, even if it is somewhat rare. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 19 ++- commit.h | 1 + 2 files changed, 19 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index 3e39c86abf..95ae7e13a3 100644 --- a/commit.

[PATCH v2 00/10] Compute and consume generation numbers

roviding a significant speedup (at least 95% for some cases). A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively. This patch series depends on v7 of ds/commit-graph. Derrick Stolee (10): object.c: parse commit in graph first

[PATCH v2 03/10] commit: add generation number to struct commmit

. The second (_ZERO) means the generation number was loaded from a commit graph file that was stored before generation numbers were computed. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- alloc.c| 1 + commit-graph.c | 2 ++ commit.h | 4 3 files changed, 7 inse

[PATCH v2 01/10] object.c: parse commit in graph first

need to ensure that any commit that exists in the graph is loaded from the graph, so check parse_commit_in_graph() before calling parse_commit_buffer(). Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- object.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/ob

Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph

On 4/8/2018 7:18 PM, Junio C Hamano wrote: Jeff King writes: If I were doing it myself, I probably would have folded patches 1 and 3 together. They are touching all the same spots, and it would be an error for any case converted in patch 1 to not get converted in patch 3. I'm

Re: What's cooking in git.git (Apr 2018, #01; Mon, 9)

On 4/9/2018 6:21 AM, Junio C Hamano wrote: * ds/commit-graph (2018-04-02) 16 commits - commit-graph: implement "--additive" option - commit-graph: build graph from starting commits - commit-graph: read only from specific pack-indexes - commit: integrate commit graph with commit parsing

Re: [PATCH 02/19] replace-object: move replace_object to object store

On 4/6/2018 7:21 PM, Stefan Beller wrote: Refs belong to particular repositories, so the replacements defined by them should belong to a particular repository as well. Move the definition of a single object replacement to a new header "replace-object.h". While at it replace the hardcoded 20 by

Re: [RFC PATCH 00/19] object-store refactoring 3 (replace objects, main ref store)

these patches and only found one set of whitespace errors. Compiles and tests fine on my machine. Reviewed-by: Derrick Stolee <dsto...@microsoft.com>

Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph

On 4/7/2018 2:40 PM, Jakub Narebski wrote: Derrick Stolee <dsto...@microsoft.com> writes: [...] On the Linux repository, performance tests were run for the following command: git log --graph --oneline -1000 Before: 0.92s After: 0.66s Rel %: -28.3% Adding '--

Re: [PATCH 0/6] Compute and consume generation numbers

On 4/7/2018 12:55 PM, Jakub Narebski wrote: Currently I am at the stage of reproducing results in FELINE paper: "Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach" by Renê R. Veloso, Loïc Cerf, Wagner Meira Jr and Mohammed J. Zaki (2014). This paper is available

Re: [PATCH 7/6] ref-filter: use generation number for --contains

On 4/4/2018 3:42 PM, Jeff King wrote: On Wed, Apr 04, 2018 at 03:22:01PM -0400, Derrick Stolee wrote: That is the idea. I should make this clearer in all of my commit messages. Yes, please. :) And maybe in the documentation of the file format, if it's not there (I didn't check). It's a very

Re: [PATCH v3 3/9] commit: use generations in paint_down_to_common()

On 4/18/2018 10:31 AM, Jakub Narebski wrote: Derrick Stolee <dsto...@microsoft.com> writes: Define compare_commits_by_gen_then_commit_date(), which uses generation numbers as a primary comparison and commit date to break ties (or as a comparison when both commits do not have co

Re: What's cooking in git.git (Apr 2018, #02; Tue, 17)

to say "this one is good" with good enough understanding of both the issue the series addresses and the solution in the series. I'm sorry that my second message was terse. My response to v1 [1] was > I looked through these patches and only found one set of whitespace > errors. Compi

[PATCH v3 8/9] commit-graph: always load commit-graph information

the given buffer. Only fill this information when specified by the 'check_graph' parameter. This avoids duplicate work when we already checked the graph in parse_commit_gently() or when simply checking the buffer contents in check_commit(). Signed-off-by: Derrick Stolee <dsto...@microsoft.

[PATCH v3 4/9] commit-graph.txt: update design document

-by: Derrick Stolee <dsto...@microsoft.com> --- Documentation/technical/commit-graph.txt | 30 +++- 1 file changed, 24 insertions(+), 6 deletions(-) diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt index 0550c6d0dc..d9f2713efa

[PATCH v3 9/9] merge: check config before loading commits

test to t5318-commit-graph.sh that exercises this code path to prevent a regression. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- builtin/merge.c | 5 +++-- t/t5318-commit-graph.sh | 9 + 2 files changed, 12 insertions(+), 2 deletions(-) diff --git a/builtin/merge.

[PATCH v3 7/9] commit: add short-circuit to paint_down_to_common()

After: 0.13s Rel %: -38% Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 18 ++ 1 file changed, 14 insertions(+), 4 deletions(-) diff --git a/commit.c b/commit.c index bceb79c419..a70f120878 100644 --- a/commit.c +++ b/commit.c @@ -805,11 +8

[PATCH v3 2/9] commit-graph: compute generation numbers

commits to the commit-graph file. If a computed generation number would exceed GENERATION_NUMBER_MAX, then use GENERATION_NUMBER_MAX instead. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit-graph.c | 46 ++ 1 file changed, 46 inse

[PATCH v3 1/9] commit: add generation number to struct commmit

-by: Derrick Stolee <dsto...@microsoft.com> --- alloc.c| 1 + commit-graph.c | 2 ++ commit.h | 4 3 files changed, 7 insertions(+) diff --git a/alloc.c b/alloc.c index cf4f8b61e1..e8ab14f4a1 100644 --- a/alloc.c +++ b/alloc.c @@ -94,6 +94,7 @@ void *alloc_commit_nod

[PATCH v3 6/9] commit: use generation numbers for in_merge_bases()

--contains' was tested: Before: 60.0s After: 0.4s Rel %: -99.3% Reported-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 9 - 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index a44899c733

[PATCH v3 0/9] Compute and consume generation numbers

h series is build on ds/lazy-load-trees. Derrick Stolee (9): commit: add generation number to struct commmit commit-graph: compute generation numbers commit: use generations in paint_down_to_common() commit-graph.txt: update design document ref-filter: use generation number for --contains

[PATCH v3 3/9] commit: use generations in paint_down_to_common()

ers avoids this extra effort, even if it is somewhat rare. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 20 +++- commit.h | 1 + 2 files changed, 20 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index 711f674c18..a44899c733 100644 --- a/commit.

[PATCH v3 5/9] ref-filter: use generation number for --contains

in v4.13 but no earlier tag, the command 'git tag --contains HEAD' had the following peformance improvement: Before: 0.81s After: 0.04s Rel %: -95% Helped-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- ref-filter.c | 23 +++

Re: [PATCH v3 5/9] ref-filter: use generation number for --contains

On 4/24/2018 2:56 PM, Jakub Narebski wrote: Derrick Stolee <sto...@gmail.com> writes: One way to fix this is to call 'prepare_commit_graph()' directly and then test that 'commit_graph' is non-null before performing any parses. I'm not thrilled with how that couples the commit

[PATCH v4 01/10] ref-filter: fix outdated comment on in_commit_list

The in_commit_list() method does not check the parents of the candidate for containment in the list. Fix the comment that incorrectly states that it does. Reported-by: Jakub Narebski <jna...@gmail.com> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- ref-filter.c | 2 +- 1

[PATCH v4 00/10] Compute and consume generation numbers

for 'git tag --contains), providing a significant speedup (at least 95% for some cases). A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively. This patch series is built on ds/lazy-load-trees. Derrick Stolee (10): ref-filter:

[PATCH v4 03/10] commit-graph: compute generation numbers

commits to the commit-graph file. If a computed generation number would exceed GENERATION_NUMBER_MAX, then use GENERATION_NUMBER_MAX instead. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit-graph.c | 45 + 1 file changed, 45 inse

[PATCH v4 02/10] commit: add generation number to struct commmit

-by: Derrick Stolee <dsto...@microsoft.com> --- alloc.c| 1 + commit-graph.c | 2 ++ commit.h | 4 3 files changed, 7 insertions(+) diff --git a/alloc.c b/alloc.c index cf4f8b61e1..e8ab14f4a1 100644 --- a/alloc.c +++ b/alloc.c @@ -94,6 +94,7 @@ void *alloc_commit_nod

[PATCH v4 07/10] commit: use generation numbers for in_merge_bases()

--contains' was tested: Before: 60.0s After: 0.4s Rel %: -99.3% Reported-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 9 - 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index 39a3749abd

[PATCH v4 04/10] commit: use generations in paint_down_to_common()

ers avoids this extra effort, even if it is somewhat rare. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 20 +++- commit.h | 1 + 2 files changed, 20 insertions(+), 1 deletion(-) diff --git a/commit.c b/commit.c index 711f674c18..4d00b0a1d6 100644 --- a/commit.

[PATCH v4 05/10] commit-graph: always load commit-graph information

the given buffer. Only fill this information when specified by the 'check_graph' parameter. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit-graph.c | 45 ++--- commit-graph.h | 8 commit.c | 7 +-- commit.h

[PATCH v4 08/10] commit: add short-circuit to paint_down_to_common()

After: 0.13s Rel %: -38% Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- commit.c | 18 ++ 1 file changed, 14 insertions(+), 4 deletions(-) diff --git a/commit.c b/commit.c index 7bb007f56a..e2e16ea1a7 100644 --- a/commit.c +++ b/commit.c @@ -808,11 +8

[PATCH v4 06/10] ref-filter: use generation number for --contains

is containd in v4.13 but no earlier tag, the command 'git tag --contains HEAD' had the following peformance improvement: Before: 0.81s After: 0.04s Rel %: -95% Helped-by: Jeff King <p...@peff.net> Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- ref-filter.c | 24 +++

[PATCH v4 10/10] commit-graph.txt: update design document

-by: Derrick Stolee <dsto...@microsoft.com> --- Documentation/technical/commit-graph.txt | 30 +++- 1 file changed, 24 insertions(+), 6 deletions(-) diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt index 0550c6d0dc..d9f2713efa

[PATCH v4 09/10] merge: check config before loading commits

test to t5318-commit-graph.sh that exercises this code path to prevent a regression. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- builtin/merge.c | 7 --- t/t5318-commit-graph.sh | 9 + 2 files changed, 13 insertions(+), 3 deletions(-) diff --git a/builtin/merge.

Re: [PATCH v4 00/10] Compute and consume generation numbers

As promised, here is the diff from v3. Thanks, -Stolee -- >8 -- diff --git a/builtin/merge.c b/builtin/merge.c index 7e1da6c6ea..b819756946 100644 --- a/builtin/merge.c +++ b/builtin/merge.c @@ -1148,6 +1148,7 @@ int cmd_merge(int argc, const char **argv, const char *prefix)     branch =

Re: [PATCH v3 6/9] commit: use generation numbers for in_merge_bases()

On 4/18/2018 6:15 PM, Jakub Narebski wrote: Derrick Stolee <dsto...@microsoft.com> writes: The containment algorithm for 'git branch --contains' is different from that for 'git tag --contains' in that it uses is_descendant_of() instead of contains_tag_algo(). The expensive p

Re: [PATCH v3 7/9] commit: add short-circuit to paint_down_to_common()

On 4/18/2018 7:19 PM, Jakub Narebski wrote: Derrick Stolee <dsto...@microsoft.com> writes: [...] [...], and this saves time during 'git branch --contains' queries that would otherwise walk "around" the commit we are inspecting. If I understand the code properly, what happen

<    4   5   6   7   8   9   10   11   12   13   >