[PATCH] revision: introduce prepare_revision_walk_extended()

[PATCH] revision: introduce prepare_revision_walk_extended()

[René Scharfe]

prepare_revision_walk() allows callers to take ownership of the array of
pending objects by setting the rev_info flag "leak_pending" and copying
the object_array "pending".  They use it to clear commit marks after
setup is done.  This interface is brittle enough that it requires
extensive comments.

Provide an easier way by adding a function that can hand over the array
to a caller-supplied output parameter and converting all users of the
flag "leak_pending" to call prepare_revision_walk_extended() instead.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 Documentation/technical/api-revision-walking.txt |  6 ++++++
 bisect.c                                         | 17 +++++------------
 builtin/checkout.c                               |  9 +--------
 bundle.c                                         |  9 +--------
 revision.c                                       | 10 +++++++++-
 revision.h                                       | 14 ++------------
 6 files changed, 24 insertions(+), 41 deletions(-)

diff --git a/Documentation/technical/api-revision-walking.txt b/Documentation/technical/api-revision-walking.txt
index 55b878ade8..9dc573d2ec 100644
--- a/Documentation/technical/api-revision-walking.txt
+++ b/Documentation/technical/api-revision-walking.txt
@@ -50,6 +50,12 @@ function.
 	returns any error (non-zero return code) and if it does not, you can
 	start using get_revision() to do the iteration.
 
+`prepare_revision_walk_extended`::
+
+	Like prepare_revision_walk(), but allows callers to take ownership
+	of the array of pending objects by passing an object_array pointer
+	as the second parameter; passing NULL clears the array.
+
 `get_revision`::
 
 	Takes a pointer to a `rev_info` structure and iterates over it,
diff --git a/bisect.c b/bisect.c
index 0fca17c02b..a2af405d28 100644
--- a/bisect.c
+++ b/bisect.c
@@ -641,9 +641,10 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
 	/* XXX leak rev_argv, as "revs" may still be pointing to it */
 }
 
-static void bisect_common(struct rev_info *revs)
+static void bisect_common(struct rev_info *revs,
+			  struct object_array *old_pending_ptr)
 {
-	if (prepare_revision_walk(revs))
+	if (prepare_revision_walk_extended(revs, old_pending_ptr))
 		die("revision walk setup failed");
 	if (revs->tree_objects)
 		mark_edges_uninteresting(revs, NULL);
@@ -825,15 +826,7 @@ static int check_ancestors(const char *prefix)
 	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
 
 	/* Save pending objects, so they can be cleaned up later. */
-	pending_copy = revs.pending;
-	revs.leak_pending = 1;
-
-	/*
-	 * bisect_common calls prepare_revision_walk right away, which
-	 * (together with .leak_pending = 1) makes us the sole owner of
-	 * the list of pending objects.
-	 */
-	bisect_common(&revs);
+	bisect_common(&revs, &pending_copy);
 	res = (revs.commits != NULL);
 
 	/* Clean up objects used, as they will be reused. */
@@ -964,7 +957,7 @@ int bisect_next_all(const char *prefix, int no_checkout)
 	bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
 	revs.limited = 1;
 
-	bisect_common(&revs);
+	bisect_common(&revs, NULL);
 
 	find_bisection(&revs.commits, &reaches, &all, !!skipped_revs.nr);
 	revs.commits = managed_skipped(revs.commits, &tried);
diff --git a/builtin/checkout.c b/builtin/checkout.c
index e1e157d205..1f04f5d5e5 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -796,14 +796,7 @@ static void orphaned_commit_warning(struct commit *old, struct commit *new)
 	add_pending_oid(&revs, "HEAD", &new->object.oid, UNINTERESTING);
 
 	/* Save pending objects, so they can be cleaned up later. */
-	refs = revs.pending;
-	revs.leak_pending = 1;
-
-	/*
-	 * prepare_revision_walk (together with .leak_pending = 1) makes us
-	 * the sole owner of the list of pending objects.
-	 */
-	if (prepare_revision_walk(&revs))
+	if (prepare_revision_walk_extended(&revs, &refs))
 		die(_("internal error in revision walk"));
 	if (!(old->object.flags & UNINTERESTING))
 		suggest_reattach(old, &revs);
diff --git a/bundle.c b/bundle.c
index 93290962c9..6af6e38c40 100644
--- a/bundle.c
+++ b/bundle.c
@@ -158,14 +158,7 @@ int verify_bundle(struct bundle_header *header, int verbose)
 	setup_revisions(2, argv, &revs, NULL);
 
 	/* Save pending objects, so they can be cleaned up later. */
-	refs = revs.pending;
-	revs.leak_pending = 1;
-
-	/*
-	 * prepare_revision_walk (together with .leak_pending = 1) makes us
-	 * the sole owner of the list of pending objects.
-	 */
-	if (prepare_revision_walk(&revs))
+	if (prepare_revision_walk_extended(&revs, &refs))
 		die(_("revision walk setup failed"));
 
 	i = req_nr;
diff --git a/revision.c b/revision.c
index f6a3da5cd9..3a231451a4 100644
--- a/revision.c
+++ b/revision.c
@@ -2841,6 +2841,12 @@ void reset_revision_walk(void)
 }
 
 int prepare_revision_walk(struct rev_info *revs)
+{
+	return prepare_revision_walk_extended(revs, NULL);
+}
+
+int prepare_revision_walk_extended(struct rev_info *revs,
+				   struct object_array *old_pending_ptr)
 {
 	int i;
 	struct object_array old_pending;
@@ -2860,7 +2866,9 @@ int prepare_revision_walk(struct rev_info *revs)
 			}
 		}
 	}
-	if (!revs->leak_pending)
+	if (old_pending_ptr)
+		*old_pending_ptr = old_pending;
+	else
 		object_array_clear(&old_pending);
 
 	/* Signal whether we need per-parent treesame decoration */
diff --git a/revision.h b/revision.h
index 54761200ad..5d4b475334 100644
--- a/revision.h
+++ b/revision.h
@@ -150,18 +150,6 @@ struct rev_info {
 			date_mode_explicit:1,
 			preserve_subject:1;
 	unsigned int	disable_stdin:1;
-	/*
-	 * Set `leak_pending` to prevent `prepare_revision_walk()` from clearing
-	 * the array of pending objects (`pending`). It will still forget about
-	 * the array and its entries, so they really are leaked. This can be
-	 * useful if the `struct object_array` `pending` is copied before
-	 * calling `prepare_revision_walk()`. By setting `leak_pending`, you
-	 * effectively claim ownership of the old array, so you should most
-	 * likely call `object_array_clear(&pending_copy)` once you are done.
-	 * Observe that this is about ownership of the array and its entries,
-	 * not the commits referenced by those entries.
-	 */
-	unsigned int	leak_pending:1;
 	/* --show-linear-break */
 	unsigned int	track_linear:1,
 			track_first_time:1,
@@ -270,6 +258,8 @@ extern int handle_revision_arg(const char *arg, struct rev_info *revs,
 
 extern void reset_revision_walk(void);
 extern int prepare_revision_walk(struct rev_info *revs);
+extern int prepare_revision_walk_extended(struct rev_info *revs,
+					  struct object_array *old_pending_ptr);
 extern struct commit *get_revision(struct rev_info *revs);
 extern char *get_revision_mark(const struct rev_info *revs,
 			       const struct commit *commit);
-- 
2.15.1

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[Martin Ågren]

On 16 December 2017 at 13:12, René Scharfe <l.s.r@web.de> wrote:
> prepare_revision_walk() allows callers to take ownership of the array of
> pending objects by setting the rev_info flag "leak_pending" and copying
> the object_array "pending".  They use it to clear commit marks after
> setup is done.  This interface is brittle enough that it requires
> extensive comments.
>
> Provide an easier way by adding a function that can hand over the array
> to a caller-supplied output parameter and converting all users of the
> flag "leak_pending" to call prepare_revision_walk_extended() instead.
>
> Signed-off-by: Rene Scharfe <l.s.r@web.de>
> ---
>  Documentation/technical/api-revision-walking.txt |  6 ++++++
>  bisect.c                                         | 17 +++++------------
>  builtin/checkout.c                               |  9 +--------
>  bundle.c                                         |  9 +--------
>  revision.c                                       | 10 +++++++++-
>  revision.h                                       | 14 ++------------
>  6 files changed, 24 insertions(+), 41 deletions(-)
>
> diff --git a/Documentation/technical/api-revision-walking.txt b/Documentation/technical/api-revision-walking.txt
> index 55b878ade8..9dc573d2ec 100644
> --- a/Documentation/technical/api-revision-walking.txt
> +++ b/Documentation/technical/api-revision-walking.txt
> @@ -50,6 +50,12 @@ function.
>         returns any error (non-zero return code) and if it does not, you can
>         start using get_revision() to do the iteration.
>
> +`prepare_revision_walk_extended`::
> +
> +       Like prepare_revision_walk(), but allows callers to take ownership
> +       of the array of pending objects by passing an object_array pointer
> +       as the second parameter; passing NULL clears the array.

This might make someone wonder what the difference between passing NULL
and using `prepare_revision_walk()` is. Perhaps: "passing NULL clears
the array, just as prepare_revision_walk() would." Possibly only matters
once we gain more parameters, and maybe not even then...

The name of your new function ("..._extended") doesn't describe the
nature of the extended behavior and made me wonder if it was too
generic. But that genericness might be a good thing. When/If we need to
tweak the behavior along some other axis, we can add a third parameter
to ..._extended and pass NULL/0 as appropriate. The simple cases will
stay simple and we won't gain lots of functions with minor differences.

> diff --git a/builtin/checkout.c b/builtin/checkout.c
> index e1e157d205..1f04f5d5e5 100644
> --- a/builtin/checkout.c
> +++ b/builtin/checkout.c
> @@ -796,14 +796,7 @@ static void orphaned_commit_warning(struct commit *old, struct commit *new)
>         add_pending_oid(&revs, "HEAD", &new->object.oid, UNINTERESTING);
>
>         /* Save pending objects, so they can be cleaned up later. */
> -       refs = revs.pending;
> -       revs.leak_pending = 1;
> -
> -       /*
> -        * prepare_revision_walk (together with .leak_pending = 1) makes us
> -        * the sole owner of the list of pending objects.
> -        */
> -       if (prepare_revision_walk(&revs))
> +       if (prepare_revision_walk_extended(&revs, &refs))
>                 die(_("internal error in revision walk"));
>         if (!(old->object.flags & UNINTERESTING))
>                 suggest_reattach(old, &revs);
> diff --git a/bundle.c b/bundle.c
> index 93290962c9..6af6e38c40 100644
> --- a/bundle.c
> +++ b/bundle.c
> @@ -158,14 +158,7 @@ int verify_bundle(struct bundle_header *header, int verbose)
>         setup_revisions(2, argv, &revs, NULL);
>
>         /* Save pending objects, so they can be cleaned up later. */
> -       refs = revs.pending;
> -       revs.leak_pending = 1;
> -
> -       /*
> -        * prepare_revision_walk (together with .leak_pending = 1) makes us
> -        * the sole owner of the list of pending objects.
> -        */
> -       if (prepare_revision_walk(&revs))
> +       if (prepare_revision_walk_extended(&revs, &refs))
>                 die(_("revision walk setup failed"));
>
>         i = req_nr;

This copy-paste coding that you get rid of here can be attributed to me.
I obviously like your cleaned-up version much better.

> diff --git a/revision.h b/revision.h
> index 54761200ad..5d4b475334 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -150,18 +150,6 @@ struct rev_info {
>                         date_mode_explicit:1,
>                         preserve_subject:1;
>         unsigned int    disable_stdin:1;
> -       /*
> -        * Set `leak_pending` to prevent `prepare_revision_walk()` from clearing
> -        * the array of pending objects (`pending`). It will still forget about
> -        * the array and its entries, so they really are leaked. This can be
> -        * useful if the `struct object_array` `pending` is copied before
> -        * calling `prepare_revision_walk()`. By setting `leak_pending`, you
> -        * effectively claim ownership of the old array, so you should most
> -        * likely call `object_array_clear(&pending_copy)` once you are done.
> -        * Observe that this is about ownership of the array and its entries,
> -        * not the commits referenced by those entries.
> -        */
> -       unsigned int    leak_pending:1;
>         /* --show-linear-break */
>         unsigned int    track_linear:1,
>                         track_first_time:1,

The commit message doesn't mention that you drop `leak_pending`, but
maybe that's obvious enough since you convert all users.

Thanks for tidying up,
Martin

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[Jeff King]

On Sat, Dec 16, 2017 at 01:12:16PM +0100, René Scharfe wrote:

> prepare_revision_walk() allows callers to take ownership of the array of
> pending objects by setting the rev_info flag "leak_pending" and copying
> the object_array "pending".  They use it to clear commit marks after
> setup is done.  This interface is brittle enough that it requires
> extensive comments.
> 
> Provide an easier way by adding a function that can hand over the array
> to a caller-supplied output parameter and converting all users of the
> flag "leak_pending" to call prepare_revision_walk_extended() instead.

I think this is _better_, but it's still kind of a funny interface.

The root of the matter is that the revision-walking code doesn't clean
up after itself. In every case, the caller is just saving these to clean
up commit marks, isn't it?

Could we instead have an interface like:

  revs.clear_commit_marks = 1;
  prepare_revision_walk(&revs);
  ...
  finish_revision_walk(&revs);

where that final function would do any cleanup, including clearing the
commit marks. I suspect there are other small bits that get leaked
because there's not really any "destructor" for a revision walk.

It's not as flexible as this whole "make a copy of the pending tips"
thing, but it keeps all of the details abstracted away from the callers.

Alternatively:

> +`prepare_revision_walk_extended`::
> +
> +	Like prepare_revision_walk(), but allows callers to take ownership
> +	of the array of pending objects by passing an object_array pointer
> +	as the second parameter; passing NULL clears the array.

What if we just got rid of this function and had callers do:

  object_array_copy(&old_pending, &revs);
  prepare_revision_walk(&revs);
  ...
  clear_commit_marks_for_object_array(&old_pending);

That sidesteps all of the memory ownership issues by just creating a
copy. That's less efficient, but I'd be surprised if it matters in
practice (we tend to do one or two revisions per process, there don't
tend to be a lot of pending tips, and we're really just talking about
copying some pointers here).

-Peff

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[René Scharfe]

Am 18.12.2017 um 16:10 schrieb Jeff King:
> On Sat, Dec 16, 2017 at 01:12:16PM +0100, René Scharfe wrote:
> 
>> prepare_revision_walk() allows callers to take ownership of the array of
>> pending objects by setting the rev_info flag "leak_pending" and copying
>> the object_array "pending".  They use it to clear commit marks after
>> setup is done.  This interface is brittle enough that it requires
>> extensive comments.
>>
>> Provide an easier way by adding a function that can hand over the array
>> to a caller-supplied output parameter and converting all users of the
>> flag "leak_pending" to call prepare_revision_walk_extended() instead.
> 
> I think this is _better_, but it's still kind of a funny interface.
> 
> The root of the matter is that the revision-walking code doesn't clean
> up after itself. In every case, the caller is just saving these to clean
> up commit marks, isn't it?

bundle also checks if the pending objects exists.

> Could we instead have an interface like:
> 
>    revs.clear_commit_marks = 1;
>    prepare_revision_walk(&revs);
>    ...
>    finish_revision_walk(&revs);
> 
> where that final function would do any cleanup, including clearing the
> commit marks. I suspect there are other small bits that get leaked
> because there's not really any "destructor" for a revision walk.
> 
> It's not as flexible as this whole "make a copy of the pending tips"
> thing, but it keeps all of the details abstracted away from the callers.
> 
> Alternatively:
> 
>> +`prepare_revision_walk_extended`::
>> +
>> +	Like prepare_revision_walk(), but allows callers to take ownership
>> +	of the array of pending objects by passing an object_array pointer
>> +	as the second parameter; passing NULL clears the array.
> 
> What if we just got rid of this function and had callers do:
> 
>    object_array_copy(&old_pending, &revs);
>    prepare_revision_walk(&revs);
>    ...
>    clear_commit_marks_for_object_array(&old_pending);
> 
> That sidesteps all of the memory ownership issues by just creating a
> copy. That's less efficient, but I'd be surprised if it matters in
> practice (we tend to do one or two revisions per process, there don't
> tend to be a lot of pending tips, and we're really just talking about
> copying some pointers here).

This was done before I added the leak_pending flag.

t5502 and t5571 have test cases with ca. 1000 pending objects, t5551
and t5541 with ca. 2000, p5310 more than 8000.  That's just a few KB.

I don't know if there can be real-world use cases with millions of
entries (when it would start to hurt).

Why does prepare_revision_walk() clear the list of pending objects at
all?  Assuming the list is append-only then perhaps remembering the
last handled index would suffice.

René

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[Jeff King]

On Mon, Dec 18, 2017 at 08:18:19PM +0100, René Scharfe wrote:

> > The root of the matter is that the revision-walking code doesn't clean
> > up after itself. In every case, the caller is just saving these to clean
> > up commit marks, isn't it?
> 
> bundle also checks if the pending objects exists.

Thanks, I missed that one. So just adding a feature to clean up commit
marks wouldn't be sufficient to cover that case.

> > That sidesteps all of the memory ownership issues by just creating a
> > copy. That's less efficient, but I'd be surprised if it matters in
> > practice (we tend to do one or two revisions per process, there don't
> > tend to be a lot of pending tips, and we're really just talking about
> > copying some pointers here).
> [...]
> I don't know if there can be real-world use cases with millions of
> entries (when it would start to hurt).

I've seen repos which have tens of thousands of tags. Something like
"rev-list --all" would have tens of thousands of pending objects.
I think in practice it's limited to the number of objects (though in
practice more like the number of commits).

I'd note also that for most uses we don't need a full object_array. You
really just need a pointer to the "struct object" to wipe its flags.

So there we might waste 8 bytes per object in the worst case. But bear
in mind that the process is wasting a lot more than that per "struct
commit" that we're holding. And versus the existing scheme, it's only
for the moment until prepare_revision_walk() frees the old pending list.

> Why does prepare_revision_walk() clear the list of pending objects at
> all?  Assuming the list is append-only then perhaps remembering the
> last handled index would suffice.

I assume it was mostly to clean up after itself, since there's no
explicit "I'm done with the traversal" function. But as I said earlier,
I'd be surprised of a revision walk doesn't leave some allocated cruft
in rev_info these days (e.g., pathspec cruft). In practice it doesn't
matter much because we don't do arbitrary numbers of traversals in
single process.

-Peff

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Mon, Dec 18, 2017 at 08:18:19PM +0100, René Scharfe wrote:
>
>> > The root of the matter is that the revision-walking code doesn't clean
>> > up after itself. In every case, the caller is just saving these to clean
>> > up commit marks, isn't it?
>> 
>> bundle also checks if the pending objects exists.
>
> Thanks, I missed that one. So just adding a feature to clean up commit
> marks wouldn't be sufficient to cover that case.

OK.

>> > That sidesteps all of the memory ownership issues by just creating a
>> > copy. That's less efficient, but I'd be surprised if it matters in
>> > practice (we tend to do one or two revisions per process, there don't
>> > tend to be a lot of pending tips, and we're really just talking about
>> > copying some pointers here).
>> [...]
>> I don't know if there can be real-world use cases with millions of
>> entries (when it would start to hurt).
>
> I've seen repos which have tens of thousands of tags. Something like
> "rev-list --all" would have tens of thousands of pending objects.
> I think in practice it's limited to the number of objects (though in
> practice more like the number of commits).
> ...

OK again; that is an argument against "let's copy the array".

>> Why does prepare_revision_walk() clear the list of pending objects at
>> all?  Assuming the list is append-only then perhaps remembering the
>> last handled index would suffice.

For that matter, why does it copy, instead of using revs->pending
directly?  I do not think I can answer this, as I think the design
decisions led to this code predates me.

In any case, it seems that the discussion has veered into an
interesting tangent but at this point it seems to me that it is not
likely to produce an immediate improvement over the posted patch.

Should we take the patch posted as-is and move forward?

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[Jeff King]

On Tue, Dec 19, 2017 at 10:33:55AM -0800, Junio C Hamano wrote:

> >> Why does prepare_revision_walk() clear the list of pending objects at
> >> all?  Assuming the list is append-only then perhaps remembering the
> >> last handled index would suffice.
> 
> For that matter, why does it copy, instead of using revs->pending
> directly?  I do not think I can answer this, as I think the design
> decisions led to this code predates me.

Me too, then. :) I think part of that copy is that we're moving the
items over to revs->commits, and dropping any non-commit objects.

> In any case, it seems that the discussion has veered into an
> interesting tangent but at this point it seems to me that it is not
> likely to produce an immediate improvement over the posted patch.

Fair enough.

> Should we take the patch posted as-is and move forward?

I suppose so.  I don't really have anything against the patch. My main
complaint was just that I don't think it's actually cleaning up the
gross parts of the interface. It's just substituting one gross thing (a
funny struct flag) for another (a special version of the prepare
function that takes a funny out-parameter).

-Peff

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[René Scharfe]

Am 20.12.2017 um 14:08 schrieb Jeff King:
> On Tue, Dec 19, 2017 at 10:33:55AM -0800, Junio C Hamano wrote:
> 
>> Should we take the patch posted as-is and move forward?
> 
> I suppose so.  I don't really have anything against the patch. My main
> complaint was just that I don't think it's actually cleaning up the
> gross parts of the interface. It's just substituting one gross thing (a
> funny struct flag) for another (a special version of the prepare
> function that takes a funny out-parameter).

If this is a fair description (and I have to admit that it is) then I
don't understand why you aren't against the patch.  Let's drop it.

Can we do better?  How about something this?  It reverts bundle to
duplicate the object_array, but creates just a commit_list in the other
two cases.  As a side-effect this allows clearing flags for all entries
with a single traversal.

---
 bisect.c           | 18 +++++++-----------
 builtin/checkout.c | 13 +++----------
 bundle.c           | 12 +++++-------
 commit.c           | 18 ++++++++++++++++--
 commit.h           |  3 +++
 revision.c         |  3 +--
 revision.h         | 12 ------------
 7 files changed, 35 insertions(+), 44 deletions(-)

diff --git a/bisect.c b/bisect.c
index 0fca17c02b..c966220738 100644
--- a/bisect.c
+++ b/bisect.c
@@ -819,27 +819,23 @@ static void check_merge_bases(int no_checkout)
 static int check_ancestors(const char *prefix)
 {
 	struct rev_info revs;
-	struct object_array pending_copy;
+	struct commit_list *to_clear = NULL;
 	int res;
 
 	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
 
-	/* Save pending objects, so they can be cleaned up later. */
-	pending_copy = revs.pending;
-	revs.leak_pending = 1;
-
 	/*
-	 * bisect_common calls prepare_revision_walk right away, which
-	 * (together with .leak_pending = 1) makes us the sole owner of
-	 * the list of pending objects.
+	 * bisect_common() calls prepare_revision_walk() right away,
+	 * which (among other things) clears revs.pending.  Save the
+	 * pending commits so that we can up their marks later.
 	 */
+	commit_list_insert_from_object_array(&revs.pending, &to_clear);
+
 	bisect_common(&revs);
 	res = (revs.commits != NULL);
 
 	/* Clean up objects used, as they will be reused. */
-	clear_commit_marks_for_object_array(&pending_copy, ALL_REV_FLAGS);
-
-	object_array_clear(&pending_copy);
+	clear_and_free_commit_list(to_clear, ALL_REV_FLAGS);
 
 	return res;
 }
diff --git a/builtin/checkout.c b/builtin/checkout.c
index f9f3797e11..0a694ae14a 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -791,7 +791,7 @@ static void orphaned_commit_warning(struct commit *old, struct commit *new)
 {
 	struct rev_info revs;
 	struct object *object = &old->object;
-	struct object_array refs;
+	struct commit_list *to_clear = NULL;
 
 	init_revisions(&revs, NULL);
 	setup_revisions(0, NULL, &revs, NULL);
@@ -803,13 +803,8 @@ static void orphaned_commit_warning(struct commit *old, struct commit *new)
 	add_pending_oid(&revs, "HEAD", &new->object.oid, UNINTERESTING);
 
 	/* Save pending objects, so they can be cleaned up later. */
-	refs = revs.pending;
-	revs.leak_pending = 1;
+	commit_list_insert_from_object_array(&revs.pending, &to_clear);
 
-	/*
-	 * prepare_revision_walk (together with .leak_pending = 1) makes us
-	 * the sole owner of the list of pending objects.
-	 */
 	if (prepare_revision_walk(&revs))
 		die(_("internal error in revision walk"));
 	if (!(old->object.flags & UNINTERESTING))
@@ -818,9 +813,7 @@ static void orphaned_commit_warning(struct commit *old, struct commit *new)
 		describe_detached_head(_("Previous HEAD position was"), old);
 
 	/* Clean up objects used, as they will be reused. */
-	clear_commit_marks_for_object_array(&refs, ALL_REV_FLAGS);
-
-	object_array_clear(&refs);
+	clear_and_free_commit_list(to_clear, ALL_REV_FLAGS);
 }
 
 static int switch_branches(const struct checkout_opts *opts,
diff --git a/bundle.c b/bundle.c
index 93290962c9..6916296834 100644
--- a/bundle.c
+++ b/bundle.c
@@ -134,7 +134,7 @@ int verify_bundle(struct bundle_header *header, int verbose)
 	struct ref_list *p = &header->prerequisites;
 	struct rev_info revs;
 	const char *argv[] = {NULL, "--all", NULL};
-	struct object_array refs;
+	struct object_array refs = OBJECT_ARRAY_INIT;
 	struct commit *commit;
 	int i, ret = 0, req_nr;
 	const char *message = _("Repository lacks these prerequisite commits:");
@@ -158,13 +158,11 @@ int verify_bundle(struct bundle_header *header, int verbose)
 	setup_revisions(2, argv, &revs, NULL);
 
 	/* Save pending objects, so they can be cleaned up later. */
-	refs = revs.pending;
-	revs.leak_pending = 1;
+	for (i = 0; i < revs.pending.nr; i++) {
+		struct object_array_entry *e = revs.pending.objects + i;
+		add_object_array(e->item, e->name, &refs);
+	}
 
-	/*
-	 * prepare_revision_walk (together with .leak_pending = 1) makes us
-	 * the sole owner of the list of pending objects.
-	 */
 	if (prepare_revision_walk(&revs))
 		die(_("revision walk setup failed"));
 
diff --git a/commit.c b/commit.c
index cab8d4455b..3b96277879 100644
--- a/commit.c
+++ b/commit.c
@@ -550,6 +550,11 @@ void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark)
 		commit_list_insert(*commit, &list);
 		commit++;
 	}
+	clear_and_free_commit_list(list, mark);
+}
+
+void clear_and_free_commit_list(struct commit_list *list, unsigned int mark)
+{
 	while (list)
 		clear_commit_marks_1(&list, pop_commit(&list), mark);
 }
@@ -559,7 +564,8 @@ void clear_commit_marks(struct commit *commit, unsigned int mark)
 	clear_commit_marks_many(1, &commit, mark);
 }
 
-void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
+void commit_list_insert_from_object_array(const struct object_array *a,
+					  struct commit_list **list)
 {
 	struct object *object;
 	struct commit *commit;
@@ -569,10 +575,18 @@ void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
 		object = a->objects[i].item;
 		commit = lookup_commit_reference_gently(&object->oid, 1);
 		if (commit)
-			clear_commit_marks(commit, mark);
+			commit_list_insert(commit, list);
 	}
 }
 
+void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
+{
+	struct commit_list *list = NULL;
+
+	commit_list_insert_from_object_array(a, &list);
+	clear_and_free_commit_list(list, mark);
+}
+
 struct commit *pop_commit(struct commit_list **stack)
 {
 	struct commit_list *top = *stack;
diff --git a/commit.h b/commit.h
index 99a3fea68d..128a52f264 100644
--- a/commit.h
+++ b/commit.h
@@ -115,6 +115,8 @@ unsigned commit_list_count(const struct commit_list *l);
 struct commit_list *commit_list_insert_by_date(struct commit *item,
 				    struct commit_list **list);
 void commit_list_sort_by_date(struct commit_list **list);
+void commit_list_insert_from_object_array(const struct object_array *a,
+					  struct commit_list **list);
 
 /* Shallow copy of the input list */
 struct commit_list *copy_commit_list(struct commit_list *list);
@@ -220,6 +222,7 @@ struct commit *pop_commit(struct commit_list **stack);
 void clear_commit_marks(struct commit *commit, unsigned int mark);
 void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);
 void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);
+void clear_and_free_commit_list(struct commit_list *list, unsigned int mark);
 
 
 enum rev_sort_order {
diff --git a/revision.c b/revision.c
index f6a3da5cd9..7239315de9 100644
--- a/revision.c
+++ b/revision.c
@@ -2860,8 +2860,7 @@ int prepare_revision_walk(struct rev_info *revs)
 			}
 		}
 	}
-	if (!revs->leak_pending)
-		object_array_clear(&old_pending);
+	object_array_clear(&old_pending);
 
 	/* Signal whether we need per-parent treesame decoration */
 	if (revs->simplify_merges ||
diff --git a/revision.h b/revision.h
index 54761200ad..27be70e75c 100644
--- a/revision.h
+++ b/revision.h
@@ -150,18 +150,6 @@ struct rev_info {
 			date_mode_explicit:1,
 			preserve_subject:1;
 	unsigned int	disable_stdin:1;
-	/*
-	 * Set `leak_pending` to prevent `prepare_revision_walk()` from clearing
-	 * the array of pending objects (`pending`). It will still forget about
-	 * the array and its entries, so they really are leaked. This can be
-	 * useful if the `struct object_array` `pending` is copied before
-	 * calling `prepare_revision_walk()`. By setting `leak_pending`, you
-	 * effectively claim ownership of the old array, so you should most
-	 * likely call `object_array_clear(&pending_copy)` once you are done.
-	 * Observe that this is about ownership of the array and its entries,
-	 * not the commits referenced by those entries.
-	 */
-	unsigned int	leak_pending:1;
 	/* --show-linear-break */
 	unsigned int	track_linear:1,
 			track_first_time:1,

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[Jeff King]

On Thu, Dec 21, 2017 at 07:41:44PM +0100, René Scharfe wrote:

> Am 20.12.2017 um 14:08 schrieb Jeff King:
> > On Tue, Dec 19, 2017 at 10:33:55AM -0800, Junio C Hamano wrote:
> > 
> >> Should we take the patch posted as-is and move forward?
> > 
> > I suppose so.  I don't really have anything against the patch. My main
> > complaint was just that I don't think it's actually cleaning up the
> > gross parts of the interface. It's just substituting one gross thing (a
> > funny struct flag) for another (a special version of the prepare
> > function that takes a funny out-parameter).
> 
> If this is a fair description (and I have to admit that it is) then I
> don't understand why you aren't against the patch.  Let's drop it.

Heh, I almost wrote more on this. My thinking was two-fold:

  - while I think the fundamental gross-ness is still there after your
    patch, it does smooth some of the rough edges. So it's a slight
    improvement over the status quo.

  - I read an article a while back (which unfortunately I can't find
    now) about the idea of "default to yes" in open source. I.e., the
    idea that if somebody bothered to cook up a patch and there is no
    good reason to reject it, you should take it.

    Certainly there are cases where that can go too far: obvious ones
    like bad ideas where it is not really "default" anymore, but also
    subtle ones where the changes are code churn whose fallouts will
    be dealt with by others. But this patch is a good example. I'm not
    convinced it makes things better, but I don't think it makes things
    worse. If you, who looked a lot closer at the problem than I did,
    still think it's a good idea after our discussion, it's probably
    worth applying.

So my comments weren't really "this is a bad idea" as much as "is there
a better idea". We didn't come up with one after some discussion, and
I'm willing to let it go there for now.

But if you want to keep thinking on it, I'm game. ;)

> Can we do better?  How about something this?  It reverts bundle to
> duplicate the object_array, but creates just a commit_list in the other
> two cases.  As a side-effect this allows clearing flags for all entries
> with a single traversal.

I think this is basically the "copy it before-hand" thing from earlier
in the thread. Switching to just keeping commits seems like a nice
change. It's an easy (if minor) optimization, and it makes clear exactly
which part of the data we need to keep around.

The single-traversal thing I suspect doesn't matter much in practice. In
both cases if we would visit commit X twice, we'd immediately see on the
second visit that it has already been cleared and not do anymore work.

  Side note: Another question is whether it would simply be faster to
  clear the flags for _all_ objects that we've touched in the current
  process (we have clear_object_flags() for this already). Then we know
  that we touch each one once, and we as a bonus we don't even have to
  keep the previous tips. The downsides are:

    - if another traversal in the process looked at many objects, but
      our current traversal looked at few, then we would examine more
      objects than we need to (albeit with lower cost per object)

    - it's possible there's another traversal in the same process whose
      flags we would want to have saved. I suspect such a setup is
      broken already, though, unless there's a guarantee that the two
      traversals don't overlap.

So anyway, I think this is a reasonable approach, unless we're really
worried about the extra O(# of pending) allocation.

-Peff

Re: [PATCH] revision: introduce prepare_revision_walk_extended()

[René Scharfe]

Am 24.12.2017 um 15:22 schrieb Jeff King:
> The single-traversal thing I suspect doesn't matter much in practice. In
> both cases if we would visit commit X twice, we'd immediately see on the
> second visit that it has already been cleared and not do anymore work.

Good point.  That makes clear_commit_marks_many() less useful than
advertised in e895cb5135, though.

>    Side note: Another question is whether it would simply be faster to
>    clear the flags for _all_ objects that we've touched in the current
>    process (we have clear_object_flags() for this already). Then we know
>    that we touch each one once, and we as a bonus we don't even have to
>    keep the previous tips. The downsides are:
> 
>      - if another traversal in the process looked at many objects, but
>        our current traversal looked at few, then we would examine more
>        objects than we need to (albeit with lower cost per object)
> 
>      - it's possible there's another traversal in the same process whose
>        flags we would want to have saved. I suspect such a setup is
>        broken already, though, unless there's a guarantee that the two
>        traversals don't overlap.

I thought about that nuclear option as well.  It might be a good idea
for code in cmd_* and similar leaf functions for cleaning up between
unrelated stages (e.g. between parts that had been separate external
git command calls before).  They probably only load potentially
interesting objects into memory and don't need to bother much about
interactions with other functions.

But clear_object_flags() makes me nervous because it clears the flags
of all kinds of objects, not just for commits, and I can't easily
convince myself that this is safe.  Adding a version that checks the
object type would be an easy way out.

René

[PATCH v2 0/9] revision: get rid of the flag leak_pending

[René Scharfe]

The flag leak_pending is weird, let's get rid of it.

Changes from v1: Everything.

An independent optimization found while working on this series:

  commit: avoid allocation in clear_commit_marks_many()

Trivial unrelated conversions (included as bonus patches):

  commit: use clear_commit_marks_many() in remove_redundant()
  ref-filter: use clear_commit_marks_many() in do_merge_filter()

A new function is introduced, will be used by checkout:

  object: add clear_commit_marks_all()

The users of leak_pending are are converted to use alternatives:

  bisect: avoid using the rev_info flag leak_pending
  bundle: avoid using the rev_info flag leak_pending
  checkout: avoid using the rev_info flag leak_pending

Cleanups:

  revision: remove the unused flag leak_pending
  commit: remove unused function clear_commit_marks_for_object_array()

 bisect.c           | 30 +++++++++---------------------
 builtin/checkout.c | 13 +------------
 bundle.c           | 35 ++++++++++++++++-------------------
 commit.c           | 19 ++-----------------
 commit.h           |  1 -
 object.c           | 11 +++++++++++
 object.h           |  5 +++++
 ref-filter.c       |  3 +--
 revision.c         |  3 +--
 revision.h         | 12 ------------
 10 files changed, 46 insertions(+), 86 deletions(-)

-- 
2.15.1

[PATCH v2 1/9] commit: avoid allocation in clear_commit_marks_many()

[René Scharfe]

Pass the entries of the commit array directly to clear_commit_marks_1()
instead of adding them to a commit_list first.  The function clears the
commit and any first parent without allocation; only higher numbered
parents are added to a list for later treatment.  This change extends
that optimization to clear_commit_marks_many().

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 commit.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/commit.c b/commit.c
index cab8d4455b..82667514bd 100644
--- a/commit.c
+++ b/commit.c
@@ -545,11 +545,11 @@ static void clear_commit_marks_1(struct commit_list **plist,
 void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark)
 {
 	struct commit_list *list = NULL;
 
 	while (nr--) {
-		commit_list_insert(*commit, &list);
+		clear_commit_marks_1(&list, *commit, mark);
 		commit++;
 	}
 	while (list)
 		clear_commit_marks_1(&list, pop_commit(&list), mark);
 }
-- 
2.15.1

[PATCH v2 2/9] commit: use clear_commit_marks_many() in remove_redundant()

[René Scharfe]

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 commit.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/commit.c b/commit.c
index 82667514bd..9edc12f338 100644
--- a/commit.c
+++ b/commit.c
@@ -929,8 +929,7 @@ static int remove_redundant(struct commit **array, int cnt)
 			if (work[j]->object.flags & PARENT1)
 				redundant[filled_index[j]] = 1;
 		clear_commit_marks(array[i], all_flags);
-		for (j = 0; j < filled; j++)
-			clear_commit_marks(work[j], all_flags);
+		clear_commit_marks_many(filled, work, all_flags);
 		free_commit_list(common);
 	}
 
-- 
2.15.1

[PATCH v2 3/9] ref-filter: use clear_commit_marks_many() in do_merge_filter()

[René Scharfe]

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 ref-filter.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/ref-filter.c b/ref-filter.c
index 3f9161707e..f9e25aea7a 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1995,8 +1995,7 @@ static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
 			free_array_item(item);
 	}
 
-	for (i = 0; i < old_nr; i++)
-		clear_commit_marks(to_clear[i], ALL_REV_FLAGS);
+	clear_commit_marks_many(old_nr, to_clear, ALL_REV_FLAGS);
 	clear_commit_marks(filter->merge_commit, ALL_REV_FLAGS);
 	free(to_clear);
 }
-- 
2.15.1

[PATCH v2 4/9] object: add clear_commit_marks_all()

[René Scharfe]

Add a function for clearing the commit marks of all in-core commit
objects.  It's similar to clear_object_flags(), but more precise, since
it leaves the other object types alone.  It still has to iterate through
them, though.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 object.c | 11 +++++++++++
 object.h |  5 +++++
 2 files changed, 16 insertions(+)

diff --git a/object.c b/object.c
index b9a4a0e501..0afdfd19b7 100644
--- a/object.c
+++ b/object.c
@@ -434,3 +434,14 @@ void clear_object_flags(unsigned flags)
 			obj->flags &= ~flags;
 	}
 }
+
+void clear_commit_marks_all(unsigned int flags)
+{
+	int i;
+
+	for (i = 0; i < obj_hash_size; i++) {
+		struct object *obj = obj_hash[i];
+		if (obj && obj->type == OBJ_COMMIT)
+			obj->flags &= ~flags;
+	}
+}
diff --git a/object.h b/object.h
index df8abe96f7..1111f64dd9 100644
--- a/object.h
+++ b/object.h
@@ -148,4 +148,9 @@ void object_array_clear(struct object_array *array);
 
 void clear_object_flags(unsigned flags);
 
+/*
+ * Clear the specified object flags from all in-core commit objects.
+ */
+extern void clear_commit_marks_all(unsigned int flags);
+
 #endif /* OBJECT_H */
-- 
2.15.1

[PATCH v2 5/9] bisect: avoid using the rev_info flag leak_pending

[René Scharfe]

The leak_pending flag is so awkward to use that multiple comments had to
be added around each occurrence.  We only use it for remembering the
commits whose marks we have to clear after checking if all of the good
ones are ancestors of the bad one.  This is easy, though: We need to do
that for the bad and good commits, of course.

Let check_good_are_ancestors_of_bad() create and own the array of bad
and good commits, and use it to clear the commit marks as well.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 bisect.c | 30 +++++++++---------------------
 1 file changed, 9 insertions(+), 21 deletions(-)

diff --git a/bisect.c b/bisect.c
index 0fca17c02b..c02accaf3c 100644
--- a/bisect.c
+++ b/bisect.c
@@ -790,100 +790,88 @@ static void handle_skipped_merge_base(const struct object_id *mb)
  * - If one is "skipped", we can't know but we should warn.
  * - If we don't know, we should check it out and ask the user to test.
  */
-static void check_merge_bases(int no_checkout)
+static void check_merge_bases(int rev_nr, struct commit **rev, int no_checkout)
 {
 	struct commit_list *result;
-	int rev_nr;
-	struct commit **rev = get_bad_and_good_commits(&rev_nr);
 
 	result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1);
 
 	for (; result; result = result->next) {
 		const struct object_id *mb = &result->item->object.oid;
 		if (!oidcmp(mb, current_bad_oid)) {
 			handle_bad_merge_base();
 		} else if (0 <= oid_array_lookup(&good_revs, mb)) {
 			continue;
 		} else if (0 <= oid_array_lookup(&skipped_revs, mb)) {
 			handle_skipped_merge_base(mb);
 		} else {
 			printf(_("Bisecting: a merge base must be tested\n"));
 			exit(bisect_checkout(mb, no_checkout));
 		}
 	}
 
-	free(rev);
 	free_commit_list(result);
 }
 
-static int check_ancestors(const char *prefix)
+static int check_ancestors(int rev_nr, struct commit **rev, const char *prefix)
 {
 	struct rev_info revs;
-	struct object_array pending_copy;
 	int res;
 
 	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
 
-	/* Save pending objects, so they can be cleaned up later. */
-	pending_copy = revs.pending;
-	revs.leak_pending = 1;
-
-	/*
-	 * bisect_common calls prepare_revision_walk right away, which
-	 * (together with .leak_pending = 1) makes us the sole owner of
-	 * the list of pending objects.
-	 */
 	bisect_common(&revs);
 	res = (revs.commits != NULL);
 
 	/* Clean up objects used, as they will be reused. */
-	clear_commit_marks_for_object_array(&pending_copy, ALL_REV_FLAGS);
-
-	object_array_clear(&pending_copy);
+	clear_commit_marks_many(rev_nr, rev, ALL_REV_FLAGS);
 
 	return res;
 }
 
 /*
  * "check_good_are_ancestors_of_bad" checks that all "good" revs are
  * ancestor of the "bad" rev.
  *
  * If that's not the case, we need to check the merge bases.
  * If a merge base must be tested by the user, its source code will be
  * checked out to be tested by the user and we will exit.
  */
 static void check_good_are_ancestors_of_bad(const char *prefix, int no_checkout)
 {
 	char *filename = git_pathdup("BISECT_ANCESTORS_OK");
 	struct stat st;
-	int fd;
+	int fd, rev_nr;
+	struct commit **rev;
 
 	if (!current_bad_oid)
 		die(_("a %s revision is needed"), term_bad);
 
 	/* Check if file BISECT_ANCESTORS_OK exists. */
 	if (!stat(filename, &st) && S_ISREG(st.st_mode))
 		goto done;
 
 	/* Bisecting with no good rev is ok. */
 	if (good_revs.nr == 0)
 		goto done;
 
 	/* Check if all good revs are ancestor of the bad rev. */
-	if (check_ancestors(prefix))
-		check_merge_bases(no_checkout);
+	rev = get_bad_and_good_commits(&rev_nr);
+	if (check_ancestors(rev_nr, rev, prefix))
+		check_merge_bases(rev_nr, rev, no_checkout);
+	free(rev);
 
 	/* Create file BISECT_ANCESTORS_OK. */
 	fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
 	if (fd < 0)
 		warning_errno(_("could not create file '%s'"),
 			      filename);
 	else
 		close(fd);
  done:
 	free(filename);
 }
 
 /*
  * This does "git diff-tree --pretty COMMIT" without one fork+exec.
  */
-- 
2.15.1

[PATCH v2 6/9] bundle: avoid using the rev_info flag leak_pending

[René Scharfe]

The leak_pending flag is so awkward to use that multiple comments had to
be added around each occurrence.  We use it for remembering the
prerequisites for the bundle.  That is easy, though: We have the
ref_list named "prerequisites" in the header for just that purpose.

Use this original list of prerequisites to check if all of them are
present and to clear their commit marks afterward.  The two new loops
are intentionally kept similar to the first one in the function.
Calling parse_object() a second time is expected be quick and successful
in each case -- any errors should have been handled in the first round.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 bundle.c | 35 ++++++++++++++++-------------------
 1 file changed, 16 insertions(+), 19 deletions(-)

diff --git a/bundle.c b/bundle.c
index 93290962c9..efe547e25f 100644
--- a/bundle.c
+++ b/bundle.c
@@ -128,83 +128,80 @@ static int list_refs(struct ref_list *r, int argc, const char **argv)
 int verify_bundle(struct bundle_header *header, int verbose)
 {
 	/*
 	 * Do fast check, then if any prereqs are missing then go line by line
 	 * to be verbose about the errors
 	 */
 	struct ref_list *p = &header->prerequisites;
 	struct rev_info revs;
 	const char *argv[] = {NULL, "--all", NULL};
-	struct object_array refs;
 	struct commit *commit;
 	int i, ret = 0, req_nr;
 	const char *message = _("Repository lacks these prerequisite commits:");
 
 	init_revisions(&revs, NULL);
 	for (i = 0; i < p->nr; i++) {
 		struct ref_list_entry *e = p->list + i;
 		struct object *o = parse_object(&e->oid);
 		if (o) {
 			o->flags |= PREREQ_MARK;
 			add_pending_object(&revs, o, e->name);
 			continue;
 		}
 		if (++ret == 1)
 			error("%s", message);
 		error("%s %s", oid_to_hex(&e->oid), e->name);
 	}
 	if (revs.pending.nr != p->nr)
 		return ret;
 	req_nr = revs.pending.nr;
 	setup_revisions(2, argv, &revs, NULL);
 
-	/* Save pending objects, so they can be cleaned up later. */
-	refs = revs.pending;
-	revs.leak_pending = 1;
-
-	/*
-	 * prepare_revision_walk (together with .leak_pending = 1) makes us
-	 * the sole owner of the list of pending objects.
-	 */
 	if (prepare_revision_walk(&revs))
 		die(_("revision walk setup failed"));
 
 	i = req_nr;
 	while (i && (commit = get_revision(&revs)))
 		if (commit->object.flags & PREREQ_MARK)
 			i--;
 
-	for (i = 0; i < req_nr; i++)
-		if (!(refs.objects[i].item->flags & SHOWN)) {
-			if (++ret == 1)
-				error("%s", message);
-			error("%s %s", oid_to_hex(&refs.objects[i].item->oid),
-				refs.objects[i].name);
-		}
+	for (i = 0; i < p->nr; i++) {
+		struct ref_list_entry *e = p->list + i;
+		struct object *o = parse_object(&e->oid);
+		assert(o); /* otherwise we'd have returned early */
+		if (o->flags & SHOWN)
+			continue;
+		if (++ret == 1)
+			error("%s", message);
+		error("%s %s", oid_to_hex(&e->oid), e->name);
+	}
 
 	/* Clean up objects used, as they will be reused. */
-	clear_commit_marks_for_object_array(&refs, ALL_REV_FLAGS);
-
-	object_array_clear(&refs);
+	for (i = 0; i < p->nr; i++) {
+		struct ref_list_entry *e = p->list + i;
+		commit = lookup_commit_reference_gently(&e->oid, 1);
+		if (commit)
+			clear_commit_marks(commit, ALL_REV_FLAGS);
+	}
 
 	if (verbose) {
 		struct ref_list *r;
 
 		r = &header->references;
 		printf_ln(Q_("The bundle contains this ref:",
 			     "The bundle contains these %d refs:",
 			     r->nr),
 			  r->nr);
 		list_refs(r, 0, NULL);
 		r = &header->prerequisites;
 		if (!r->nr) {
 			printf_ln(_("The bundle records a complete history."));
 		} else {
 			printf_ln(Q_("The bundle requires this ref:",
 				     "The bundle requires these %d refs:",
 				     r->nr),
 				  r->nr);
 			list_refs(r, 0, NULL);
 		}
 	}
 	return ret;
 }
-- 
2.15.1

[PATCH v2 7/9] checkout: avoid using the rev_info flag leak_pending

[René Scharfe]

The leak_pending flag is so awkward to use that multiple comments had to
be added around each occurrence.  We only use it for remembering the
commits whose marks we have to clear after checking if the old HEAD is
detached.  This is easy, though: We need to do that for the old commit,
the new one -- and for all refs.

Don't bother tracking exactly which commits need their flags cleared,
just nuke all we have in-core.  This change is safe because refs can
point at anything, so other program parts can't depend on any kept flags
anyway.  And since all refs are loaded we have to basically deal with
all commits anyway, so performance should not be negatively impacted.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 builtin/checkout.c | 13 +------------
 1 file changed, 1 insertion(+), 12 deletions(-)

diff --git a/builtin/checkout.c b/builtin/checkout.c
index f9f3797e11..afb225ca79 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -790,37 +790,26 @@ static void suggest_reattach(struct commit *commit, struct rev_info *revs)
 static void orphaned_commit_warning(struct commit *old, struct commit *new)
 {
 	struct rev_info revs;
 	struct object *object = &old->object;
-	struct object_array refs;
 
 	init_revisions(&revs, NULL);
 	setup_revisions(0, NULL, &revs, NULL);
 
 	object->flags &= ~UNINTERESTING;
 	add_pending_object(&revs, object, oid_to_hex(&object->oid));
 
 	for_each_ref(add_pending_uninteresting_ref, &revs);
 	add_pending_oid(&revs, "HEAD", &new->object.oid, UNINTERESTING);
 
-	/* Save pending objects, so they can be cleaned up later. */
-	refs = revs.pending;
-	revs.leak_pending = 1;
-
-	/*
-	 * prepare_revision_walk (together with .leak_pending = 1) makes us
-	 * the sole owner of the list of pending objects.
-	 */
 	if (prepare_revision_walk(&revs))
 		die(_("internal error in revision walk"));
 	if (!(old->object.flags & UNINTERESTING))
 		suggest_reattach(old, &revs);
 	else
 		describe_detached_head(_("Previous HEAD position was"), old);
 
 	/* Clean up objects used, as they will be reused. */
-	clear_commit_marks_for_object_array(&refs, ALL_REV_FLAGS);
-
-	object_array_clear(&refs);
+	clear_commit_marks_all(ALL_REV_FLAGS);
 }
 
 static int switch_branches(const struct checkout_opts *opts,
-- 
2.15.1

[PATCH v2 8/9] revision: remove the unused flag leak_pending

[René Scharfe]

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 revision.c |  3 +--
 revision.h | 12 ------------
 2 files changed, 1 insertion(+), 14 deletions(-)

diff --git a/revision.c b/revision.c
index f6a3da5cd9..7239315de9 100644
--- a/revision.c
+++ b/revision.c
@@ -2860,8 +2860,7 @@ int prepare_revision_walk(struct rev_info *revs)
 			}
 		}
 	}
-	if (!revs->leak_pending)
-		object_array_clear(&old_pending);
+	object_array_clear(&old_pending);
 
 	/* Signal whether we need per-parent treesame decoration */
 	if (revs->simplify_merges ||
diff --git a/revision.h b/revision.h
index 54761200ad..27be70e75c 100644
--- a/revision.h
+++ b/revision.h
@@ -150,18 +150,6 @@ struct rev_info {
 			date_mode_explicit:1,
 			preserve_subject:1;
 	unsigned int	disable_stdin:1;
-	/*
-	 * Set `leak_pending` to prevent `prepare_revision_walk()` from clearing
-	 * the array of pending objects (`pending`). It will still forget about
-	 * the array and its entries, so they really are leaked. This can be
-	 * useful if the `struct object_array` `pending` is copied before
-	 * calling `prepare_revision_walk()`. By setting `leak_pending`, you
-	 * effectively claim ownership of the old array, so you should most
-	 * likely call `object_array_clear(&pending_copy)` once you are done.
-	 * Observe that this is about ownership of the array and its entries,
-	 * not the commits referenced by those entries.
-	 */
-	unsigned int	leak_pending:1;
 	/* --show-linear-break */
 	unsigned int	track_linear:1,
 			track_first_time:1,
-- 
2.15.1

[PATCH v2 9/9] commit: remove unused function clear_commit_marks_for_object_array()

[René Scharfe]

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 commit.c | 14 --------------
 commit.h |  1 -
 2 files changed, 15 deletions(-)

diff --git a/commit.c b/commit.c
index 9edc12f338..ff51c9f34a 100644
--- a/commit.c
+++ b/commit.c
@@ -559,20 +559,6 @@ void clear_commit_marks(struct commit *commit, unsigned int mark)
 	clear_commit_marks_many(1, &commit, mark);
 }
 
-void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
-{
-	struct object *object;
-	struct commit *commit;
-	unsigned int i;
-
-	for (i = 0; i < a->nr; i++) {
-		object = a->objects[i].item;
-		commit = lookup_commit_reference_gently(&object->oid, 1);
-		if (commit)
-			clear_commit_marks(commit, mark);
-	}
-}
-
 struct commit *pop_commit(struct commit_list **stack)
 {
 	struct commit_list *top = *stack;
diff --git a/commit.h b/commit.h
index 99a3fea68d..bdf14f0a72 100644
--- a/commit.h
+++ b/commit.h
@@ -219,7 +219,6 @@ struct commit *pop_commit(struct commit_list **stack);
 
 void clear_commit_marks(struct commit *commit, unsigned int mark);
 void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);
-void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);
 
 
 enum rev_sort_order {
-- 
2.15.1

Re: [PATCH v2 0/9] revision: get rid of the flag leak_pending

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> The flag leak_pending is weird, let's get rid of it.
>
> Changes from v1: Everything.

;-)

> An independent optimization found while working on this series:
>
>   commit: avoid allocation in clear_commit_marks_many()
>
> Trivial unrelated conversions (included as bonus patches):
>
>   commit: use clear_commit_marks_many() in remove_redundant()
>   ref-filter: use clear_commit_marks_many() in do_merge_filter()
>
> A new function is introduced, will be used by checkout:
>
>   object: add clear_commit_marks_all()
>
> The users of leak_pending are are converted to use alternatives:
>
>   bisect: avoid using the rev_info flag leak_pending
>   bundle: avoid using the rev_info flag leak_pending
>   checkout: avoid using the rev_info flag leak_pending
>
> Cleanups:
>
>   revision: remove the unused flag leak_pending
>   commit: remove unused function clear_commit_marks_for_object_array()

Will take a look at.  Thanks.

>
>  bisect.c           | 30 +++++++++---------------------
>  builtin/checkout.c | 13 +------------
>  bundle.c           | 35 ++++++++++++++++-------------------
>  commit.c           | 19 ++-----------------
>  commit.h           |  1 -
>  object.c           | 11 +++++++++++
>  object.h           |  5 +++++
>  ref-filter.c       |  3 +--
>  revision.c         |  3 +--
>  revision.h         | 12 ------------
>  10 files changed, 46 insertions(+), 86 deletions(-)

Re: [PATCH v2 6/9] bundle: avoid using the rev_info flag leak_pending

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> The leak_pending flag is so awkward to use that multiple comments had to
> be added around each occurrence.  We use it for remembering the
> prerequisites for the bundle.  That is easy, though: We have the
> ref_list named "prerequisites" in the header for just that purpose.

Hmph.

>  int verify_bundle(struct bundle_header *header, int verbose)
>  {
>  ...
>  	struct rev_info revs;
>  	const char *argv[] = {NULL, "--all", NULL};
> -	struct object_array refs;
>  	struct commit *commit;
>  	int i, ret = 0, req_nr;
>  	const char *message = _("Repository lacks these prerequisite commits:");
>  
>  	init_revisions(&revs, NULL);
>  	for (i = 0; i < p->nr; i++) {
>  		struct ref_list_entry *e = p->list + i;
>  		struct object *o = parse_object(&e->oid);
>  		if (o) {
>  			o->flags |= PREREQ_MARK;
>  			add_pending_object(&revs, o, e->name);
>  			continue;
>  		}

We mark the prereq objects with PREREQ_MARK and then ...

>  		if (++ret == 1)
>  			error("%s", message);
>  		error("%s %s", oid_to_hex(&e->oid), e->name);
>  	}
>  	if (revs.pending.nr != p->nr)
>  		return ret;
>  	req_nr = revs.pending.nr;
>  	setup_revisions(2, argv, &revs, NULL);

... run "rev-list" with "--all" plus these prereq objects, and ...

> ...
>  	i = req_nr;
>  	while (i && (commit = get_revision(&revs)))
>  		if (commit->object.flags & PREREQ_MARK)
>  			i--;

... let the traversal run until we see all the objects with PREREQ_MARK
set (i.e. those that appear in p->list[]).

> ...
> +	for (i = 0; i < p->nr; i++) {
> +		struct ref_list_entry *e = p->list + i;
> +		struct object *o = parse_object(&e->oid);
> +		assert(o); /* otherwise we'd have returned early */
> +		if (o->flags & SHOWN)
> +			continue;
> +		if (++ret == 1)
> +			error("%s", message);
> +		error("%s %s", oid_to_hex(&e->oid), e->name);
> +	}

And then make sure that all of those that appear in p->list[] are
already shown.

Doesn't that mean that these SHOWN and other flags are first given
to the commits at the tip of "--all" refs and propagated down to
those in p->list[]?  Would it be sufficient to clear those that can
be reached from them, like the following?

>  
>  	/* Clean up objects used, as they will be reused. */
> -	clear_commit_marks_for_object_array(&refs, ALL_REV_FLAGS);
> -
> -	object_array_clear(&refs);
> +	for (i = 0; i < p->nr; i++) {
> +		struct ref_list_entry *e = p->list + i;
> +		commit = lookup_commit_reference_gently(&e->oid, 1);
> +		if (commit)
> +			clear_commit_marks(commit, ALL_REV_FLAGS);
> +	}

I do not think the patch in question changes behaviour.  The set of
objects the code starts the clearing does not change.  So I am more
puzzled by the original than the conversion done with this change.

Re: [PATCH v2 7/9] checkout: avoid using the rev_info flag leak_pending

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> diff --git a/builtin/checkout.c b/builtin/checkout.c
> index f9f3797e11..afb225ca79 100644
> --- a/builtin/checkout.c
> +++ b/builtin/checkout.c
> @@ -790,37 +790,26 @@ static void suggest_reattach(struct commit *commit, struct rev_info *revs)
>  static void orphaned_commit_warning(struct commit *old, struct commit *new)
>  {
>  	struct rev_info revs;
>  	struct object *object = &old->object;
> -	struct object_array refs;
>  
>  	init_revisions(&revs, NULL);
>  	setup_revisions(0, NULL, &revs, NULL);
>  
>  	object->flags &= ~UNINTERESTING;
>  	add_pending_object(&revs, object, oid_to_hex(&object->oid));
>  
>  	for_each_ref(add_pending_uninteresting_ref, &revs);
>  	add_pending_oid(&revs, "HEAD", &new->object.oid, UNINTERESTING);

Somewhat unrelated tangent, but I mention it only because that it
appears that the use of leak-pending is closely associated with the
"are these objects all reachable from some ref?" query.  This one of
course is asking that exact question (and the way to ask that in a
script is "rev-list $objects --not --all" to see if anything comes
out). The one in "bundle" we saw earlier is another one.  Even
though the implementation is quite different, everything_local()
shares the same purpose.  

I wonder if we want a single unified implementation of this query so
that reinventions do not have to get the details wrong.

The conversion looks obviously correct.  Thanks.

Re: [PATCH v2 1/9] commit: avoid allocation in clear_commit_marks_many()

[Jeff King]

On Mon, Dec 25, 2017 at 06:43:37PM +0100, René Scharfe wrote:

> Pass the entries of the commit array directly to clear_commit_marks_1()
> instead of adding them to a commit_list first.  The function clears the
> commit and any first parent without allocation; only higher numbered
> parents are added to a list for later treatment.  This change extends
> that optimization to clear_commit_marks_many().

It took a bit of head-scratching to see that is indeed what
clear_commit_marks_1 does. I suspect this doesn't make all that big a
difference in practice (after all, we're doing an allocation for each
merge anyway, so allocating for the tips is likely to be a subset), but
it doesn't hurt to do so.

-Peff

Re: [PATCH v2 4/9] object: add clear_commit_marks_all()

[Jeff King]

On Mon, Dec 25, 2017 at 06:44:58PM +0100, René Scharfe wrote:

> Add a function for clearing the commit marks of all in-core commit
> objects.  It's similar to clear_object_flags(), but more precise, since
> it leaves the other object types alone.  It still has to iterate through
> them, though.

Makes sense.

Is it worth having:

  void clear_object_flags_from_type(int type, unsigned flags);

rather than having two near-identical functions? I guess we'd need some
way of saying "all types" to reimplement clear_object_flags() as a
wrapper (OBJ_NONE, I guess?).

The run-time check is maybe a little bit slower in the middle of a tight
loop, but I'm not sure it would matter much (I'd actually be curious if
this approach is faster than the existing traversal code, too).

-Peff

Re: [PATCH v2 5/9] bisect: avoid using the rev_info flag leak_pending

[Jeff King]

On Mon, Dec 25, 2017 at 06:45:36PM +0100, René Scharfe wrote:

> The leak_pending flag is so awkward to use that multiple comments had to
> be added around each occurrence.  We only use it for remembering the
> commits whose marks we have to clear after checking if all of the good
> ones are ancestors of the bad one.  This is easy, though: We need to do
> that for the bad and good commits, of course.

Are we sure that our list is the same as what is traversed? I won't be
surprised if it is true, but it doesn't seem immediately obvious from
the code:

> -static int check_ancestors(const char *prefix)
> +static int check_ancestors(int rev_nr, struct commit **rev, const char *prefix)
>  {

So now we take in a set of objects...

>  	struct rev_info revs;
> -	struct object_array pending_copy;
>  	int res;
>  
>  	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);

But those objects aren't provided here. bisect_rev_setup() puts its own
set of objects into the pending list...

> -	/* Save pending objects, so they can be cleaned up later. */
> -	pending_copy = revs.pending;
> -	revs.leak_pending = 1;
> -
> -	/*
> -	 * bisect_common calls prepare_revision_walk right away, which
> -	 * (together with .leak_pending = 1) makes us the sole owner of
> -	 * the list of pending objects.
> -	 */
>  	bisect_common(&revs);
>  	res = (revs.commits != NULL);

And then we traverse, and then...

>  
>  	/* Clean up objects used, as they will be reused. */
> -	clear_commit_marks_for_object_array(&pending_copy, ALL_REV_FLAGS);
> -
> -	object_array_clear(&pending_copy);
> +	clear_commit_marks_many(rev_nr, rev, ALL_REV_FLAGS);

...this is the first time we look at "rev".

If we already have the list of tips, could we just feed it ourselves to
bisect_rev_setup (I think that would require us remembering which were
"good" and "bad", but that doesn't seem like a big deal).

I'm not overly concerned that you've introduced a bug here, but just
wondering if we could make this a bit more maintainable going forward.

-Peff

Re: [PATCH v2 6/9] bundle: avoid using the rev_info flag leak_pending

[Jeff King]

On Mon, Dec 25, 2017 at 06:46:14PM +0100, René Scharfe wrote:

> The leak_pending flag is so awkward to use that multiple comments had to
> be added around each occurrence.  We use it for remembering the
> prerequisites for the bundle.  That is easy, though: We have the
> ref_list named "prerequisites" in the header for just that purpose.
> 
> Use this original list of prerequisites to check if all of them are
> present and to clear their commit marks afterward.  The two new loops
> are intentionally kept similar to the first one in the function.
> Calling parse_object() a second time is expected be quick and successful
> in each case -- any errors should have been handled in the first round.

There are a few code paths which unset the "parsed" flag, and could
cause us to actually re-load an object. I doubt we could trigger any
here. And AFAICT this is what the original code was doing inside the
helper function anyway.

I do wonder what this is supposed to do for refs that point to
non-commits (both before and after your patch). Are we failing to clear
the flags on them?

I guess not, because we do not pass "--objects" to the traversal in the
first place, so we would never visit them (though that also makes me
wonder if we do the wrong thing in the verification step for such a
ref).

-Peff

Re: [PATCH v2 0/9] revision: get rid of the flag leak_pending

[Jeff King]

On Mon, Dec 25, 2017 at 06:41:18PM +0100, René Scharfe wrote:

> The flag leak_pending is weird, let's get rid of it.
> 
> Changes from v1: Everything.

I left a few comments, but didn't see any show-stoppers (which is good,
because this is already in 'next' ;) ). Any I didn't comment on looked
fine to me.

-Peff

Re: [PATCH v2 4/9] object: add clear_commit_marks_all()

[René Scharfe]

Am 10.01.2018 um 08:58 schrieb Jeff King:
> On Mon, Dec 25, 2017 at 06:44:58PM +0100, René Scharfe wrote:
> 
>> Add a function for clearing the commit marks of all in-core commit
>> objects.  It's similar to clear_object_flags(), but more precise, since
>> it leaves the other object types alone.  It still has to iterate through
>> them, though.
> 
> Makes sense.
> 
> Is it worth having:
> 
>    void clear_object_flags_from_type(int type, unsigned flags);
> 
> rather than having two near-identical functions? I guess we'd need some
> way of saying "all types" to reimplement clear_object_flags() as a
> wrapper (OBJ_NONE, I guess?).

I don't know if there is a demand.  Perhaps the two callers of
clear_object_flags() should be switched to clear_commit_marks_all()?
They look like they only care about commits as well.  Or is it safe to
stomp over the flags of objects of other types?  Then we'd only need
to keep clear_object_flags()..

> The run-time check is maybe a little bit slower in the middle of a tight
> loop, but I'm not sure it would matter much (I'd actually be curious if
> this approach is faster than the existing traversal code, too).

I don't know how to measure this properly.  With 100 runs each I get
this for the git repo and the silly test program below, which measures
the duration of the respective function call:

   mean        stddev method
   ----------- ------ ----------------------
   5.89763e+06 613106 clear_commit_marks
   2.72572e+06 507689 clear_commit_marks_all
   1.96582e+06 494753 clear_object_flags

So these are noisy numbers, but kind of in the expected range.

René

---
 Makefile                           |  1 +
 t/helper/test-clear-commit-marks.c | 67 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 68 insertions(+)
 create mode 100644 t/helper/test-clear-commit-marks.c

diff --git a/Makefile b/Makefile
index 1a9b23b679..7db2c6ca7f 100644
--- a/Makefile
+++ b/Makefile
@@ -648,6 +648,7 @@ X =
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
 TEST_PROGRAMS_NEED_X += test-chmtime
+TEST_PROGRAMS_NEED_X += test-clear-commit-marks
 TEST_PROGRAMS_NEED_X += test-ctype
 TEST_PROGRAMS_NEED_X += test-config
 TEST_PROGRAMS_NEED_X += test-date
diff --git a/t/helper/test-clear-commit-marks.c b/t/helper/test-clear-commit-marks.c
new file mode 100644
index 0000000000..296ca0286f
--- /dev/null
+++ b/t/helper/test-clear-commit-marks.c
@@ -0,0 +1,67 @@
+#include "cache.h"
+#include "commit.h"
+#include "revision.h"
+
+static void start(struct timespec *start)
+{
+	clock_gettime(CLOCK_MONOTONIC, start);
+}
+
+static void print_duration(struct timespec *start)
+{
+	struct timespec end;
+	uint64_t d;
+	clock_gettime(CLOCK_MONOTONIC, &end);
+	d = end.tv_sec - start->tv_sec;
+	d *= 1000000000;
+	d += end.tv_nsec - start->tv_nsec;
+	printf("%lu", d);
+}
+
+int cmd_main(int argc, const char **argv)
+{
+	struct rev_info revs;
+	struct object_id oid;
+	struct commit *commit;
+	struct timespec ts;
+
+	setup_git_directory();
+
+	if (get_oid("HEAD", &oid))
+		die("No HEAD?");
+	commit = lookup_commit(&oid);
+	if (!commit)
+		die("HEAD is not a committish?");
+
+	init_revisions(&revs, NULL);
+	add_pending_object(&revs, &commit->object, "HEAD");
+	if (prepare_revision_walk(&revs))
+		die("revision walk setup failed");
+	while (get_revision(&revs))
+		; /* nothing */
+
+	if (argc != 2)
+		return 0;
+
+	if (!strcmp(argv[1], "clear_commit_marks")) {
+		start(&ts);
+		clear_commit_marks(commit, ALL_REV_FLAGS);
+		print_duration(&ts);
+	}
+
+	if (!strcmp(argv[1], "clear_commit_marks_all")) {
+		start(&ts);
+		clear_commit_marks_all(ALL_REV_FLAGS);
+		print_duration(&ts);
+	}
+
+	if (!strcmp(argv[1], "clear_object_flags")) {
+		start(&ts);
+		clear_object_flags(ALL_REV_FLAGS);
+		print_duration(&ts);
+	}
+
+	printf(" %s\n", argv[1]);
+
+	return 0;
+}
-- 
2.15.1

Re: [PATCH v2 5/9] bisect: avoid using the rev_info flag leak_pending

[René Scharfe]

Am 10.01.2018 um 09:07 schrieb Jeff King:
> On Mon, Dec 25, 2017 at 06:45:36PM +0100, René Scharfe wrote:
> 
>> The leak_pending flag is so awkward to use that multiple comments had to
>> be added around each occurrence.  We only use it for remembering the
>> commits whose marks we have to clear after checking if all of the good
>> ones are ancestors of the bad one.  This is easy, though: We need to do
>> that for the bad and good commits, of course.
> 
> Are we sure that our list is the same as what is traversed? I won't be
> surprised if it is true, but it doesn't seem immediately obvious from
> the code:
> 
>> -static int check_ancestors(const char *prefix)
>> +static int check_ancestors(int rev_nr, struct commit **rev, const char *prefix)
>>   {
> 
> So now we take in a set of objects...
> 
>>   	struct rev_info revs;
>> -	struct object_array pending_copy;
>>   	int res;
>>   
>>   	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
> 
> But those objects aren't provided here. bisect_rev_setup() puts its own
> set of objects into the pending list...

Yes, namely from the global variables current_bad_oid and good_revs.

>> -	/* Save pending objects, so they can be cleaned up later. */
>> -	pending_copy = revs.pending;
>> -	revs.leak_pending = 1;
>> -
>> -	/*
>> -	 * bisect_common calls prepare_revision_walk right away, which
>> -	 * (together with .leak_pending = 1) makes us the sole owner of
>> -	 * the list of pending objects.
>> -	 */
>>   	bisect_common(&revs);
>>   	res = (revs.commits != NULL);
> 
> And then we traverse, and then...
> 
>>   
>>   	/* Clean up objects used, as they will be reused. */
>> -	clear_commit_marks_for_object_array(&pending_copy, ALL_REV_FLAGS);
>> -
>> -	object_array_clear(&pending_copy);
>> +	clear_commit_marks_many(rev_nr, rev, ALL_REV_FLAGS);
> 
> ...this is the first time we look at "rev".

... which is populated by get_bad_and_good_commits() using the global
variables current_bad_oid and good_revs.

> If we already have the list of tips, could we just feed it ourselves to
> bisect_rev_setup (I think that would require us remembering which were
> "good" and "bad", but that doesn't seem like a big deal).

That's done already under the covers.  De-globalizing these variables
would make this visible.

Another way would be to store the bad and good revs in a format that
allows them to be used everywhere, thus avoiding confusing
duplication/conversions.  Commit pointers and arrays thereof should
work everywhere we currently use object_ids and oid_arrays for bad
and good revs, right?

René

Re: [PATCH v2 4/9] object: add clear_commit_marks_all()

[Jeff King]

On Thu, Jan 11, 2018 at 07:57:42PM +0100, René Scharfe wrote:

> > Is it worth having:
> > 
> >    void clear_object_flags_from_type(int type, unsigned flags);
> > 
> > rather than having two near-identical functions? I guess we'd need some
> > way of saying "all types" to reimplement clear_object_flags() as a
> > wrapper (OBJ_NONE, I guess?).
> 
> I don't know if there is a demand.  Perhaps the two callers of
> clear_object_flags() should be switched to clear_commit_marks_all()?
> They look like they only care about commits as well.  Or is it safe to
> stomp over the flags of objects of other types?  Then we'd only need
> to keep clear_object_flags()..

I'd worry that the call in reset_revision_walk() might want to clear
non-commits if the revisions have "--objects" passed to them.

I do suspect that clearing flags from all objects would just work in the
general case (since we're limiting ourselves to only a particular set of
flags). But it's probably not worth the risk of unintended fallout,
since there's not much benefit after your series.

> > The run-time check is maybe a little bit slower in the middle of a tight
> > loop, but I'm not sure it would matter much (I'd actually be curious if
> > this approach is faster than the existing traversal code, too).
> 
> I don't know how to measure this properly.  With 100 runs each I get
> this for the git repo and the silly test program below, which measures
> the duration of the respective function call:
> 
>    mean        stddev method
>    ----------- ------ ----------------------
>    5.89763e+06 613106 clear_commit_marks
>    2.72572e+06 507689 clear_commit_marks_all
>    1.96582e+06 494753 clear_object_flags
> 
> So these are noisy numbers, but kind of in the expected range.

That's about what I'd expect. The "bad" case for looking at all objects
is when there are a bunch of objects loaded that _weren't_ part of this
particular traversal. I have no idea how often that happens, but we can
guess at the impact in the worst case: having done a previous --objects
traversal in the process and then traversing all of the commits a second
time, we'd probably have about 5-10x as many objects to look through for
that second path. So clear_commit_marks() would win there.

The absolute numbers are small enough that it probably doesn't matter
either way.

-Peff

Re: [PATCH v2 5/9] bisect: avoid using the rev_info flag leak_pending

[Jeff King]

On Thu, Jan 11, 2018 at 07:57:51PM +0100, René Scharfe wrote:

> > If we already have the list of tips, could we just feed it ourselves to
> > bisect_rev_setup (I think that would require us remembering which were
> > "good" and "bad", but that doesn't seem like a big deal).
> 
> That's done already under the covers.  De-globalizing these variables
> would make this visible.
> 
> Another way would be to store the bad and good revs in a format that
> allows them to be used everywhere, thus avoiding confusing
> duplication/conversions.  Commit pointers and arrays thereof should
> work everywhere we currently use object_ids and oid_arrays for bad
> and good revs, right?

I think bisect_rev_setup() has to munge that into "^" and non-"^"
arguments. Though arguably we could shove stuff into the pending commit
list directly.

I dunno. It may not be worth spending more time on it.

-Peff