Re: [PATCH 3/3] name-rev: --weight option (WIP)

Junio C Hamano [off-list ref] writes:

Note that this is fairly expensive (see NEEDSWORK comment in the
code).

And this is with the "notes-cache".

    (priming the cache from scratch)
    $ rm .git/refs/notes/name-rev-weight 
    $ /usr/bin/time ../git.git/git-name-rev --weight --tags 0136db586c
    0136db586c tags/v3.5-rc1~83^2~81^2~76
    6.06user 0.46system 0:06.54elapsed 99%CPU (0avgtext+0avgdata 1861456maxresident)k
    8inputs+16outputs (0major+128576minor)pagefaults 0swaps

    (with valid cache)
    $ /usr/bin/time ../git.git/git-name-rev --weight --tags 0136db586c
    0136db586c tags/v3.5-rc1~83^2~81^2~76
    0.50user 0.22system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 244224maxresident)k
    0inputs+0outputs (0major+16062minor)pagefaults 0swaps

    (the old "shortest path" version)
    $ /usr/bin/time git name-rev --tags 0136db586c
    0136db586c tags/v3.6-rc1~59^2~56^2~76
    0.31user 0.01system 0:00.32elapsed 100%CPU (0avgtext+0avgdata 243488maxresident)k
    0inputs+0outputs (0major+16000minor)pagefaults 0swaps


 builtin/name-rev.c | 38 +++++++++++++++++++++++++++++++++-----
 1 file changed, 33 insertions(+), 5 deletions(-)

diff --git c/builtin/name-rev.c w/builtin/name-rev.c
index 69da41d..fdd087c 100644
--- c/builtin/name-rev.c
+++ w/builtin/name-rev.c

@@ -6,6 +6,7 @@
 #include "parse-options.h"
 #include "diff.h"
 #include "revision.h"
+#include "notes-cache.h"
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 

@@ -32,10 +33,6 @@ struct rev_name {
  */
 static int use_weight;
 
-/*
- * NEEDSWORK: the result of this computation must be cached to
- * a dedicated notes tree, keyed by the commit object name.
- */
 static int compute_tip_weight(struct commit *commit)
 {
 	struct rev_info revs;

@@ -50,6 +47,31 @@ static int compute_tip_weight(struct commit *commit)
 	return weight;
 }
 
+static struct notes_cache weight_cache;
+static int weight_cache_updated;
+
+static int get_tip_weight(struct commit *commit)
+{
+	struct strbuf buf = STRBUF_INIT;
+	size_t sz;
+	int weight;
+	char *note = notes_cache_get(&weight_cache, commit->object.sha1, &sz);
+
+	if (note && !strtol_i(note, 10, &weight)) {
+		free(note);
+		return weight;
+	}
+	free(note);
+
+	weight = compute_tip_weight(commit);
+	strbuf_addf(&buf, "%d", weight);
+	notes_cache_put(&weight_cache, commit->object.sha1,
+			buf.buf, buf.len);
+	strbuf_release(&buf);
+	weight_cache_updated = 1;
+	return weight;
+}
+
 static int tip_weight(const char *tip, size_t reflen)
 {
 	struct strbuf buf = STRBUF_INIT;

@@ -69,7 +91,7 @@ static int tip_weight(const char *tip, size_t reflen)
 	if (!name)
 		die("Internal error: a tip without name '%s'", tip);
 	if (!name->weight)
-		name->weight = compute_tip_weight(commit);
+		name->weight = get_tip_weight(commit);
 	return name->weight;
 }
 

@@ -346,6 +368,9 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 	if (all || transform_stdin)
 		cutoff = 0;
 
+	if (use_weight)
+		notes_cache_init(&weight_cache, "name-rev-weight", "2012-08-29");
+
 	for (; argc; argc--, argv++) {
 		unsigned char sha1[20];
 		struct object *o;

@@ -401,5 +426,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 				  always, allow_undefined, data.name_only);
 	}
 
+	if (use_weight && weight_cache_updated)
+		notes_cache_write(&weight_cache);
+
 	return 0;
 }

On Wed, Aug 29, 2012 at 04:37:06PM -0700, Junio C Hamano wrote:

Junio C Hamano [off-list ref] writes:

quoted

Note that this is fairly expensive (see NEEDSWORK comment in the
code).

And this is with the "notes-cache".
[...]
+static int get_tip_weight(struct commit *commit)
+{
+	struct strbuf buf = STRBUF_INIT;
+	size_t sz;
+	int weight;
+	char *note = notes_cache_get(&weight_cache, commit->object.sha1, &sz);
+
+	if (note && !strtol_i(note, 10, &weight)) {
+		free(note);
+		return weight;
+	}
+	free(note);
+
+	weight = compute_tip_weight(commit);
+	strbuf_addf(&buf, "%d", weight);
+	notes_cache_put(&weight_cache, commit->object.sha1,
+			buf.buf, buf.len);
+	strbuf_release(&buf);
+	weight_cache_updated = 1;
+	return weight;
+}

It looks like you didn't update compute_tip_weight at all, so it will
still do the full traversal down to the roots. I wonder if you can
define the weight as a recursive function of the parents. Using the sum
of the weights of the parents is not right, because you would
double-count in this situation:

  A--B--C--D---M
      \       /
       E--F--G

That would double-count "A" and "B" in this example. But maybe there is
a clever way to define it that avoids that.

The advantage would be that you could cheaply find the weights of new
commits by only traversing back to the last cached one. I did something
similar with the generation number cache (but the recursive definition
is easier there).

+	if (use_weight)
+		notes_cache_init(&weight_cache, "name-rev-weight", "2012-08-29");

Is that a sufficient validity field? What about grafts or replace
objects? For the generation cache, I used a hash of the graft and
replace fields.

-Peff