Re: [PATCH] Use path comparison for patch ids before the file content

[Johannes Schindelin]

Hi Kevin,

congratulations for your first patch on the Git mailing list!

On Thu, 14 Jul 2016, Kevin Willford wrote:

> When limiting the list in a revision walk using cherry pick, patch ids are
> calculated by producing the diff of the content of the files.  This would
> be more efficent by using a patch id looking at the paths that were
> changed in the commits and only if all the file changed are the same fall
> back to getting the content of the files in the commits to determine if
> the commits are the same.
> 
> This change uses a hashmap to store entries with a hash of the patch id
> calculated by just using the file paths.  The entries constist of the
> commit and the patch id calculated using file contents which is initially
> empty.  If there are commits that are found in the hashmap it means that
> the same files were changed in the commits and the file contents need to
> be checked in order to determine if the commits are truly the same.  The
> patch id that is calcuated based on the file contents is then stored in the
> hashmap entry if needed in later comparisons.  If the commits are determined 
> to be
> the same the cherry_flag is set on the commit being checked as well as the
> commit in the hashmap entry saving running though the original list of
> commits checking a seen flag.  This will speed up a rebase where the
> upstream has many changes but none of them have been pulled into the
> current branch.
> ---

How about pulling out the change that replaces patch-id's ad-hoc hashmap
with the struct hashmap solution?

It would become a two-part patch series, then.

BTW I tried my hand at a different commit message, maybe you want to
cherry-pick parts of it?

-- snip --
rebase: avoid computing unnecessary patch IDs

The `rebase` family of Git commands avoid applying patches that were
already integrated upstream. They do that by using the revision walking
option that computes the patch IDs of the two sides of the rebase
(local-only patches vs upstream-only ones) and skipping those local
patches whose patch ID matches one of the upstream ones.

In many cases, this causes unnecessary churn, as already the set of
paths touched by a given commit would suffice to determine that an
upstream patch has no local equivalent.

This hurts performance in particular when there are a lot of upstream
patches, and/or large ones.

Therefore, let's introduce the concept of a "header-only" patch ID,
compare those first, and only evaluate the "full" patch ID lazily.

Please note that in contrast to the "full" patch IDs, those "header-only"
patch IDs are prone to collide with one another, as adjacent commits
frequently touch the very same files. Hence we now have to be careful to
allow multiple hash entries with the same hash.
-- snap --

And as Junio pointed out, please add your Signed-off-by: lines (see
https://github.com/git/git/blob/v2.9.1/Documentation/SubmittingPatches#L239-L291
for an explanation).

And here are a couple of comments on the code (please read all the way to
the end, I cut the parts that I do not address):

> diff --git a/diff.c b/diff.c
> index fa78fc1..f38b663 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -4449,7 +4449,7 @@ static void patch_id_consume(void *priv, char *line, 
> unsigned long len)
>  }
>  
>  /* returns 0 upon success, and writes result into sha1 */
> -static int diff_get_patch_id(struct diff_options *options, unsigned char 
> *sha1)
> +static int diff_get_patch_id(struct diff_options *options, unsigned char 
> *sha1, int use_path_only)

If we used `diff_header_only`, we could address Junio's concern about the
naming of this parameter.

> diff --git a/patch-ids.c b/patch-ids.c
> index a4d0016..f0262ce 100644
> --- a/patch-ids.c
> +++ b/patch-ids.c
> @@ -4,8 +4,9 @@
>  #include "sha1-lookup.h"
>  #include "patch-ids.h"
>  
> -int commit_patch_id(struct commit *commit, struct diff_options *options,
> - unsigned char *sha1)
> +
> +static int ll_commit_patch_id(struct commit *commit, struct diff_options 
> *options,

How about simply changing the signature of the commit_patch_id() function?
It's not like Git guarantees any kind of stable API of its libgit.a or
something.

> +int commit_patch_id(struct commit *commit, struct diff_options *options,
> + unsigned char *sha1)
>  {
> - return sha1_pos(id, table, nr, patch_id_access);
> + return ll_commit_patch_id(commit, options, sha1, 0);
>  }
>  
> -#define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */
> -struct patch_id_bucket {
> - struct patch_id_bucket *next;
> - int nr;
> - struct patch_id bucket[BUCKET_SIZE];
> -};

The idea of the original code was to get as close to 4kB for the initial
(and probably final) hashmap. I do not think we can, or have to, achieve
the same with struct hashmap. But we should use a larger initial size than
64 (maybe 128? I would actually go for 256, even if that roughly doubles
the initial hashmap size) by passing an explicit 

Re: [PATCH] Use path comparison for patch ids before the file content

[Junio C Hamano]

Kevin Willford  writes:

> When limiting the list in a revision walk using cherry pick, patch ids are
> calculated by producing the diff of the content of the files.  This would
> be more efficent by using a patch id looking at the paths that were
> changed in the commits and only if all the file changed are the same fall
> back to getting the content of the files in the commits to determine if
> the commits are the same.

The basic idea of this change makes sense.  When we have many
commits, but if we can tell that no other commit changes the same
set of paths as this commit does, we can immediately know that this
commit cannot have an equivalent other commit among the rest.  By
first computing a lot cheaper "hash of touched paths" for commits,
and throwing them into separate bins keyed by the "hash of touched
paths", you can narrow the commits whose patch IDs must be compared,
and if a bin happens to be a singleton, you do not even need to
produce any patch ID by running a textual diff.  I like it.

Explaining this as "hash of touched paths" is somewhat misleading.
Your "use_path_only" mode actually hashes a lot more than just
paths.  Because the "use_path_only" mode actually hashes the entire
basic diff header and not just paths, it can differentiate a commit
that adds a file and another commit that modifies the same file, for
example.

> ...  This will speed up a rebase where the
> upstream has many changes but none of them have been pulled into the
> current branch.
> ---

Missing sign-off.

>  diff.c  |  16 +
>  diff.h  |   2 +-

The changes in the above two files looked OK to me.
I didn't read the changes to the other three files carefully.

>  patch-ids.c | 114 
> +---
>  patch-ids.h |   7 ++--
>  revision.c  |  19 ++
>  5 files changed, 73 insertions(+), 85 deletions(-)

>
> diff --git a/patch-ids.c b/patch-ids.c
> index a4d0016..f0262ce 100644
> --- a/patch-ids.c
> +++ b/patch-ids.c
> @@ -4,8 +4,9 @@
> ...
> +}
> \ No newline at end of file

No newline at end of file.


Thanks.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH] Use path comparison for patch ids before the file content

[Kevin Willford]

When limiting the list in a revision walk using cherry pick, patch ids are
calculated by producing the diff of the content of the files.  This would
be more efficent by using a patch id looking at the paths that were
changed in the commits and only if all the file changed are the same fall
back to getting the content of the files in the commits to determine if
the commits are the same.

This change uses a hashmap to store entries with a hash of the patch id
calculated by just using the file paths.  The entries constist of the
commit and the patch id calculated using file contents which is initially
empty.  If there are commits that are found in the hashmap it means that
the same files were changed in the commits and the file contents need to
be checked in order to determine if the commits are truly the same.  The
patch id that is calcuated based on the file contents is then stored in the
hashmap entry if needed in later comparisons.  If the commits are determined to 
be
the same the cherry_flag is set on the commit being checked as well as the
commit in the hashmap entry saving running though the original list of
commits checking a seen flag.  This will speed up a rebase where the
upstream has many changes but none of them have been pulled into the
current branch.
---
 diff.c  |  16 +
 diff.h  |   2 +-
 patch-ids.c | 114 +---
 patch-ids.h |   7 ++--
 revision.c  |  19 ++
 5 files changed, 73 insertions(+), 85 deletions(-)

diff --git a/diff.c b/diff.c
index fa78fc1..f38b663 100644
--- a/diff.c
+++ b/diff.c
@@ -4449,7 +4449,7 @@ static void patch_id_consume(void *priv, char *line, 
unsigned long len)
 }
 
 /* returns 0 upon success, and writes result into sha1 */
-static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)
+static int diff_get_patch_id(struct diff_options *options, unsigned char 
*sha1, int use_path_only)
 {
struct diff_queue_struct *q = _queued_diff;
int i;
@@ -4484,9 +4484,6 @@ static int diff_get_patch_id(struct diff_options 
*options, unsigned char *sha1)
 
diff_fill_sha1_info(p->one);
diff_fill_sha1_info(p->two);
-   if (fill_mmfile(, p->one) < 0 ||
-   fill_mmfile(, p->two) < 0)
-   return error("unable to read files to diff");
 
len1 = remove_space(p->one->path, strlen(p->one->path));
len2 = remove_space(p->two->path, strlen(p->two->path));
@@ -4521,6 +4518,13 @@ static int diff_get_patch_id(struct diff_options 
*options, unsigned char *sha1)
len2, p->two->path);
git_SHA1_Update(, buffer, len1);
 
+   if (use_path_only)
+   continue;
+
+   if (fill_mmfile(, p->one) < 0 ||
+   fill_mmfile(, p->two) < 0)
+   return error("unable to read files to diff");
+
if (diff_filespec_is_binary(p->one) ||
diff_filespec_is_binary(p->two)) {
git_SHA1_Update(, sha1_to_hex(p->one->sha1), 40);
@@ -4541,11 +4545,11 @@ static int diff_get_patch_id(struct diff_options 
*options, unsigned char *sha1)
return 0;
 }
 
-int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1)
+int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1, int 
use_path_only)
 {
struct diff_queue_struct *q = _queued_diff;
int i;
-   int result = diff_get_patch_id(options, sha1);
+   int result = diff_get_patch_id(options, sha1, use_path_only);
 
for (i = 0; i < q->nr; i++)
diff_free_filepair(q->queue[i]);
diff --git a/diff.h b/diff.h
index 125447b..7883729 100644
--- a/diff.h
+++ b/diff.h
@@ -342,7 +342,7 @@ extern int run_diff_files(struct rev_info *revs, unsigned 
int option);
 extern int run_diff_index(struct rev_info *revs, int cached);
 
 extern int do_diff_cache(const unsigned char *, struct diff_options *);
-extern int diff_flush_patch_id(struct diff_options *, unsigned char *);
+extern int diff_flush_patch_id(struct diff_options *, unsigned char *, int);
 
 extern int diff_result_code(struct diff_options *, int);
 
diff --git a/patch-ids.c b/patch-ids.c
index a4d0016..f0262ce 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -4,8 +4,9 @@
 #include "sha1-lookup.h"
 #include "patch-ids.h"
 
-int commit_patch_id(struct commit *commit, struct diff_options *options,
-   unsigned char *sha1)
+
+static int ll_commit_patch_id(struct commit *commit, struct diff_options 
*options,
+   unsigned char *sha1, int use_path_only)
 {
if (commit->parents)
diff_tree_sha1(commit->parents->item->object.oid.hash,
@@ -13,93 +14,90 @@ int commit_patch_id(struct commit *commit, struct 
diff_options *options,
else
diff_root_tree_sha1(commit->object.oid.hash, "",