Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Johannes Schindelin]

Hi Junio,

On Wed, 3 Aug 2016, Junio C Hamano wrote:

> Junio C Hamano  writes:
> 
> > I do not think negative (or non-zero) return is an "abuse" at all.
> > It is misleading in the context of the function whose name has "cmp"
> > in it, but that is not the fault of this function, rather, the
> > breakage is more in the API that calls a function that wants to know
> > only equality a "cmp".  A in-code comment before the function name
> > may be appropriate:
> >
> > /*
> >  * hashmap API calls hashmap_cmp_fn, but it only wants
> >  * "does the key match the entry?" with 0 (matches) and
> >  * non-zero (does not match).
> >  */
> > static int patch_id_match(const struct patch_id *ent,
> >   const struct patch_id *key,
> >   const void *keydata)
> > {
> > ...
> 
> How about this one instead (to be squashed into 4/4)?
> 
> The updated wording directly addresses the puzzlement I initially
> felt "This returns error() which is always negative, so comparing
> (A, B) would say A < B, while comparing (B, A) would say B < A.
> Would it cause a problem in the caller?" while reading the function
> by being explicit that the sign does not matter.

Please squash it in. Kevin is on vacation and I am sure he is fine with
this change.

Thanks,
Dscho
--
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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Junio C Hamano]

Junio C Hamano  writes:

> I do not think negative (or non-zero) return is an "abuse" at all.
> It is misleading in the context of the function whose name has "cmp"
> in it, but that is not the fault of this function, rather, the
> breakage is more in the API that calls a function that wants to know
> only equality a "cmp".  A in-code comment before the function name
> may be appropriate:
>
> /*
>  * hashmap API calls hashmap_cmp_fn, but it only wants
>  * "does the key match the entry?" with 0 (matches) and
>  * non-zero (does not match).
>  */
> static int patch_id_match(const struct patch_id *ent,
>   const struct patch_id *key,
>   const void *keydata)
> {
> ...

How about this one instead (to be squashed into 4/4)?

The updated wording directly addresses the puzzlement I initially
felt "This returns error() which is always negative, so comparing
(A, B) would say A < B, while comparing (B, A) would say B < A.
Would it cause a problem in the caller?" while reading the function
by being explicit that the sign does not matter.

 patch-ids.c | 10 ++
 1 file changed, 10 insertions(+)

diff --git a/patch-ids.c b/patch-ids.c
index 0a4828a..082412a 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -16,6 +16,16 @@ int commit_patch_id(struct commit *commit, struct 
diff_options *options,
return diff_flush_patch_id(options, sha1, diff_header_only);
 }
 
+/*
+ * When we cannot load the full patch-id for both commits for whatever
+ * reason, the function returns -1 (i.e. return error(...)). Despite
+ * the "cmp" in the name of this function, the caller only cares about
+ * the return value being zero (a and b are equivalent) or non-zero (a
+ * and b are different), and returning non-zero would keep both in the
+ * result, even if they actually were equivalent, in order to err on
+ * the side of safety.  The actual value being negative does not have
+ * any significance; only that it is non-zero matters.
+ */
 static int patch_id_cmp(struct patch_id *a,
struct patch_id *b,
struct diff_options *opt)
--
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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Junio C Hamano]

Johannes Schindelin  writes:

>> Perhaps hashmap API needs fixing in the longer term not to call this
>> type hashmap_cmp_fn; instead it should lose cmp and say something
>> like hashmap_eq_fn or something.
>
> Maybe.
>
> But to make sure: you do not expect Kevin to do that in the context of
> this here patch series, right?

I think I already answered this in the message you are responding
to.

> Do you want a note in the commit message about this "abuse" of a negative
> return value, or a code comment?

I do not think negative (or non-zero) return is an "abuse" at all.
It is misleading in the context of the function whose name has "cmp"
in it, but that is not the fault of this function, rather, the
breakage is more in the API that calls a function that wants to know
only equality a "cmp".  A in-code comment before the function name
may be appropriate:

/*
 * hashmap API calls hashmap_cmp_fn, but it only wants
 * "does the key match the entry?" with 0 (matches) and
 * non-zero (does not match).
 */
static int patch_id_match(const struct patch_id *ent,
  const struct patch_id *key,
  const void *keydata)
{
...

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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Junio C Hamano]

Jakub Narębski  writes:

> The problem is that one expects hashmap_cmp_fn() to return ==0 on equality,
> while one would expect for hashmap_eq_fn() to return true (==1) on equality.
> So we would have to rewrite all calling sites.

Yes, and I do not think it is a "problem".  There only are about a
dozen callsites of hashmap_init().

> It would be nice to have a comment about how hashmap uses cmpfn in
> hashmap.h.  

That is the absolute minimum but I think that is already done in the
Documentation/technical/api-hashmap.txt.

> Though... currently our hashmap implementation uses linked
> list (separate chaining) for handling hash collisions (for collision
> resolution). More sophisticated data structures, such as balanced search
> trees,...

But that requires total ordering of the elements registered in a
hashmap.  So far, because cmp_fn that was misnamed was only about
equality, you can safely use a hashmap to store things that do not
have inherent order among them.  Besides, if your hashmap has to
optimize the hash collision resolution part with complex strucure,
your hash function is bad or your hash bucket growing strategy is
suboptimal, or both, which is the first thing you should look at,
not the "now how would we find it in the bucket with too many
things?"

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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Johannes Schindelin]

Hi Junio,

On Mon, 1 Aug 2016, Junio C Hamano wrote:

> Johannes Schindelin  writes:
> 
> > On Fri, 29 Jul 2016, Junio C Hamano wrote:
> >
> >> Kevin Willford  writes:
> >> 
> >> >  static int patch_id_cmp(struct patch_id *a,
> >> >  struct patch_id *b,
> >> > -void *keydata)
> >> > +struct diff_options *opt)
> >> >  {
> >> > +if (is_null_sha1(a->patch_id) &&
> >> > +commit_patch_id(a->commit, opt, a->patch_id, 0))
> >> > +return error("Could not get patch ID for %s",
> >> > +oid_to_hex(>commit->object.oid));
> >> > +if (is_null_sha1(b->patch_id) &&
> >> > +commit_patch_id(b->commit, opt, b->patch_id, 0))
> >> > +return error("Could not get patch ID for %s",
> >> > +oid_to_hex(>commit->object.oid));
> >> >  return hashcmp(a->patch_id, b->patch_id);
> >> >  }
> >> 
> >> These error returns initially looks slightly iffy in that in general
> >> the caller of any_cmp_fn() wants to know how a/b compares, but by
> >> returning error(), it always says "a is smaller than b".
> >
> > I am to blame, as this is my design.
> >
> > And yes, it is kind of funny that we require a cmpfn that returns <0, ==0
> > and >0 for comparisons, when hashmaps try to avoid any order.
> 
> Perhaps hashmap API needs fixing in the longer term not to call this
> type hashmap_cmp_fn; instead it should lose cmp and say something
> like hashmap_eq_fn or something.

Maybe.

But to make sure: you do not expect Kevin to do that in the context of
this here patch series, right?

Ciao,
Dscho
--
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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Jakub Narębski]

W dniu 01.08.2016 o 22:11, Junio C Hamano pisze:
> Johannes Schindelin  writes:
>> On Fri, 29 Jul 2016, Junio C Hamano wrote:

>>> These error returns initially looks slightly iffy in that in general
>>> the caller of any_cmp_fn() wants to know how a/b compares, but by
>>> returning error(), it always says "a is smaller than b".
>>
>> I am to blame, as this is my design.
>>
>> And yes, it is kind of funny that we require a cmpfn that returns <0, ==0
>> and >0 for comparisons, when hashmaps try to avoid any order.
> 
> Perhaps hashmap API needs fixing in the longer term not to call this
> type hashmap_cmp_fn; instead it should lose cmp and say something
> like hashmap_eq_fn or something.

The problem is that one expects hashmap_cmp_fn() to return ==0 on equality,
while one would expect for hashmap_eq_fn() to return true (==1) on equality.
So we would have to rewrite all calling sites.

It would be nice to have a comment about how hashmap uses cmpfn in
hashmap.h.  


Though... currently our hashmap implementation uses linked
list (separate chaining) for handling hash collisions (for collision
resolution). More sophisticated data structures, such as balanced search
trees, or splay trees, are worth considering only if the load factor is
large, or if the hash distribution is likely to be very non-uniform,
or if one must guarantee good performance even in a worst-case scenario.
So almost certainly comparing function (which is needed for trees)
won't be needed.

Best,
-- 
Jakub Narębski

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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Junio C Hamano]

Johannes Schindelin  writes:

> Hi Junio,
>
> On Fri, 29 Jul 2016, Junio C Hamano wrote:
>
>> Kevin Willford  writes:
>> 
>> >  static int patch_id_cmp(struct patch_id *a,
>> >struct patch_id *b,
>> > -  void *keydata)
>> > +  struct diff_options *opt)
>> >  {
>> > +  if (is_null_sha1(a->patch_id) &&
>> > +  commit_patch_id(a->commit, opt, a->patch_id, 0))
>> > +  return error("Could not get patch ID for %s",
>> > +  oid_to_hex(>commit->object.oid));
>> > +  if (is_null_sha1(b->patch_id) &&
>> > +  commit_patch_id(b->commit, opt, b->patch_id, 0))
>> > +  return error("Could not get patch ID for %s",
>> > +  oid_to_hex(>commit->object.oid));
>> >return hashcmp(a->patch_id, b->patch_id);
>> >  }
>> 
>> These error returns initially looks slightly iffy in that in general
>> the caller of any_cmp_fn() wants to know how a/b compares, but by
>> returning error(), it always says "a is smaller than b".
>
> I am to blame, as this is my design.
>
> And yes, it is kind of funny that we require a cmpfn that returns <0, ==0
> and >0 for comparisons, when hashmaps try to avoid any order.

Perhaps hashmap API needs fixing in the longer term not to call this
type hashmap_cmp_fn; instead it should lose cmp and say something
like hashmap_eq_fn or something.

> Do you want a note in the commit message about this "abuse" of a negative
> return value, or a code comment?

I do not think negative (or non-zero) return is an "abuse" at all.
It is misleading in the context of the function whose name has "cmp"
in it, but that is not the fault of this function, rather, the
breakage is more in the API that calls a function that wants to know
only equality a "cmp".  A in-code comment before the function name
may be appropriate:

/*
 * hashmap API calls hashmap_cmp_fn, but it only wants
 * "does the key match the entry?" with 0 (matches) and
 * non-zero (does not match).
 */
static int patch_id_match(const struct patch_id *ent,
  const struct patch_id *key,
  const void *keydata)
{
...

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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Johannes Schindelin]

Hi Junio,

On Fri, 29 Jul 2016, Junio C Hamano wrote:

> Kevin Willford  writes:
> 
> >  static int patch_id_cmp(struct patch_id *a,
> > struct patch_id *b,
> > -   void *keydata)
> > +   struct diff_options *opt)
> >  {
> > +   if (is_null_sha1(a->patch_id) &&
> > +   commit_patch_id(a->commit, opt, a->patch_id, 0))
> > +   return error("Could not get patch ID for %s",
> > +   oid_to_hex(>commit->object.oid));
> > +   if (is_null_sha1(b->patch_id) &&
> > +   commit_patch_id(b->commit, opt, b->patch_id, 0))
> > +   return error("Could not get patch ID for %s",
> > +   oid_to_hex(>commit->object.oid));
> > return hashcmp(a->patch_id, b->patch_id);
> >  }
> 
> These error returns initially looks slightly iffy in that in general
> the caller of any_cmp_fn() wants to know how a/b compares, but by
> returning error(), it always says "a is smaller than b".

I am to blame, as this is my design.

And yes, it is kind of funny that we require a cmpfn that returns <0, ==0
and >0 for comparisons, when hashmaps try to avoid any order.

Do you want a note in the commit message about this "abuse" of a negative
return value, or a code comment?

> The idea of using the two level hash, computing the more expensive
> one only when the hashmap hashes of the result of the cheaper hash
> function collide, is excellent.

Thanks :-)

Ciao,
Dscho
--
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

Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Junio C Hamano]

Kevin Willford  writes:

>  static int patch_id_cmp(struct patch_id *a,
>   struct patch_id *b,
> - void *keydata)
> + struct diff_options *opt)
>  {
> + if (is_null_sha1(a->patch_id) &&
> + commit_patch_id(a->commit, opt, a->patch_id, 0))
> + return error("Could not get patch ID for %s",
> + oid_to_hex(>commit->object.oid));
> + if (is_null_sha1(b->patch_id) &&
> + commit_patch_id(b->commit, opt, b->patch_id, 0))
> + return error("Could not get patch ID for %s",
> + oid_to_hex(>commit->object.oid));
>   return hashcmp(a->patch_id, b->patch_id);
>  }

These error returns initially looks slightly iffy in that in general
the caller of any_cmp_fn() wants to know how a/b compares, but by
returning error(), it always says "a is smaller than b".  This
however may be OK because the callers in hashmap_get* implementation
only wants to know "are they equal?", and we are saying "no they
cannot possibly be equal" here.  The original that ran a full
commit_patch_id() in now-removed add_commit() helper function didn't
even diagnose this error and silently omitted the commit from the
candidate list, so this may be even seen as an improvement.

The idea of using the two level hash, computing the more expensive
one only when the hashmap hashes of the result of the cheaper hash
function collide, is excellent.  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 v2] 4/4] rebase: avoid computing unnecessary patch IDs

[Kevin Willford]

From: Kevin Willford 

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 "diff-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
"diff-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.
We accomplish that by using the hashmap_add() function that does not even
test for hash collisions.  This also allows us to evaluate the full patch ID
lazily, i.e. only when we found commits with matching diff-header-only
patch IDs.

We add a performance test that demonstrates ~1-6% improvement.  In
practice this will depend on various factors such as how many upstream
changes and how big those changes are along with whether file system
caches are cold or warm.  As Git's test suite has no way of catching
performance regressions, we also add a regression test that verifies
that the full patch ID computation is skipped when the diff-header-only
computation suffices.

Signed-off-by: Kevin Willford 
---
 builtin/log.c|  2 +-
 patch-ids.c  | 22 --
 patch-ids.h  |  2 +-
 t/perf/p3400-rebase.sh   | 36 
 t/t6007-rev-list-cherry-pick-file.sh | 17 +
 5 files changed, 71 insertions(+), 8 deletions(-)
 create mode 100644 t/perf/p3400-rebase.sh

diff --git a/builtin/log.c b/builtin/log.c
index fd1652f..b076993 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1331,7 +1331,7 @@ static void prepare_bases(struct base_tree_info *bases,
struct object_id *patch_id;
if (commit->util)
continue;
-   if (commit_patch_id(commit, , sha1))
+   if (commit_patch_id(commit, , sha1, 0))
die(_("cannot get patch id"));
ALLOC_GROW(bases->patch_id, bases->nr_patch_id + 1, 
bases->alloc_patch_id);
patch_id = bases->patch_id + bases->nr_patch_id;
diff --git a/patch-ids.c b/patch-ids.c
index 69a14a3..0a4828a 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -5,7 +5,7 @@
 #include "patch-ids.h"
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,
-   unsigned char *sha1)
+   unsigned char *sha1, int diff_header_only)
 {
if (commit->parents)
diff_tree_sha1(commit->parents->item->object.oid.hash,
@@ -13,13 +13,21 @@ int commit_patch_id(struct commit *commit, struct 
diff_options *options,
else
diff_root_tree_sha1(commit->object.oid.hash, "", options);
diffcore_std(options);
-   return diff_flush_patch_id(options, sha1, 0);
+   return diff_flush_patch_id(options, sha1, diff_header_only);
 }
 
 static int patch_id_cmp(struct patch_id *a,
struct patch_id *b,
-   void *keydata)
+   struct diff_options *opt)
 {
+   if (is_null_sha1(a->patch_id) &&
+   commit_patch_id(a->commit, opt, a->patch_id, 0))
+   return error("Could not get patch ID for %s",
+   oid_to_hex(>commit->object.oid));
+   if (is_null_sha1(b->patch_id) &&
+   commit_patch_id(b->commit, opt, b->patch_id, 0))
+   return error("Could not get patch ID for %s",
+   oid_to_hex(>commit->object.oid));
return hashcmp(a->patch_id, b->patch_id);
 }
 
@@ -43,11 +51,13 @@ static int init_patch_id_entry(struct patch_id *patch,
   struct commit *commit,
   struct patch_ids *ids)
 {
+   unsigned char header_only_patch_id[GIT_SHA1_RAWSZ];
+
patch->commit = commit;
-   if (commit_patch_id(commit, >diffopts, patch->patch_id))
+   if (commit_patch_id(commit, >diffopts, header_only_patch_id, 1))
return -1;
 
-   hashmap_entry_init(patch, sha1hash(patch->patch_id));
+   hashmap_entry_init(patch, sha1hash(header_only_patch_id));
return 0;
 }
 
@@ -60,7 +70,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,
if (init_patch_id_entry(, commit, ids))