Re: topological index field for commit objects

W dniu 2016-06-29 o 20:59, Junio C Hamano pisze:

On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz
[off-list ref] wrote:

quoted

This is no RFE but rather recurring thoughts whenever I'm working with
commit graphs: a topological index attribute for commit objects would be
incredible useful. By "topological index" I mean a simple integer for which
following condition holds true:

 if commit C is part of the history of commit D,
   then C's topological index is smaller than D's index

This would allow topological sorting of commits (e.g. in queues) on the fly
and quickly give a "no" answer on the question whether D is part of
C's history. 

Look for "generation numbers" in the list archive, perhaps?

If I remember correctly the discussion, the problem by adding generation number
to the commit object format was twofold (at least).

First there was a problem of backward compatibility, namely what to do with
existing repositories, where commit objects do not have generation number.
Objects in Git are immutable (and I think replacements mechanism wasn't
invented yet - anyway too many replacements would slow down operations
I guess).

Second objection was of philosophical nature: generation numbers duplicate
(cache) information that is stored in the graph of revisions. Also, what
if they get out of sync?

That is, if I remember the summary of that discussion correctly.


Also, generation numbers (graph level) only help with topological sorting;
for finding of two commits are connected (two nodes are connected) people
play with different ideas, for example FELINE index:
  http://openproceedings.org/EDBT/2014/paper_166.pdf

Nowadays there is also [compressed] bitmap index (if enabled), though I am
not sure if it is yet used to speed-up reachability queries
  http://githubengineering.com/counting-objects/
  https://www.eclipsecon.org/2013/sites/eclipsecon.org.2013/files/Scaling%20Up%20JGit%20-%20EclipseCon%202013.pdf

-- 
Jakub Narębski