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
ali1234 commentedon Jun 10, 2018
I can't understand how to compile that, but I got different results from git-count and git itself, and I don't even know which one of them is correct.
Byron commentedon Jun 10, 2018
You can compile it with
cargo run --example git-count --release -- <args>.It has the same result as
git rerify-pack, as far as the counts go.I think it would be good if the problem you are trying to solve would be stated as well. By that it might be easier to determine which algorithm is preferable.
Generally I would think its best to build the count on top of an algorithm you trust, and the one using
gitdirectly andGitPythonfor lookups is certainly the one I would trust, assuming that I like what git outputs in the first place.ali1234 commentedon Jun 10, 2018
I think in the past week I have spent more time explaining to people what I am doing than writing code. :)
The problem: given a list of remote repositories and an arbitrary tree which does not exist in any of them, calculate the list of parent commits that will produce the merge commit with the smallest possible diff when committing the tree with commit-tree.
The algorithm:
a. Create a defaultdict mapping binsha to lists.
b. For every blob and tree in the repo, append its list to the lists of its children.
c. For every commit, add its binsha to the list of its tree.
a. Create a defaultdict mapping binsha to bitmaps of length equal to the number of blobs in the input tree.
b. For every blob in the input tree, look it up in the inverted repo graph and follow the references to the leaf nodes, which are commits. This gives a list of every commit containing the blob.
c. For every commit in the list, set the bitmap equal to 1 for the current blob.
a. Create a bitmap of length equal to the number of blobs, set entirely to True, called "unfound"
b. For every commit, AND with unfound, count the number of 1 bits, and yield the one with the most.
c. Subtract the best commit from unfound, ie
unfound &= ~bestd. Repeat until you run out of commits or blobs, ie
best & unfound == 0.a. git checkout the first commit produced by the above algorithm.
b. Copy the input tree over the workdir.
c. Make a temporary commit and then run
git cat-file -p HEADto get the tree's binsha.d. Run
git commit-tree -p <parent-sha1> -p ... <tree-sha1>listing every commit output by the algorithm as a parent, including the first one used in step 4a.The list of remote repositories: #765 (comment)
The input tree: https://github.com/dguidipc/gemini-android-kernel-3.18/tree/56760a6e806bb4399d70626dd2e6cf22f7c9e9c1/kernel-3.18
The code: https://github.com/ali1234/gitxref/
The resulting merge: https://github.com/ali1234/linux-gemini/tree/20ba641d006ed0335de2c06ecd075f04d4f7065a
Now you are probably going to ask "why not just do X?" (everyone else did). The answer is speed. This algorithm takes around 8 hours and 10GB of RAM to run. There are 54,000 blobs in the input tree and 900,000 commits in the upstream repos. One algorithm that has been suggested is:
This is not practical, because walking the tree of an arbitrary kernel commit takes approximately 2 seconds. That means this algorithm will take approximately 3 weeks to complete.
Another method which has been suggested:
This is slightly better but still much worse than my approach.
git describewith an arbitrary blob sha1 takes about 5 seconds to run, so this will take approximately 3 days to complete. And when it does, it will only have told me ONE commit containing the blob, instead of ALL of them which is what I want.So now that you hopefully fully understand what I am doing and why, let's look at the actual problem:
In step 1b I wrote "for each blob and commit in the repo..." and in 1c I wrote "for each commit in the repo..." For speed, I do this with a single loop which just looks at every object in the repo.
And the problem I have is that the various tools do not agree on the number of objects in the repo.
ali1234 commentedon Jun 10, 2018
Yes, exactly. It's for when OEMs release tarballs with no history. I like that phrase, "historically-suitable", it captures what I am trying to do very well.
Yes. If the tree (or a superset of it) exists in the remotes, the algorithm should output one commit.
I already do this using pickle. Building the backrefs takes about 12 minutes with 8 "threads". Single thread version takes about 70 minutes. Loading it back in from disk takes about 90 seconds. It is 2GB on disk and 6GB in RAM. :)
If you can make a way to fetch a list of every commit containing a blob given its SHA1 which takes less than 1 second and I can call it from Python, then I am interested.
If you want to rewrite the whole thing in rust then go ahead - but I have no knowledge of rust programming at all.
Regarding
git rev-list --objects --all: I'm not sure what it really does. I suspect that it does not see orphaned objects, while directly iterating the database will. That would explain why git-count saw more objects. However it cannot explain why GitCmdObjectDB saw fewer.I don't think I want orphaned objects because presumably they do not have a useful history, and the whole point is to reconstruct history...
ali1234 commentedon Jun 10, 2018
PS thanks for taking an interest. Most people were just like "well, good luck with that" after I spent 15 minutes explaining the problem to them :)
I also met one other person trying to solve the same problem, with a different OEM tarball, but they took a totally different approach: https://framagit.org/GNUtoo/reconstruct-git-history
ali1234 commentedon Jun 10, 2018
Are you building a map of commit -> list of objects it contains?
That won't work... the result will be 900000 lists of ~54000 objects. You need a minimum of 3 bytes to uniquely identify all the binshas, so the result will be at an absolute minimum 150GB of data, not including datastructure overhead.
What I do is invert the graph... so where in git a tree has a list of subtrees and blobs, in backrefs every tree and blob has a list of trees it appears in. And top level trees also have the binsha of the commit(s) they belong to. This is still much larger than the forward version that git stores. Trying to flattening makes it grow exponentially.
I still had to use some tricks to make it fit in memory:
If tree A is in tree B, then A does not store the binsha of B in its list. Instead it stores a direct reference to the list representing B, which is another list of lists... and so on. The only data that gets stored is the binshas of commits. Everything else is lists of lists. This saved about 16GB of RAM, although curiously it had almost no effect on the on-disk size of the pickled data.
Another trick: Every binsha seen by the program is stored in a dict. Whenever it sees a new one it checks the dict and returns a reference to the existing one, instead of allocating new memory for the same string. This saved 2GB. The dict is thrown away once the backrefs table has been built.
This seems quite slow too... after 24 minutes it has indexed 10000 commits (using 18GB), so the total expected run time would be about 1.5 days (using 1.6TB of RAM). I think this is because you are walking the commits, and then walking the tree of each commit. This is very slow as you are looking at the same trees over and over. But it is possible (actually very likely) that I do not understand this rust code at all. :)
ali1234 commentedon Jun 10, 2018
If you are storing a bitvec/bitarray/bitmap of length
total number of blobsfor each commit, then you have gone directly to step 2. But the problem with that is my repo has over 1.8 million blobs and 0.9 million commits, so the full bitmap would be about 200GB - in memory or on disk. That's why I build the backrefs table (~6GB) and then build the bitmaps only for the 54,000 blobs I am interested in (another ~6GB).ali1234 commentedon Jun 11, 2018
Back on the topic of object counts, I figured out that cat-file can be used to do it MUCH faster than rev-list. Like 12 times faster. And it gives the same result if you don't have any dangling objects. Also it can be used to count objects directly from the shell with:
And you can check for dangling objects with:
I also got a further speedup by calling git myself with subprocess rather than using the GitPython interface.
ali1234 commentedon Jun 11, 2018
I've been implementing speed ups and multiprocessing code all day. My python now builds the LUT in 6 minutes (including 90 seconds to write the cache) vs 8 minutes for your rust.
However I just realised that actually, all we need to do is:
This takes two minutes to run and is naturally multithreaded by nature of being a shell pipeline. It is just a matter of parsing the firehose quickly, because it contains exactly the minimum amount of data you can pull from the repo and nothing else. No need to implement multithreading inside the program. If written directly to disk it is 13GB.
ali1234 commentedon Jun 12, 2018
54000 look ups completed in 42 minutes.
ali1234 commentedon Jun 12, 2018
It's actually very fast compared to my python. Of course more speed is always good. :)
ali1234 commentedon Jun 12, 2018
Not sure what you did but it is much slower now - like 100x slower. (Head currently at 55d9886).
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.