Repository navigation
Git, GitDB, and GitCmdObjectDB give different results when counting objects. #765
Description
Activity
@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 uselibgit2from python directly, too. For now I just want to see what the kinds are usinglibgit2.
Thank youThis is my .git/config:
[core] repositoryformatversion = 0 filemode = true bare = false logallrefupdates = true [remote "linux-stable"] url = git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git fetch = +refs/heads/*:refs/remotes/linux-stable/* [remote "linux-stable-rc"] url = git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable-rc.git fetch = +refs/heads/*:refs/remotes/linux-stable-rc/* [remote "linux-next"] url = git://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git fetch = +refs/heads/*:refs/remotes/linux-next/* [remote "linux-next-history"] url = git://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next-history.git fetch = +refs/heads/*:refs/remotes/linux-next-history/* [remote "android-common"] url = https://android.googlesource.com/kernel/common fetch = +refs/heads/*:refs/remotes/android-common/* [remote "android-mediatek"] url = https://android.googlesource.com/kernel/mediatek fetch = +refs/heads/*:refs/remotes/android-mediatek/* [merge] renamelimit = 12000Also 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.import argparse import pathlib from collections import defaultdict import git from gitdb.util import hex_to_bin 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() repo = git.Repo(str(args.repository), odbt=git.GitCmdObjectDB) typecount = defaultdict(int) for line in repo.git.rev_list('--objects', '--all').split('\n'): binsha = hex_to_bin(line.split()[0]) oinfo = repo.odb.info(binsha) typecount[oinfo.type] += 1 print(', '.join('{:s}s: {:d}'.format(k.decode('utf8').capitalize(), v) for k, v in typecount.items())) if __name__ == '__main__': main()I get different numbers from git-count and my script.
git-count:
commits: 1069996, trees: 4943730, blobs: 2252783, tags: 2469, any: 0, unknown: 0 real 14m9.732s user 14m7.562s sys 0m1.664sand for my script:
Commits: 909667, Tags: 2469, Trees: 4178263, Blobs: 1899631 real 2m36.989s user 2m37.376s sys 0m29.017s6m32.922s for the release build.
Same git version here, on Ubuntu 18.04.
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:
➜ git-odb git:(master) time ./target/release/examples/git-count /Users/byron/dev/GitPython/linux-stable.git/objects/pack/pack-930627d122f4fd6a6e203b61f58ea4ad441da724.idx /Users/byron/dev/GitPython/linux-stable.git/objects/pack/pack-930627d122f4fd6a6e203b61f58ea4ad441da724.pack commits: 804501, trees: 170520, blobs: 94462, tags: 2389, deltas: 5667694 ./target/release/examples/git-count 1.32s user 0.35s system 99% cpu 1.671 totalPlease 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 you30 remaining items
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:
def list_opt(l): count = 0 for n in range(len(l)): while type(l[n]) is list and len(l[n]) == 1: l[n] = l[n][0] count += 1 return countIt 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.
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:
- Reverse the repository graph.
- Remove all source vertices except the blobs found in the tarball.
- Compute the transitive closure of the resulting graph.
There is probably a much better algorithm for computing the transitive closure than walking from every source vertex.
6m25s with cached graph, numpy, and 1 thread:
Topological sort: 100%|█████████████████████████████████████████████████████████████████████████████████████████| 53741/53741 [00:46<00:00, 1152.03 sources/s] Making bitmaps: 100%|██████████████████████████████████████████████████████████████████████████████████████| 1775132/1775132 [04:29<00:00, 6586.07 vertices/s] Command being timed: "python3 -m gitxref /home/al/gemini/kernel2/upstream/ /home/al/gemini/kernel2/kernel-3.18/" User time (seconds): 380.67 System time (seconds): 4.70 Percent of CPU this job got: 99% Elapsed (wall clock) time (h:mm:ss or m:ss): 6:25.43 Average shared text size (kbytes): 0 Average unshared data size (kbytes): 0 Average stack size (kbytes): 0 Average total size (kbytes): 0 Maximum resident set size (kbytes): 14130952 Average resident set size (kbytes): 0 Major (requiring I/O) page faults: 0 Minor (reclaiming a frame) page faults: 3610107 Voluntary context switches: 199 Involuntary context switches: 2021 Swaps: 0 File system inputs: 0 File system outputs: 8 Socket messages sent: 0 Socket messages received: 0 Signals delivered: 0 Page size (bytes): 4096 Exit status: 0Building 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.
- Assuming correctness, your excursion to graph theory soooo paid off! I am absolutely blown away 🤩! Also I won’t be able to sleep anymore until I have beaten that time 😉. Great show of how optimizations usually go. By far the most powerful tool is the choice of algorithm, everything else comes afterwards. I see it is now using 14.3GB of memory, is that up or down for you? Admittedly for that speed up, I am happily paying a few gig more 😅.…On Fri 15. Jun 2018 at 14:11, Alistair Buxton ***@***.***> wrote: 6m25s with cached graph, numpy, and 1 thread: Topological sort: 100%|█████████████████████████████████████████████████████████████████████████████████████████| 53741/53741 [00:46<00:00, 1152.03 sources/s] Making bitmaps: 100%|██████████████████████████████████████████████████████████████████████████████████████| 1775132/1775132 [04:29<00:00, 6586.07 vertices/s] Command being timed: "python3 -m gitxref /home/al/gemini/kernel2/upstream/ /home/al/gemini/kernel2/kernel-3.18/" User time (seconds): 380.67 System time (seconds): 4.70 Percent of CPU this job got: 99% Elapsed (wall clock) time (h:mm:ss or m:ss): 6:25.43 Average shared text size (kbytes): 0 Average unshared data size (kbytes): 0 Average stack size (kbytes): 0 Average total size (kbytes): 0 Maximum resident set size (kbytes): 14130952 Average resident set size (kbytes): 0 Major (requiring I/O) page faults: 0 Minor (reclaiming a frame) page faults: 3610107 Voluntary context switches: 199 Involuntary context switches: 2021 Swaps: 0 File system inputs: 0 File system outputs: 8 Socket messages sent: 0 Socket messages received: 0 Signals delivered: 0 Page size (bytes): 4096 Exit status: 0 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. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#765 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAD4hnDW45F1ozCA0ZJ0WsZzL4Ik0-wtks5t86RjgaJpZM4UbZjX> .
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:
- Each blob includes itself, so give it a bitmap with only itself marked.
- Do a topological sort, starting from each of the blobs you want to look up.
- For each vertex in the sorted list, OR its bitmap into each child's bitmap. If the child doesn't have a bitmap, give it a copy of the current vertex bitmap. If the child is a commit, OR the vertex bitmap into the result set/dict instead.
- Delete the current vertex bitmap.
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.
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.
git rev-list --objects --all, fetch each object with name_to_object, and count each type:Result:
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.