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

[Jeff King <peff@peff.net>]

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

> 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