v20/4] Use header data patch ids for rebase to avoid loading file content

This patch series is to remove the hand rolled hashmap in the patch_ids and use the hashmap.h implementation. It also introduces the idea of having a header only patch id so that the contents of the files do not have to be loaded in order to determine if two commits are different.

Kevin Willford (4):
  patch-ids: stop using a hand-rolled hashmap implementation
  patch-ids: replace the seen indicator with a commit pointer
  patch-ids: add flag to create the diff patch id using header only data
  rebase: avoid computing unnecessary patch IDs

 builtin/log.c                        |  2 +-
 diff.c                               | 16 +++---
 diff.h                               |  2 +-
 patch-ids.c                          | 99 +++++++++++++++---------------------
 patch-ids.h                          | 11 ++--
 revision.c                           | 18 ++-----
 t/perf/p3400-rebase.sh               | 36 +++++++++++++
 t/t6007-rev-list-cherry-pick-file.sh | 17 +++++++
 8 files changed, 114 insertions(+), 87 deletions(-)
 create mode 100644 t/perf/p3400-rebase.sh

From: Kevin Willford <kewillf@microsoft.com>

This change will use the hashmap from the hashmap.h to keep track of the patch_ids that have been encountered instead of using an internal implementation. This simplifies the implementation of the patch ids.

Signed-off-by: Kevin Willford <kcwillford@gmail.com>
---
 patch-ids.c | 86 +++++++++++++++++++++----------------------------------------
 patch-ids.h |  7 +++--
 2 files changed, 32 insertions(+), 61 deletions(-)

Kevin Willford <kcwillford@gmail.com> writes:

The patch text itself is almost unreadble because of a lot of verbose code it had to carry before this change, and the removal of that unreadable code of course is the point of this very welcome clean-up ;-). The resulting code is very readable.

This is a tangent, but this made me wonder if it is safe to simply free(3) the result of calling hashmap_entry_init() which is called in init_patch_id_entry(). It would obviously become a resource leak, if a hashmap_entry (which the api documentation says is "an opaque structure") holds any allocated resource.

The fact that hashmap_entry_init() is there but there is no corresponding hashmap_entry_clear() hints that there is nothing to be worried about and I can see from the implementation of hashmap_entry_init() that no extra resource is held inside, but an API user should not have to guess. We may want to do one of the two things:

 * document that an embedded hashmap_entry does not hold any
   resource that need to be released and it is safe to free the user
   structure that embeds one; or

 * implement hashmap_entry_clear() that currently is a no-op.

If we anticipate that the hashmap implementation may gain more fields in this "opaque" structure, the latter might be a more future-proof approach, as all the callers of hashmap_entry_init() would already be calling hashmap_entry_clear() to clean it up when such a change to the hashmap implementation happens. On the other hand, a caller that does not call hashmap_entry_clear() would not be noticed by anybody as leaking resources until such a change happens, so the future-proofing may not have much practical value (iow, the existing callers of _init() would need to be audited anyway to make sure they also call _clear()).

Hi Junio,

first of all: Kevin & I are colleagues and I helped prepare this patch series. I had the idea to have a two-level patch ID to help e.g. when an alternate object store is hosted on a (slow) network drive.

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

It would be a serious bug if hashmap_entry_init() played games with references, given its signature (that this function does not have any access to the hashmap structure, only to the entry itself):

	void hashmap_entry_init(void *entry, unsigned int hash)

Please note that the `void *entry` really needs to point to a struct whose first field is of type `struct hashmap_entry`. This is not type-safe, of course, but C does not allow a strong sub-typing of the kind we want to use here.

Urgh. The only reason we have hashmap_entry_init() is that we *may* want to extend `struct hashmap_entry` at some point. That is *already* over-engineered because that point in time seems quite unlikely to arrive, like, ever.

In that light, as you said, why would we overengineer things even further by introducing a hashmap_entry_clear(), especially given that we won't catch any forgotten _clear() calls, given that it is a no-op anyway?

Let's just not.

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

I do not think we are on the same page. The "reference to other resource" I wondered was inside the hashmap_entry structure, IOW, "the entry itself".

Which is declared to be opaque to the API users, so whoever defined that API cannot blame me for not checking its definition to see that it only has "unsigned int hash" and no allocated memory or open file descriptor in it that needs freeing.

By the way, the first parameter of the function being "void *" is merely to help lazy API users, who have their own structure that embeds the hashmap_entry as its first element, as API documentation tells them to do, e.g.

	struct foo {
        	struct hashmap_entry e;
                ... other "foo" specific fields come here ...
	} foo;

and because of the lazy "void *", they do not have to do this:

	hashmap_entry_init(&foo->e, ...);

which would be required if the first parameter were "struct hashmap_entry *", but they can just do this:

	hashmap_entry_init(&foo, ...);

I have a slight preference to avoid the lazy "void *", but that is an unrelated tangent.

I am saying that an uneven over-enginnering is bad.

To be consistent with having _init() and declaring the entry structure to be opaque, you would either need _clear() or document you would never need to worry about the lack of _clear().

Junio C Hamano <gitster@pobox.com> wrote:

<snip>

Me too. I noticed this while working on the http-walker speedups and my self-rejected last patch:

  https://public-inbox.org/git/20160711210243.GA1604%40whir/

Extracting list_entry from list.h (currently in next[1]) and exposing that generically as "container_of" for use with hashmap_* would make it safer-to-use and allow structs to belong to multiple hashmaps.

list_entry is also an alias for container_of in the Linux kernel, but we don't have enough code using list_* to warrant two names for the same macro.

[1] https://public-inbox.org/git/20160711205131.1291-4-e%4080x24.org/

Hi Junio,

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

Oh, I see now.

Actually, not really. We cannot do that in C: we need to define the struct in hashmap.h so that its size is known to the users.

That is the reason, I guess, why we have the documentation in Documentation/technical/api-hashmap.txt: it would have to talk about your hypothetical hashmap_entry_clear() (which would better be named *_release() BTW, unless I misunderstood what you want a hypothetical future version of that function to do).

And quite frankly, unless we *have* to, I would rather try to avoid introducing that function as much as possible, as it would make using the hashmap API even more finicky than it already is.

Yes, I know that. It is the common way to simulate subclassing in C, for lack of a more compile-safe construct.

Oh, we are already safely in Unrelated Tangent Land for a while, I would think. Nothing of what we are discussing in this thread has anything to do with Kevin's patch series, which is about trying to use resources more sensibly when using the revision machinery's --cherry-pick option.

And since we are already there, I'll offer an opinion in favor of `void *`: doing the &foo->e dance could quite possibly suggest that `e` is a field just like any other field (and does not necessarily *need* to be the first).

But again, this has nothing to do with the patch series we are discussing here.

Hmm. I guess that the _init() function could be replaced by an _INIT macro a la STRBUF_INIT. Not sure it is really worth the effort, though.

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

What I meant was what Documentation/technical/api-hashmap.txt said. I know that we cannot embed a true "opaque" structure in C just as you do.

I think there is no misunderstanding on your part. I am following the conclusion (as I recall) of a discussion on the list not in so distant past about X_free(x) that frees the resource an instance of "struct X" holds and also the instance itself, and X_clear(x) that only frees the resources without freeing the instance (the latter of which allows x to be on stack, you do X_init(&x) and conclude with X_clear(&x)). The name X_clear() is more in line with existing API functions like string_list_clear(), argv_array_clear(). An oddball is strbuf_release(), which I think made you make the above comment.

Oh, no question about that. Go back to my review, to which your message I am responding to is a reply to. What you wrote are all about things after "This is a tangent, but this made me wonder if it is safe to simply free(3) the result...", which pointed out rough points in the hashmap API from the API user's point of view and suggested a few possible improvement opportunities.

I do not think so, as X_init() and X_INIT() from the point of view of the API user would not make much difference; as long as the documentation does not say it is safe to make it go out of scope without "deinitialize" it, the reader will be left wondering.

Junio C Hamano <gitster@pobox.com> writes:

In other words, I'd be happy with a patch like this, outside the scope of and independent from this series.

When the hashmap_entry structure does acquire references to external resources (which I wouldn't judge the likelihood of), this paragraph will become stale, but that is exactly the point at which _clear() function needs to be added to the API and described here, replacing this paragraph.

I do not mind having an empty _clear() before that happens, but I do not think it adds much safety. A disciplined user of the API may call that empty _clear() to make her code future-proof, but we know there are undisciplined developers and reviewers and there will be codepaths that call _init() without calling the empty _clear(), and we won't notice it. Whoever is adding the real need for _clear() must audit the codebase at that point _anyway_, and that is why I think having an empty _clear() before would not buy us much.

 Documentation/technical/api-hashmap.txt | 5 +++++
 1 file changed, 5 insertions(+)

Kevin Willford <kcwillford@gmail.com> writes:

This is a tangent, and I do not suggest to change patch 1/4 to flip the style, but I am not sure if this is a good style, or casting it the other way around is better from the type-checking point of view, i.e.

    static int cmp_fn(const void *a_, const void *b_, const void *keydata)
    {
	struct patch_id *a = a_;
        struct patch_id *b = b_;
	return hashcmp(a->patch_id, b->patch_id);
    }

    ...
    	hashmap_init(..., cmp_fn, ...);
    ...

I see many existing calls to hashmap_init() follow this pattern, so as I said, patch 1/4 is fine as-is.

Thanks.

From: Kevin Willford <kewillf@microsoft.com>

The cherry_pick_list was looping through the original side checking the seen indicator and setting the cherry_flag on the commit. If we save off the commit in the patch_id we can set the cherry_flag on the correct commit when running through the other side when a patch_id match is found.

Signed-off-by: Kevin Willford <kcwillford@gmail.com>
---
 patch-ids.c |  1 +
 patch-ids.h |  2 +-
 revision.c  | 18 +++---------------
 3 files changed, 5 insertions(+), 16 deletions(-)

Kevin Willford <kcwillford@gmail.com> writes:

We lose the final loop to fix up the shorter side, because the second loop now marks both sides.

And as a side effect, we do not use commit->util which is a scarce shared resource (aka historical API wart).

Makes sense.  Thanks.

From: Kevin Willford <kewillf@microsoft.com>

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 <kcwillford@gmail.com>
---
 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

Kevin Willford <kcwillford@gmail.com> writes:

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.

Hi Junio,

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

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?

Thanks :-)

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> 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.

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

W dniu 01.08.2016 o 22:11, Junio C Hamano pisze:

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 <jnareb@gmail.com> writes:

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

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

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

Hi Junio,

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

Maybe.

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

Ciao, Dscho

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

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

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

Junio C Hamano <gitster@pobox.com> writes:

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(+)

Hi Junio,

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

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

Thanks, Dscho

From: Kevin Willford <kewillf@microsoft.com>

This will allow a diff patch id to be created using only the header data so that the contents of the file will not have to be loaded.

Signed-off-by: Kevin Willford <kcwillford@gmail.com>
---
 diff.c      | 16 ++++++++++------
 diff.h      |  2 +-
 patch-ids.c |  2 +-
 3 files changed, 12 insertions(+), 8 deletions(-)

Kevin Willford <kcwillford@gmail.com> writes:

Did you do "format-patch --subject-prefix='[PATCH v2]'" or something like that? When applied, that would result in a commit title like this:

	1/4] patch-ids: stop using a ...

because we stop at the first ']', and we do not bother to count up to "matching bracket".

    git format-patch --subject-prefix='PATCH v2'

or even better

    git format-patch -v2

would have been more appropriate.

Hi Junio,

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

This is my fault, sorry, I suggested this usage (misremembering the semantics because I only use my mail-patch-series.sh helper and never use format-patch manually anymore).

Oooh, I did not know about the latter form. Nice.

Thanks, Dscho