Re: [PATCH 0/3] Using a bit more decoration

From: Jeff King <peff@peff.net>
Date: Apr 9, 2013, 04:39 UTC
Message-ID: <20130409043938.GA31447@sigill.intra.peff.net>
In-Reply-To: <7vsj30tk0p.fsf@alter.siamese.dyndns.org>

On Mon, Apr 08, 2013 at 09:17:42PM -0700, Junio C Hamano wrote:

Show 14 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> > [1] The thing that made me think about this was making a version of
> >     paint_down_to_common that could keep a separate color for each
> >     source, rather than only PARENT1 and PARENT2. That would let us do
> >     the "--contains" traversal in a breadth-first way, but calculate the
> >     answer simultaneously for all sources (i.e., avoid the depth-first
> >     "go to roots" problem that the current "tag --contains" has if you
> >     do not use timestamp cutoffs).
> 
> Yes, show-branch operates independently of rev-list machinery, hence
> can use full set of bits, but the full set of bits in a word is not
> always sufficient and it can be helped greatly with such an unbound
> set of bits machinery.

The tricky part is how to store the index for each commit (or object). I don't see a way around adding a new field to "struct commit" to do so. It _might_ be worth it, because that index would be reusable for many different operations.

I had hoped to do something clever and implicit with the commit pointer, since we allocate from a pool. For example, if you have pointer X and know that the pool starts at Y, you can get an index with simple subtraction. But of course we don't know what the pool is for any given allocator without searching the pools, which grow linearly with the number of objects. So it ends up with the same algorithmic complexity as just searching for the commit in a data structure (albeit with a smaller constant, since we allocate big chunks of objects).

-Peff