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

[Jeff King <peff@peff.net>]

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

> Junio C Hamano <gitster@pobox.com> writes:
> 
> > 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