{"thread":{"id":"4475","subject":"svn to git, N-squared?","startedAt":"2006-06-12T02:02:18Z","lastAt":"2006-06-12T19:17:37Z","messageCount":9,"participants":["Jon Smirl","Linus Torvalds","Eric Wong","Randal L. Schwartz","Yakov Lerner"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"21621","messageId":"9e4733910606111902l709c71ccyf45070d55112739e@mail.gmail.com","threadId":"4475","inReplyTo":null,"subject":"svn to git, N-squared?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-06-12T02:02:18Z","receivedAt":"2006-06-12T02:02:18Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I have Mozilla CVS in a SVN repository. I've been using git-svnimport\nto import it. This time I am letting it run to completion; but the\nimport has been running for four days now and it is only up to 2004.\nThe import task is stable at 570MB and it is using about 50% of my\nCPU. It is constantly spawning off git write-tree, read-tree,\nhash-object, update-index. It is not doing excessive disk activity.\n\nThe import seems to be getting n-squared slower. It is still making\nforward progress but the progress seems to be getting slower and\nslower.\n\nIt looks like it is doing write-tree, read-tree, hash-object,\nupdate-index once or more per change set. If these commands are\nn-proportional and they are getting run n times, then this is a\nn-squared process. Projecting this out, the import may take 10 days or\nmore to completely finish.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"21624","messageId":"Pine.LNX.4.64.0606112028010.5498@g5.osdl.org","threadId":"4475","inReplyTo":"9e4733910606111902l709c71ccyf45070d55112739e@mail.gmail.com","subject":"Re: svn to git, N-squared?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-12T03:31:26Z","receivedAt":"2006-06-12T03:31:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 11 Jun 2006, Jon Smirl wrote:\n>\n> I have Mozilla CVS in a SVN repository. I've been using git-svnimport\n> to import it. This time I am letting it run to completion; but the\n> import has been running for four days now and it is only up to 2004.\n> The import task is stable at 570MB and it is using about 50% of my\n> CPU. It is constantly spawning off git write-tree, read-tree,\n> hash-object, update-index. It is not doing excessive disk activity.\n\nThis sounds like _exactly_ what happens if you don't repack occasionally. \nExpecially if you are using a filesystem without hashed filename lookup, \nbut it's true to some degree even with that - the filesystem tends to end \nup spending tons of time in kernel space, trying to find a place to put \nnew objects.\n\nI don't think git-svnimport has the repack logic in it, so that would be \nit.\n\nYou can probably stop it with ^Z, do a \"git repack -a -d\", and then let it \ncontinue.\n\n(The only reason for stopping it is actually to let \"git repack\" remove \nmost of the object directories - many filesystems, including ext3, don't \neven speed up all that much if the directories are emptied after they've \ngrown big, and it's much better if the object directories get totally \nremoved and re-created)\n\n\t\t\tLinus\n"},{"id":"21625","messageId":"9e4733910606112039p7aff60c7w7a074d0e35c7b0f@mail.gmail.com","threadId":"4475","inReplyTo":"Pine.LNX.4.64.0606112028010.5498@g5.osdl.org","subject":"Re: svn to git, N-squared?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-06-12T03:39:08Z","receivedAt":"2006-06-12T03:39:08Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 6/11/06, Linus Torvalds <torvalds@osdl.org> wrote:\n>\n>\n> On Sun, 11 Jun 2006, Jon Smirl wrote:\n> >\n> > I have Mozilla CVS in a SVN repository. I've been using git-svnimport\n> > to import it. This time I am letting it run to completion; but the\n> > import has been running for four days now and it is only up to 2004.\n> > The import task is stable at 570MB and it is using about 50% of my\n> > CPU. It is constantly spawning off git write-tree, read-tree,\n> > hash-object, update-index. It is not doing excessive disk activity.\n>\n> This sounds like _exactly_ what happens if you don't repack occasionally.\n> Expecially if you are using a filesystem without hashed filename lookup,\n> but it's true to some degree even with that - the filesystem tends to end\n> up spending tons of time in kernel space, trying to find a place to put\n> new objects.\n>\n> I don't think git-svnimport has the repack logic in it, so that would be\n> it.\n>\n> You can probably stop it with ^Z, do a \"git repack -a -d\", and then let it\n> continue.\n\nI have it stopped and I am running the repack.\nThere are 1.27M files in my .git directory\n\nI ordered 2GB more RAM which should be here Tuesday.\n\n> (The only reason for stopping it is actually to let \"git repack\" remove\n> most of the object directories - many filesystems, including ext3, don't\n> even speed up all that much if the directories are emptied after they've\n> grown big, and it's much better if the object directories get totally\n> removed and re-created)\n>\n>                         Linus\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"21628","messageId":"Pine.LNX.4.64.0606112056440.5498@g5.osdl.org","threadId":"4475","inReplyTo":"9e4733910606112039p7aff60c7w7a074d0e35c7b0f@mail.gmail.com","subject":"Re: svn to git, N-squared?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-12T04:02:44Z","receivedAt":"2006-06-12T04:02:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 11 Jun 2006, Jon Smirl wrote:\n> \n> I have it stopped and I am running the repack.\n> There are 1.27M files in my .git directory\n\nYeah, that would do it. That's ~5000 files per object directory, so I \nassume that your directories are 200+kB in size, and for every new object \nadded, you'll basically have to traverse the old directory fully in order \nto find an empty place for it (and without hashing, you'll traverse it \n_twice_ - first to look for it, then to look for the empty space).\n\nBtw, after repacking, if it still has lots of lose objects, and you still \nhave several directories that are huge (because there are pending objects \nfor a commit that didn't happen yet when you ^Z'd the svnimport), you'll \nliterally get better performance if you do something like\n\n\tfor i in ??\n\tdo\n\t\tcp -r $i $i.new\n\t\trm -rf $i\n\t\tmv $i.new $i\n\tdone\n\nin your .git/objects/ directory (CAREFUL! Any script that does \"rm -rf\" \nshould be double- and triple-checked for sanity! ;)\n\nThat should make sure that you don't still have huge directories.\n\n(And yes, this is a real problem at least with ext3).\n\nThe git cvsimporter ends up repacking the archive every thousand commits. \nThat's just a random number, but it's indicative of what we did there to \nhandle large imports. I don't think anybody has done a large import using \nthe git-svnimport before, so you're in new territory which explains some \nof the teething problems.\n\n\t\tLinus\n"},{"id":"21629","messageId":"20060612042934.GA12083@hand.yhbt.net","threadId":"4475","inReplyTo":"9e4733910606111902l709c71ccyf45070d55112739e@mail.gmail.com","subject":"Re: svn to git, N-squared?","fromName":"Eric Wong","fromEmail":"normalperson@yhbt.net","sentAt":"2006-06-12T04:29:34Z","receivedAt":"2006-06-12T04:29:34Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jon Smirl <jonsmirl@gmail.com> wrote:\n> I have Mozilla CVS in a SVN repository. I've been using git-svnimport\n> to import it. This time I am letting it run to completion; but the\n> import has been running for four days now and it is only up to 2004.\n> The import task is stable at 570MB and it is using about 50% of my\n> CPU. It is constantly spawning off git write-tree, read-tree,\n> hash-object, update-index. It is not doing excessive disk activity.\n\nSVN itself seems to get much slower as you get towards newer revisions\nin a repository (FSFS) with lots of history.  I've been experimenting a\nbit with a local copy of the gcc repo from November and git-svn SUCKED\nat importing it (it took over a week and I cancelled it out of\nfrustration).   I started repacking too, but, and it didn't help,  Much\nof the performance defieciency was the svn sub process. being extremely\nslow at updating.\n\nI also tried git-svnimport, of course, but I only had 512M on that\nmachine and the machine became unusable due to heavy swapping.\n\n> The import seems to be getting n-squared slower. It is still making\n> forward progress but the progress seems to be getting slower and\n> slower.\n> \n> It looks like it is doing write-tree, read-tree, hash-object,\n> update-index once or more per change set. If these commands are\n> n-proportional and they are getting run n times, then this is a\n> n-squared process. Projecting this out, the import may take 10 days or\n> more to completely finish.\n\nI'm working on some improvements to git-svn to make it a bit more\nspiffy.\n\n-- \nEric Wong\n"},{"id":"21652","messageId":"86irn6wdob.fsf@blue.stonehenge.com","threadId":"4475","inReplyTo":"Pine.LNX.4.64.0606112028010.5498@g5.osdl.org","subject":"Re: svn to git, N-squared?","fromName":"Randal L. Schwartz","fromEmail":"merlyn@stonehenge.com","sentAt":"2006-06-12T16:18:12Z","receivedAt":"2006-06-12T16:18:12Z","isPatch":false,"sender":{"key":"merlyn@stonehenge.com","avatar":"https://gravatar.com/avatar/dc528d210743ff0333e6213f9ee7b33b23f1b7bc1f3c5a8c2d819074ecd7ab19?d=mp&s=160"},"body":">>>>> \"Linus\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLinus> This sounds like _exactly_ what happens if you don't repack\nLinus> occasionally.  Expecially if you are using a filesystem without hashed\nLinus> filename lookup, but it's true to some degree even with that - the\nLinus> filesystem tends to end up spending tons of time in kernel space,\nLinus> trying to find a place to put new objects.\n\nI'm using git-svn to do a similar thing with a 11K-commit history.  It's now 4\ndays running, and yes, I'm repacking and deleting empty dirs every 200-300\ncommits, but I'm only up to commit 4000 or so.  At this rate, I *may* finish\nby sometime next week. :(\n\nHowever, I notice one thing that can't be good: .git/git-svn/revs has one file\nper revision.  Yes, I'll end up with 11000 files in a single directory.  Ugh.\n\n-- \nRandal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095\n<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>\nPerl/Unix/security consulting, Technical writing, Comedy, etc. etc.\nSee PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!\n"},{"id":"21654","messageId":"867j3mwdcu.fsf@blue.stonehenge.com","threadId":"4475","inReplyTo":"86irn6wdob.fsf@blue.stonehenge.com","subject":"Re: svn to git, N-squared?","fromName":"Randal L. Schwartz","fromEmail":"merlyn@stonehenge.com","sentAt":"2006-06-12T16:25:05Z","receivedAt":"2006-06-12T16:25:05Z","isPatch":false,"sender":{"key":"merlyn@stonehenge.com","avatar":"https://gravatar.com/avatar/dc528d210743ff0333e6213f9ee7b33b23f1b7bc1f3c5a8c2d819074ecd7ab19?d=mp&s=160"},"body":">>>>> \"Randal\" == Randal L Schwartz <merlyn@stonehenge.com> writes:\n\n>>>>> \"Linus\" == Linus Torvalds <torvalds@osdl.org> writes:\nLinus> This sounds like _exactly_ what happens if you don't repack\nLinus> occasionally.  Expecially if you are using a filesystem without hashed\nLinus> filename lookup, but it's true to some degree even with that - the\nLinus> filesystem tends to end up spending tons of time in kernel space,\nLinus> trying to find a place to put new objects.\n\nRandal> I'm using git-svn to do a similar thing with a 11K-commit history.  It's now 4\nRandal> days running, and yes, I'm repacking and deleting empty dirs every 200-300\nRandal> commits, but I'm only up to commit 4000 or so.  At this rate, I *may* finish\nRandal> by sometime next week. :(\n\nRandal> However, I notice one thing that can't be good: .git/git-svn/revs has one file\nRandal> per revision.  Yes, I'll end up with 11000 files in a single directory.  Ugh.\n\nAnother contributing factor is that there's 2500 files in the repo (at\nrevision 3931).  I was recording 20 commits a minute in the early part of the\ncycle, and now I'm down to 1 commit every two minutes.  Doing a bit of\nback-of-the-scribbled-on-envelope calcs, I won't be finished for\nanother two weeks or so. :(\n\n-- \nRandal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095\n<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>\nPerl/Unix/security consulting, Technical writing, Comedy, etc. etc.\nSee PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!\n"},{"id":"21667","messageId":"f36b08ee0606121204q1f9dfb5dv3c09c4e9e6a16a0f@mail.gmail.com","threadId":"4475","inReplyTo":"Pine.LNX.4.64.0606112056440.5498@g5.osdl.org","subject":"Re: svn to git, N-squared?","fromName":"Yakov Lerner","fromEmail":"iler.ml@gmail.com","sentAt":"2006-06-12T19:04:00Z","receivedAt":"2006-06-12T19:04:00Z","isPatch":false,"sender":{"key":"iler.ml@gmail.com","avatar":null},"body":"On 6/12/06, Linus Torvalds <torvalds@osdl.org> wrote:\n> On Sun, 11 Jun 2006, Jon Smirl wrote:\n> > I have it stopped and I am running the repack.\n> > There are 1.27M files in my .git directory\n> Yeah, that would do it. That's ~5000 files per object directory, so I\n> assume that your directories are 200+kB in size, and for every new object\n> added, you'll basically have to traverse the old directory fully in order\n> to find an empty place for it\n\nIs this related to 1-level dir tree for objects (12/object)\nvs 2-level dir tree (12/34/object) ? Does git employ more levels\nfor object tree for large projects ?\n\nYakov\n"},{"id":"21672","messageId":"Pine.LNX.4.64.0606121214420.5498@g5.osdl.org","threadId":"4475","inReplyTo":"f36b08ee0606121204q1f9dfb5dv3c09c4e9e6a16a0f@mail.gmail.com","subject":"Re: svn to git, N-squared?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-12T19:17:37Z","receivedAt":"2006-06-12T19:17:37Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Jun 2006, Yakov Lerner wrote:\n> \n> Is this related to 1-level dir tree for objects (12/object)\n> vs 2-level dir tree (12/34/object) ? Does git employ more levels\n> for object tree for large projects ?\n\nThe \"more levels\" approach was certainly an option early on, when we \ndiscussed how the objects should be spread out.\n\nIt was basically made a non-issue by the pack-files. These days, the rule \nis really more along the lines of \"if you ever have more than a few \nthousand files, you've not repacked properly\".\n\nThe git-svnimport script obviously doesn't do it right, but it should be \ntrivial to fix. For the git cvsimporter, the fix was literally to just do\n\n\t$commitcount++;\n\t..\n\tif (($commitcount & 1023) == 0) {\n\t\tsystem(\"git repack -a -d\");  \n\t}\n\nwhen committing and that was it. It doesn't get much simpler than that, \nbut the svnimporter just hasn't done it yet.\n\n\t\tLinus\n"}]}