{"thread":{"id":"29680","subject":"Git tree object storing policy","startedAt":"2012-02-21T09:22:12Z","lastAt":"2012-02-21T10:18:27Z","messageCount":2,"participants":["Ivan Tolstosheyev","Thomas Rast"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"185065","messageId":"loom.20120221T094746-680@post.gmane.org","threadId":"29680","inReplyTo":null,"subject":"Git tree object storing policy","fromName":"Ivan Tolstosheyev","fromEmail":"ivan.tolstosheyev@gmail.com","sentAt":"2012-02-21T09:22:12Z","receivedAt":"2012-02-21T09:22:12Z","isPatch":false,"sender":{"key":"ivan.tolstosheyev@gmail.com","avatar":null},"body":"Hello,\n\nnow tree object is a simple list of <attributes, hash, name>sorted by name\n(tricky sorted, cause we assuming that directory name \"$X\" is actually \"$X/\"\nin comparison function). The problem is, that if I want to insert 10k files\nin empty git repository on / folder there will be 10k new \ntrees with sizes from (1 to 10k)*(hash+name+attribute)+eps  .\n\nitroot@localhost ~/tmp> cat git-test.sh \n#!/usr/bin/env bash\n\ngit init test\ncd test\nfor i in `seq 1 10000` \ndo\ntouch ${i} ; git add ${i} ; git commit -m \"Add ${i}\" ;\ndone\ncd ..\ndu -hs test\nitroot@localhost ~/tmp>\n\nitroot@localhost ~/tmp> ./git-test.sh\n...\n180M\ttest\nitroot@localhost ~/tmp>\n\n180 MB!!!?? and 7.4M after `git gc` - thanks to delta compression!\n\nOk, you can say that this example is artificial, and I can add 10k files\nwith 1 commit. Thats true. But manipulating files in big tree objects\n(in a big directories) is storage-expensive, and if I need to store a \nlot of files in one directory and frequently change them - git just\ndon't scales now properly at this use-case.\n\nWhat do I propose? \nWe can add another git object, named for example \"btree\" , \nthat contains another \"btree\" objects or files.  This will be a simple\nbtree structure (tree entries sorted practically by name, BTW,\nmaybe it's time to fix sorting =] ), that allows us to do insertion,\nremoval, search in ln(n) time. But - we do not have troubles \nwith big direcories now. BTW, if all directories are small, btree\nwill be tree-like - just btree pointing to  files.\nSo, one big tree with 10k files transforms to (hmm, for example...)\n101 btrees - one, pointing to 100 btrees, and thay points to files.\n(100 entries per btree is a wild guess =) )\n\nSuggestions?\n\n \n"},{"id":"185069","messageId":"87vcn0bibw.fsf@thomas.inf.ethz.ch","threadId":"29680","inReplyTo":"loom.20120221T094746-680@post.gmane.org","subject":"Re: Git tree object storing policy","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-02-21T10:18:27Z","receivedAt":"2012-02-21T10:18:27Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Ivan Tolstosheyev <ivan.tolstosheyev@gmail.com> writes:\n\n> #!/usr/bin/env bash\n>\n> git init test\n> cd test\n> for i in `seq 1 10000` \n> do\n> touch ${i} ; git add ${i} ; git commit -m \"Add ${i}\" ;\n> done\n> cd ..\n> du -hs test\n[...]\n> 180 MB!!!?? and 7.4M after `git gc` - thanks to delta compression!\n\nMost of those 180MB are waste from mostly unused 4KB (presumably) blocks\nof your filesystem.  You should be looking at the post-gc'd numbers.\n\nLet's see the breakdown of 'du -h .git':\n\n0       .git/rr-cache\n1.5M    .git/logs/refs/heads\n1.5M    .git/logs/refs\n2.9M    .git/logs\n4.0K    .git/objects/info\n2.8M    .git/objects/pack\n2.8M    .git/objects\n0       .git/branches\n12K     .git/info\n0       .git/remotes\n88K     .git/hooks\n0       .git/refs/tags\n0       .git/refs/heads\n0       .git/refs\n6.5M    .git\n\nSo 2.9MB are git keeping a reflog of everything we did (on HEAD and on\nmaster).  Since merely storing a SHA1 for each of your 10000 operations\nalready takes 200K, that's not so far off -- the factor of 10 is in the\nemail, date and log message.\n\nIn my case 704K went into the index (not directly visible above, it's\nthe bulk of the top level).  That's also not unreasonable: merely\nstoring the object SHA1 (20 bytes) and a bunch of timestamps for 10000\nfiles also gets you into the 500K ballpark.\n\nThe pack index amazingly takes only about 500K, even though it is\nindexing 10000 trees and 10000 commits, so again the SHA1s alone get you\ninto the 400K ballpark.\n\nThat leaves only 2.3MB for the actual pack (which contains all the\ndata!).  But every commit must store a tree and a parent, so there are\nat least 2*10000*20 = 400K uncompressable bytes in the commits\nalready[*].  So we are within a factor of 6 of just the data required to\nsave the shape of your history DAG, no content included.  I'd say that's\nnot too bad.\n\n\n[*] This is not quite true, the parents and trees might be pointers\nwithin the pack.  AFAIK the proposed pack v4 format does this, and would\nyield a more efficient compression.  So if you're going to waste energy\nworrying about this, you should help with pack v4.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"}]}