Re: topological index field for commit objects

["Jakub Narębski" <jnareb@gmail.com>]

W dniu 2016-06-29 o 22:56, Jeff King pisze:
> On Wed, Jun 29, 2016 at 01:39:17PM -0700, Junio C Hamano wrote:
> 
>>> Would it make sense to refuse creating commits that have a commit date
>>> prior to its parents commit date (except when the user gives a
>>> `--dammit-I-know-I-break-a-wildy-used-heuristic`)?
>>
>> I think that has also been discussed in the past.  I do not think it
>> would help very much in practice, as projects already have up to 10
>> years (and the ones migrated from CVS, even more) worth of commits
>> they cannot rewrite that may record incorrect committer dates.
> 
> Yep, it has been discussed and I agree it runs into a lot of corner
> cases.
> 
>> If the use of generation number can somehow be limited narrowly, we
>> may be able to incrementally introduce it only for new commits, but
>> I haven't thought things through, so let me do so aloud here ;-)
> 
> I think the problem is that you really _do_ want generation numbers for
> old commits. One of the most obvious cases is something like "tag
> --contains HEAD", because it has to examine older tags.
> 
> So your history looks something like:
> 
>   A -- B -- ... Z
>         \        \
> 	 v1.0     HEAD
> 
> Without generation numbers (or some proxy), you have to walk the history
> between B..Z to find the answer. With generation numbers, it is
> immediately obvious.
> 
> So this is the ideal case for generation numbers (the worst cases are
> when the things you are looking for are in branchy, close history where
> the generation numbers don't tell you much; but in such cases the
> walking is usually not too bad).

There are other approaches (special indices) that help reachability
queries beside "generation number".

> 
> So I think you really do want to be able to generate and store
> generation numbers after the fact. That has an added bonus that you do
> not have to worry about baking incorrect values into your objects; you
> do the topological walk once, and you _know_ it is correct (at least as
> correct as the parent links, but that is our source of truth).

By the way, what should happen if you add a replacement (in the git-replace
meaning) that creates a shortcut, therefore invalidating generation numbers,
at least in strict sense - committerdate as generation number would be still
good, I think?
 
> I have patches that generate and store the numbers at pack time, similar
> to the way we do the reachability bitmaps. They're not production ready,
> but they could probably be made so without too much effort. You wouldn't
> have ready-made generation numbers for commits since the last full
> repack, but you can compute them incrementally based on what you do have
> at a cost linear to the unpacked commits (this is the same for bitmaps).

Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still
limited to object counting?

-- 
Jakub Narębski