{"thread":{"id":"142","subject":"[PATCH] write-tree performance problems","startedAt":"2005-04-19T16:50:09Z","lastAt":"2005-04-20T22:29:54Z","messageCount":54,"participants":["Chris Mason","Linus Torvalds","Olivier Galibert","David Lang","C. Scott Ananian","Christopher Li","H. Peter Anvin","Ingo Molnar","Jon Seymour","Martin Uecker","Morten Welinder","David Woodhouse","David Willmore","David S. Miller"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"833","messageId":"200504191250.10286.mason@suse.com","threadId":"142","inReplyTo":null,"subject":"[PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-19T16:50:09Z","receivedAt":"2005-04-19T16:50:09Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"Hello everyone,\n\nI did a quick experiment with applying/commit 100 patches from the suse kernel \ninto a kernel git tree, which quilt can do in 2 seconds. git needs 1m5s.\n\nThe primary performance problem during each commit is write-tree recalculating \nthe hash of each directory, even though the contents of most directories are \nnot changing. I've attached a very quick and dirty mod of write-tree.c, it \ntakes an optional tree id (sha1) and list of directories. The hash of any \ndirectories not in the list are read in from existing files instead of being \nrecalculated.\n\nYou have to pass each sub dir with a modified file. So, if you change \nfs/super.c and fs/ext3/super.c, you would call \"write-tree sha1 fs fs/ext3\"\nWith this patch, the time to apply 100 commits goes down to 22 seconds. It \ncould be faster (and easier to use) if the index stored the hash of trees \ninstead of just blobs, but that would be a larger change.\n\nI was able to get the commit time down to 13 seconds by changing read-tree.c, \nupdate-cache.c and read-cache.c to store/read the index in tmpfs instead of \non the local filesystem. I haven't attached the patch for that, but it seems \neasiest to move .git/index into .git/index_dir/index, and let the user decide \nwhere to put index_dir.\n\nQuick speed summary, apply/commit 100 patches\nquilt push -a : 2s\ngit (unmodified): 1m5s\ngit (tree hash reduction) 22s\ngit (tree hash, tmpfs index) 13s\n\nThis patch is against pasky's tree from this morning, but also applies to \nlinus' tree. It's nasty stuff, but will hopefully get some discussion \nstarted on speeding things up.\n\n-chris\n\n\n--- a/write-tree.c\n+++ b/write-tree.c\n@@ -4,6 +4,8 @@\n * Copyright (C) Linus Torvalds, 2005\n */\n #include \"cache.h\"\n+static char **dirs;\n+static int num_dirs = 0;\n \n static int check_valid_sha1(unsigned char *sha1)\n {\n@@ -27,15 +29,47 @@ static int prepend_integer(char *buffer,\n \treturn i;\n }\n \n+static int find_sha(char *buffer, int size, const char *base, int baselen, char *returnsha1)\n+{\n+\twhile(size) {\n+\t\tint len = strlen(buffer)+1;\n+\t\tunsigned char *sha1 = buffer + len;\n+\t\tchar *path = strchr(buffer, ' ')+1;\n+\t\tunsigned int mode;\n+\n+\t\tif (size < len + 20 || sscanf(buffer, \"%o\", &mode) != 1)\n+\t\t\tdie(\"corrupt 'tree' file\");\n+\t\tbuffer = sha1 + 20;\n+\t\tsize -= len + 20;\n+\t\tif (strncmp(path, base, baselen) == 0 &&\n+\t\t strlen(path) == baselen) {\n+\t\t\tmemcpy(returnsha1, sha1, 20);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\treturn -1;\n+}\n+\n #define ORIG_OFFSET (40)\t/* Enough space to add the header of \"tree \\0\" */\n \n-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n+static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1, char *treesha)\n {\n \tunsigned char subdir_sha1[20];\n \tunsigned long size, offset;\n \tchar *buffer;\n \tint i, nr;\n-\n+\tchar *tree = NULL;\n+\tunsigned long tree_size;\n+\tchar type[20];\n+\tif (treesha) {\n+\t\ttree = read_sha1_file(treesha, type, &tree_size);\n+\t\tif (!tree) {\n+\t\t\tdie(\"unable to read sha1 file\");\n+\t\t} else {\n+\t\t}\n+\t\tif (strcmp(type, \"tree\"))\n+\t\t\tdie(\"expected a tree node\");\n+\t}\n \t/* Guess at some random initial size */\n \tsize = 8192;\n \tbuffer = malloc(size);\n@@ -55,15 +89,60 @@ static int write_tree(struct cache_entry\n \n \t\tsha1 = ce->sha1;\n \t\tmode = ntohl(ce->ce_mode);\n-\n \t\t/* Do we have _further_ subdirectories? */\n \t\tfilename = pathname + baselen;\n \t\tdirname = strchr(filename, '/');\n \t\tif (dirname) {\n \t\t\tint subdir_written;\n-\n-\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n-\t\t\tnr += subdir_written;\n+\t\t\tint dirlen = dirname - pathname;\n+\t\t\tint dirmatch = 1;\n+\t\t\tif (tree && num_dirs > 0) {\n+\t\t\t\tdirmatch = 0;\n+\t\t\t\tfor(i = 0 ; i < num_dirs; i++) {\n+\t\t\t\t\tint len = strlen(dirs[i]);\n+\t\t\t\t\tif (len <= baselen)\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\tif (memcmp(dirs[i], pathname, dirlen)==0 &&\n+\t\t\t\t\t pathname[dirlen] == '/') {\n+\t\t\t\t\t\tdirmatch = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t\tif (!dirmatch && find_sha(tree, tree_size, \n+\t\t\t\t\t\t\t filename, \n+\t\t\t\t\t\t\t dirname-filename, \n+\t\t\t\t\t\t\t subdir_sha1)) {\n+\t\t\t\t\tdirmatch = 1;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif (!dirmatch) {\n+\t\t\t\t/* eat all the entries in this dir */\n+\t\t\t\twhile(++nr < maxentries) {\n+\t\t\t\t\tchar *p;\n+\t\t\t\t\tce = cachep[nr];\n+\t\t\t\t\tp = strchr(ce->name + baselen, '/');\n+\t\t\t\t\tif (!p)\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tif (p - ce->name != dirname-pathname)\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tif (memcmp(pathname, ce->name, p-ce->name))\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t\tunsigned char thisdir_sha1[20];\n+\t\t\t\tchar *p = thisdir_sha1;\n+\t\t\t\tif (num_dirs && tree) {\n+\t\t\t\t if (find_sha(tree, tree_size, filename, \n+\t\t\t\t dirname-filename, p)) {\n+\t\t\t\t \tnum_dirs = 0;\n+\t\t\t\t\tp = NULL;\n+\t\t\t\t }\n+\t\t\t\t} else {\n+\t\t\t\t\tp = NULL;\n+\t\t\t\t}\n+\t\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1, p);\n+\t\t\t\tnr += subdir_written;\n+\t\t\t}\n \n \t\t\t/* Now we need to write out the directory entry into this tree.. */\n \t\t\tmode = S_IFDIR;\n@@ -92,9 +172,10 @@ static int write_tree(struct cache_entry\n \ti = prepend_integer(buffer, offset - ORIG_OFFSET, ORIG_OFFSET);\n \ti -= 5;\n \tmemcpy(buffer+i, \"tree \", 5);\n-\n \twrite_sha1_file(buffer + i, offset - i, returnsha1);\n \tfree(buffer);\n+\tif (tree)\n+\t\tfree(tree);\n \treturn nr;\n }\n \n@@ -103,7 +184,19 @@ int main(int argc, char **argv)\n \tint i, unmerged;\n \tint entries = read_cache();\n \tunsigned char sha1[20];\n+\tunsigned char treesha1[20];\n+\tchar *p = NULL;\n \n+\tif (argc > 1) {\n+\t\tif (argc < 3)\n+\t\t\tdie(\"usage: write-tree [sha1 dir1 dir2 ...]\");\n+\t\tnum_dirs = argc - 2;\n+\t\tdirs = argv + 2;\n+\t\tif (get_sha1_hex(argv[1], treesha1) < 0)\n+\t\t\tdie(\"bad sha1 given\");\n+\t\tp = treesha1;\n+\n+\t}\n \tif (entries <= 0)\n \t\tdie(\"write-tree: no cache contents to write\");\n \n@@ -123,7 +216,7 @@ int main(int argc, char **argv)\n \t\tdie(\"write-tree: not able to write tree\");\n \n \t/* Ok, write it out */\n-\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n+\tif (write_tree(active_cache, entries, \"\", 0, sha1, p) != entries)\n \t\tdie(\"write-tree: internal error\");\n \tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \treturn 0;\n"},{"id":"841","messageId":"Pine.LNX.4.58.0504191017300.19286@ppc970.osdl.org","threadId":"142","inReplyTo":"200504191250.10286.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-19T17:36:06Z","receivedAt":"2005-04-19T17:36:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, Chris Mason wrote:\n> \n> I did a quick experiment with applying/commit 100 patches from the suse kernel \n> into a kernel git tree, which quilt can do in 2 seconds. git needs 1m5s.\n\nNote that I don't think you want to replace quilt with git. The approaches \nare totally different, and git does _not_ obviate the need for the quilt \nkind of \"patch testing\".\n\nIn fact, git has all the same issues that BK had, and for the same \nfundamental reason: if you do distributed work, you have to always \n\"append\" stuff, and that means that you can never re-order anything after \nthe fact.\n\nSo git really is _not_ very good at all at doing what quilt does. Also, \nthere's an inevitable cost of being careful, and as you note, the sha1 \ncalculation is expensive (*).\n\nHowever, I hate your modification. Yeah, I know, performance is important \nto me, but even more than performance is that I can trust the end results, \nand that means that we calculate the hashes instead of just taking them \nfrom somewhere else..\n\nWhat I _would_ like is the ability to re-use an old tree, though. What you \nreally want to do is not pass in a set of directory names and just trust \nthat they are correct, but just pass in a directory to compare with, and \nif the contents match, you don't need to write out a new one.\n\nI'll try to whip up something that does what you want done, but doesn't\nneed (or take) any untrusted information from the user in the form \"trust\nme, it hasn't changed\".\n\n\t\tLinus\n\n(*) Actually, I think it's the compression that ends up being the most\nexpensive part.\n"},{"id":"848","messageId":"200504191412.00227.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191017300.19286@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-19T18:11:59Z","receivedAt":"2005-04-19T18:11:59Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 19 April 2005 13:36, Linus Torvalds wrote:\n> On Tue, 19 Apr 2005, Chris Mason wrote:\n> > I did a quick experiment with applying/commit 100 patches from the suse\n> > kernel into a kernel git tree, which quilt can do in 2 seconds. git\n> > needs 1m5s.\n>\n> Note that I don't think you want to replace quilt with git. The approaches\n> are totally different, and git does _not_ obviate the need for the quilt\n> kind of \"patch testing\".\n>\n> In fact, git has all the same issues that BK had, and for the same\n> fundamental reason: if you do distributed work, you have to always\n> \"append\" stuff, and that means that you can never re-order anything after\n> the fact.\n\nVery true, you can't replace quilt with git without ruining both of them. But \nit would be nice to take a quilt tree and turn it into a git tree for merging \npurposes, or to make use of whatever visualization tools might exist someday. \n\n> What I _would_ like is the ability to re-use an old tree, though. What you\n> really want to do is not pass in a set of directory names and just trust\n> that they are correct, but just pass in a directory to compare with, and\n> if the contents match, you don't need to write out a new one.\n>\n> I'll try to whip up something that does what you want done, but doesn't\n> need (or take) any untrusted information from the user in the form \"trust\n> me, it hasn't changed\".\n\nWe already have a \"trust me, it hasn't changed\" via update-cache. If it gets \ncalled wrong the tree won't reflect reality. The patch doesn't change the \nwrite-tree default, but does enable you to give write-tree better information \nabout the parts of the tree you want written back to git.\n\nWith that said, I hate the patch too. I didn't see how to compare against the \nold tree without reading each tree object from the old tree, and that should \nbe slower then what write-tree does now. So I wimped out and made the quick \npatch that demonstrates the cause of the performance hit.\n\nThe \"move .git/index to a tmpfs file\" change should be easier though, and has \na real benefit. How do you feel about s|.git/index|.git/index_dir/index| in \nthe sources? This gives us the flexibility to link it wherever is needed.\n\n-chris\n"},{"id":"851","messageId":"20050419185124.GB86697@dspnet.fr.eu.org","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191017300.19286@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Olivier Galibert","fromEmail":"galibert@pobox.com","sentAt":"2005-04-19T18:51:25Z","receivedAt":"2005-04-19T18:51:25Z","isPatch":true,"sender":{"key":"galibert@pobox.com","avatar":null},"body":"On Tue, Apr 19, 2005 at 10:36:06AM -0700, Linus Torvalds wrote:\n> In fact, git has all the same issues that BK had, and for the same \n> fundamental reason: if you do distributed work, you have to always \n> \"append\" stuff, and that means that you can never re-order anything after \n> the fact.\n\nYou can, moving a patch around is just a chain of merges.\n\n[Warning, ascii \"art\" ahead]\n\nA merge is traditionally seen as:\n\n1- Start with (A, B, C... are nodes/trees..., Pn are patches/changesets):\n\n /--P1->B\n /\n A\n \\\n \\--P2->C\n\n2- End with:\n\n /--P1->B\n /\n A----(P1+P2)->D\n \\\n \\--P2->C\n\n where D is the merge between B and C with A as common ancestor.\n\nBut you can also see the result as:\n\n /--P1->B--P2--\\\n / \\\n A D\n \\ /\n \\--P2->C--P1--/\n\ni.e. you have two patch chains, one being A-P1->B-P2->D and the other\nA-P2->C-P1->D. I.e. you have the two patches P1 and P2 in two\npossible patching orders. But you can do even more amusing. Start\nwith a patch chain:\n\n E--P3-->F--P4-->G\n\nand merge E and G with F as common ancestor. You'll then get H where\nE--P4-->H--P3-->G. I.e. you inverted two patches in your patch chain.\nOr, if you keep H instead of G as your head, you removed P3 from your\npatch chain.\n\nOf course you can permute blocs of patches that way by having E, F and\nG further away from each other. You just increase the merge conflict\nprobability.\n\nThat is, I think, the way to do quilt/arch patch handling with safe\ndistribution and safe backtracing procedures.\n\n OG.\n\n"},{"id":"854","messageId":"Pine.LNX.4.58.0504191143220.19286@ppc970.osdl.org","threadId":"142","inReplyTo":"200504191412.00227.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-19T19:03:35Z","receivedAt":"2005-04-19T19:03:35Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, Chris Mason wrote:\n> \n> Very true, you can't replace quilt with git without ruining both of them. But \n> it would be nice to take a quilt tree and turn it into a git tree for merging \n> purposes, or to make use of whatever visualization tools might exist someday. \n\nFair enough. The thing is, going from quilt->git really is a pretty \"big\ndecision\", since it's the decision that says \"I will now really commit all\nthis quilt changes forever and ever\".\n\nWhich is also why I think it's actually ok to take a minute to do 100\nquilt patches. This is not something you do on a whim. It's something\nyou'd better think about. It's turning a very fluid environment into a\nunchangable, final thing.\n\nThat said, I agree that \"write-tree\" is expensive. It tends to be by far\nthe most expensive op you normally do. I'll make sure it goes faster.\n\n> We already have a \"trust me, it hasn't changed\" via update-cache.\n\nHeh. I see \"update-cache\" not as a \"it hasn't changed\", but a \"it _has_ \nchanged, and now I want you to reflect that fact\". In other words, \nupdate-cache is an active statement: it says that you're ready to commit \nyour changes.\n\nIn contrast, to me your \"write-tree\" thing in many ways is the reverse of \nthat: it's saying \"don't look here, there's nothing interesting there\".\n\nWhich to me smells like trying to hide problems rather than being positive \nabout them.\n\nWhich it is, of course. It's trying to hide the fact that writing a tree \nis not instantaenous.\n\n> With that said, I hate the patch too. I didn't see how to compare against the \n> old tree without reading each tree object from the old tree, and that should \n> be slower then what write-tree does now.\n\nReading a tree is faster, simply because you uncompress instead of\ncompress. So I can read a tree in 0.28 seconds, but it takes me 0.34\nseconds to write one. That said, reading the trees has disk seek issues if\nit's not in the cache.\n\nWhat I'd actually prefer to do is to just handle tree caching the same way\nwe handle file caching - in the index.\n\nIe we could have the index file track \"what subtree is this directory\nassociated with\", and have a \"update-cache --refresh-dir\" thing that\nupdates it (and any entry update in that directory obviously removes the\ndir-cache entry).\n\nNormally we'd not bother and it would never trigger, but it would be\nuseful for your scripted setup it would end up caching all the tree\ninformation in a very efficient manner. Totally transparently, apart from\nthe one \"--refresh-dir\" at the beginning. That one would be slightly\nexpensive (ie would do all the stuff that \"write-tree\" does, but it would\nbe done just once).\n\n(We could also just make \"write-tree\" do it _totally_ transparently, but\nthen we're back to having write-tree both read _and_ write the index file,\nwhich is a situation that I've been trying to avoid. It's so much easier \nto verify the correctness of an operation if it is purely \"one-way\").\n\nI'll think about it. I'd love to speed up write-tree, and keeping track of \nit in the index is a nice little trick, but it's not quite high enough up \non my worries for me to act on it right now.\n\nBut if you want to try to see how nasty it would be to add tree index\nentries to the index file at \"write-tree\" time automatically, hey...\n\n\t\tLinus\n"},{"id":"866","messageId":"200504191708.23536.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191143220.19286@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-19T21:08:22Z","receivedAt":"2005-04-19T21:08:22Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 19 April 2005 15:03, Linus Torvalds wrote:\n> On Tue, 19 Apr 2005, Chris Mason wrote:\n> > Very true, you can't replace quilt with git without ruining both of them.\n> > But it would be nice to take a quilt tree and turn it into a git tree\n> > for merging purposes, or to make use of whatever visualization tools\n> > might exist someday.\n>\n> Fair enough. The thing is, going from quilt->git really is a pretty \"big\n> decision\", since it's the decision that says \"I will now really commit all\n> this quilt changes forever and ever\".\n>\n> Which is also why I think it's actually ok to take a minute to do 100\n> quilt patches. This is not something you do on a whim. It's something\n> you'd better think about. It's turning a very fluid environment into a\n> unchangable, final thing.\n>\n\nIt's only final when someone pulls from you...for me, all the trees would be \ntemporary.\n\n[ ... subtree tree hashes in the index file ... ]\n\n> I'll think about it. I'd love to speed up write-tree, and keeping track of\n> it in the index is a nice little trick, but it's not quite high enough up\n> on my worries for me to act on it right now.\n>\n> But if you want to try to see how nasty it would be to add tree index\n> entries to the index file at \"write-tree\" time automatically, hey...\n>\n\nMakes sense, I'll let the merge development frenzy die down and give it a try \none weekend. I might look into making it a special case of the merging index \nchanges, since some of the concepts seem similar.\n\nRegardless, putting it into the index somehow should be fastest, I'll see what \nI can do.\n\n-chris\n"},{"id":"868","messageId":"Pine.LNX.4.58.0504191420060.19286@ppc970.osdl.org","threadId":"142","inReplyTo":"200504191708.23536.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-19T21:23:33Z","receivedAt":"2005-04-19T21:23:33Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, Chris Mason wrote:\n> \n> Regardless, putting it into the index somehow should be fastest, I'll see what \n> I can do.\n\nStart by putting it in at \"read-tree\" time, and adding the code to\ninvalidate all parent directory indexes when somebody changes a file in\nthe index (ie \"update-cache\" for anything but a \"--refresh\").\n\nThat would be needed anyway, since those two are the ones that already\nchange the index file.\n\nOnce you're sure that you can correctly invalidate the entries (so that\nyou could never use a stale tree entry by mistake), the second stage would\nbe to update it at \"write-tree\" time.\n\n\t\tLinus\n"},{"id":"920","messageId":"20050419215248.GA6932@64m.dyndns.org","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191651110.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Christopher Li","fromEmail":"git@chrisli.org","sentAt":"2005-04-19T21:52:48Z","receivedAt":"2005-04-19T21:52:48Z","isPatch":true,"sender":{"key":"git@chrisli.org","avatar":null},"body":"On Tue, Apr 19, 2005 at 04:59:18PM -0700, Linus Torvalds wrote:\n> \n> However, it definitely wouldn't be useful for _me_. The whole thing that\n> I'm after is to allow painless merging of distributed work. If I have to\n> merge one patch at a time, I'd much rather see people send me patches\n> directly - that's much simpler than having a whole new GIT repository.\n> \n> So at least to me, a git repository only makes sense when it is a\n> collection of patches.\n\nSame here, I have been toying the idea to using git as quilt back\nend then I can get rid of the .pc/ directory in quilt.\n\nBut think about it more, I don't get a good reason to do it.\nquilt as it is, works great with git or other SCM. Using git to\nstore the quilt patches will require merge more often, instead of\njust applying patches. Introduce more steps and more objects to clean\nup later on. It seems that every thing I have been using quilt for,\nit is easier just deal with the series patches.\n\nChris\n\n"},{"id":"873","messageId":"Pine.LNX.4.62.0504191508060.26365@qynat.qvtvafvgr.pbz","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191143220.19286@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-19T22:09:26Z","receivedAt":"2005-04-19T22:09:26Z","isPatch":true,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Tue, 19 Apr 2005, Linus Torvalds wrote:\n\n> On Tue, 19 Apr 2005, Chris Mason wrote:\n>>\n>> Very true, you can't replace quilt with git without ruining both of them. But\n>> it would be nice to take a quilt tree and turn it into a git tree for merging\n>> purposes, or to make use of whatever visualization tools might exist someday.\n>\n> Fair enough. The thing is, going from quilt->git really is a pretty \"big\n> decision\", since it's the decision that says \"I will now really commit all\n> this quilt changes forever and ever\".\n>\n> Which is also why I think it's actually ok to take a minute to do 100\n> quilt patches. This is not something you do on a whim. It's something\n> you'd better think about. It's turning a very fluid environment into a\n> unchangable, final thing.\n\nwhat if you turned the forest of quilt patches into a forest of git trees? \n(essentially applying each patch against the baseline seperatly) would \nthis make sense or be useful?\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"874","messageId":"Pine.LNX.4.58.0504191514550.2274@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.62.0504191508060.26365@qynat.qvtvafvgr.pbz","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-19T22:21:01Z","receivedAt":"2005-04-19T22:21:01Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, David Lang wrote:\n> \n> what if you turned the forest of quilt patches into a forest of git trees? \n> (essentially applying each patch against the baseline seperatly) would \n> this make sense or be useful?\n\nIt has a certain charm, but the fact is, it gets really messy to sort out \nlater.\n\nThe thing is, there's a huge benefit to a straight-line tree: you can do \nbinary searching etc of patches that cause problems, and in general it's \njust a lot _easier_ to work with a linear set of patches for pretty much \neverybody.\n\nSo yes, it's \"cool\" to show the fact that patches are independent and show \nthem as each applying to the baseline (and then you can have the \"mother \nof all merges\" that ties them all together), but that's just a _nightmare_ \nwhen you actually try to debug things and sort things out.\n\nSo while I'm a huge proponent of parallell development, and having lots of\nbranches, I actually think that _linearizing_ stuff is a good thing. \n\nSo let's put it this way: parallel development and merging is wonderful as\na tool to handle true distributed development, and it's the thing that GIT\nreally tries to do. But once you have \"local\" development (like in a set\nof quilt patches), the _last_ thing you want to do is try to make it look\nparallel. You're much better off picking a good order, and sticking with\nit. Because otherwise, 2 months down the line, you'll just look at that\ntree, and what you'll want to do is to visualize them linearly anyway.\n\n\t\tLinus\n"},{"id":"888","messageId":"Pine.LNX.4.61.0504191846160.29929@cag.csail.mit.edu","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191017300.19286@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-19T22:47:31Z","receivedAt":"2005-04-19T22:47:31Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Tue, 19 Apr 2005, Linus Torvalds wrote:\n\n> (*) Actually, I think it's the compression that ends up being the most\n> expensive part.\n\nYou're also using the equivalent of '-9', too -- and *that's slow*.\nChanging to Z_NORMAL_COMPRESSION would probably help a lot\n(but would break all existing repositories, sigh).\n --scott\n\nDES WTO Indonesia NRA LCPANGS supercomputer plastique class struggle \nAEFOX Pakistan ODEARL Secretary KUGOWN Cheney ODIBEX SDI AP JMMADD\n ( http://cscott.net/ )\n"},{"id":"894","messageId":"Pine.LNX.4.62.0504191557410.26365@qynat.qvtvafvgr.pbz","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191514550.2274@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-19T23:00:04Z","receivedAt":"2005-04-19T23:00:04Z","isPatch":true,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Tue, 19 Apr 2005, Linus Torvalds wrote:\n\n> On Tue, 19 Apr 2005, David Lang wrote:\n>>\n>> what if you turned the forest of quilt patches into a forest of git trees?\n>> (essentially applying each patch against the baseline seperatly) would\n>> this make sense or be useful?\n>\n> It has a certain charm, but the fact is, it gets really messy to sort out\n> later.\n>\n> The thing is, there's a huge benefit to a straight-line tree: you can do\n> binary searching etc of patches that cause problems, and in general it's\n> just a lot _easier_ to work with a linear set of patches for pretty much\n> everybody.\n>\n> So yes, it's \"cool\" to show the fact that patches are independent and show\n> them as each applying to the baseline (and then you can have the \"mother\n> of all merges\" that ties them all together), but that's just a _nightmare_\n> when you actually try to debug things and sort things out.\n>\n> So while I'm a huge proponent of parallell development, and having lots of\n> branches, I actually think that _linearizing_ stuff is a good thing.\n>\n> So let's put it this way: parallel development and merging is wonderful as\n> a tool to handle true distributed development, and it's the thing that GIT\n> really tries to do. But once you have \"local\" development (like in a set\n> of quilt patches), the _last_ thing you want to do is try to make it look\n> parallel. You're much better off picking a good order, and sticking with\n> it. Because otherwise, 2 months down the line, you'll just look at that\n> tree, and what you'll want to do is to visualize them linearly anyway.\n\nif you are useing quilt for locally developed patches I fully agree with \nyou, but I was thinking of the case where Andrew is receiving independant \npatches from lots of people and storing them in quilt for testing, and \nthen sending them on to you. In this case the patches really are \nindependant and it may be useful to continue to treat them this way \ninstead of collapsing them into one 'update from Andrew' feed.\n\nI don't know if this sort of thing happens enough to matter or not.\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"901","messageId":"Pine.LNX.4.58.0504191608230.2274@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.62.0504191557410.26365@qynat.qvtvafvgr.pbz","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-19T23:09:27Z","receivedAt":"2005-04-19T23:09:27Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, David Lang wrote:\n> \n> if you are useing quilt for locally developed patches I fully agree with \n> you, but I was thinking of the case where Andrew is receiving independant \n> patches from lots of people and storing them in quilt for testing, and \n> then sending them on to you. In this case the patches really are \n> independant and it may be useful to continue to treat them this way \n> instead of collapsing them into one 'update from Andrew' feed.\n\nIf so, he should set up one repository per quilt patch. \n\nThat would be crazy, but yes, it would allow me to cherry-pick which\none(s) I want to merge with.\n\nBut the fact is, that cherry-picking should happen at quilt-time not at\ngit time.\n\n\t\tLinus\n"},{"id":"912","messageId":"Pine.LNX.4.62.0504191629410.26365@qynat.qvtvafvgr.pbz","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191608230.2274@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-19T23:42:33Z","receivedAt":"2005-04-19T23:42:33Z","isPatch":true,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Tue, 19 Apr 2005, Linus Torvalds wrote:\n\n> On Tue, 19 Apr 2005, David Lang wrote:\n>>\n>> if you are useing quilt for locally developed patches I fully agree with\n>> you, but I was thinking of the case where Andrew is receiving independant\n>> patches from lots of people and storing them in quilt for testing, and\n>> then sending them on to you. In this case the patches really are\n>> independant and it may be useful to continue to treat them this way\n>> instead of collapsing them into one 'update from Andrew' feed.\n>\n> If so, he should set up one repository per quilt patch.\n\na tool to do this automaticaly is what I was trying to suggest (and asking \nif it would be useful)\n\n> That would be crazy, but yes, it would allow me to cherry-pick which\n> one(s) I want to merge with.\n>\n> But the fact is, that cherry-picking should happen at quilt-time not at\n> git time.\n\nOk, I could see arguments for both methods. if the forest of disposeable \nrepositories is fast enough and flexible enough there is some value of \ngetting patches into git as quickly as possible, and not having to fan \nthem out to quilt as an intermediate step, but it may not be enough value \nto be worth the added complexity.\n\nnot being at all familar with quilt (in fact haveing never seen it, just \nseen it discussed here and LKML), how painful would it be to try and \nimplement it useing git as a back-end? you would end up with a bunch of \nextra objects that you will ignore (they are parts of branches that you \nthrow away), but I don't know if that space cost (plus the cost of the \nextra trees in git) is going to be too high.\n\nthis brings up a thought, is there a way to point at a bunch of \nrepositories (trees) and a collection of objects and tell git to purge any \nobjects that don't have anything linking to them? in the short-medium term \nthis isn't a problem, but in the long term you will have extra objects \nbeing created and then orphaned when a branch gets thrown away that will \neventually amount to a noticable amount of space.\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"914","messageId":"Pine.LNX.4.58.0504191651110.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.62.0504191629410.26365@qynat.qvtvafvgr.pbz","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-19T23:59:18Z","receivedAt":"2005-04-19T23:59:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, David Lang wrote:\n> >\n> > If so, he should set up one repository per quilt patch.\n> \n> a tool to do this automaticaly is what I was trying to suggest (and asking \n> if it would be useful)\n\nHeh. It's certainly possible. Esepcially with the object sharing, you \ncould create a git archive by just doing a \"read-tree\" and updating a few \nfiles, and you'd never have to even check out the rest of the files at \nall.\n\nIOW, you can probably set up a new git archive in not much more time than\nit takes for a \"read-tree\" + \"write-tree\", with very little in between. \nThat comes out to about a second, and the write-tree index optimizations\nwould take it down to next to nothing..\n\nHowever, it definitely wouldn't be useful for _me_. The whole thing that\nI'm after is to allow painless merging of distributed work. If I have to\nmerge one patch at a time, I'd much rather see people send me patches\ndirectly - that's much simpler than having a whole new GIT repository.\n\nSo at least to me, a git repository only makes sense when it is a\ncollection of patches.\n\nDoes that mean that it wouldn't make sense to others? No. It's really\ncheap to keep a shared object directory, and have a number of different\ngit archives using that, and you can have ten different trees tracking ten\ndifferent things, with very little overhead.\n\nBut even \"cheap\" is relative. If you actually want to do _work_ in those\nrepositories, you want to check things out in them, and populate them with\nfiles. Even if you do that with hardlinked blobs, just _populating_ the\ntree itself (setting up the subdirectories and the links) is going to be\nmore expensive than applying a patch in quilt.\n\n\t\tLinus\n"},{"id":"919","messageId":"200504192049.21947.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504191420060.19286@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-20T00:49:21Z","receivedAt":"2005-04-20T00:49:21Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 19 April 2005 17:23, Linus Torvalds wrote:\n> On Tue, 19 Apr 2005, Chris Mason wrote:\n> > Regardless, putting it into the index somehow should be fastest, I'll see\n> > what I can do.\n>\n> Start by putting it in at \"read-tree\" time, and adding the code to\n> invalidate all parent directory indexes when somebody changes a file in\n> the index (ie \"update-cache\" for anything but a \"--refresh\").\n>\n> That would be needed anyway, since those two are the ones that already\n> change the index file.\n>\n> Once you're sure that you can correctly invalidate the entries (so that\n> you could never use a stale tree entry by mistake), the second stage would\n> be to update it at \"write-tree\" time.\n\nThis was much easier then I expected, and it seems to be working here. It \ndoes slow down the write-tree slightly because we have to write out the index \nfile, but I can get around that with the index file on tmpfs change.\n\nThe original write-tree needs .54 seconds to run\n\nwrite-tree with the index speedup gets that down to .024s (same as my first \npatch) when nothing has changed. When it has to rewrite the index file \nbecause something changed, it's .167s.\n\nI'll finish off the patch once you ok the basics below. My current code works \nlike this:\n\n1) read-tree will insert index entries for directories. There is no index \nentry for the root.\n\n2) update-cache removes index entries for all parents of the file you're \nupdating. So, if you update-cache fs/ext3/inode.c, I remove the index of fs \nand fs/ext3\n\n3) If write-tree finds a directory in the index, it uses the sha1 in the cache \nentry and skips all files/dirs under that directory.\n\n4) If write-tree detects a subdir with no directory in the index, it calls \nwrite_tree the same way it used to. It then inserts a new cache object with \nthe calculated sha1.\n\n5) right before exiting, write-tree updates the index if it made any changes.\n\nThe downside to this setup is that I've got to change other index users to \ndeal with directory entries that are there sometimes and missing other times. \nThe nice part is that I don't have to \"invalidate\" the directory entry, if it \nis present, it is valid.\n\n-chris\n"},{"id":"921","messageId":"Pine.LNX.4.58.0504191804180.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"200504192049.21947.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T01:09:04Z","receivedAt":"2005-04-20T01:09:04Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, Chris Mason wrote:\n> \n> 5) right before exiting, write-tree updates the index if it made any changes.\n\nThis part won't work. It needs to do the proper locking, which means that \nit needs to create \"index.lock\" _before_ it reads the index file, and \nwrite everything to that one and then do a rename.\n\nIf it doesn't need to do the write, it can just remove index.lock without \nwriting to it, obviously.\n\n> The downside to this setup is that I've got to change other index users to \n> deal with directory entries that are there sometimes and missing other times. \n> The nice part is that I don't have to \"invalidate\" the directory entry, if it \n> is present, it is valid.\n\nTo me, the biggest downside is actually the complexity part, and worrying\nabout the directory index ever getting stale. How big do the changes end\nup being?\n\n\t\tLinus\n"},{"id":"947","messageId":"Pine.LNX.4.58.0504192337120.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"200504192049.21947.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T06:43:53Z","receivedAt":"2005-04-20T06:43:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Apr 2005, Chris Mason wrote:\n> \n> I'll finish off the patch once you ok the basics below. My current code works \n> like this:\n\nChris, before you do anything further, let me re-consider.\n\nAssuming that the real cost of write-tree is the compression (and I think\nit is), I really suspect that this ends up being the death-knell to my\n\"use the sha1 of the _compressed_ object\" approach. I thought it was\nclever, and I was ready to ignore the other arguments against it, but if\nit turns out that we can speed up write-tree a lot by just doing the SHA1\non the uncompressed data, and noticing that we already have the tree\nbefore we need to compress it and write it out, then that may be a good\nenough reason for me to just admit that I was wrong about that decision.\n\nSo I'll see if I can turn the current fsck into a \"convert into\nuncompressed format\", and do a nice clean format conversion. \n\nMost of git is very format-agnostic, so that shouldn't be that painful. \nKnock wood.\n\n\t\t\tLinus\n"},{"id":"949","messageId":"42660708.60109@zytor.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504192337120.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-04-20T07:38:48Z","receivedAt":"2005-04-20T07:38:48Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> So I'll see if I can turn the current fsck into a \"convert into\n> uncompressed format\", and do a nice clean format conversion. \n> \n\nJust let me know what you want to do, and I can trivially change the \nconversion scripts I've already written to do what you want.\n\n\t-hpa\n"},{"id":"958","messageId":"Pine.LNX.4.58.0504200144260.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"42660708.60109@zytor.com","subject":"WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T09:08:26Z","receivedAt":"2005-04-20T09:08:26Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nI converted my git archives (kernel and git itself) to do the SHA1 hash \n_before_ the compression phase.\n\nSo I'll just have to publically admit that everybody who complained about \nthat particular design decision was right. Oh, well.\n\nOn Wed, 20 Apr 2005, H. Peter Anvin wrote:\n> Linus Torvalds wrote:\n> > \n> > So I'll see if I can turn the current fsck into a \"convert into\n> > uncompressed format\", and do a nice clean format conversion. \n> > \n> \n> Just let me know what you want to do, and I can trivially change the \n> conversion scripts I've already written to do what you want.\n\nI actually wrote a trivial converter myself, and while I have to say that \nthis object database conversion is a bit painful, the nice thing is that I \ntried very hard to make it so that the \"git\" programs will work with both \na pre-conversion and a post-conversion database.\n\nThe only program where that isn't true is \"fsck-cache\", since fsck-cache\nfor obvious reasons is very very unhappy if the sha1 of a file doesn't\nmatch what it should be. But even there, a post-conversion fsck will eat\nold objects, it will just warn about a sha1 mismatch (and eventually it\nwill refuse to touch them).\n\nAnyway, what this means is that you should be actually able to get my\nalready-converted git database even using an older version of git: fsck\nwill complain mightily, so don't run it.\n\nWhat I've done is to just switch the SHA1 calculation and the compression\naround, but I've left all other data structures in their original format,\nincluding the low-level object details like the fact that all objects are\ntagged with their type and length.\n\nAs a result, the _only_ thing that breaks is that a new object will not\nhave a SHA1 that matches the expectations of an old git, but since\n_checking_ the SHA1 is only done by fsck, not normal operations, all\nnormal ops should work fine.\n\nSo to convert your old git setup to a new git setup, do the following:\n\n - save your old setup. Just in case. I've converted my whole kernel tree \n this way, so it's actually tested and I felt comfortable enough with it \n to blow the old one away, but never take risks.\n\n - do _not_ update to my new version first. Instead, while you still have \n an fsck that is happy with your old archive, make sure to fsck \n everything you have with\n\n\tfsck-cache --unreachable $(cat .git/HEAD)\n\n and it shouldn't complain about anything. Use \"git-prune-script\" to \n remove dangling objects if you want.\n\n (If you read this after you already updated, no worries - everything \n should still work. It's just a good idea to verify your old repo first)\n\n - update to my new git tools. checkout, build, install\n\n - convert your git object database with\n\n\tconvert-cache $(cat .git/HEAD)\n\n which will give you a new head object. Just for fun, you can \n double-check that \"re-converting\" that head object should always result\n in the same head object. If it doesn't, something is wrong.\n\n - take the new head object, and make it your new head:\n\n\techo xxxxxx > .git/HEAD\n\n - run the new \"fsck-cache\". It should complain about \"sha1 mismatch\" for \n all your old objects, and they should all be unreachable (and you \n should have two root objects: your old root and your new root)\n\n - run \"git-prune-script\" to remove all the unreachable objects (which are \n all old).\n\n - run \"fsck-cache --unreachable $(cat .git/HEAD)\" with the new fsck\n again, just to check that it is now quiet.\n\n - blow your old index file away by re-reading your HEAD tree:\n\n\tcat-file commit $(cat .git/HEAD)\n\tread-tree .....\n\n - \"update-cache --refresh\"\n\nDoing this on the git repository is nearly instantaneous. Doing it on the\nkernel takes maybe a minute or so, depending on how fast your machine is.\n\nSorry about this, but it's a hell of a lot simpler to do it now than it\nwill be after we have lots of users, and I've really tried to make the\nconversion be as simple and painless as possible.\n\nAnd while it doesn't matter right now (since git still does exactly the\nsame - I did the minimal changes necessary to get the new hashes, and\nthat's it), this _will_ allow us to notice existing objects before we\ncompress them, and we can now play with different compression levels\nwithout it being horribly painful.\n\n\t\t\t\tLinus\n"},{"id":"966","messageId":"20050420100445.GA25477@elte.hu","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200144260.6467@ppc970.osdl.org","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-20T10:04:45Z","receivedAt":"2005-04-20T10:04:45Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Linus Torvalds wrote:\n\n> So to convert your old git setup to a new git setup, do the following:\n> [...]\n\ndid this for two repositories (git and kernel-git), it works as \nadvertised.\n\n\tIngo\n"},{"id":"973","messageId":"2cfc403205042005116484231c@mail.gmail.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200144260.6467@ppc970.osdl.org","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-04-20T12:11:10Z","receivedAt":"2005-04-20T12:11:10Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 4/20/05, Linus Torvalds wrote:\n> \n> \n> I converted my git archives (kernel and git itself) to do the SHA1 hash\n> _before_ the compression phase.\n> \n\nLinus,\n \n Am I correct to understand that with this change, all the objects in\nthe database are still being compressed (so no net performance benefit\nnow), but by doing the SHA1 calculations before compression you are\nkeeping open the possibility that at some point in the future you may\nuse a different compression technique (including none at all) for some\nor all of the objects?\n\njon.\n\n[ reposted to list, because list post was bounced because of rich text\nformatting ]\n"},{"id":"975","messageId":"20050420132446.GA10126@macavity","threadId":"142","inReplyTo":"2cfc403205042005116484231c@mail.gmail.com","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-20T13:24:47Z","receivedAt":"2005-04-20T13:24:47Z","isPatch":true,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Wed, Apr 20, 2005 at 10:11:10PM +1000, Jon Seymour wrote:\n> On 4/20/05, Linus Torvalds wrote:\n> > \n> > \n> > I converted my git archives (kernel and git itself) to do the SHA1 hash\n> > _before_ the compression phase.\n> > \n> \n> Linus,\n> \n> Am I correct to understand that with this change, all the objects in\n> the database are still being compressed (so no net performance benefit\n> now), but by doing the SHA1 calculations before compression you are\n> keeping open the possibility that at some point in the future you may\n> use a different compression technique (including none at all) for some\n> or all of the objects?\n\nThe main point is not about trying different compression\ntechniques but that you don't need to compress at all just\nto calculate the hash of some data. (to know if it is\nunchanged for example)\n\nThere are still some other design decisions I am worried\nabout:\n\nThe storage method of the database of a collection of\nfiles in the underlying file system. Because of the\nrandom nature of the hashes this leads to a horrible\namount of seeking for all operations which walk the\nlogical structure of some tree stored in the database.\n\nWhy not store all objects linearized in one or more\nflat file?\n\n\nThe other thing I don't like is the use of a sha1\nfor a complete file. Switching to some kind of hash\ntree would allow to introduce chunks later. This has\ntwo advantages:\n\nIt would allow git to scale to repositories of large\nbinary files. And it would allow to build a very cool\ncontent transport algorithm for those repositories.\nThis algorithm could combine all the advantages of\nbittorrent and rsync (without the cpu load).\n\n\nAnd it would allow trivial merging of patches which\napply to different chunks of a file in exact the same\nway as merging changesets which apply to different\nfiles in a tree.\n\n\nMartin\n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"976","messageId":"Pine.LNX.4.61.0504200917070.28851@cag.csail.mit.edu","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200144260.6467@ppc970.osdl.org","subject":"Blob chunking code. [First look.]","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T13:30:42Z","receivedAt":"2005-04-20T13:30:42Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"So I wrote up my ideas regarding blob chunking as code; see attached.\nThis is against git-0.4 (I know, ancient, but I had to start somewhere.)\n\nThe idea here is that blobs are chunked using a rolling checksum (so the \nchunk boundaries are content-dependent and stay fixed even if you mutate \npieces of the file). The chunks are then tree-structured as 'treaps', \nwhich will ensure that chunk trees can be profitably reused. (If you \ncreate a flat 'chunk index' instead of tree-structuring it, then you need \nto write two files even if you make a small change to a small file. If \nyou use a full binary tree, then insertions at the beginning (say) still \nchange the entire tree structure. The treap ensures that on avg O(ln N) \nchunks need to be written per change, where N is the number of chunks in \nthe file). More details are in the code.\n\nCompatibility with existing archives in git-0.4 was tricky, because of \ngit's 'compress-before-hash' thingy. Moving to 'hash before compress' is \n*much* better, although because the file size is included in the hash, I will \nneed to perform (the equivalent of) O(ln N) hashes of the complete file.\nIf the file size weren't included, or if it were put at the end, then 2 \nhashes would suffice. (Basically, we can save work hashing subranges which \nare prefix-identical, but including the length means that no subtrees are\nprefix-identical.)\n\nI'll work on bringing this forward to the latest git, but I thought I'd \npost it here for early reviews and comments. My informal testing shows \nthat 1) my chunk size is currently too small, and 2) subrange sharing \nworks well even on relatively small files. I'll be working on getting \nconcrete numbers for larger archives.\n --scott\n\nDNC NRA Kojarena ESCOBILLA QKENCHANT STANDEL shotgun ESGAIN KGB Mossad \noverthrow ASW cracking HOPEFUL KUBARK counter-intelligence Yakima\n ( http://cscott.net/ )\n------- begin chunk.c ----------\n#include \n\n/* we could be clever and do this even if we don't fit in memory...\n * ... but we're going to be quick and dirty. */\n\n/* C source has approx 5 bits per character of entropy.\n * We'd like to get 32 bits of good entropy; that means 7 bytes is a\n * reasonable minimum for the window size. */\n#define ROLLING_WINDOW 30\n#define CHUNK_SIZE 1023 /* desired block size */\n\n#include \n#include \"cache.h\"\n\n/*\n * This file implements a treap-based chunked content store. The\n * idea is that every stored file is broken down into tree-structured\n * chunks (that is, every chunk has an optional 'prefix' and 'suffix'\n * chunk), and these chunks are put in the object store. This way\n * similar files will be expected to share chunks, saving space.\n * Files less than one disk block long are expected to fit in a single\n * chunk, so there is no extra indirection overhead for this case.\n */\n\n/* First, some data structures: */\nstruct chunk {\n /* a chunk represents some range of the underlying file */\n size_t start /* inclusive */, end /*exclusive*/;\n unsigned char sha1[20]; /* sha1 for this chunk; used as the heap key */\n};\nstruct chunklist {\n /* a dynamically-sized list of chunks */\n struct chunk *chunk; /* an array of chunks */\n size_t num_items; /* how many items are currently in the list */\n size_t allocd; /* how many items we've allocated space for */\n};\nstruct treap {\n /* A treap node represents a run of consecutive chunks. */\n\n struct chunk *chunk; /* some chunk in the run. */\n /* treaps representing the run before 'chunk' (left) and\n * after 'chunk' (right). */\n struct treap *left, *right;\n /* sha1 for the run represented by this treap */\n unsigned char sha1[20];\n};\n\nstatic struct chunklist *\ncreate_chunklist(int expected_items) {\n struct chunklist *cl = malloc(sizeof(*cl));\n cl->num_items = 0;\n cl->allocd = expected_items;\n cl->chunk = malloc(sizeof(cl->chunk[0]) * cl->allocd);\n return cl;\n}\nstatic void\nfree_chunklist(struct chunklist *cl) {\n free(cl->chunk);\n free(cl);\n}\n\n/* Add a chunk to the chunk list, calculating its SHA1 in the process. */\n/* The chunk includes buf[start] to buf[end-1]. */\nstatic void\nadd_chunk(struct chunklist *cl, char *buf, size_t start, size_t end) {\n struct chunk *ch;\n SHA_CTX c;\n assert(startnum_items >= cl->allocd) {\n \tcl->allocd = cl->allocd*3/2;\n \tcl->chunk = realloc(cl->chunk, cl->allocd * sizeof(*(cl->chunk)));\n }\n assert(cl->num_items < cl->allocd);\n ch = cl->chunk + (cl->num_items++);\n ch->start = start;\n ch->end = end;\n // compute SHA-1\n SHA1_Init(&c);\n SHA1_Update(&c, buf+start, end-start);\n SHA1_Final(ch->sha1, &c);\n // done!\n}\n\n/* Split a buffer into chunks, using a rolling checksum over ROLLING_WINDOW\n * bytes to determine chunk boundaries. We try to split chunks into pieces\n * whose size averages out to be 'CHUNK_SIZE'. */\nstatic void\nchunkify(struct chunklist *cl, char *buf, size_t size) {\n int i, rsync_s1, rsync_s2, last=-1;\n /* Make seed non-zero so that leading 0s don't create 1-char chunks. */\n rsync_s1 = rsync_s2 = 0xBABE; /* arbitrary */\n /* While window is filling: */\n for (i=0; isha1) as the heap key and the\n * file location (chunk->start) as the tree key.\n * For more info on treaps, see:\n * C. R. Aragon and R. G. Seidel, \"Randomized search trees\",\n * Proc. 30th IEEE FOCS (1989), 540-545.\n * There are many possible binary trees we could build; enforcing the\n * heap constraint ensures that similar files will build similar trees.\n */\n\n/* Assertion helper: check tree and heap constraints. */\nstatic int\ntreap_valid(struct treap *t) {\n int valid = 1;\n if (!t) return 1;\n if (t->chunk==NULL) return 0;\n if (t->left!=NULL) {\n \t/* Tree constraint. */\n \tvalid = valid && (t->left->chunk->start < t->chunk->start);\n \t/* Heap constraint. */\n \tvalid = valid && (memcmp(t->chunk->sha1, t->left->chunk->sha1,\n \t\t\t\t sizeof(t->chunk->sha1)) < 0);\n }\n if (t->right!=NULL) {\n \t/* Tree constraint. */\n \tvalid = valid && (t->chunk->start < t->right->chunk->start);\n \t/* Heap constraint. */\n \tvalid = valid && (memcmp(t->chunk->sha1, t->right->chunk->sha1,\n \t\t\t\t sizeof(t->chunk->sha1)) < 0);\n }\n return valid;\n}\n\n/* Restore heap constraint without disturbing tree ordering. */\n/* Only the root of the given treap will violate the heap constraint. */\nstatic struct treap *\ntreapify(struct treap *t) {\n struct treap *x, *y, *a, *b, *c;\n int left_ok, right_ok, rotate_left;\n assert(treap_valid(t->left));\n assert(treap_valid(t->right));\n left_ok = (t->left == NULL) ||\n \t(memcmp(t->chunk->sha1, t->left->chunk->sha1,\n \t\tsizeof(t->chunk->sha1)) < 0);\n right_ok = (t->right == NULL) ||\n \t(memcmp(t->chunk->sha1, t->right->chunk->sha1,\n \t\tsizeof(t->chunk->sha1)) < 0);\n if (left_ok && right_ok) { /* well, that's easy */\n \tassert(treap_valid(t));\n \treturn t;\n }\n /* okay, someone needs to rotate */\n rotate_left = (!left_ok) &&\n \t(right_ok || /* if neither is okay, the rotate smallest up */\n \t memcmp(t->left->chunk->sha1, t->right->chunk->sha1,\n \t\tsizeof(t->chunk->sha1)) < 0);\n /* Rotation:\n * y -bring left up-> x\n * / \\ / \\\n * x c a y\n * / \\ / \\\n * a b <-bring right up- b c\n */\n if (rotate_left) {\n \ty = t; x = y->left; c = y->right; a = x->left; b = x->right;\n \ty->left = b;\n \ty->right = c;\n \tx->left = a;\n \tx->right = treapify(y); // recurse to check heap constraint\n \tassert(treap_valid(x));\n \treturn x;\n } else {\n \tx = t; a = x->left; y = x->right; b = y->left; c = y->right;\n \tx->left = a;\n \tx->right = b;\n \ty->right = c;\n \ty->left = treapify(x); // recurse to check heap constraint.\n \tassert(treap_valid(y));\n \treturn y;\n }\n}\n\n/* Use list of chunks to build treap bottom-up, calling treapify to\n * restore heap order on the subtree after we add each interior node.\n * This is O(N), where N is the number of chunks. */\nstatic struct treap *\nbuild_treap(struct chunklist *cl, int chunk_st, int chunk_end) {\n struct treap *result;\n /* Some treaps are trivial to build: */\n if (chunk_st >= chunk_end) return NULL;\n /* Claim a chunk in the middle for ourself. */\n int c = (chunk_st + chunk_end)/2;\n result = (struct treap *)malloc(sizeof(*result));\n result->chunk = &(cl->chunk[c]);\n /* Divide and conquer: build well-formed treaps for our kids.*/\n result->left = build_treap(cl, chunk_st, c);\n result->right = build_treap(cl, c+1, chunk_end);\n /* Now we need to ensure that the heap constraint is satisfied; that is,\n * result->chunk->sha1 < result->left->chunk->sha1 and\n * result->chunk->sha1 < result->right->chunk->sha1.\n */\n assert(treap_valid(result->left));\n assert(treap_valid(result->right));\n return treapify(result);\n}\n\nstatic void\nfree_treap(struct treap *t) {\n if (!t) return;\n if (t->left) free_treap(t->left);\n if (t->right) free_treap(t->right);\n free(t);\n}\n\n/* Now that we've broken it down into treap-structured pieces, let's write\n * them to the object store. */\n\n/* Write a single treap piece to the object store. Note that 't' may be\n * NULL for the special case of a zero-byte file. Writes the hash of\n * this piece back to 'sha1', which must be non-NULL. Returns 0 on success.*/\nstatic int\nwrite_one(struct treap *t, char *buf, unsigned char *sha1) {\n/* two hundred bytes is two 20-byte SHA1 hashes, two presence bytes,\n * six bytes of type, one null, and plus 10^151 file length. (Conservative.) */\n#define MAX_METADATA_LEN 200\n z_stream stream;\n size_t max_out_bytes;\n size_t chunk_size = t ? (t->chunk->end - t->chunk->start) : 0;\n size_t content_size = chunk_size;\n char metadata[MAX_METADATA_LEN];\n void *out;\n SHA_CTX c;\n\n memset(&stream, 0, sizeof(stream));\n deflateInit(&stream, Z_BEST_COMPRESSION);\n max_out_bytes = deflateBound(&stream, chunk_size+sizeof(metadata));\n out = malloc(max_out_bytes);\n stream.next_out = out;\n stream.avail_out = max_out_bytes;\n /*\n * Metadata: Type, ASCII size, null byte, then left & right hashes.\n */\n content_size = chunk_size+2; /* prefix/suffix delimiters */\n if (t && t->left) content_size += sizeof(t->left->sha1);\n if (t && t->right) content_size += sizeof(t->right->sha1);\n\n stream.next_in = metadata;\n stream.avail_in = 1+sprintf(metadata, \"chunk %lu\",\n \t\t\t\t(unsigned long) content_size);\n if (t && t->left) { /* left hash */\n \tstream.next_in[stream.avail_in++] = 1;\n \tmemcpy(stream.next_in + stream.avail_in,\n \t t->left->sha1, sizeof(t->left->sha1));\n \tstream.avail_in += sizeof(t->left->sha1);\n } else\n \tstream.next_in[stream.avail_in++] = 0; /* no prefix chunk */\n if (t && t->right) { /* right hash */\n \tstream.next_in[stream.avail_in++] = 1;\n \tmemcpy(stream.next_in + stream.avail_in,\n \t t->right->sha1, sizeof(t->right->sha1));\n \tstream.avail_in += sizeof(t->right->sha1);\n } else\n \tstream.next_in[stream.avail_in++] = 0; /* no suffix chunk */\n\n while (deflate(&stream, 0) == Z_OK)\n \t/* nothing */;\n /*\n * Chunk content.\n */\n stream.next_in = buf + ( t ? t->chunk->start : 0);\n stream.avail_in = chunk_size; /* possibly zero */\n while (deflate(&stream, Z_FINISH) == Z_OK)\n \t/* nothing */;\n\n deflateEnd(&stream);\n\n SHA1_Init(&c);\n SHA1_Update(&c, out, stream.total_out);\n SHA1_Final(sha1, &c);\n\n return write_sha1_buffer(sha1, out, stream.total_out);\n}\n\n/* Write a sub-treap to disk, setting the 'sha1' fields of all nodes\n * as we go. */\nstatic int\nwrite_treap(struct treap *t, char *buf, unsigned char *sha1) {\n /* First write children (which initializes their SHA1 info). */\n if (t && t->left)\n \tif (write_treap(t->left, buf, NULL) < 0)\n \t return -1; /* failure. */\n if (t && t->right)\n \tif (write_treap(t->right, buf, NULL) < 0)\n \t return -1; /* failure. */\n /* Now write us. Note t may == NULL for a zero-byte file. */\n if (write_one(t, buf, t ? t->sha1 : sha1) < 0)\n \treturn -1; /* failure. */\n if (t && sha1)\n \tmemcpy(sha1, t->sha1, sizeof(t->sha1));\n return 0;\n}\n\n/* EXPORTED FUNCTION: write the file open on file descriptor 'fd'\n * and described by 'ce' and 'st' to the object store. Return\n * 0 on success, -1 on failure. */\n/* This does the same thing as 'index_fd' in Linus' update-cache.c */\nint\nchunk_index_fd(struct cache_entry *ce, int fd, struct stat *st) {\n struct chunklist *cl;\n struct treap *t;\n char *in;\n\n /* We expect there to be 'file length / CHUNK_SIZE' chunks. Over-estimate\n * a little, and do the initial chunk list allocation. */\n cl = create_chunklist(1 + ((3 * st->st_size) / (2 * CHUNK_SIZE)));\n /* Split the file into chunks. */\n in = mmap(NULL, st->st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n if (!in) return -1;\n chunkify(cl, in, st->st_size);\n /* Build the treap. */\n t = build_treap(cl, 0, cl->num_items);\n assert(treap_valid(t));\n /* Now write all the pieces, updating SHA1 for this file in the process. */\n if (write_treap(t, in, ce->sha1) < 0)\n \treturn -1;\n /* Free everything; we're done. */\n free_treap(t);\n free_chunklist(cl);\n munmap(in, st->st_size);\n close(fd);\n return 0; /* success! */\n}\n\n/*** Functions to read a chunked file into a contiguous buffer. ***/\n\nstruct read_chunk {\n void *data, *chunk_data;\n unsigned long chunk_size, total_size;\n struct read_chunk *left, *right;\n};\nstatic struct read_chunk *\nread_chunk2(const unsigned char *sha1, void *data, unsigned long size);\n\nstatic struct read_chunk *\nread_chunk(const unsigned char *sha1) {\n void *data;\n unsigned long size;\n char type[10];\n data = read_sha1_file(sha1, type, &size);\n assert(strcmp(type, \"chunk\")==0);\n return read_chunk2(sha1, data, size); \n}\nstatic struct read_chunk *\nread_chunk2(const unsigned char *sha1, void *data, unsigned long size) {\n unsigned char *cp;\n struct read_chunk *result = malloc(sizeof(*result));\n cp = result->data = data;\n printf(\"CHUNK %s (%d bytes)\\n\", sha1_to_hex(sha1), size);\n /* Parse the chunk data. */\n result->left = result->right = NULL;\n if (*cp++) {\n \tresult->left = read_chunk(cp); cp+=20;\n }\n if (*cp++) {\n \tresult->right = read_chunk(cp); cp+=20;\n }\n result->chunk_data = cp;\n result->chunk_size = size - (result->chunk_data - result->data);\n result->total_size = result->chunk_size +\n \t(result->left ? result->left->total_size : 0) +\n \t(result->right ? result->right->total_size : 0);\n return result;\n}\nstatic void\ncopy_read_chunk(void *dest, struct read_chunk *rc) {\n if (rc->left) {\n \tcopy_read_chunk(dest, rc->left);\n \tdest += rc->left->total_size;\n }\n memcpy(dest, rc->chunk_data, rc->chunk_size);\n if (rc->right)\n \tcopy_read_chunk(dest + rc->chunk_size, rc->right);\n}\nstatic void\nfree_read_chunk(struct read_chunk *rc) {\n if (rc->left) free_read_chunk(rc->left);\n if (rc->right) free_read_chunk(rc->right);\n free(rc->data);\n free(rc);\n}\n\n/* This does the same thing as 'read_sha1_file' in Linus' read_cache.c,\n * except that it knows about the 'chunk' encoding and will transparently\n * stitch together the appropriate prefix and suffix chunks and pass it\n * off as a 'blob'. */\nvoid *\nchunk_read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size) {\n struct read_chunk *rc;\n void *result = read_sha1_file(sha1, type, size);\n if (strcmp(type, \"chunk\")!=0) return result;\n /* This is a 'chunk' object; get the rest of the pieces. */\n rc = read_chunk2(sha1, result, *size);\n /* Now concatenate them together. */\n strcpy(type, \"blob\");\n *size = rc->total_size;\n result = malloc(*size);\n copy_read_chunk(result, rc);\n /* done! */\n free_read_chunk(rc);\n return result;\n}\n\n/* Exercise this code. */\nint main(int argc, char **argv) {\n struct cache_entry ce;\n struct stat st;\n char *buf, type[10];\n unsigned long size;\n int fd;\n fd = open(argv[1], O_RDONLY);\n if (fd < 0) exit(1);\n if (fstat(fd, &st) < 0) exit(1);\n if (chunk_index_fd(&ce, fd, &st) < 0) exit(1);\n /* seemed to work! */\n buf = chunk_read_sha1_file(ce.sha1, type, &size);\n if (!buf) exit(1);\n printf(\"Read file %s, of type %s (%lu bytes):\\n\",\n \t sha1_to_hex(ce.sha1), type, size);\n fwrite(buf, size, 1, stdout);\n /* done! */\n return 0;\n}\n"},{"id":"977","messageId":"118833cc0504200635408b5dd@mail.gmail.com","threadId":"142","inReplyTo":"20050420132446.GA10126@macavity","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2005-04-20T13:35:53Z","receivedAt":"2005-04-20T13:35:53Z","isPatch":true,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"On 4/20/05, Martin Uecker wrote:\n\n> The storage method of the database of a collection of\n> files in the underlying file system. Because of the\n> random nature of the hashes this leads to a horrible\n> amount of seeking for all operations which walk the\n> logical structure of some tree stored in the database.\n> \n> Why not store all objects linearized in one or more\n> flat file?\n\nI've been thinking along the same lines and it doesn't look too hard\nto factor out the\n\"back end\", i.e., provide methods to\nread/write/stat/remove/mmap/whatever objects.\n(Note the mmap there. Apart from that, the backend could be an http connection\nor worse.)\n\nIt will, however, seriously break rsync as transport for people who\ncommit to their trees.\nThus you need an alternative in place before you can present it as an\nalternative.\n\nMorten\n"},{"id":"978","messageId":"2cfc4032050420064167186802@mail.gmail.com","threadId":"142","inReplyTo":"20050420132446.GA10126@macavity","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-04-20T13:41:14Z","receivedAt":"2005-04-20T13:41:14Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"> The main point is not about trying different compression\n> techniques but that you don't need to compress at all just\n> to calculate the hash of some data. (to know if it is\n> unchanged for example)\n> \n\nAh, ok, I didn't understand that there were extra compresses being\nperformed for that reason. Thanks for the explanation.\n\njon.\n"},{"id":"979","messageId":"1114006429.5877.42.camel@localhost.localdomain","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200144260.6467@ppc970.osdl.org","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"David Woodhouse","fromEmail":"dwmw2@infradead.org","sentAt":"2005-04-20T14:13:48Z","receivedAt":"2005-04-20T14:13:48Z","isPatch":true,"sender":{"key":"dwmw2@infradead.org","avatar":"https://gravatar.com/avatar/7afd4f07e0cf7d7e046ae2d23678296b37777c96488e6f3451e78a5514154ebd?d=mp&s=160"},"body":"On Wed, 2005-04-20 at 02:08 -0700, Linus Torvalds wrote:\n> I converted my git archives (kernel and git itself) to do the SHA1\n> hash _before_ the compression phase.\n\nI'm happy to see that -- because I'm going to be asking you to make\nanother change which will also require a simple repository conversion. \n\nWe are working on getting the complete history since 2.4.0 into git\nform. When it's done and checked (which should be RSN) I'd like you to\nedit the first commit object in your tree -- the import of 2.6.12-rc2,\nand give it a parent. That parent will be the sha1 hash of the\n2.6.12-rc2 commit in the newly-provided history, and of course will\nchange the sha1 hash of your first commit, and all subsequent commits. \nWe'll provide a tool to do that, of course.\n\nThe history itself will be absent from your tree. Obviously we'll need\nto make sure that the tools can cope with an absentee parent, probably\nby just treating that case as if no parent exists. That won't be hard,\nit'll be useful for people to prune their trees of unwanted older\nhistory in the general case too. That history won't be lost or undone --\nit'll just be archived elsewhere.\n\nThe reason for doing this is that without it, we can't ever have a full\nhistory actually connected to the current trees. There'd always be a\nbreak at 2.6.12-rc2, at which point you'd have to switch to an entirely\ndifferent git repository.\n\n-- \ndwmw2\n\n"},{"id":"980","messageId":"Pine.LNX.4.58.0504200725110.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"2cfc4032050420050655265d3a@mail.gmail.com","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T14:29:29Z","receivedAt":"2005-04-20T14:29:29Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Jon Seymour wrote:\n> \n> Am I correct to understand that with this change, all the objects in the \n> database are still being compressed (so no net performance benefit), but by \n> doing the SHA1 calculations before compression you are keeping open the \n> possibility that at some point in the future you may use a different \n> compression technique (including none at all) for some or all of the \n> objects?\n\nCorrect. There is zero performance benefit to this right now, and the only \nreason for doing it is because it will allow other things to happen.\n\nNote that the other things include:\n - change the compression format to make it cheaper\n - _keep_ the same compression format, but notice that we already have an \n object by looking at the uncompressed one.\n\nI'm actually leaning towards just #2 at this time. I like how things\ncompress, and it sure is simple. The fact that we use the equivalent of\n\"-9\" may be expensive, but the thing is, we don't actually write new files\nthat often, and it's \"just\" CPU time (no seeking on disk or anything like\nthat), which tends to get cheaper over time.\n\nSo I suspect that once I optimize the tree writing to notice that \"oh, I\nalready have this tree object\", and thus build it up but never compressing\nit, \"write-tree\" performance will go up _hugely_ even without removing the\ncompressioin. Because most of the time, write-tree actually only needs to\ncreate a couple of small new tree objects.\n\n\t\t\tLinus\n"},{"id":"981","messageId":"Pine.LNX.4.61.0504201025030.2630@cag.csail.mit.edu","threadId":"142","inReplyTo":"20050420132446.GA10126@macavity","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T14:30:15Z","receivedAt":"2005-04-20T14:30:15Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Wed, 20 Apr 2005, Martin Uecker wrote:\n\n> The other thing I don't like is the use of a sha1\n> for a complete file. Switching to some kind of hash\n> tree would allow to introduce chunks later. This has\n> two advantages:\n\nYou can (and my code demonstrates/will demonstrate) still use a whole-file \nhash to use chunking. With content prefixes, this takes O(N ln M) time \n(where N is the file size and M is the number of chunks) to compute all \nhashes; if subtrees can share the same prefix, then you can do this in \nO(N) time (ie, as fast as possible, modulo a constant factor, which is \n'2'). You don't *need* internal hashing functions.\n\n> It would allow git to scale to repositories of large\n> binary files. And it would allow to build a very cool\n> content transport algorithm for those repositories.\n> This algorithm could combine all the advantages of\n> bittorrent and rsync (without the cpu load).\n\nYes, the big benefit of internal hashing is that it lets you check \nvalidity of a chunk w/o having the entire file available. I'm not sure \nthat's terribly useful in this case. [And, if it is, then it can \nobviously be done w/ other means.]\n\n> And it would allow trivial merging of patches which\n> apply to different chunks of a file in exact the same\n> way as merging changesets which apply to different\n> files in a tree.\n\nI'm not sure anyone should be looking at chunks. To me, at least, they \nare an object-store-implementation detail only. For merging, etc, we \nshould be looking at whole files, or (better) the whole repository.\nThe chunking algorithm is guaranteed not to respect semantic boundaries \n(for *some* semantics of *some* file).\n --scott\n\nexplosion JMTRAX DC KUBARK biowarfare LCFLUTTER ESMERALDITE for Dummies \nHager Nader Israel General ZRMETAL Castro cryptographic Indonesia\n ( http://cscott.net/ )\n"},{"id":"982","messageId":"Pine.LNX.4.61.0504201031350.2630@cag.csail.mit.edu","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200725110.6467@ppc970.osdl.org","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T14:35:02Z","receivedAt":"2005-04-20T14:35:02Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Wed, 20 Apr 2005, Linus Torvalds wrote:\n\n> - _keep_ the same compression format, but notice that we already have an\n> object by looking at the uncompressed one.\n\nWith a chunked file, you can also skip writing certain *subtrees* of the \nfile as soon as you notice it's already present on disk. I can code this \nup if you are interested.\n\nOf course, the paranoid folks will give up any performance benefit you \nobtain if they keep their \"yes the SHA1 matches, but is the file *really* \nthe same\" code. But maybe they're willing to be slow -- and they can do \nan uncompress rather than a compress in order to do the comparison, which \nwill give *some* performance improvement.\n --scott\n\nLCPANGS Serbian MKSEARCH security KUCLUB LCPANES Saddam Hussein Secretary \nDelta Force AMLASH ESMERALDITE TPAJAX plutonium ESGAIN Ft. Meade India\n ( http://cscott.net/ )\n"},{"id":"984","messageId":"Pine.LNX.4.58.0504200731590.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"1114006429.5877.42.camel@localhost.localdomain","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T14:59:49Z","receivedAt":"2005-04-20T14:59:49Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Apr 2005, David Woodhouse wrote:\n> \n> The reason for doing this is that without it, we can't ever have a full\n> history actually connected to the current trees. There'd always be a\n> break at 2.6.12-rc2, at which point you'd have to switch to an entirely\n> different git repository.\n\nQuite frankly, I'd _much_ rather have a notion of \"external references\" \nthan start depending on external hashes.\n\nIOW, I'd be happier with a new line in the header (after the normal\n\"author\"/\"committer\" lines) that just pointed to an external tree, aka\n\n\texternal linux-2.6.12-rc2-tree\n\nand then people could literally use this to link whatever they wanted, and \nit would not force one particular version of an external tree on you.\n\nWhy? Because we can't keep re-generating trees.\n\nHowever, the second part of that plan is that once you do that, you might \nas well make the \"external\" linkages be external to the repository itself. \nIOW, you could just make a file that the git tools can parse that say\n\n\texternal-parent \n\t\tcomment for this parent\n\n\texternal-parent \n\t\tcomment for this parent\n\nand the nice thing about that is that now that information allows you to \nadd external parents at any point. \n\nWhy do it like this? First off, I think that the \"initial import\" ends up\nbeing just one special case of the much more _generic_ issue of having\npatches come in from other source control systems (ie the above would\nactually work with the darcs issues too, and allow people to track the\ndependencies between a tree maintained in git and maintained elsewhere).\n\nSecondly, we do need something like this for pruning off history anyway, \nso that the tools have a better way of saying \"history has been pruned \noff\" than just hitting a missing commit. That's not a big deal right now, \nsince I'm not planning on letting people prune their history (or at least \nI'm planning on having tools complain loudly), but it _will_ be an issue. \nI think history pruning is wonderful, but I do want to have some mechanism \nto say \"it was pruned\" as opposed to \"it was lost\".\n\nThirdly, I don't actually want my new tree to depend on a conversion of\nthe old BK tree.\n\nTwo reasons: if it's a really full conversion, there are definitely going\nto be issues with BitMover. They do not want people to try to reverse\nengineer how they do namespace merges, which is why they have the \"don't\nlook at git and do another SCM at the same time\" clause in the first\nplace. Namespace merges (and probably other things too, for that matter)\ntend to be the thing they tend to do better than anybody else. The kernel\nprobably does not actually have a lot of those so it might be ok by them,\nbut the keyword is _might_, and I don't want to cloud git by another\nflamewar.\n\nThe other reason is just the really obvious one: in the last week, I've\nalready changed the format _twice_ in ways that change the hash. As long\nas it's 119MB of data, it's not going to be too nasty to do again. If it's\n3+GB of data, I'm going to feel really constrained about the kind of\nconversions I can do. It's one thing to have something that takes a few\nminutes and that anybody can do. It's another thing entirely to do\nsomething that requires the convertee to dedicate tons of diskspace and\nhours of work on it.\n\nLet's face it, I doubt we did our last conversion ever. I still think that\nthe git data model is the best model _ever_ for an SCM, but it's not all\nthe minute details I'm proud over, it's the general big things. For\nexample, let's see how the \"blobs are sequences of smaller hashes\" thing\nworks out. I was doubtful, but Scott's first chunking code doesn't make me\nhurl chunks, and I've been wrong before.\n\nAnd the thing is, I'm ok with being wrong. Especially if I can fix things \nup later.\n\nSo I've got tons of reasons (that you may not agree with, obviously) for\nwhy I don't think it's a good idea to base the kernel on a large\nconversion. Some (or all) of those reasons may become moot in another week\nor month, but I'd definitely _not_ that interested in doing it now. If it\nturns out later that we do want to re-base the kernel, we can do any\nconversion we want at a later time - it's not that it's necessarily the\nwrong thing to do, but I think it is the wrogn thing to do _now_.\n\n\t\tLinus\n"},{"id":"985","messageId":"20050420151902.GA13175@macavity","threadId":"142","inReplyTo":"Pine.LNX.4.61.0504201025030.2630@cag.csail.mit.edu","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-20T15:19:02Z","receivedAt":"2005-04-20T15:19:02Z","isPatch":true,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Wed, Apr 20, 2005 at 10:30:15AM -0400, C. Scott Ananian wrote:\n\nHi,\n\nyour code looks pretty cool. thank you!\n\n> On Wed, 20 Apr 2005, Martin Uecker wrote:\n> \n> >The other thing I don't like is the use of a sha1\n> >for a complete file. Switching to some kind of hash\n> >tree would allow to introduce chunks later. This has\n> >two advantages:\n> \n> You can (and my code demonstrates/will demonstrate) still use a whole-file \n> hash to use chunking. With content prefixes, this takes O(N ln M) time \n> (where N is the file size and M is the number of chunks) to compute all \n> hashes; if subtrees can share the same prefix, then you can do this in \n> O(N) time (ie, as fast as possible, modulo a constant factor, which is \n> '2'). You don't *need* internal hashing functions.\n\nI don't understand this paragraph. What is an internal\nhash function? Your code seems to do exactly what I want.\nThe hashes are computed recusively as in a hash tree\nwith O(N ln N). The only difference between your design\nand a design based on a conventional (binary) hash tree\nseems to be that data is stored in the intermediate nodes\ntoo. \n\n> >It would allow git to scale to repositories of large\n> >binary files. And it would allow to build a very cool\n> >content transport algorithm for those repositories.\n> >This algorithm could combine all the advantages of\n> >bittorrent and rsync (without the cpu load).\n> \n> Yes, the big benefit of internal hashing is that it lets you check \n> validity of a chunk w/o having the entire file available. I'm not sure \n> that's terribly useful in this case. [And, if it is, then it can \n> obviously be done w/ other means.]\n\nIf I don't miss anything essential, you can validate\neach treap piece at the moment you get it from the\nnetwork with its SHA1 hash and then proceed with\ndownloading the prefix and suffix tree (in parallel\nif you have more than one peer a la bittorrent).\n\n> >And it would allow trivial merging of patches which\n> >apply to different chunks of a file in exact the same\n> >way as merging changesets which apply to different\n> >files in a tree.\n> \n> I'm not sure anyone should be looking at chunks. To me, at least, they \n> are an object-store-implementation detail only. For merging, etc, we \n> should be looking at whole files, or (better) the whole repository.\n> The chunking algorithm is guaranteed not to respect semantic boundaries \n> (for *some* semantics of *some* file).\n\nYou might be right. I just wanted to point out this\npossibility because it would allow to avoid calling\nexternal merging code for a lot of trivial merges.\n\nbye,\nMartin\n\n\n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"986","messageId":"200504201122.35448.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504192337120.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-20T15:22:35Z","receivedAt":"2005-04-20T15:22:35Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 20 April 2005 02:43, Linus Torvalds wrote:\n> On Tue, 19 Apr 2005, Chris Mason wrote:\n> > I'll finish off the patch once you ok the basics below. My current code\n> > works like this:\n>\n> Chris, before you do anything further, let me re-consider.\n>\n> Assuming that the real cost of write-tree is the compression (and I think\n> it is), I really suspect that this ends up being the death-knell to my\n> \"use the sha1 of the _compressed_ object\" approach. \n\nThanks for looking at this. Your new tree is faster, it gets the commit 100 \npatches time down from 1m5s to 50s. I've attached my patch from last night, \nwhich is mostly a rough guess of the changes we would need, I haven't \nvalidated or cleaned things up.\n\nWith the basic changes I described before, the 100 patch time only goes down \nto 40s. Certainly not fast enough to justify the changes. In this case, the \nbulk of the extra time comes from write-tree writing the index file, so I \nsplit write-tree.c up into libwrite-tree.c, and created update-cache \n--write-tree.\n\nThis gets our time back down to 21s.\n\nThe attached patch is not against your latest revs. After updating I would \nneed to sprinkle a few S_ISDIR checks into diff-cache.c and checkout-cache.c, \nbut the changes should be small.\n\n-chris\n\n\nIndex: Makefile\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/Makefile (mode:100644 sha1:6a04941a337ec50da06cf4cf52aa58f3b1435776)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/Makefile (mode:100644 sha1:2ba6d49196e8a2335cfcd77ec0dbe9cda3e402dd)\n@@ -29,7 +29,7 @@\n \n VERSION= VERSION\n \n-LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o\n+LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o libwrite-tree.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h\n \nIndex: cache.h\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/cache.h (mode:100644 sha1:c182ea0c5c1def37d899f9a05f8884ebe17c9d92)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/cache.h (mode:100644 sha1:0882b713222b71e67c9dab5d58ab6f15c3c49ed6)\n@@ -74,7 +74,7 @@\n #define ce_stage(ce) ((CE_STAGEMASK & ntohs((ce)->ce_flags)) >> CE_STAGESHIFT)\n \n #define ce_permissions(mode) (((mode) & 0100) ? 0755 : 0644)\n-#define create_ce_mode(mode) htonl(S_IFREG | ce_permissions(mode))\n+#define create_ce_mode(mode) htonl((mode & (S_IFREG|S_IFDIR)) | ce_permissions(mode))\n \n #define cache_entry_size(len) ((offsetof(struct cache_entry,name) + (len) + 8) & ~7)\n \nIndex: libwrite-tree.c\n===================================================================\n--- /dev/null (tree:dbeacafeb442bcfd39dfdc90c360d47d4215c185)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/libwrite-tree.c (mode:100644 sha1:52202930d02b3721f5a388ae1178c5a4d99ec1b4)\n@@ -0,0 +1,174 @@\n+/*\n+ * GIT - The information manager from hell\n+ *\n+ * Copyright (C) Linus Torvalds, 2005\n+ */\n+#include \"cache.h\"\n+\n+struct new_ce {\n+\tstruct new_ce *next;\n+\tstruct cache_entry ce;\n+};\n+\n+static struct new_ce *add_list = NULL;\n+\n+static int check_valid_sha1(unsigned char *sha1)\n+{\n+\tchar *filename = sha1_file_name(sha1);\n+\tint ret;\n+\n+\t/* If we were anal, we'd check that the sha1 of the contents actually matches */\n+\tret = access(filename, R_OK);\n+\tif (ret)\n+\t\tperror(filename);\n+\treturn ret;\n+}\n+\n+static int prepend_integer(char *buffer, unsigned val, int i)\n+{\n+\tbuffer[--i] = '\\0';\n+\tdo {\n+\t\tbuffer[--i] = '0' + (val % 10);\n+\t\tval /= 10;\n+\t} while (val);\n+\treturn i;\n+}\n+\n+#define ORIG_OFFSET (40)\t/* Enough space to add the header of \"tree \\0\" */\n+\n+static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n+{\n+\tunsigned char subdir_sha1[20];\n+\tunsigned long size, offset;\n+\tchar *buffer;\n+\tint i, nr;\n+\n+\t/* Guess at some random initial size */\n+\tsize = 8192;\n+\tbuffer = malloc(size);\n+\toffset = ORIG_OFFSET;\n+\n+\tnr = 0;\n+\tdo {\n+\t\tstruct cache_entry *ce = cachep[nr];\n+\t\tconst char *pathname = ce->name, *filename, *dirname;\n+\t\tint pathlen = ce_namelen(ce), entrylen;\n+\t\tunsigned char *sha1;\n+\t\tunsigned int mode;\n+\n+\t\t/* Did we hit the end of the directory? Return how many we wrote */\n+\t\tif (baselen >= pathlen || memcmp(base, pathname, baselen))\n+\t\t\tbreak;\n+\n+\t\tsha1 = ce->sha1;\n+\t\tmode = ntohl(ce->ce_mode);\n+\n+\t\t/* Do we have _further_ subdirectories? */\n+\t\tfilename = pathname + baselen;\n+\t\tdirname = strchr(filename, '/');\n+\t\tif (dirname) {\n+\t\t\tint subdir_written;\n+\t\t\tint len = dirname - pathname;\n+\t\t\tunsigned int size = cache_entry_size(len);\n+\t\t\tstruct new_ce *new_ce = malloc(size + sizeof(struct new_ce *));\n+\t\t\tstruct cache_entry *c = &new_ce->ce;\n+\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n+\t\t\tnr += subdir_written - 1;\n+\n+\t\t\t/* Now we need to write out the directory entry into this tree.. */\n+\t\t\tmode = S_IFDIR;\n+\t\t\tpathlen = dirname - pathname;\n+\n+\t\t\tsha1 = subdir_sha1;\n+\n+\t\t\tmemset(c, 0, size);\n+\n+\t\t\t/* create a new cache entry for what we just calculated.\n+\t\t\t * place the new entry on a list for adding later so we\n+\t\t\t * don't change the size of the cache right now.\n+\t\t\t */\n+\t\t\tc->ce_mode = create_ce_mode(mode);\n+\t\t\tc->ce_flags = create_ce_flags(len, 0);\n+\t\t\tmemcpy(c->name, pathname, len);\n+\t\t\tc->name[len] = '\\0';\n+\t\t\tmemcpy(c->sha1, sha1, 20);\n+\t\t\tnew_ce->next = add_list;\n+\t\t\tadd_list = new_ce;\n+\t\t} else if (mode & S_IFDIR) {\n+\t\t\t/* eat all the entries below this directory */\n+\t\t\twhile(++nr < maxentries) {\n+\t\t\t\tstruct cache_entry *c = cachep[nr];\n+\t\t\t\t\n+\t\t\t\tif (strlen(c->name) < pathlen)\n+\t\t\t\t\tbreak;\n+\t\t\t\tif (memcmp(c->name, pathname, pathlen) ||\n+\t\t\t\t c->name[pathlen] != '/')\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\t/* our loop went too far by 1 */\n+\t\t\tnr--;\n+\t\t\tmode = S_IFDIR;\n+\t\t}\n+\n+\t\tif (check_valid_sha1(sha1) < 0)\n+\t\t\texit(1);\n+\n+\t\tentrylen = pathlen - baselen;\n+\t\tif (offset + entrylen + 100 > size) {\n+\t\t\tsize = alloc_nr(offset + entrylen + 100);\n+\t\t\tbuffer = realloc(buffer, size);\n+\t\t}\n+\t\toffset += sprintf(buffer + offset, \"%o %.*s\", mode, entrylen, filename);\n+\t\tbuffer[offset++] = 0;\n+\t\tmemcpy(buffer + offset, sha1, 20);\n+\t\toffset += 20;\n+\t\tnr++;\n+\t} while (nr < maxentries);\n+\n+\ti = prepend_integer(buffer, offset - ORIG_OFFSET, ORIG_OFFSET);\n+\ti -= 5;\n+\tmemcpy(buffer+i, \"tree \", 5);\n+\n+\twrite_sha1_file(buffer + i, offset - i, returnsha1);\n+\tfree(buffer);\n+\treturn nr;\n+}\n+\n+void write_full_tree(int entries) {\n+\tunsigned char sha1[20];\n+\tint i, unmerged;\n+\n+\tif (entries <= 0)\n+\t\tdie(\"write-tree: no cache contents to write\");\n+\n+\t/* Verify that the tree is merged */\n+\tunmerged = 0;\n+\tfor (i = 0; i < entries; i++) {\n+\t\tstruct cache_entry *ce = active_cache[i];\n+\t\tif (ntohs(ce->ce_flags) & ~CE_NAMEMASK) {\n+\t\t\tif (++unmerged > 10) {\n+\t\t\t\tfprintf(stderr, \"...\\n\");\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tfprintf(stderr, \"%s: unmerged (%s)\\n\", ce->name, sha1_to_hex(ce->sha1));\n+\t\t}\n+\t}\n+\tif (unmerged)\n+\t\tdie(\"write-tree: not able to write tree\");\n+\n+\t/* Ok, write it out */\n+\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n+\t\tdie(\"write-tree: internal error\");\n+\tprintf(\"%s\\n\", sha1_to_hex(sha1));\n+\tif (add_list) {\n+\t\tstruct new_ce *nc = add_list;\n+\t\twhile(nc) {\n+\t\t\tadd_cache_entry(&nc->ce, 1);\n+\t\t\tnc = nc->next;\n+\t\t}\n+\t}\n+}\n+\n+int write_tree_updated_cache(void) {\n+\treturn add_list != NULL;\n+}\nIndex: merge-cache.c\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/merge-cache.c (mode:100644 sha1:96c86c26d06837bf604a70caf9dd2133884a63bc)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/merge-cache.c (mode:100644 sha1:1b45bfc8cf5b4c610a4b149f3a4295081bc0e00f)\n@@ -63,8 +63,16 @@\n \t * If it already exists in the cache as stage0, it's\n \t * already merged and there is nothing to do.\n \t */\n-\tif (pos < 0)\n-\t\tmerge_entry(-pos-1, path);\n+\tif (pos < 0) {\n+\t\tpos = -pos-1;\n+\t\twhile(pos > 0) {\n+\t\t\tint mode = htonl(active_cache[pos]->ce_mode);\n+\t\t\tif (S_ISREG(mode))\n+\t\t\t\tbreak;\n+\t\t\tpos--;\n+\t\t}\n+\t\tmerge_entry(pos, path);\n+\t}\n }\n \n static void merge_all(void)\n@@ -74,7 +82,8 @@\n \t\tstruct cache_entry *ce = active_cache[i];\n \t\tif (!ce_stage(ce))\n \t\t\tcontinue;\n-\t\ti += merge_entry(i, ce->name)-1;\n+\t\tif (S_ISREG(htonl(ce->ce_mode)))\n+\t\t\ti += merge_entry(i, ce->name)-1;\n \t}\n }\n \nIndex: read-cache.c\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/read-cache.c (mode:100644 sha1:17d4d2284e79d3f1070b51200d797115f2d09d6a)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/read-cache.c (mode:100644 sha1:d2fc8e35f5ef602f7baa1a4c83c74dbf373fc3e0)\n@@ -96,11 +96,30 @@\n \treturn 1;\n }\n \n+static void invalidate_trees(char *path) {\n+\tchar *p;\n+\tint len = strlen(path);\n+\tint pos;\n+\textern void *memrchr(__const void *, int, size_t);\n+\twhile(1) {\n+\t\tp = memrchr(path, '/', len);\n+\t\tif (!p || p == path)\n+\t\t\treturn;\n+\t\tlen = p-path;\n+\t\tpos = cache_name_pos(path, len);\n+\t\tif (pos < 0)\n+\t\t\treturn;\n+\t\tremove_entry_at(pos);\n+\t}\t\n+}\n+\n int remove_file_from_cache(char *path)\n {\n \tint pos = cache_name_pos(path, strlen(path));\n-\tif (pos >= 0)\n+\tif (pos >= 0) {\n \t\tremove_entry_at(pos);\n+\t\tinvalidate_trees(path);\n+\t}\n \treturn 0;\n }\n \n@@ -113,12 +132,16 @@\n int add_cache_entry(struct cache_entry *ce, int ok_to_add)\n {\n \tint pos;\n+\tint invalidate = S_ISREG(htonl(ce->ce_mode));\n \n \tpos = cache_name_pos(ce->name, htons(ce->ce_flags));\n \n \t/* existing match? Just replace it */\n \tif (pos >= 0) {\n \t\tactive_cache[pos] = ce;\n+\t\tif (invalidate) {\n+\t\t\tinvalidate_trees(ce->name);\n+\t\t}\n \t\treturn 0;\n \t}\n \tpos = -pos-1;\n@@ -149,6 +172,9 @@\n \tif (active_nr > pos)\n \t\tmemmove(active_cache + pos + 1, active_cache + pos, (active_nr - pos - 1) * sizeof(ce));\n \tactive_cache[pos] = ce;\n+\tif (invalidate) {\n+\t\tinvalidate_trees(ce->name);\n+\t}\n \treturn 0;\n }\n \nIndex: read-tree.c\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/read-tree.c (mode:100644 sha1:a573a3155e532081a8be0dab60f1ec35ea159ddf)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/read-tree.c (mode:100644 sha1:fa497650937a62caadd043897032cf5f9e07dea2)\n@@ -63,7 +63,6 @@\n \t\t\t\tfree(buffer);\n \t\t\t\treturn -1;\n \t\t\t}\n-\t\t\tcontinue;\n \t\t}\n \t\tif (read_one_entry(sha1, base, baselen, path, mode) < 0) {\n \t\t\tfree(buffer);\nIndex: show-diff.c\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/show-diff.c (mode:100644 sha1:007dabd2978de4c58f49050d3969ca353278dbb6)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/show-diff.c (mode:100644 sha1:a7b0a0bca00c173f591a0d8ef0dfbcbdd96ef8a9)\n@@ -163,6 +163,8 @@\n \t\tif (1 < argc &&\n \t\t ! matches_pathspec(ce, argv+1, argc-1))\n \t\t\tcontinue;\n+\t\tif (S_ISDIR(htonl(ce->ce_mode)))\n+\t\t\tcontinue;\n \t\tmatched++;\n \n \t\tif (ce_stage(ce)) {\nIndex: update-cache.c\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/update-cache.c (mode:100644 sha1:11388582a830a6161d1c769aa8616bed6f593b8a)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/update-cache.c (mode:100644 sha1:cab4e8e1fa7aceff287cfb3464710b1dd52f3a5f)\n@@ -4,6 +4,7 @@\n * Copyright (C) Linus Torvalds, 2005\n */\n #include \"cache.h\"\n+#include \"write-tree.h\"\n \n /*\n * Default to not allowing changes to the list of files. The\n@@ -12,7 +13,7 @@\n * like \"update-cache *\" and suddenly having all the object\n * files be revision controlled.\n */\n-static int allow_add = 0, allow_remove = 0;\n+static int allow_add = 0, allow_remove = 0, write_tree = 0;\n \n static int index_fd(unsigned char *sha1, int fd, struct stat *st)\n {\n@@ -182,7 +183,6 @@\n \n \tif (stat(ce->name, &st) < 0)\n \t\treturn NULL;\n-\n \tchanged = cache_match_stat(ce, &st);\n \tif (!changed)\n \t\treturn ce;\n@@ -191,12 +191,11 @@\n \t * If the mode has changed, there's no point in trying\n \t * to refresh the entry - it's not going to match\n \t */\n-\tif (changed & MODE_CHANGED)\n+\tif (changed & MODE_CHANGED) {\n \t\treturn NULL;\n-\n+\t}\n \tif (compare_data(ce, st.st_size))\n \t\treturn NULL;\n-\n \tsize = ce_size(ce);\n \tupdated = malloc(size);\n \tmemcpy(updated, ce, size);\n@@ -222,7 +221,8 @@\n \n \t\tnew = refresh_entry(ce);\n \t\tif (!new) {\n-\t\t\tprintf(\"%s: needs update\\n\", ce->name);\n+\t\t\tif (S_ISREG(ntohl(ce->ce_mode)))\n+\t\t\t\tprintf(\"%s: needs update\\n\", ce->name);\n \t\t\tcontinue;\n \t\t}\n \t\t/* You can NOT just free active_cache[i] here, since it\n@@ -336,6 +336,10 @@\n \t\t\t\ti += 3;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!strcmp(path, \"--write-tree\")) {\n+\t\t\t\twrite_tree = 1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tdie(\"unknown option %s\", path);\n \t\t}\n \t\tif (!verify_path(path)) {\n@@ -345,6 +349,9 @@\n \t\tif (add_file_to_cache(path))\n \t\t\tdie(\"Unable to add %s to database\", path);\n \t}\n+\tif (write_tree) {\n+\t\twrite_full_tree(active_nr);\n+\t}\n \tif (write_cache(newfd, active_cache, active_nr) ||\n \t rename(\".git/index.lock\", \".git/index\"))\n \t\tdie(\"Unable to write new cachefile\");\nIndex: write-tree.c\n===================================================================\n--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/write-tree.c (mode:100644 sha1:fb046aa6ce6b9fce6a523a1e36ff43adab9bdd93)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/write-tree.c (mode:100644 sha1:c3d62242f0d5fff0c245cd46ac8a5b72d4aef4cd)\n@@ -4,127 +4,28 @@\n * Copyright (C) Linus Torvalds, 2005\n */\n #include \"cache.h\"\n-\n-static int check_valid_sha1(unsigned char *sha1)\n-{\n-\tchar *filename = sha1_file_name(sha1);\n-\tint ret;\n-\n-\t/* If we were anal, we'd check that the sha1 of the contents actually matches */\n-\tret = access(filename, R_OK);\n-\tif (ret)\n-\t\tperror(filename);\n-\treturn ret;\n-}\n-\n-static int prepend_integer(char *buffer, unsigned val, int i)\n-{\n-\tbuffer[--i] = '\\0';\n-\tdo {\n-\t\tbuffer[--i] = '0' + (val % 10);\n-\t\tval /= 10;\n-\t} while (val);\n-\treturn i;\n-}\n-\n-#define ORIG_OFFSET (40)\t/* Enough space to add the header of \"tree \\0\" */\n-\n-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n-{\n-\tunsigned char subdir_sha1[20];\n-\tunsigned long size, offset;\n-\tchar *buffer;\n-\tint i, nr;\n-\n-\t/* Guess at some random initial size */\n-\tsize = 8192;\n-\tbuffer = malloc(size);\n-\toffset = ORIG_OFFSET;\n-\n-\tnr = 0;\n-\tdo {\n-\t\tstruct cache_entry *ce = cachep[nr];\n-\t\tconst char *pathname = ce->name, *filename, *dirname;\n-\t\tint pathlen = ce_namelen(ce), entrylen;\n-\t\tunsigned char *sha1;\n-\t\tunsigned int mode;\n-\n-\t\t/* Did we hit the end of the directory? Return how many we wrote */\n-\t\tif (baselen >= pathlen || memcmp(base, pathname, baselen))\n-\t\t\tbreak;\n-\n-\t\tsha1 = ce->sha1;\n-\t\tmode = ntohl(ce->ce_mode);\n-\n-\t\t/* Do we have _further_ subdirectories? */\n-\t\tfilename = pathname + baselen;\n-\t\tdirname = strchr(filename, '/');\n-\t\tif (dirname) {\n-\t\t\tint subdir_written;\n-\n-\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n-\t\t\tnr += subdir_written;\n-\n-\t\t\t/* Now we need to write out the directory entry into this tree.. */\n-\t\t\tmode = S_IFDIR;\n-\t\t\tpathlen = dirname - pathname;\n-\n-\t\t\t/* ..but the directory entry doesn't count towards the total count */\n-\t\t\tnr--;\n-\t\t\tsha1 = subdir_sha1;\n-\t\t}\n-\n-\t\tif (check_valid_sha1(sha1) < 0)\n-\t\t\texit(1);\n-\n-\t\tentrylen = pathlen - baselen;\n-\t\tif (offset + entrylen + 100 > size) {\n-\t\t\tsize = alloc_nr(offset + entrylen + 100);\n-\t\t\tbuffer = realloc(buffer, size);\n-\t\t}\n-\t\toffset += sprintf(buffer + offset, \"%o %.*s\", mode, entrylen, filename);\n-\t\tbuffer[offset++] = 0;\n-\t\tmemcpy(buffer + offset, sha1, 20);\n-\t\toffset += 20;\n-\t\tnr++;\n-\t} while (nr < maxentries);\n-\n-\ti = prepend_integer(buffer, offset - ORIG_OFFSET, ORIG_OFFSET);\n-\ti -= 5;\n-\tmemcpy(buffer+i, \"tree \", 5);\n-\n-\twrite_sha1_file(buffer + i, offset - i, returnsha1);\n-\tfree(buffer);\n-\treturn nr;\n-}\n+#include \"write-tree.h\"\n \n int main(int argc, char **argv)\n {\n-\tint i, unmerged;\n \tint entries = read_cache();\n-\tunsigned char sha1[20];\n+\tint newfd;\n+\tnewfd = open(\".git/index.lock\", O_RDWR | O_CREAT | O_EXCL, 0600);\n+\tif (newfd < 0)\n+\t\tdie(\"unable to create new cachefile\");\n+\n \n \tif (entries <= 0)\n \t\tdie(\"write-tree: no cache contents to write\");\n \n-\t/* Verify that the tree is merged */\n-\tunmerged = 0;\n-\tfor (i = 0; i < entries; i++) {\n-\t\tstruct cache_entry *ce = active_cache[i];\n-\t\tif (ntohs(ce->ce_flags) & ~CE_NAMEMASK) {\n-\t\t\tif (++unmerged > 10) {\n-\t\t\t\tfprintf(stderr, \"...\\n\");\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t\tfprintf(stderr, \"%s: unmerged (%s)\\n\", ce->name, sha1_to_hex(ce->sha1));\n-\t\t}\n+\twrite_full_tree(entries);\n+\tif (write_tree_updated_cache()) {\n+\t\tif (write_cache(newfd, active_cache, active_nr) ||\n+\t\t rename(\".git/index.lock\", \".git/index\"))\n+\t\t\tdie(\"Unable to write new cachefile\");\n+\t} else {\n+\t\tclose(newfd);\n+\t\tunlink(\".git/index.lock\");\n \t}\n-\tif (unmerged)\n-\t\tdie(\"write-tree: not able to write tree\");\n-\n-\t/* Ok, write it out */\n-\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n-\t\tdie(\"write-tree: internal error\");\n-\tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \treturn 0;\n }\nIndex: write-tree.h\n===================================================================\n--- /dev/null (tree:dbeacafeb442bcfd39dfdc90c360d47d4215c185)\n+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/write-tree.h (mode:100644 sha1:0ad5fe36126577e56544e08e0f4dfa766350e841)\n@@ -0,0 +1,3 @@\n+\n+void write_full_tree(int);\n+int write_tree_updated_cache(void);\n"},{"id":"987","messageId":"Pine.LNX.4.61.0504201121490.2630@cag.csail.mit.edu","threadId":"142","inReplyTo":"20050420151902.GA13175@macavity","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T15:28:20Z","receivedAt":"2005-04-20T15:28:20Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Wed, 20 Apr 2005, Martin Uecker wrote:\n\n>> You can (and my code demonstrates/will demonstrate) still use a whole-file\n>> hash to use chunking. With content prefixes, this takes O(N ln M) time\n>> (where N is the file size and M is the number of chunks) to compute all\n>> hashes; if subtrees can share the same prefix, then you can do this in\n>> O(N) time (ie, as fast as possible, modulo a constant factor, which is\n>> '2'). You don't *need* internal hashing functions.\n>\n> I don't understand this paragraph. What is an internal\n> hash function? Your code seems to do exactly what I want.\n> The hashes are computed recusively as in a hash tree\n> with O(N ln N). The only difference between your design\n> and a design based on a conventional (binary) hash tree\n> seems to be that data is stored in the intermediate nodes\n> too.\n\nA merkle-tree (which I think you initially pointed me at) makes the hash \nof the internal nodes be a hash of the chunk's hashes; ie not a straight \ncontent hash. This is roughly what my current implementation does, but\nI would like to identify each subtree with the hash of the \n*(expanded) contents of that subtree* (ie no explicit reference to \nsubtree hashes). This makes it interoperable with non-chunked or \ndifferently-chunked representations, in that the top-level hash is *just \nthe hash of the complete content*, not some hash-of-subtree-hashes. Does \nthat make more sense?\n\nThe code I posted doesn't demonstrate this very well, but now that Linus \nhas abandoned the 'hash of compressed content' stuff, my next code posting \nshould show this more clearly.\n\n> If I don't miss anything essential, you can validate\n> each treap piece at the moment you get it from the\n> network with its SHA1 hash and then proceed with\n> downloading the prefix and suffix tree (in parallel\n> if you have more than one peer a la bittorrent).\n\nYes, I guess this is the detail I was going to abandon. =)\n\nI viewed the fact that the top-level hash was dependent on the exact chunk \nmakeup a 'misfeature', because it doesn't allow easy interoperability with \nexisting non-chunked repos.\n --scott\n\nWTO atomic operation Mossad Castro overthrow FSF fissionable HTAUTOMAT \nLCPANES MKDELTA Bush non-violent protest OVER THE HORIZON RADAR KUPALM\n ( http://cscott.net/ )\n"},{"id":"989","messageId":"Pine.LNX.4.61.0504201128550.2630@cag.csail.mit.edu","threadId":"142","inReplyTo":"200504201122.35448.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T15:30:22Z","receivedAt":"2005-04-20T15:30:22Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Wed, 20 Apr 2005, Chris Mason wrote:\n\n> With the basic changes I described before, the 100 patch time only goes down\n> to 40s. Certainly not fast enough to justify the changes. In this case, the\n> bulk of the extra time comes from write-tree writing the index file, so I\n> split write-tree.c up into libwrite-tree.c, and created update-cache\n> --write-tree.\n\nHmm. Are our index files too large, or is there some other factor?\nI was considering using a chunked representation for *all* files (not just \nblobs), which would avoid the original 'trees must reference other trees \nor they become too large' issue -- and maybe the performance issue you're \nreferring to, as well?\n --scott\n\nBoston MI6 quiche LPMEDLEY BLUEBIRD PBSUCCESS jihad biowarfare non-violent protest \nYakima NRA EZLN DES hack SARANAC KMPLEBE Echelon PBCABOOSE security\n ( http://cscott.net/ )\n"},{"id":"990","messageId":"Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"200504201122.35448.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T15:40:18Z","receivedAt":"2005-04-20T15:40:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Chris Mason wrote:\n> \n> Thanks for looking at this. Your new tree is faster, it gets the commit 100 \n> patches time down from 1m5s to 50s.\n\nIt really _shouldn't_ be faster. It still does the compression, and throws\nthe end result away.\n\nTo actually go faster, it _should_ need this patch. Untested. See if it \nworks..\n\n\t\tLinus\n---\nsha1_file.c: 40c00b77d0e52b31dda1696f10026fe6f92bc082\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -173,12 +173,27 @@ int write_sha1_file(char *buf, unsigned \n \tz_stream stream;\n \tunsigned char sha1[20];\n \tSHA_CTX c;\n+\tchar *filename;\n+\tint fd;\n \n \t/* Sha1.. */\n \tSHA1_Init(&c);\n \tSHA1_Update(&c, buf, len);\n \tSHA1_Final(sha1, &c);\n \n+\tfilename = sha1_file_name(sha1);\n+\tfd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0) {\n+\t\tif (errno != EEXIST)\n+\t\t\treturn -1;\n+\n+\t\t/*\n+\t\t * We might do collision checking here, but we'd need to\n+\t\t * uncompress the old file and check it. Later.\n+\t\t */\n+\t\treturn 0;\n+\t}\n+\n \t/* Set it up */\n \tmemset(&stream, 0, sizeof(stream));\n \tdeflateInit(&stream, Z_BEST_COMPRESSION);\n@@ -195,8 +210,10 @@ int write_sha1_file(char *buf, unsigned \n \tdeflateEnd(&stream);\n \tsize = stream.total_out;\n \n-\tif (write_sha1_buffer(sha1, compressed, size) < 0)\n-\t\treturn -1;\n+\tif (write(fd, compressed, size) != size)\n+\t\tdie(\"unable to write file\");\n+\tclose(fd);\n+\t\t\n \tif (returnsha1)\n \t\tmemcpy(returnsha1, sha1, 20);\n \treturn 0;\n"},{"id":"991","messageId":"Pine.LNX.4.58.0504200840240.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.61.0504201128550.2630@cag.csail.mit.edu","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T15:46:19Z","receivedAt":"2005-04-20T15:46:19Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, C. Scott Ananian wrote:\n> \n> Hmm. Are our index files too large, or is there some other factor?\n\nThey _are_ pretty large, but they have to be,\n\nFor the kernel, the index file is about 1.6MB. That's \n\n - 17,000+ files and filenames\n - stat information for all of them\n - the sha1 for them all\n\nie for the kernel it averages to 93.5 bytes per file. Which is actually \npretty dense (just the sha1 and stat information is about half of it, and \nthose are required).\n\n> I was considering using a chunked representation for *all* files (not just \n> blobs), which would avoid the original 'trees must reference other trees \n> or they become too large' issue -- and maybe the performance issue you're \n> referring to, as well?\n\nNo. The most common index file operation is reading, and that's the one \nthat has to be _fast_. And it is - it's a single \"mmap\" and some parsing.\n\nIn fact, writing it is pretty fast too, exactly because the index file is \ntotally linear and isn't compressed or anything fancy like that. It's a \n_lot_ faster than the \"tree objects\", exactly because it doesn't need to \nbe as careful.\n\nThe main cost of the index file is probably the fact that I add a sha1 \nsignature of the file into itself to verify that it's ok. The advantage is \nthat the signature means that the file is ok, and the parsing of it can be \nmuch more relaxed. You win some, you lose some.\n\n\t\tLinus\n"},{"id":"992","messageId":"Pine.LNX.4.61.0504201147280.2630@cag.csail.mit.edu","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200840240.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T15:52:02Z","receivedAt":"2005-04-20T15:52:02Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Wed, 20 Apr 2005, Linus Torvalds wrote:\n\n>> I was considering using a chunked representation for *all* files (not just\n>> blobs), which would avoid the original 'trees must reference other trees\n>> or they become too large' issue -- and maybe the performance issue you're\n>> referring to, as well?\n> No. The most common index file operation is reading, and that's the one\n> that has to be _fast_. And it is - it's a single \"mmap\" and some parsing.\n\nOK, sure. But how 'bout chunking trees? Are you grown happy with the new \ntrees-reference-other-trees paradigm, or is there a deep longing in your \nheart for the simplicity of 'trees-reference-blobs-period'? I'm fairly\ncertain that chunking could get you the space-savings you need without \nmulti-level trees, if the simplicity of that is still appealing.\n\nNot necessarily for rev.1 of the chunking code, but I'm curious as to \nwhether it's still of interest at all. I don't know exactly how far\ningrained multilevel trees have become since they were adopted.\n --scott\n\nJapan explosion BLUEBIRD Honduras jihad D5 SLBM Diplomat overthrow \nJMTIDE CABOUNCE AMTHUG ESODIC Kennedy AVBRANDY CLOWER mail drop PHOENIX\n ( http://cscott.net/ )\n"},{"id":"994","messageId":"20050420155734.GA13575@macavity","threadId":"142","inReplyTo":"Pine.LNX.4.61.0504201121490.2630@cag.csail.mit.edu","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-20T15:57:34Z","receivedAt":"2005-04-20T15:57:34Z","isPatch":true,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Wed, Apr 20, 2005 at 11:28:20AM -0400, C. Scott Ananian wrote:\n\nHi,\n \n> A merkle-tree (which I think you initially pointed me at) makes the hash \n> of the internal nodes be a hash of the chunk's hashes; ie not a straight \n> content hash. This is roughly what my current implementation does, but\n> I would like to identify each subtree with the hash of the \n> *(expanded) contents of that subtree* (ie no explicit reference to \n> subtree hashes). This makes it interoperable with non-chunked or \n> differently-chunked representations, in that the top-level hash is *just \n> the hash of the complete content*, not some hash-of-subtree-hashes. Does \n> that make more sense?\n\nYes, thank you. But I would like to argue against this:\n\nYou can make the representations interoperable\nif you calculate the hash for the non-chunked\nrepresentations exactly as if this file is stored\nchunked but simple do not store it in that way.\n\nOf course this is not backward compatible to the\nmonolithic hash and not compatible with a differently\nchunked representation (but you could store subtrees\nunchunked if you think your chunks are too small).\n\n> The code I posted doesn't demonstrate this very well, but now that Linus \n> has abandoned the 'hash of compressed content' stuff, my next code posting \n> should show this more clearly.\n\nI think the hash of the treap piece should be calculated\nfrom the hash of the prefix and suffix tree and the already\ncalculated hash of the uncompressed data. This makes hashing\nnearly as cheap as in Linus version which is important\nbecause checking whether a given file has identically\ncontent as a stored version should be fast.\n\n> >If I don't miss anything essential, you can validate\n> >each treap piece at the moment you get it from the\n> >network with its SHA1 hash and then proceed with\n> >downloading the prefix and suffix tree (in parallel\n> >if you have more than one peer a la bittorrent).\n> \n> Yes, I guess this is the detail I was going to abandon. =)\n> \n> I viewed the fact that the top-level hash was dependent on the exact chunk \n> makeup a 'misfeature', because it doesn't allow easy interoperability with \n> existing non-chunked repos.\n\nI thought this as a misfeature too before I realized how\nmany advantages this has.\n\nMartin\n \n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"995","messageId":"1cddf4cc05042009101b151139@mail.gmail.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"David Willmore","fromEmail":"davidwillmore@gmail.com","sentAt":"2005-04-20T16:10:19Z","receivedAt":"2005-04-20T16:10:19Z","isPatch":true,"sender":{"key":"davidwillmore@gmail.com","avatar":null},"body":"On 4/20/05, Linus Torvalds wrote:\n> It really _shouldn't_ be faster. It still does the compression, and throws\n> the end result away.\n\nAm I misunderstanding or is the proglem that doing:\n -> compress -> sha1 -> compare with existing hash\n\nis expensive?\n\nWhat about doing:\n -> uncompress -> compare with\nunknown status file\n\nIt's more file I/O, but the uncompress is much cheaper than the compress.\n\nOn a second issue, what's the format of the main 'index' file? Is it:\n \n \n?\nIf so, that's not going to compress well. A file like:\n\n\n\n\n\n\nWill compress better.\n\nStop me if I'm way off base--I'm just following the mailing list, I\nhaven't tried out the code.\n\nCheers,\nDavid\n"},{"id":"996","messageId":"Pine.LNX.4.58.0504200910000.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.61.0504201147280.2630@cag.csail.mit.edu","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T16:21:08Z","receivedAt":"2005-04-20T16:21:08Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, C. Scott Ananian wrote:\n> \n> OK, sure. But how 'bout chunking trees? Are you grown happy with the new \n> trees-reference-other-trees paradigm, or is there a deep longing in your \n> heart for the simplicity of 'trees-reference-blobs-period'?\n\nI'm pretty sure we do better chunking on a subdirectory basis, especially \nas it allows us to do various optimizations (avoid diffing common parts).\n\nYes, you could try to do the same optimizations with chunking, but then \nyou'd need to make sure that the chunking was always on a full tree entry \nboundary etc - ie much harder than blob chunking. \n\nBut hey, numbers talk, bullshit walks. \n\n\t\tLinus\n"},{"id":"997","messageId":"Pine.LNX.4.58.0504200931020.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T16:33:27Z","receivedAt":"2005-04-20T16:33:27Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Linus Torvalds wrote:\n> \n> To actually go faster, it _should_ need this patch. Untested. See if it \n> works..\n\nNO! Don't see if this works. For the \"sha1 file already exists\" file, it \nforgot to return the SHA1 value in \"returnsha1\", and would thus corrupt \nthe trees it wrote.\n\nSo don't apply, don't test. You won't corrupt your archive (you'll just\nwrite bogus tree objects), but if you commit the bogus trees you're going\nto be in a world of hurt and will have to undo everything you did.\n\nIt's a good test for \"fsck\" though. It core-dumps because it tries to add \nreferences to NULL objects.\n\n\t\tLinus\n"},{"id":"998","messageId":"20050420163342.GA14434@macavity","threadId":"142","inReplyTo":"20050420155734.GA13575@macavity","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-20T16:33:42Z","receivedAt":"2005-04-20T16:33:42Z","isPatch":true,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Wed, Apr 20, 2005 at 05:57:34PM +0200, Martin Uecker wrote:\n> On Wed, Apr 20, 2005 at 11:28:20AM -0400, C. Scott Ananian wrote:\n> \n> > Yes, I guess this is the detail I was going to abandon. =)\n> > \n> > I viewed the fact that the top-level hash was dependent on the exact chunk \n> > makeup a 'misfeature', because it doesn't allow easy interoperability with \n> > existing non-chunked repos.\n> \n> I thought this as a misfeature too before I realized how\n> many advantages this has.\n\nTo make it more clear: Ofcourse it is a bug if the\nhash depends on unimportant implementation details.\n\nBut a hash which is calculated recusively from\nsubhashes is a lot more usefull than a hash\nwhich can only be calculated from the entire data\nat once. And if this hash can be recalculated\ncheaply from subhashes even if some data was\ninserted somewhere this is an even more usefull\nthing.\n\nMartin\n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"999","messageId":"200504201237.38374.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-20T16:37:37Z","receivedAt":"2005-04-20T16:37:37Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 20 April 2005 11:40, Linus Torvalds wrote:\n> On Wed, 20 Apr 2005, Chris Mason wrote:\n> > Thanks for looking at this. Your new tree is faster, it gets the commit\n> > 100 patches time down from 1m5s to 50s.\n>\n> It really _shouldn't_ be faster. It still does the compression, and throws\n> the end result away.\n\nWell, that's a little odd. I had thought about making sure you did this \nchange and forgotten. 1 minute benchmarks are a horrible idea since they run \ninto noise with cache writebacks. I should know better...\n\nAt any rate, the time for a single write-tree is pretty consistent. Before it \nwas around .5 seconds, and with this change it goes down to .128s. My patch \nwas .024.\n\nThe 100 patch time is down to 32s (3 run average). This is close enough that \nI don't think my patch is worth it if no other part of git can benefit from \nhaving trees in the index.\n\n>\n> To actually go faster, it _should_ need this patch. Untested. See if it\n> works..\n\nThanks. This one missed the filling in the returnsha1. New patch attached.\n\n-chris\n\n\ndiff -u linus.back/sha1_file.c linus/sha1_file.c\n--- linus.back/sha1_file.c\t2005-04-20 12:31:00.240181016 -0400\n+++ linus/sha1_file.c\t2005-04-20 12:13:56.339837528 -0400\n@@ -173,12 +173,27 @@\n \tz_stream stream;\n \tunsigned char sha1[20];\n \tSHA_CTX c;\n+\tchar *filename;\n+\tint fd;\n \n \t/* Sha1.. */\n \tSHA1_Init(&c);\n \tSHA1_Update(&c, buf, len);\n \tSHA1_Final(sha1, &c);\n \n+\tfilename = sha1_file_name(sha1);\n+\tfd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0) {\n+\t\tif (errno != EEXIST)\n+\t\t\treturn -1;\n+\n+\t\t/*\n+\t\t * We might do collision checking here, but we'd need to\n+\t\t * uncompress the old file and check it. Later.\n+\t\t */\n+\t\tgoto out;\n+\t}\n+\n \t/* Set it up */\n \tmemset(&stream, 0, sizeof(stream));\n \tdeflateInit(&stream, Z_BEST_COMPRESSION);\n@@ -195,8 +210,10 @@\n \tdeflateEnd(&stream);\n \tsize = stream.total_out;\n \n-\tif (write_sha1_buffer(sha1, compressed, size) < 0)\n-\t\treturn -1;\n+\tif (write(fd, compressed, size) != size)\n+\t\tdie(\"unable to write file\");\n+\tclose(fd);\n+out:\t\t\n \tif (returnsha1)\n \t\tmemcpy(returnsha1, sha1, 20);\n \treturn 0;\n"},{"id":"1000","messageId":"Pine.LNX.4.58.0504200939290.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200931020.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T16:41:16Z","receivedAt":"2005-04-20T16:41:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Linus Torvalds wrote:\n> \n> NO! Don't see if this works. For the \"sha1 file already exists\" file, it \n> forgot to return the SHA1 value in \"returnsha1\", and would thus corrupt \n> the trees it wrote.\n\nProper version with fixes checked in. For me, it brings down the time to\nwrite a kernel tree from 0.34s to 0.24s, so a third of the time was just\ncompressing objects that we ended up already having.\n\nTwo thirds to go ;)\n\n\t\tLinus\n"},{"id":"1002","messageId":"Pine.LNX.4.58.0504200957030.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"200504201237.38374.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T17:06:15Z","receivedAt":"2005-04-20T17:06:15Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Chris Mason wrote:\n> \n> At any rate, the time for a single write-tree is pretty consistent. Before it \n> was around .5 seconds, and with this change it goes down to .128s.\n\nOh, wow.\n\nI bet your SHA1 implementation is done with hand-optimized and scheduled\nx86 MMX code or something, while my poor G5 is probably using some slow\ngeneric routine. As a result, it only improved by 33% for me since the\ncompression was just part of the picture, but with your cheap SHA1 the\ncompression costs really dominated, and so it's almost four times faster\nfor you.\n\nAnyway, that's good. It definitely means that I consider tree writing to \nbe \"fast enough\". You can commit patches in a third of a second on your \nmachine.\n\nI'll consider the problem solved for now. Yeah, I realize that it still \ntakes you half a minute to commit the 100 quilt patches, but I just can't \nbring myself to think it's a huge problem in the kind of usage patterns I \nthink are realistic.\n\nIf somebody really wants to replace quilt with git, he'd need to spend\nsome effort on it. If you just want to work together reasonably well, I\nthink 3 patches per second is pretty much there.\n\n\t\t\tLinus\n"},{"id":"1010","messageId":"200504201323.05447.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200957030.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-20T17:23:04Z","receivedAt":"2005-04-20T17:23:04Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 20 April 2005 13:06, Linus Torvalds wrote:\n> On Wed, 20 Apr 2005, Chris Mason wrote:\n> > At any rate, the time for a single write-tree is pretty consistent. \n> > Before it was around .5 seconds, and with this change it goes down to\n> > .128s.\n>\n> Oh, wow.\n>\n> I bet your SHA1 implementation is done with hand-optimized and scheduled\n> x86 MMX code or something, while my poor G5 is probably using some slow\n> generic routine. As a result, it only improved by 33% for me since the\n> compression was just part of the picture, but with your cheap SHA1 the\n> compression costs really dominated, and so it's almost four times faster\n> for you.\n\nAha, I was wondering why your write-tree speeds sounded so bad...this athlon \nmachine is ~2years old now.\n\nYour comments about costs for writing the index file got me thinking, so I \nbenchmarked how long the update-cache takes if we don't do the sha1 of the \nindex file. There was almost no difference at all. update-cache currently \ntakes about .152 seconds\n\nThe code to write the cache calls write() for every cache entry, writing just \na few bytes at a time. I changed it to collect these into a 16k buffer, \nwhich brings me down to .044s. This might not help as much on ext23, since \nthey are faster than reiser for tiny writes.\n\nThe patch below with your current tree brings my 100 patch test down to 22 \nseconds again.\n\n-chris\n\n\n--- linus.back/read-cache.c\t2005-04-20 10:14:23.268310000 -0400\n+++ linus/read-cache.c\t2005-04-20 13:05:13.200083672 -0400\n@@ -232,11 +232,12 @@\n \tSHA_CTX c;\n \tstruct cache_header hdr;\n \tint i;\n+\tchar *buf;\n+\tint len = 0;\n \n \thdr.hdr_signature = htonl(CACHE_SIGNATURE);\n \thdr.hdr_version = htonl(1);\n \thdr.hdr_entries = htonl(entries);\n-\n \tSHA1_Init(&c);\n \tSHA1_Update(&c, &hdr, offsetof(struct cache_header, sha1));\n \tfor (i = 0; i < entries; i++) {\n@@ -246,13 +247,31 @@\n \t}\n \tSHA1_Final(hdr.sha1, &c);\n \n+\tbuf = malloc(16384);\n+\tif (!buf) {\n+\t\treturn -1;\n+\t}\n \tif (write(newfd, &hdr, sizeof(hdr)) != sizeof(hdr))\n \t\treturn -1;\n \n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n \t\tint size = ce_size(ce);\n-\t\tif (write(newfd, ce, size) != size)\n+\t\tif (size > 16384) {\n+\t\t\tif (write(newfd, ce, size) != size)\n+\t\t\t\treturn -1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (len + size > 16384) {\n+\t\t\tif (write(newfd, buf, len) != len)\n+\t\t\t\treturn -1;\n+\t\t\tlen = 0;\n+\t\t}\n+\t\tmemcpy(buf + len, ce, size);\n+\t\tlen += size;\n+\t}\n+\tif (len) {\n+\t\tif (write(newfd, buf, len) != len)\n \t\t\treturn -1;\n \t}\n \treturn 0;\n"},{"id":"1011","messageId":"Pine.LNX.4.61.0504201325550.2630@cag.csail.mit.edu","threadId":"142","inReplyTo":"Pine.LNX.4.61.0504200917070.28851@cag.csail.mit.edu","subject":"Blob chunking code. [Second look]","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-20T17:31:07Z","receivedAt":"2005-04-20T17:31:07Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"Here's a quick rev of the chunking code. This is compatible with \ngit-current, where the hashes are of the *uncompressed* file.\nThe 'chunk' file gets dropped in at the same SHA1 filename as the\n'blob' file, as it represents identical contents. Martin won't like\nthis (because of how the hash is computed), but this is the short-term\ndirection I want to pursue to validate the concept: it means I can\nrun a simple converter over all the blob objects and don't have to\nrewrite tree and commit objects.\n\nIf the approach is seen to have merit, then we can perhaps think about \ndoing another bulk repository format conversion where all the hashes\nchange. But (IMO) it's a little early to be thinking of this yet.\n --scott\n\nnuclear RUCKUS KUPALM ODACID LA STANDEL Mossad LITEMPO atomic mail drop \nHussein JUBILIST class struggle SSBN 731 Bush quiche Nazi MKULTRA\n ( http://cscott.net/ )\n--------- chunk.c ----------\n/*\n * This file implements a treap-based chunked content store. The\n * idea is that every stored file is broken down into tree-structured\n * chunks (that is, every chunk has an optional 'prefix' and 'suffix'\n * chunk), and these chunks are put in the object store. This way\n * similar files will be expected to share chunks, saving space.\n * Files less than one disk block long are expected to fit in a single\n * chunk, so there is no extra indirection overhead for this case.\n *\n * Copyright (C) 2005 C. Scott Ananian \n */\n\n/*\n * We assume that the file and the chunk information all fits in memory.\n * A slightly more-clever implementation would work even if the file\n * didn't fit. Basically, we could scan it an keep the\n * 'N' lowest heap keys (chunk hashes), where 'N' is chosen to fit\n * comfortably in memory. These would form the root and top\n * of the resulting treap, constructing it top-down. Then we'd scan\n * again any only keep the next 'N' lowest heap keys, etc.\n *\n * But we're going to keep things simple. We do try to maintain locality\n * where possible, so if you need to swap things still shouldn't be too bad.\n */\n\n#include \n#include \n#include \"cache.h\"\n#include \"chunk.h\"\n\ntypedef unsigned long ch_size_t;\n\n/* Our magic numbers: these can be tuned without breaking files already\n * in the archive, although space re-use is only expected between files which\n * have these constants set to the same values. */\n\n/* The window size determines how much context we use when looking for a\n * chunk boundary.\n * C source has approx 5 bits per character of entropy.\n * We'd like to get 32 bits of good entropy into our boundary checksum;\n * that means 7 bytes is a rough minimum for the window size.\n * 30 bytes is what 'rsyncable zlib' uses; that should be fine. */\n#define ROLLING_WINDOW 30\n/* The ideal chunk size will fit most chunks into a disk block. A typical\n * disk block size is 4k, and we expect (say) 50% compression. */\n#define CHUNK_SIZE 7901 /* primes are nice to use */\n\n/* Data structures: */\nstruct chunk {\n /* a chunk represents some range of the underlying file */\n ch_size_t start /* inclusive */, end /*exclusive*/;\n unsigned char sha1[20]; /* sha1 for this chunk; used as the heap key */\n};\nstruct chunklist {\n /* a dynamically-sized list of chunks */\n struct chunk *chunk; /* an array of chunks */\n ch_size_t num_items; /* how many items are currently in the list */\n ch_size_t allocd; /* how many items we've allocated space for */\n};\nstruct treap {\n /* A treap node represents a run of consecutive chunks. */\n\n /* the start and end of the run: */\n ch_size_t start /* inclusive */, end /*exclusive*/;\n struct chunk *chunk; /* some chunk in the run. */\n /* treaps representing the run before 'chunk' (left) and\n * after 'chunk' (right). */\n struct treap *left, *right;\n /* sha1 for the run represented by this treap */\n unsigned char sha1[20];\n};\n\nstatic struct chunklist *\ncreate_chunklist(int expected_items) {\n struct chunklist *cl = malloc(sizeof(*cl));\n cl->num_items = 0;\n cl->allocd = expected_items;\n cl->chunk = malloc(sizeof(cl->chunk[0]) * cl->allocd);\n return cl;\n}\nstatic void\nfree_chunklist(struct chunklist *cl) {\n free(cl->chunk);\n free(cl);\n}\n\n/* Add a chunk to the chunk list, calculating its SHA1 in the process. */\n/* The chunk includes buf[start] to buf[end-1]. */\nstatic void\nadd_chunk(struct chunklist *cl, char *buf, ch_size_t start, ch_size_t end) {\n struct chunk *ch;\n SHA_CTX c;\n assert(startnum_items >= cl->allocd) {\n \tcl->allocd = cl->allocd*3/2;\n \tcl->chunk = realloc(cl->chunk, cl->allocd * sizeof(*(cl->chunk)));\n }\n assert(cl->num_items < cl->allocd);\n ch = cl->chunk + (cl->num_items++);\n ch->start = start;\n ch->end = end;\n /* compute SHA-1 of the chunk. */\n SHA1_Init(&c);\n SHA1_Update(&c, buf+start, end-start);\n SHA1_Final(ch->sha1, &c);\n /* done! */\n}\n\n/* Split a buffer into chunks, using a rolling checksum over ROLLING_WINDOW\n * bytes to determine chunk boundaries. We try to split chunks into pieces\n * whose size averages out to be 'CHUNK_SIZE'. */\nstatic void\nchunkify(struct chunklist *cl, char *buf, ch_size_t size) {\n int i, rsync_s1=0, rsync_s2=0, last=-1;\n /* While window is filling: */\n for (i=0; isha1) as the heap key and the\n * file location (chunk->start) as the tree key.\n * For more info on treaps, see:\n * C. R. Aragon and R. G. Seidel, \"Randomized search trees\",\n * Proc. 30th IEEE FOCS (1989), 540-545.\n * There are many possible binary trees we could build; enforcing the\n * heap constraint ensures that similar files will build similar trees.\n * (The root of the constructed tree will always be the chunk with the\n * smallest hash key; it's left child will be the chunk with the smallest\n * hash among those chunk before the root in file order; and so on\n * recursively.)\n */\n\n/* Assertion helper: check tree and heap constraints. */\nstatic int\ntreap_valid(struct treap *t) {\n int valid = 1;\n if (!t) return 1;\n if (t->chunk==NULL) return 0;\n if (t->left!=NULL) {\n \t/* Tree constraint. */\n \tvalid = valid && (t->left->chunk->start < t->chunk->start);\n \t/* Heap constraint. */\n \tvalid = valid && (memcmp(t->chunk->sha1, t->left->chunk->sha1,\n \t\t\t\t sizeof(t->chunk->sha1)) < 0);\n \t/* 'start' validity */\n \tvalid = valid && (t->start == t->left->start);\n } else\n \tvalid = valid && (t->start == t->chunk->start);\n if (t->right!=NULL) {\n \t/* Tree constraint. */\n \tvalid = valid && (t->chunk->start < t->right->chunk->start);\n \t/* Heap constraint. */\n \tvalid = valid && (memcmp(t->chunk->sha1, t->right->chunk->sha1,\n \t\t\t\t sizeof(t->chunk->sha1)) < 0);\n \t/* 'end' validity. */\n \tvalid = valid && (t->end == t->right->end);\n } else\n \tvalid = valid && (t->end == t->chunk->end);\n return valid;\n}\n\n/* Restore heap constraint without disturbing tree ordering. */\n/* Only the root of the given treap will violate the heap constraint. */\nstatic struct treap *\ntreapify(struct treap *t) {\n struct treap *x, *y, *a, *b, *c;\n int left_ok, right_ok, rotate_left;\n assert(treap_valid(t->left));\n assert(treap_valid(t->right));\n left_ok = (t->left == NULL) ||\n \t(memcmp(t->chunk->sha1, t->left->chunk->sha1,\n \t\tsizeof(t->chunk->sha1)) < 0);\n right_ok = (t->right == NULL) ||\n \t(memcmp(t->chunk->sha1, t->right->chunk->sha1,\n \t\tsizeof(t->chunk->sha1)) < 0);\n if (left_ok && right_ok) { /* well, that's easy */\n \tassert(treap_valid(t));\n \treturn t;\n }\n /* okay, someone needs to rotate */\n rotate_left = (!left_ok) &&\n \t(right_ok || /* if neither is okay, then rotate smallest up */\n \t memcmp(t->left->chunk->sha1, t->right->chunk->sha1,\n \t\tsizeof(t->chunk->sha1)) < 0);\n /* Rotation:\n * y -bring left up-> x\n * / \\ / \\\n * x c a y\n * / \\ / \\\n * a b <-bring right up- b c\n */\n if (rotate_left) {\n \ty = t; x = y->left; c = y->right; a = x->left; b = x->right;\n \ty->left = b;\n \ty->right = c;\n \ty->start = y->left ? y->left->start : y->chunk->start;\n \ty->end = y->right ? y->right->end : y->chunk->end;\n \tx->left = a;\n \tx->right = treapify(y); // recurse to check heap constraint\n \tx->start = x->left ? x->left->start : x->chunk->start;\n \tx->end = x->right ? x->right->end : x->chunk->end;\n \tassert(treap_valid(x));\n \treturn x;\n } else {\n \tx = t; a = x->left; y = x->right; b = y->left; c = y->right;\n \tx->left = a;\n \tx->right = b;\n \tx->start = x->left ? x->left->start : x->chunk->start;\n \tx->end = x->right ? x->right->end : x->chunk->end;\n \ty->right = c;\n \ty->left = treapify(x); // recurse to check heap constraint.\n \ty->start = y->left ? y->left->start : y->chunk->start;\n \ty->end = y->right ? y->right->end : y->chunk->end;\n \tassert(treap_valid(y));\n \treturn y;\n }\n}\n\n/* Use list of chunks to build treap bottom-up, calling treapify to\n * restore heap order on the subtree after we add each interior node.\n * This is O(N), where N is the number of chunks. */\nstatic struct treap *\nbuild_treap(struct chunklist *cl, int chunk_st, int chunk_end) {\n struct treap *result;\n /* Some treaps are trivial to build: */\n if (chunk_st >= chunk_end) return NULL;\n /* Claim a chunk in the middle for ourself. */\n int c = (chunk_st + chunk_end)/2;\n result = (struct treap *)malloc(sizeof(*result));\n result->chunk = &(cl->chunk[c]);\n /* Divide and conquer: build well-formed treaps for our kids.*/\n result->left = build_treap(cl, chunk_st, c);\n result->right = build_treap(cl, c+1, chunk_end);\n result->start = result->left ? result->left->start : result->chunk->start;\n result->end = result->right ? result->right->end : result->chunk->end;\n /* Now we need to ensure that the heap constraint is satisfied; that is,\n * result->chunk->sha1 < result->left->chunk->sha1 and\n * result->chunk->sha1 < result->right->chunk->sha1.\n */\n assert(treap_valid(result->left));\n assert(treap_valid(result->right));\n return treapify(result);\n}\n\nstatic void\nfree_treap(struct treap *t) {\n if (!t) return;\n free_treap(t->left);\n free_treap(t->right);\n free(t);\n}\n\nstatic int\ntreap_depth(struct treap *t) {\n int l, r;\n if (!t) return 0;\n l = treap_depth(t->left);\n r = treap_depth(t->right);\n return 1 + ((l > r) ? l : r);\n}\n\n/* Fill in the treap hashes. This will be O(N ln M), where N is the\n * file length and M is the number of chunks. We could actually do\n * this in 2*N time if the subtree hashes were prefix-identical.\n * Since we need to include the chunk length in the hash prefix,\n * we can't reuse the hashing context and we need to pay the extra\n * O(ln M) factor. */\nstatic void\ndo_treap_hash(struct treap *t, void *data, SHA_CTX *accum, int accum_len) {\n char prefix[200];\n SHA_CTX *cp;\n int i;\n\n assert(treap_valid(t));\n if (!t) return;\n\n /* Start a new treap context. */\n cp = &(accum[accum_len++]);\n SHA1_Init(cp);\n /* Sticking the size in the prefix makes me unhappy. =( */\n SHA1_Update(cp, prefix, 1+sprintf(prefix, \"blob %lu\", t->end - t->start));\n /* Recurse on the left. */\n do_treap_hash(t->left, data, accum, accum_len);\n /* Add in our chunk. */\n for (i=0; ichunk->start,\n \t\t t->chunk->end - t->chunk->start);\n /* Recurse on the right. */\n do_treap_hash(t->right, data, accum, accum_len);\n /* Finalize and write it to t->sha1. */\n SHA1_Final(t->sha1, cp);\n /* Done! */\n}\n/* Helper method. */\nstatic void\ncompute_treap_hashes(struct treap *t, void *data) {\n /* Allocate space for each level of the treap to have its own context. */\n SHA_CTX contexts[treap_depth(t)];\n do_treap_hash(t, data, contexts, 0);\n}\n/* Yuck. */\nstatic const char *\ncompute_null_treap_hash() {\n static const char fixed[] = { \"blob 0\" };\n static char sha1[20], *cp=NULL;\n SHA_CTX c;\n if (cp) return cp;\n SHA1_Init(&c);\n SHA1_Update(&c, fixed, sizeof(fixed));\n SHA1_Final(sha1, &c);\n cp = sha1;\n return cp;\n}\n\n\n/* Now that we've broken it down into treap-structured pieces, let's write\n * them to the object store. */\n\n/* Write a single treap piece to the object store. Note that 't' may be\n * NULL for the special case of a zero-byte file. Writes the hash of\n * this piece back to 'sha1', which must be non-NULL. Returns 0 on success.*/\nstatic int\nwrite_one(struct treap *t, char *buf) {\n/* two hundred bytes is two 20-byte SHA1 hashes, two presence bytes,\n * six bytes of type, one null, and plus 10^151 file length. (Conservative.) */\n#define MAX_METADATA_LEN 200\n z_stream stream;\n ch_size_t max_out_bytes;\n ch_size_t chunk_size = t ? (t->chunk->end - t->chunk->start) : 0;\n ch_size_t content_size, metadata_size;\n char metadata[MAX_METADATA_LEN];\n void *out;\n\n /*\n * Metadata: Type, ASCII size, null byte, then left & right hashes.\n */\n content_size = chunk_size+2; /* prefix/suffix delimiters */\n if (t && t->left) content_size += sizeof(t->left->sha1);\n if (t && t->right) content_size += sizeof(t->right->sha1);\n metadata_size = 1+sprintf(metadata, \"chunk %lu\", content_size);\n if (t && t->left) { /* left hash */\n \tmetadata[metadata_size++] = 1;\n \tmemcpy(metadata + metadata_size, t->left->sha1, sizeof(t->left->sha1));\n \tmetadata_size += sizeof(t->left->sha1);\n } else\n \tmetadata[metadata_size++] = 0; /* no prefix chunk */\n if (t && t->right) { /* right hash */\n \tmetadata[metadata_size++] = 1;\n \tmemcpy(metadata + metadata_size,t->right->sha1,sizeof(t->right->sha1));\n \tmetadata_size += sizeof(t->right->sha1);\n } else\n \tmetadata[metadata_size++] = 0; /* no suffix chunk */\n\n memset(&stream, 0, sizeof(stream));\n deflateInit(&stream, Z_BEST_COMPRESSION);\n max_out_bytes = deflateBound(&stream, chunk_size+metadata_size);\n out = malloc(max_out_bytes);\n stream.next_out = out;\n stream.avail_out = max_out_bytes;\n\n /* Compress metadata. */\n stream.next_in = metadata;\n stream.avail_in = metadata_size;\n while (deflate(&stream, 0) == Z_OK)\n \t /* nothing */;\n\n /*\n * Chunk content.\n */\n stream.next_in = buf + ( t ? t->chunk->start : 0);\n stream.avail_in = chunk_size; /* possibly zero */\n while (deflate(&stream, Z_FINISH) == Z_OK)\n \t/* nothing */;\n\n deflateEnd(&stream);\n\n return write_sha1_buffer(t ? (const char*) t->sha1 :\n \t\t\t compute_null_treap_hash(),\n \t\t\t out, stream.total_out);\n}\n\n/* Write all treap nodes to disk. */\nstatic int\nwrite_treap(struct treap *t, char *buf, char *sha1) {\n /* First write children (which initializes their SHA1 info). */\n if (t && t->left)\n \tif (write_treap(t->left, buf, NULL) < 0)\n \t return -1; /* failure. */\n if (t && t->right)\n \tif (write_treap(t->right, buf, NULL) < 0)\n \t return -1; /* failure. */\n /* Now write us. Note t may == NULL for a zero-byte file. */\n if (write_one(t, buf) < 0)\n \treturn -1; /* failure. */\n /* Write back sha1, if wanted. */\n if (sha1)\n \tmemcpy(sha1, t ? (const char*)t->sha1 : compute_null_treap_hash(),\n \t sizeof(t->sha1));\n return 0;\n}\n\n/* EXPORTED FUNCTION: write the file open on file descriptor 'fd'\n * and described by 'ce' and 'st' to the object store. Return\n * 0 on success, -1 on failure. */\n/* This does the same thing as 'index_fd' in Linus' update-cache.c */\nint\nchunk_index_fd(struct cache_entry *ce, int fd, struct stat *st) {\n struct chunklist *cl;\n struct treap *t;\n char *in;\n\n /* We expect there to be 'file length / CHUNK_SIZE' chunks. Over-estimate\n * a little, and do the initial chunk list allocation. */\n cl = create_chunklist(1 + ((3 * st->st_size) / (2 * CHUNK_SIZE)));\n /* Split the file into chunks. */\n in = \"\";\n if (st->st_size)\n \tin = mmap(NULL, st->st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n close(fd);\n if (in==MAP_FAILED) return -1;\n\n chunkify(cl, in, st->st_size);\n /* Build the treap. */\n t = build_treap(cl, 0, cl->num_items);\n assert(treap_valid(t));\n /* Compute all the hashes. */\n compute_treap_hashes(t, in);\n /* Now write all the pieces, updating SHA1 for this file in the process. */\n if (write_treap(t, in, ce->sha1) < 0)\n \treturn -1;\n /* Free everything; we're done. */\n free_treap(t);\n free_chunklist(cl);\n if (st->st_size)\n \tmunmap(in, st->st_size);\n return 0; /* success! */\n}\n\n/*** Functions to read a chunked file into a contiguous buffer. ***/\n\nstruct read_chunk {\n void *data, *chunk_data;\n ch_size_t chunk_size, total_size;\n struct read_chunk *left, *right;\n};\nstatic struct read_chunk *\nread_chunk2(const unsigned char *sha1, void *data, ch_size_t size);\n\nstatic struct read_chunk *\nread_chunk(const unsigned char *sha1) {\n void *data;\n ch_size_t size;\n char type[10];\n data = read_sha1_file(sha1, type, &size);\n assert(strcmp(type, \"chunk\")==0);\n return read_chunk2(sha1, data, size); \n}\nstatic struct read_chunk *\nread_chunk2(const unsigned char *sha1, void *data, ch_size_t size) {\n unsigned char *cp;\n struct read_chunk *result = malloc(sizeof(*result));\n cp = result->data = data;\n printf(\"CHUNK %s (%lu bytes)\\n\", sha1_to_hex(sha1), size);\n /* Parse the chunk data. */\n result->left = result->right = NULL;\n if (*cp++) {\n \tresult->left = read_chunk(cp); cp+=20;\n }\n if (*cp++) {\n \tresult->right = read_chunk(cp); cp+=20;\n }\n result->chunk_data = cp;\n result->chunk_size = size - (result->chunk_data - result->data);\n result->total_size = result->chunk_size +\n \t(result->left ? result->left->total_size : 0) +\n \t(result->right ? result->right->total_size : 0);\n return result;\n}\nstatic void\ncopy_read_chunk(void *dest, struct read_chunk *rc) {\n if (rc->left) {\n \tcopy_read_chunk(dest, rc->left);\n \tdest += rc->left->total_size;\n }\n memcpy(dest, rc->chunk_data, rc->chunk_size);\n if (rc->right)\n \tcopy_read_chunk(dest + rc->chunk_size, rc->right);\n}\nstatic void\nfree_read_chunk(struct read_chunk *rc) {\n if (rc->left) free_read_chunk(rc->left);\n if (rc->right) free_read_chunk(rc->right);\n free(rc->data);\n free(rc);\n}\n\n/* This does the same thing as 'read_sha1_file' in Linus' read_cache.c,\n * except that it knows about the 'chunk' encoding and will transparently\n * stitch together the appropriate prefix and suffix chunks and pass it\n * off as a 'blob'. */\nvoid *\nchunk_read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size) {\n struct read_chunk *rc;\n void *result = read_sha1_file(sha1, type, size);\n if (strcmp(type, \"chunk\")!=0) return result;\n /* This is a 'chunk' object; get the rest of the pieces. */\n rc = read_chunk2(sha1, result, *size);\n /* Now concatenate them together. */\n strcpy(type, \"blob\");\n *size = rc->total_size;\n result = malloc(*size);\n copy_read_chunk(result, rc);\n /* done! */\n free_read_chunk(rc);\n return result;\n}\n\n#if 0\n/* Exercise this code. */\nint main(int argc, char **argv) {\n struct cache_entry ce;\n struct stat st;\n char *buf, type[10];\n unsigned long size;\n int fd;\n fd = open(argv[1], O_RDONLY);\n if (fd < 0) exit(1);\n if (fstat(fd, &st) < 0) exit(1);\n if (chunk_index_fd(&ce, fd, &st) < 0) exit(1);\n printf(\"Wrote file %s.\\n\", sha1_to_hex(ce.sha1));\n /* seemed to work! */\n buf = chunk_read_sha1_file(ce.sha1, type, &size);\n if (!buf) exit(1);\n printf(\"Read file %s, of type %s (%lu bytes):\\n\",\n \t sha1_to_hex(ce.sha1), type, size);\n fwrite(buf, size, 1, stdout);\n /* done! */\n return 0;\n}\n#endif\n"},{"id":"1013","messageId":"Pine.LNX.4.58.0504201040400.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"200504201323.05447.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T17:52:17Z","receivedAt":"2005-04-20T17:52:17Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Chris Mason wrote:\n> \n> The patch below with your current tree brings my 100 patch test down to 22 \n> seconds again.\n\nIf you ever have a cache_entry bigger than 16384, your code will write \nthings out in the wrong order (write the new cache without flushing the \nold buffer).\n\nYou also don't free the buffer.\n\nFinally, if you really want to go fast, you should really try to make your\nwrites powers-of-two, ie fill up the buffer entirely rather than saying\n\"if I were to overflow, flush it now\". It doesn't matter that much for\nsome filesystems (especially local and append-only like the patterns are\nhere), but it can definitely matter for the stupid ones.\n\nBut yeah, we could obviously chunk things out properly. You might want to \njust use stdio and \"fwrite()\", though, which does all of that for you, and \nhopefully does it right.\n\n(I'm not a big fan of stdio for something like this, so if you want to \ncreate a little helper function that just does the chunking, go wild. \nSomething like\n\n\t#define BUFSIZ 8192\n\tstatic char buffer[BUFSIZ];\n\tstatic unsigned long buflen;\n\n\tint ce_write(int fd, void *data, unsigned int len)\n\t{\n\t\twhile (len) {\n\t\t\tunsigned int buffered = buflen;\n\t\t\tunsigned int partial = BUFSIZ - buflen;\n\t\t\tif (partial > len)\n\t\t\t\tpartial = len;\n\t\t\tmemcpy(buffer + buflen, data, partial);\n\t\t\tbuffered += partial;\n\t\t\tif (buffered == BUFSIZ) {\n\t\t\t\tif (write(fd, buffer, BUFSIZ) != BUFSIZ)\n\t\t\t\t\tdie(\"unable to write\");\n\t\t\t\tbuffered = 0;\n\t\t\t}\n\t\t\tbuflen = buffered;\n\t\t\tlen -= partial;\n\t\t\tdata += partial;\n\t\t}\n\t}\n\n\tint ce_flush(int fd)\n\t{\n\t\tunsigned int left = buflen;\n\t\tif (left) {\n\t\t\tbuflen = 0;\n\t\t\tif (write(fd, buffer, left) != left)\n\t\t\t\tdie(\"unable to write\");\n\t\t}\n\t}\n\nwhich should be ok, and cheesily avoids the allocation overhread issues by\njust having a nice static buffer.\n\n\"If you want to go fast, do it right\".\n\nUntested, as usual.\n\n\t\tLinus\n"},{"id":"1015","messageId":"20050420110720.0ff887b4.davem@davemloft.net","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200957030.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"David S. Miller","fromEmail":"davem@davemloft.net","sentAt":"2005-04-20T18:07:20Z","receivedAt":"2005-04-20T18:07:20Z","isPatch":true,"sender":{"key":"davem@davemloft.net","avatar":null},"body":"On Wed, 20 Apr 2005 10:06:15 -0700 (PDT)\nLinus Torvalds wrote:\n\n> I bet your SHA1 implementation is done with hand-optimized and scheduled\n> x86 MMX code or something, while my poor G5 is probably using some slow\n> generic routine. As a result, it only improved by 33% for me since the\n> compression was just part of the picture, but with your cheap SHA1 the\n> compression costs really dominated, and so it's almost four times faster\n> for you.\n\nThe openssl tree has a i586 optimized SHA1 implementation.\nA quick scan of the 0.9.7e tree I happen to have lying around\nshows there aren't optimized for other cpus in there, just i586.\n"},{"id":"1017","messageId":"200504201504.59541.mason@suse.com","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504201040400.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-20T19:04:58Z","receivedAt":"2005-04-20T19:04:58Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 20 April 2005 13:52, Linus Torvalds wrote:\n> On Wed, 20 Apr 2005, Chris Mason wrote:\n> > The patch below with your current tree brings my 100 patch test down to\n> > 22 seconds again.\n>\n> If you ever have a cache_entry bigger than 16384, your code will write\n> things out in the wrong order (write the new cache without flushing the\n> old buffer).\n\nWhoops\n\n> Finally, if you really want to go fast, you should really try to make your\n> writes powers-of-two, ie fill up the buffer entirely rather than saying\n> \"if I were to overflow, flush it now\". It doesn't matter that much for\n> some filesystems (especially local and append-only like the patterns are\n> here), but it can definitely matter for the stupid ones.\n\nWell, the difference there should be pretty hard to see with any benchmark.\nBut I was being lazy...new patch attached. This one gets the same perf \nnumbers, if this is still wrong then I really need some more coffee.\n\n-chris\n\n\n\n--- linus.back/read-cache.c\t2005-04-20 10:14:23.268310000 -0400\n+++ linus/read-cache.c\t2005-04-20 14:54:28.554518320 -0400\n@@ -232,11 +232,13 @@\n \tSHA_CTX c;\n \tstruct cache_header hdr;\n \tint i;\n+\t#define BUFLEN 16384\n+\tstatic char buf[BUFLEN];\n+\tint len = 0;\n \n \thdr.hdr_signature = htonl(CACHE_SIGNATURE);\n \thdr.hdr_version = htonl(1);\n \thdr.hdr_entries = htonl(entries);\n-\n \tSHA1_Init(&c);\n \tSHA1_Update(&c, &hdr, offsetof(struct cache_header, sha1));\n \tfor (i = 0; i < entries; i++) {\n@@ -246,13 +248,37 @@\n \t}\n \tSHA1_Final(hdr.sha1, &c);\n \n-\tif (write(newfd, &hdr, sizeof(hdr)) != sizeof(hdr))\n-\t\treturn -1;\n-\n+\t/* hdr is small right now, but just\n+\t * in case someone changes that...\n+\t */\n+\tif (sizeof(hdr) < BUFLEN) {\n+\t\tmemcpy(buf, &hdr, sizeof(hdr));\n+\t\tlen += sizeof(hdr);\n+\t} else {\n+\t\tif (write(newfd, &hdr, sizeof(hdr)) != sizeof(hdr))\n+\t\t\treturn -1;\n+\t}\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n \t\tint size = ce_size(ce);\n-\t\tif (write(newfd, ce, size) != size)\n+\t\tchar *p = (char *)ce;\n+\t\twhile(size > 0) {\n+\t\t\tint count = size;\n+\t\t\tif (count > BUFLEN - len)\n+\t\t\t\tcount = BUFLEN - len;\n+\t\t\tmemcpy(buf + len, p, count);\n+\t\t\tsize -= count;\n+\t\t\tlen += count;\n+\t\t\tp += count;\n+\t\t\tif (len == BUFLEN) {\n+\t\t\t\tif (write(newfd, buf, len) != len)\n+\t\t\t\t\treturn -1;\n+\t\t\t\tlen = 0;\n+\t\t\t}\n+\t\t}\n+\t}\n+\tif (len) {\n+\t\tif (write(newfd, buf, len) != len)\n \t\t\treturn -1;\n \t}\n \treturn 0;\n"},{"id":"1018","messageId":"Pine.LNX.4.58.0504201218360.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"200504201504.59541.mason@suse.com","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T19:19:53Z","receivedAt":"2005-04-20T19:19:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Chris Mason wrote:\n> \n> Well, the difference there should be pretty hard to see with any benchmark.\n> But I was being lazy...new patch attached. This one gets the same perf \n> numbers, if this is still wrong then I really need some more coffee.\n\nI did my preferred version. Makes a big difference here too.\n\nIt would be nicer for the cache to make the index file \"header\" be a \n\"footer\", and write it out last - that way we'd be able to do the SHA1 as \nwe write rather than doing a two-pass thing. That's for another time.\n\n\t\tLinus\n"},{"id":"1019","messageId":"Pine.LNX.4.58.0504201237340.6467@ppc970.osdl.org","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504201218360.6467@ppc970.osdl.org","subject":"Re: [PATCH] write-tree performance problems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-20T19:47:59Z","receivedAt":"2005-04-20T19:47:59Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 20 Apr 2005, Linus Torvalds wrote:\n>\n> It would be nicer for the cache to make the index file \"header\" be a \n> \"footer\", and write it out last - that way we'd be able to do the SHA1 as \n> we write rather than doing a two-pass thing. That's for another time.\n\nThat other time was now.\n\nThe header is still a header, but the sha1 is now at the end of the file, \nwhich means that the header version has been incremented by 1 (to 2).\n\nThis is also sadly an incompatible change, so once you update and install\nthe new tools, you'll need to do\n\n\ttree=$(cat-file commit $(cat .git/HEAD) | sed 's/tree //;q')\n\tread-tree $tree\n\tupdate-cache --refresh\n\nto re-build your index file.\n\nSorry about that, but the end result should be quite fast (especially if\nyour sha1 is fast). The best benchmark is probably to just do a \"time\nupdate-cache Makefile\" in the kernel (before and after), when the cache\nwas already up-to-date and with no time spent on stating lots of files. \nThat kind of \"one file changed\" timing is actually the common case (in\nthis case Makefile won't have changed, but update-cache doesn't care).\n\n(Of course, I could optimize it to notice that the update-cache didn't do\nanything and avoid the write altogether, but that's likely optimizing for\nthe wrong case, since normally you'd call update-cache when you know\nsomething changed).\n\nYeah, it's somewhat silly doing optimizations at this point, but I want to\nmake sure that the data structures are all ready for a real release, and\nas part of that I want to make sure there are no stupid low-hanging fruit\nthat we'll curse later. Better get it done with now.\n\n\t\t\tLinus\n"},{"id":"1047","messageId":"1114036196.5877.70.camel@localhost.localdomain","threadId":"142","inReplyTo":"Pine.LNX.4.58.0504200731590.6467@ppc970.osdl.org","subject":"Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)","fromName":"David Woodhouse","fromEmail":"dwmw2@infradead.org","sentAt":"2005-04-20T22:29:54Z","receivedAt":"2005-04-20T22:29:54Z","isPatch":true,"sender":{"key":"dwmw2@infradead.org","avatar":"https://gravatar.com/avatar/7afd4f07e0cf7d7e046ae2d23678296b37777c96488e6f3451e78a5514154ebd?d=mp&s=160"},"body":"On Wed, 2005-04-20 at 07:59 -0700, Linus Torvalds wrote:\n> external-parent \n> comment for this parent\n> \n> and the nice thing about that is that now that information allows you to \n> add external parents at any point. \n> \n> Why do it like this? First off, I think that the \"initial import\" ends up\n> being just one special case of the much more _generic_ issue of having\n> patches come in from other source control systems \n\nThis isn't about patches coming in from other systems -- it's about\n_history_, and the fact that it's imported from another system is just\nan implementation detail. It's git history now, and what we have here is\njust a special case of wanting to prune ancient git history to keep the\nsize of our working trees down. You refer to this yourself...\n\n> Secondly, we do need something like this for pruning off history anyway, \n> so that the tools have a better way of saying \"history has been pruned \n> off\" than just hitting a missing commit. \n\nHaving a more explicit way of saying \"history is pruned\" than just a\nreference to a missing commit is a reasonable request -- but I really\ndon't see how we can do that by changing the now-oldest commit object to\ncontain an 'external-parent' field. Doing that would change the sha1 of\nthe commit object in question, and then ripple through all the\nsubsequent commits.\n\nCome this time next year, if I decide I want to prune anything older\nthan 2.6.40 from all the trees on my laptop, it has to happen _without_\nchanging the commit objects which occur after my arbitrarily-chosen\ncutoff point.\n\nIf we want to have an explicit record of pruning rather than just\ncopying with a missing object, then I think we'd need to do it with an\nexternal note to say \"It's OK that commit XXXXXXXXXXX is missing\".\n\n> Thirdly, I don't actually want my new tree to depend on a conversion of\n> the old BK tree.\n> \n> Two reasons: if it's a really full conversion, there are definitely going\n> to be issues with BitMover. They do not want people to try to reverse\n> engineer how they do namespace merges\n\nDon't think of it as \"a conversion of the old BK tree\". It's just an\nimport of Linux's development history. This isn't going to help\nreverse-engineer how BK does merges; it's just our own revision history.\nI'm not sure exactly how Thomas is extracting it, but AIUI it's all\nobtainable from the SCCS files anyway without actually resorting to\nusing BK itself. \n\nThere's nothing here for Larry to worry about. It's not as if we're\nactually using BK to develop git by observing BK's behaviour w.r.t\nmerges and trying to emulate it. Besides -- if we wanted to do that,\nwe'd need to use the _BK_ version of the tree; the git version wouldn't\nhelp us much anyway.\n\nAnd given that BK's merges are based on individual files and we're not\ngoing that route with git, it's not clear how much we could lift\ndirectly from BK even if we _were_ going to try that.\n\n> The other reason is just the really obvious one: in the last week, I've\n> already changed the format _twice_ in ways that change the hash. As long\n> as it's 119MB of data, it's not going to be too nasty to do again.\n\nThat's fine. But by the time we settle on a format and actually start\nusing it in anger, it'd be good to be sure that it _is_ possible to\ntrack development from current trees all the way back -- be that with\nexplicit reference to pruned history as you suggest, or with absent\nparents as I still prefer.\n\n> it's not that it's necessarily the wrong thing to do, but I think it\n> is the wrogn thing to do _now_.\n\nOK, time for us to keep arguing over the implementation details of how\nwe prune history then :)\n\n-- \ndwmw2\n\n"}]}