StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIncremental linearizing of git DAG
text
Body
copied!<p>I'm the author of <a href="http://gitx.frim.nl" rel="nofollow noreferrer" title="GitX">GitX</a>. One of the features GitX has is the visualization of branches, as can be seen <a href="http://ss.frim.nl/==967" rel="nofollow noreferrer">here</a>.</p> <p>This visualization is currently done by reading commits which are emitted from git in the correct order. For each commit the parents are known, so it's fairly easy to build up the lanes in the correct way.</p> <p>I'd like to speed up this process by using my own commit pool and linearizing the commits myself. This allows me to reuse existing loaded commits and allows git to emit commits faster because it doesn't have to emit them in the correct order.</p> <p>However, I'm not sure what algorithm to use to accomplish this. It is important that the building is incremental, as the loading of commits can take a long time (>5 seconds for 100,000 commits, which should all be displayed).</p> <p>Gitk has gone the same way, and there's a patch <a href="http://repo.or.cz/w/git.git?a=commitdiff;h=7fcc92bff4f75b69d61d8d32a5326395c20ff587" rel="nofollow noreferrer" title="Gitk patch">here</a> that shows how it is implemented, but my TCL skills are weak and the patch isn't very thoroughly commented and a bit hard to follow.</p> <p>I'd also like this algorithm to be efficient, as it'll have to handle hundreds of thousands of commits. It also has to be displayed in a table, so it's important that access to specific rows is fast.</p> <p>I'll describe the input I have so far, the output that I want and a few observations.</p> <p>Input:</p> <ul> <li>I have a current pool of commits in the form of a hash table that maps commit ids to commit objects. This pool does not have to be complete (have all commits necessary)</li> <li>I have a separate thread loading in new commits from git, with a callback that can be called every time a new commit is loaded. There is no guaranteed order in which the commits come in, but in most of the cases the next commit is a parent of the previous commit.</li> <li>A commit object has its own revision id and the revision ids of all its parents</li> <li>I have a list of branch heads that should be listed. That is, there isn't a single 'top' of the DAG that should be displayed. There also does not have to be a single graph root.</li> </ul> <p>Output:</p> <ul> <li>I'll need to linearize these commits in topological order. That is, a commit cannot be listed after its parents have been listed. </li> <li>I also need the 'branch lines' that can be seen in the screenshot above. These probably need to be precomputed as most of them depend on their children.</li> </ul> <p>A few remarks:</p> <ul> <li>It's necessary to relocate a list of commits. For example, we might have to commits (branch heads) that are unrelated, until a commit shows up which makes one head an ancestor of the other.</li> <li>Multiple branch tips must be shown</li> <li>It's important that this process is incremental, so that at least a partial view is available while the data is still loading. This means that new data has to be inserted halfway and that the branch lines have to be readjusted.</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload