Junio C Hamano <gitster@xxxxxxxxx> writes:
> Instead of naming a rev after a tip that is topologically closest,
> use the tip that is the oldest one among those which contain the
> rev.
>
> The semantics "name-rev --weight" would give us is closer to what
> people expect from "describe --contains".
>
> Note that this is fairly expensive to compute; a later change in the
> series will cache the weight value using notes-cache.
>
> Signed-off-by: Junio C Hamano <gitster@xxxxxxxxx>
Here is a trivial optimization on top of the one from the other day.
-- >8 --
It often happens that immediately after traversing from v1.2.3 to
find out its weight, we are asked to see if another commit v1.2.0
is heavier than that.
Because the commits that are reachable from v1.2.3 are painted with
the SHOWN flag until the next "rev-list" traversal, we can notice
that the new commit v1.2.0 is reachable from v1.2.3 without doing
any traversal. We cannot learn exactly how much it weighs, but we
can tell it must weigh less than v1.2.3, and that is all that the
caller wants to know.
In the kernel history, "git name-rev --tags 0136db586c" which
started this topic needs 26k calls to tip_weight_cmp(). 13k of them
are comparisons between tips based on the same ref and answered
without computing any weight. Among the remaining 13k, 1.8k
comparisons are answered with this trivial "fast-forward"
optimization.
Signed-off-by: Junio C Hamano <gitster@xxxxxxxxx>
---
builtin/name-rev.c | 37 +++++++++++++++++++++++++++++++++----
1 file changed, 33 insertions(+), 4 deletions(-)
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 7cdb758..809553b 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -32,6 +32,9 @@ struct rev_name {
*/
static int use_weight;
+/* To optimize revision traversal */
+static struct commit *painted_commit;
+
/*
* NEEDSWORK: the result of this computation must be cached to
* a dedicated notes tree, keyed by the commit object name.
@@ -47,15 +50,15 @@ static int compute_ref_weight(struct commit *commit)
prepare_revision_walk(&revs);
while (get_revision(&revs))
weight++;
+ painted_commit = commit;
return weight;
}
-static int ref_weight(const char *refname, size_t reflen)
+static struct commit *ref_commit(const char *refname, size_t reflen)
{
struct strbuf buf = STRBUF_INIT;
unsigned char sha1[20];
struct commit *commit;
- struct rev_name *name;
strbuf_add(&buf, refname, reflen);
if (get_sha1(buf.buf, sha1))
@@ -65,9 +68,16 @@ static int ref_weight(const char *refname, size_t reflen)
commit = lookup_commit_reference_gently(sha1, 0);
if (!commit)
die("Internal error: cannot look up commit '%s'", buf.buf);
+ return commit;
+}
+
+static int ref_weight(struct commit *commit, const char *refname, size_t reflen)
+{
+ struct rev_name *name;
+
name = commit->util;
if (!name)
- die("Internal error: a tip without name '%s'", buf.buf);
+ die("Internal error: a tip without name '%.*s'", (int) reflen, refname);
if (!name->weight)
name->weight = compute_ref_weight(commit);
return name->weight;
@@ -76,6 +86,7 @@ static int ref_weight(const char *refname, size_t reflen)
static int tip_weight_cmp(const char *a, const char *b)
{
size_t reflen_a, reflen_b;
+ struct commit *commit_a, *commit_b;
static const char traversal[] = "^~";
/*
@@ -89,7 +100,25 @@ static int tip_weight_cmp(const char *a, const char *b)
if (reflen_a == reflen_b && !memcmp(a, b, reflen_a))
return 0;
- return ref_weight(a, reflen_a) - ref_weight(b, reflen_b);
+ commit_a = ref_commit(a, reflen_a);
+ commit_b = ref_commit(b, reflen_b);
+
+ /* Have we painted either one of these recently? */
+ if (commit_a == painted_commit &&
+ (commit_b->object.flags & SHOWN)) {
+ /*
+ * We know b can be reached from a, so b must be older
+ * (lighter, as it has fewer commits behind it) than
+ * a.
+ */
+ return 1;
+ } else if (commit_b == painted_commit &&
+ (commit_a->object.flags & SHOWN)) {
+ /* Likewise */
+ return -1;
+ }
+
+ return ref_weight(commit_a, a, reflen_a) - ref_weight(commit_b, b, reflen_b);
}
static long cutoff = LONG_MAX;
--
1.7.12.321.g60f00e5
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html