Re: jk/tag-contains: stalled

Jeff King [off-list ref] writes:

On Thu, Aug 05, 2010 at 10:05:58AM -0700, Junio C Hamano wrote:

quoted

quoted

quoted

quoted

* jk/tag-contains (2010-07-05) 4 commits
 - Why is "git tag --contains" so slow?
 - default core.clockskew variable to one day
 - limit "contains" traversals based on commit timestamp
 - tag: speed up --contains calculation

[...]

quoted

I agree in principle; the log messages need to be cleaned up first
at the least, though.

To reduce the risk of double-work, I need to clarify.

I meant to say that I can find enough material, especially what Peff
wrote, in the discussion that followed in the thread to do the clean-up
myself.  No need to resend by anybody unless there are material
differences from what have been discussed so far that need to be
incorporated in the final series.

The only bad log message should be the final one, which should be
dropped anyway. I would recommend just merging the first two for now,
and Ted can tweak his core.clockskew manually.

After re-reviewing the one that is queued, the use of TMP_MARK smelled
somewhat bad to me.  It is named TMP_ exactly because it is meant to be
used in a closed callpath---you can use it but you are supposed to clean
it before you return the control to the caller, so that the caller can
rely on TMP_MARK absent from any objects.

Use of UNINTERESTING is similarly not kosher if this were to be used in
larger context outside of "do 'tags --contains' and exit".  You noted
these two points in your original RFC patch.

Besides, "contains()" is too generic a name to live in commit.h.

My gut feeling is that it is probably Ok if contains() and its recursive
helper are moved to builtin/tag.c and are made static, to make it clear
that this should not be reused outside the current context as a generic
"contains" function.  It would probably help to have a comment at the end
of list_tags() to say that TMP_MARK _ought_ to be cleaned before leaving
the function but we don't do that because we know it is the last function
in the callchain before we exit.

By the way, I wonder why pop_most_recent_commit() with a commit_list,
which is the usual revision traversal ingredient for doing something like
this, was not used in the patch, though.  Is it because depth-first was
necessary?

On Thu, Aug 05, 2010 at 11:47:09AM -0700, Junio C Hamano wrote:

quoted

The only bad log message should be the final one, which should be
dropped anyway. I would recommend just merging the first two for now,
and Ted can tweak his core.clockskew manually.

After re-reviewing the one that is queued, the use of TMP_MARK smelled
somewhat bad to me.  It is named TMP_ exactly because it is meant to be
used in a closed callpath---you can use it but you are supposed to clean
it before you return the control to the caller, so that the caller can
rely on TMP_MARK absent from any objects.

Use of UNINTERESTING is similarly not kosher if this were to be used in
larger context outside of "do 'tags --contains' and exit".  You noted
these two points in your original RFC patch.

Oops, thanks, I had forgotten that the marks needed to be addressed.
Should I be introducing new flags? We have 27 flag bits, but I would
hate to waste 2 of them.

Besides, "contains()" is too generic a name to live in commit.h.

I agree it's a pretty generic name. I was trying to make this as generic
as possible, at least within the domain of commits, so it could be a
faster replacement for calls to is_descendant_of. Maybe commit_contains?

My gut feeling is that it is probably Ok if contains() and its
recursive helper are moved to builtin/tag.c and are made static, to
make it clear that this should not be reused outside the current
context as a generic "contains" function.  It would probably help to
have a comment at the end of list_tags() to say that TMP_MARK _ought_
to be cleaned before leaving the function but we don't do that because
we know it is the last function in the callchain before we exit.

But my intent was to have a generic contains function. I was planning on
applying this to "git branch --contains", as well, but my initial
approach wasn't really any faster than the current code (probably
because the number of branches tends to be small compared to the number
of tags).

In an ideal object-oriented world, the interface would be:

  void contains_init(struct contains_context *c,
                     struct commit_list *needles);
  void contains_check(struct contains_context *c, struct commit *haystack);
  void contains_free(struct contains_context *c);

But for memory use reasons, we don't get our own private copy of each
commit. We can drop the "init" and have a "free" or "clear" which clears
marks on the global commit objects. But you also _must_ use the same
needle list for each contains check, or you will get bogus results
(since the marks are essentially partial cached answers).

I guess we could do:

  static struct commit_list *contains_needles;

  void contains_init(struct commit_list *needles)
  {
          if (contains_needles)
                  die("BUG: somebody else is already checking contains!");
          copy_commit_list(&contains_needles, needles);
  }

  void contains_check(struct commit *haystack)
  {
     /* like contains, but check against our static contains_needles */
  }

  void contains_clear(struct contains_context *c)
  {
          /* free contains_needles list, set it to NULL */
          /* clear commit marks */
  }

By the way, I wonder why pop_most_recent_commit() with a commit_list,
which is the usual revision traversal ingredient for doing something like
this, was not used in the patch, though.  Is it because depth-first was
necessary?

Yes, it is because of the depth-first nature. The intent is to mark
whole sections of the subgraph as "does not contain". If you can think
of a clever way around that, I would be interested to hear it. The fact
that it is a DFS is why we can possibly perform worse than the current
code (we might follow the wrong branch of a merge all the way down to
the root before realizing the commit in question is on the other side).

-Peff

On Thu, Aug 5, 2010 at 3:06 PM, Jeff King [off-list ref] wrote:

I agree it's a pretty generic name. I was trying to make this as generic
as possible, at least within the domain of commits, so it could be a
faster replacement for calls to is_descendant_of. Maybe commit_contains?

I'm going to side-track this slightly. I wonder why branch and tag
have --contains, but it is not more generically available via
rev-list?  I needed it the other day and spent 5 minutes looking at
what it would take before I ended up just calling merge-base in a loop
for the commits I wanted to check.

j.

On Thu, Aug 05, 2010 at 03:18:15PM -0400, Jay Soffian wrote:

On Thu, Aug 5, 2010 at 3:06 PM, Jeff King [off-list ref] wrote:

quoted

I agree it's a pretty generic name. I was trying to make this as generic
as possible, at least within the domain of commits, so it could be a
faster replacement for calls to is_descendant_of. Maybe commit_contains?

I'm going to side-track this slightly. I wonder why branch and tag
have --contains, but it is not more generically available via
rev-list?  I needed it the other day and spent 5 minutes looking at
what it would take before I ended up just calling merge-base in a loop
for the commits I wanted to check.

I'm not sure rev-list makes the most sense. We already have "show
commits in X, but not in Y". But I gather you wanted "from a list
(U,V,W,X), print each that contains Y". Which is not really a rev-list
function anymore, as it is not about listing revisions, but rather about
grepping a list you've given it.

Something like "git for-each-ref --contains" seems more sensible to me,
though it is not as generic as we could make it (I cannot use an
arbitrary list of commits to the "haystack", but only ones that have
refs pointing to them).

-Peff

On Thu, Aug 5, 2010 at 3:27 PM, Jeff King [off-list ref] wrote:

I'm not sure rev-list makes the most sense. We already have "show
commits in X, but not in Y". But I gather you wanted "from a list
(U,V,W,X), print each that contains Y".

Correct.

Which is not really a rev-list
function anymore, as it is not about listing revisions, but rather about
grepping a list you've given it.

Well maybe, but rev-list will already take a list of revs on stdin and
you can give it --no-walk, so it has already been abused to do more
than strictly list revisions. And what do you call this?

$ git rev-list --branches --no-walk --author=gitster

:-)

Something like "git for-each-ref --contains" seems more sensible to me,
though it is not as generic as we could make it (I cannot use an
arbitrary list of commits to the "haystack", but only ones that have
refs pointing to them).

Sure, and if I wanted to do that, I could've just created a bunch of
temporary light-weight tags for those commits I was potentially
interested in and then used tag --contains. :-)

So I don't think rev-list is such a bad place after all.

j.

On Thu, Aug 05, 2010 at 03:06:54PM -0400, Jeff King wrote:

But my intent was to have a generic contains function. I was planning on
applying this to "git branch --contains", as well, but my initial
approach wasn't really any faster than the current code (probably
because the number of branches tends to be small compared to the number
of tags).

At work we have some 100 topics branches per kernel revision, and I
have a repository with 332 branches in it at the moment.  So there may
very well be repo's where git branch --contains might be faster with
your approach.

							- Ted