Re: topological index field for commit objects

From: Jakub Narębski <jnareb@gmail.com>
Date: Jun 29, 2016, 21:00 UTC
Message-ID: <577436DD.8050708@gmail.com>
In-Reply-To: <CAPc5daVC-+0Vr30L_pbcL0GN2OmnGm-+V4tE2WTos_vPRb_S1g@mail.gmail.com>

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

Show 16 quoted lines

> On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz
> <marc.strapetz@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