git DAG的增量线性化

Question

我是GitX的作者.GitX的一个功能是分支的可视化,这可以在这里看到.

此可视化目前通过读取以正确顺序从git发出的提交来完成.对于每次提交,父母都是已知的,因此以正确的方式构建通道相当容易.

我想通过使用自己的提交池并自己线性化提交来加快这个过程.这允许我重用现有的已加载提交并允许git更快地发出提交,因为它不必以正确的顺序发出它们.

但是,我不确定使用什么算法来实现这一目标.重要的是,构建是增量的,因为提交的加载可能需要很长时间(100,000次提交> 5秒,应该全部显示).

Gitk已经以同样的方式,并有一个补丁在这里,显示它是如何实现的,但我的TCL技能薄弱,补丁是不是很详尽的注释和有点难以遵循.

我也希望这个算法有效,因为它必须处理数十万次提交.它也必须显示在表中,因此访问特定行很快很重要.

我将描述我到目前为止的输入,我想要的输出和一些观察.

输入:

• 我有一个哈希表形式的当前提交池,它将commit id映射到提交对象.此池不必完整(必须提交所有提交)
• 我在git的新提交中有一个单独的线程加载,每次加载新提交时都可以调用一个回调.提交没有保证顺序,但在大多数情况下,下一次提交是前一次提交的父级.
• 提交对象具有自己的修订版ID以及其所有父项的修订版ID
• 我有一个应该列出的分支头列表.也就是说,不应该显示DAG的单个"顶部".也不必是单个图根.

输出:

• 我需要按拓扑顺序线性化这些提交.也就是说,在列出其父项后,无法列出提交.
• 我还需要在上面的屏幕截图中看到的"分支线".这些可能需要预先计算,因为大多数都依赖于他们的孩子.

几点评论:

• 有必要重新定位提交列表.例如,我们可能必须提交不相关的(分支头),直到提交显示使一个头成为另一个头的祖先.
• 必须显示多个分支提示
• 这个过程是增量的很重要,因此在数据仍在加载时至少可以获得部分视图.这意味着必须在中途插入新数据并且必须重新调整分支线.

Answer 1

标准拓扑排序是O(n)(OK,O(V + E)),即您应该能够在几分之一秒内对内存中的一百万次提交进行排序.不需要像Tcl那样的增量黑客.

顺便说一句,我每天使用GitX(看起来比OS X上的Gitk要好得多)并且没有任何问题(也许是因为我没有在我的存储库中进行那些疯狂的合并):)