Re: Add "--show-all" revision walker flag for debugging

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Feb 11, 2008, 15:59 UTC
Message-ID: <alpine.LFD.1.00.0802110748370.2920@woody.linux-foundation.org>
In-Reply-To: <200802110224.48790.jnareb@gmail.com>

On Mon, 11 Feb 2008, Jakub Narebski wrote:

> 
> Errr... index is per workarea (per checkout), and this information
> is per repository, so IMHO storing this info in an index (dircache)
> is a layering violation. Unless you were talking about pack-file-index.

I did mean the pack-file index, not the "cache" index.

> Weren't the cases of multiple roots that were difficult? Storing roots
> would help with 'hard' (if seldom happening) cases then.

It's not that they aren't difficult, it's that they are so rare (ie having ranges that really *are* separate never happens in practice). So it's not worth worrying about from a performance angle.

The thing that worried me about multiple roots was that they make the generation numbers essentially "meaningless" when compared across totally unrelated commits, and might give incorrect results for generation number comparisons as a result.

However, I decided that if two commits really *are* totally unrelated and don't share a commit, then:

 - yes, the generation number comparison is "meaningless"

 - BUT: we don't actually care if it's correct or not, because it will 
   never matter: whatever we choose to do, it's correct. Because there are 
   just two choices:

    (a) stop early because everything we have left is uninteresting

        This is correct, because if they have two separate roots, they'll 
        never meet anyway, so from a correctness standpoint they will 
        never change a interesting commit into an uninteresting one.

    (b) continue to the root because we think we might turn something 
        interesting into an uninteresting commit. This may be wasteful 
        (because the generation numbers happened to fool us into thinking 
        we migth care and one is older than the other), but it's still 
        technically _correct_.

        And we really don't need to care about the performance issues 
        since continuing down to the root is what we'd have had to do even 
        without the generation numbers anyway, but more importantly 
        because we simply don't care - if people start doing comparisons 
        across truly independent commits, they are doing something wrong.

So that's why a generation number is sufficient.

And yes, just generating the generation number when repacking is fine. It would mean that unpacked objects don't have generation numbers, but of you have tons and tons of unpacked objects, you have more serious problems anyway!

			Linus