Hi,

On Tue, 28 Aug 2007, Jeff King wrote:

quoted text
> On Tue, Aug 28, 2007 at 12:02:22PM +0100, Johannes Schindelin wrote:
> 
> > Okay, I could have been clearer: make rev_name a linked list, where 
> > only the first contains the actual root of the name (i.e. 
> > "v2.6.22-rc1").  This can be made const char *, so that it is not 
> > allocated.
> 
> OK, I think we're on the same page.

Good!

quoted text
> > And to speed up comparison (and to know whether to point to a rev_name 
> > or a const char *) you can store the number of merge traversals:
> 
> Can't that number get stale if the pointed-to rev_name improves?

Well, we could actually do the correct thing, and not have a fifo, but a 
Fibonacci heap, so that we traverse the commits by cost.  Then there 
cannot be any clashes by definition.  First wins.

quoted text
> > struct rev_name {
> > 	union {
> > 	 	/* root is used when traversals == 0, otherwise previous */
> > 		struct rev_name *previous;
> > 		const char *root;
> > 	} p;
> > 	int generation;
> > 	int traversals;
> > }
> 
> You would also, of course, need the parent number.

But of course!

quoted text
> > Then comparison would be something like
> > 
> > 	int cmp_name(struct rev_name *n1, struct rev_name *n2)
> > 	{
> > 		int result = 0;
> > 		if (n1->traversals != n2->traversals)
> > 			return n1->traversals - n2->traversals;
> > 		do {
> > 			if (n1->generation != n2->generation)
> > 				result = n1->generation - n2->generation;
> > 			n1 = n1->p.previous;
> > 			n2 = n2->p.previous;
> > 		} while (n1->traversals);
> > 		return result;
> > 	}
> 
> I do wonder if this would actually have worse performance due to jumping
> all over the cache. I think there's no way to do without writing it.

Most comparisons (I guess) would be relatively cheap, since the traversals 
alone would suffice, and most of the others would be relatively short.

But I really wonder now if it is not just easier to increase 
MERGE_TRAVERSAL_WEIGHT to (1<<24) and be done with it once and (probably) 
for all.

Ciao,
Dscho

-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html