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

From: Jeff King <peff@peff.net>
Date: Aug 30, 2012, 03:36 UTC
Message-ID: <20120830033611.GA32268@sigill.intra.peff.net>
In-Reply-To: <7vligxuv6l.fsf@alter.siamese.dyndns.org>

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

Show 28 quoted lines

> 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