Git仓库文件版本号遍历算法的优化

Zoker 发布于 2015/10/09 14:26
阅读 37
收藏 0

背景:

目前Git@OSC使用的基于libgit2的Rugged(http://github.com/libgit2/rugged) Git开发库,替换了原来Gitlab的底层Grit Git开发库,目前遇到的问题时在查找文件的提交历史上效率相当低下, 如下图:

输入图片说明

当前目录的最新提交的版本号是094a3, 而其下的每个文件的最后更新版本号是不一样的。

当前我们使用的查找算法:遍历当前目录下的所有文件和文件夹, 找到它们各自的最近修改commit(文件夹的最新修改历史取决于其下的文件和文件夹的最近修改commit)

因此,我们希望能够设计一套效率更高的查找算法。

Git的组织结构如下图所示:输入图片说明详情请参考 http://git.oschina.net/progit/

rugged文档翻译 http://my.oschina.net/zouqilin/blog/330261

开发库: rugged/libgit2, 也可以使用c开发, 然后使用ruby封装

目标: 希望能比当前算法提高20%的查找性能, 算法稳定, 有相应的异常处理.

加载中
0
我的上铺叫路遥
我的上铺叫路遥
三个问题: 一、你们用rugged替换Grit,遍历效率低下是原来就有的,还是替换了之后才产生的?期间libgit2是否有所改动? 二、你们使用lib/rugged/repository.rb里的walk命令来测试遍历的吗? 三、截图好像是你们对rugged的一个fork,这份代码目前是否公开?
zouqilin
zouqilin
是rugged的fork 我们封装了一层 你可以使用github的rugged
zouqilin
zouqilin
使用的是walker
zouqilin
zouqilin
libgit2 没有多大改动(你可以忽略)
zouqilin
zouqilin
grit的原理是git命令行方式解析仓库的 肯定是慢的 git中查找文件历史记录还是挺快的 但是git log -- your-file 只是一个文件 我们的目标是当前目录下的所有文件的修改历史
0
Zoker
Zoker

引用来自“我的上铺叫路遥”的评论

三个问题: 一、你们用rugged替换Grit,遍历效率低下是原来就有的,还是替换了之后才产生的?期间libgit2是否有所改动? 二、你们使用lib/rugged/repository.rb里的walk命令来测试遍历的吗? 三、截图好像是你们对rugged的一个fork,这份代码目前是否公开?
已经留言沟通。
0
l
lxw1
文中提到“遍历当前目录下的所有文件和文件夹, 找到它们各自的最近修改commit” 请遍历当前目录指的是什么意思? 我猜测有三种可能: 1.指的是当前Commit对象里面包含的那个tree结构吗? 根据Git文档中的描述,文件的提交时间保存在Commit对象中,文件对象blob和目录对象tree 中并没有保存文件提交时间啊。所以遍历当前tree得不到文件或目录的提交时间啊。 2. 第二种可能,指的是沿着Commit对象的parent 向前查看每个Commit,在每个Commit对象对应的tree中按sha-1值查找是否有与该目录或文件的sha-1值相等的对象,如果找到了,继续向前查找Commit,否则说明本次Commit此文件还没有提交,下一个Commit就是这个文件或目录的提交时间。按这个查找方法不需要遍历子目录啊。如果子目录变了,那么父目录的sha-1一定会改变,所以想要确定一个文件夹的修改时间,只需要用该目录的sha-1查找就可以了,不需要先确定它的各个子文件的修改时间。 500字到了,待续。
0
l
lxw1
3. 第三种可能:你们内部已经做了一些优化,每个文件和提交该文件的Commit的映射关系已经被缓存下来了,直接根据文件的SHA-1 就可以确定此文件上次是被哪个Commit对象提交上来的,于是就确定了文件的修改时间,但文件夹与Commit对象的映射没有被缓存,所以要计算目录的修改时间,需要先确定该目录下各个文件的修改时间,然后得到目录的修改时间,是这样吗,那么为什么没有把文件夹和提交这个文件夹改动的Commit的映射关系保存下来呢?
0
l
lxw1
我目前想到了一个算法,用java实现了大概的逻辑,并写了一篇文档,您可以看看,要是能满足您的需要,我可以用ruby完整地实现出来。我把相关文档用私信发给您了。
返回顶部
顶部