Repository navigation
Git, GitDB, and GitCmdObjectDB give different results when counting objects. #765
Description
- Use git to count the objects in a repo:
$ git rev-list --objects --all | wc -l
6990030
$ git rev-list --objects --all | sort | uniq | wc -l
6990030
- Parse the output from
git rev-list --objects --all, fetch each object with name_to_object, and count each type:
Commits: 909667, Tags: 2469, Trees: 4178263, Blobs: 1899631
- Query what is ostensibly the same information using git-python:
import argparse
import pathlib
import git
def log(testname, a, b):
print(testname, ':', a, b)
def main():
parser = argparse.ArgumentParser(description='Git x ref.')
parser.add_argument('repository', metavar='repository', type=pathlib.Path,
help='Path to Git repository.')
args = parser.parse_args()
repos = [
git.Repo(str(args.repository), odbt=git.GitCmdObjectDB),
git.Repo(str(args.repository), odbt=git.GitDB)
]
log('size()', *[r.odb.size() for r in repos])
log('len(sha_iter())', *[sum(1 for x in r.odb.sha_iter()) for r in repos])
log('len(iter_trees())', *[sum(1 for x in r.iter_trees()) for r in repos])
if __name__ == '__main__':
main()
Result:
size() : 3839 8268978
len(sha_iter()) : 3839 8268978
len(iter_trees()) : 568851 568851
So:
Git thinks there are 6,990,030 objects in the database.
GitDB thinks there are 8,268,978.
GitCmdObjectDB thinks there are 3,839.
Git thinks there are 4,178,263 trees in the database.
Both GitDB and GitCmdObjectDB think there are 568,851.
Activity
Byron commentedon Jun 6, 2018
@ali1234 Could you tell me the repository you are looking at? I would like to run https://github.com/Byron/git-count on it, assuming it's as fast as
Cwould be, based onlibgit2which should be the best implementation out there to access git object databases.I am aware that writing something in Rust is not addressing the problem directly, but might indeed be a suitable workaround. One could possibly just use
libgit2from python directly, too. For now I just want to see what the kinds are usinglibgit2.Thank you
ali1234 commentedon Jun 6, 2018
This is my .git/config:
ali1234 commentedon Jun 6, 2018
Also this is my python object counter. It takes
3m14.257s2m35.187s to run and produced the above output. I would be interested to compare the speeds but I can't get your rust code to compile because it needs experimental features.ali1234 commentedon Jun 6, 2018
I get different numbers from git-count and my script.
git-count:
and for my script:
ali1234 commentedon Jun 6, 2018
6m32.922s for the release build.
ali1234 commentedon Jun 7, 2018
Same git version here, on Ubuntu 18.04.
Byron commentedon Jun 10, 2018
I realized that the only way to fix GitPython is not to use it, or at least stick with the proven cgit implementation.
In an attempt to eventually remedy the situation and offer alterantives, I decided to implement the whole thing in pure Rust.
Here is the first result:
Please note that the comparison is probably unfair, as the program just does a lookup by offset, not by SHA1, which is pretty much as efficient as it gets.
I am also declaring this issue as 'wont-fix' as the only 'working' git database is the
GitCmdDb, which seems to be doing OK.Please correct me if I am wrong, but if not it would be nice if the issue could be closed.
Thank you
30 remaining items
ali1234 commentedon Jun 13, 2018
That's a very impressive time.
Today I found an optimization. I don't know if you are already doing this. If a node has only one parent edge, then you can replace it in all children with its parent at no cost.
This Python code is called once for each node in the whole graph:
It eliminates about 350 million edges, reducing memory use and halving the lookup time. Total run time for the python version is now at about 3 hours.
ali1234 commentedon Jun 13, 2018
The output format is not particularly important. All it needs to do is print the set of commits that should be used in the merge commit. I made the commit manually.
For the datastructure stuff, remember the repository is a directed acyclic graph, not a tree. Sources are commits, sinks are blobs, everything else is a tree. Backrefs is the reversed graph, so blobs become sources and commits become sinks.
I use dict/hash to find nodes by SHA1 but they are not internal to the graph. Each vertex is simply a list of lists, except for commits which are just a binsha. The dict containing tree vertices is discarded at the end, as only the blob vertices need to be found by binsha.
While writing this post it occurred to me that, in the language of DAGs, the algorithm would be described like this:
There is probably a much better algorithm for computing the transitive closure than walking from every source vertex.
ali1234 commentedon Jun 15, 2018
6m25s with cached graph, numpy, and 1 thread:
Building the cache takes 10 minutes, also single threaded. The external git pipe line is doing most of the work.
I am not entirely convinced it is still producing valid results but assuming it is, using this algorithm in rust should allow you to get below 1 minute pretty easily I think.
Byron commentedon Jun 15, 2018
ali1234 commentedon Jun 15, 2018
Memory use is way up because intermediate bitmaps are cached in the new algorithm. backrefs.py is dead, replaced by graph.py. It works like this:
Another side effect of this algorithm is you can partition the search. You could in theory do it with a step size of 1 and that would be the same as the old way. Or you can split it in half. This reduces the memory required. The code handles this, and theoretically the partitions can be done concurrently if you adapt the way temporary bitmaps are generated.
In order to do it all in one go it is necessary to reduce the graph. This is the part I am not sure is correct. Without reduction I have 350 million edges, and generating the bitmaps all at once would need 32GB of RAM. With reduction it fits in about 8GB.
ali1234 commentedon Jun 16, 2018
I've reimplemented the full output and it looks like the results are reasonable. One problem is that there are usually several commits that match the same number of blobs and the ordering is not stable. Numpy even sped up the last part of the algorithm a lot - it is much faster at bitwise operations on long arrays than the bitarray library.