W dniu 2016-06-29 o 20:59, Junio C Hamano pisze: > On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz > <marc.strap...@syntevo.com> wrote: > >> 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
