# svn to git, N-squared? 9 messages from 2006-06-12 to 2006-06-12. Participants: Jon Smirl, Linus Torvalds, Eric Wong, Randal L. Schwartz, Yakov Lerner. Thread: https://gitlist.dev/t/4475 ## Jon Smirl, 2006-06-12 02:02 Subject: svn to git, N-squared? Message-ID: <9e4733910606111902l709c71ccyf45070d55112739e@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910606111902l709c71ccyf45070d55112739e%40mail.gmail.com ``` I have Mozilla CVS in a SVN repository. I've been using git-svnimport to import it. This time I am letting it run to completion; but the import has been running for four days now and it is only up to 2004. The import task is stable at 570MB and it is using about 50% of my CPU. It is constantly spawning off git write-tree, read-tree, hash-object, update-index. It is not doing excessive disk activity. The import seems to be getting n-squared slower. It is still making forward progress but the progress seems to be getting slower and slower. It looks like it is doing write-tree, read-tree, hash-object, update-index once or more per change set. If these commands are n-proportional and they are getting run n times, then this is a n-squared process. Projecting this out, the import may take 10 days or more to completely finish. -- Jon Smirl jonsmirl@gmail.com ``` ## Linus Torvalds, 2006-06-12 03:31 Subject: Re: svn to git, N-squared? Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0606112028010.5498%40g5.osdl.org In-Reply-To: <9e4733910606111902l709c71ccyf45070d55112739e@mail.gmail.com> ``` On Sun, 11 Jun 2006, Jon Smirl wrote: > > I have Mozilla CVS in a SVN repository. I've been using git-svnimport > to import it. This time I am letting it run to completion; but the > import has been running for four days now and it is only up to 2004. > The import task is stable at 570MB and it is using about 50% of my > CPU. It is constantly spawning off git write-tree, read-tree, > hash-object, update-index. It is not doing excessive disk activity. This sounds like _exactly_ what happens if you don't repack occasionally. Expecially if you are using a filesystem without hashed filename lookup, but it's true to some degree even with that - the filesystem tends to end up spending tons of time in kernel space, trying to find a place to put new objects. I don't think git-svnimport has the repack logic in it, so that would be it. You can probably stop it with ^Z, do a "git repack -a -d", and then let it continue. (The only reason for stopping it is actually to let "git repack" remove most of the object directories - many filesystems, including ext3, don't even speed up all that much if the directories are emptied after they've grown big, and it's much better if the object directories get totally removed and re-created) Linus ``` ## Jon Smirl, 2006-06-12 03:39 Subject: Re: svn to git, N-squared? Message-ID: <9e4733910606112039p7aff60c7w7a074d0e35c7b0f@mail.gmail.com> URL: https://gitlist.dev/e/9e4733910606112039p7aff60c7w7a074d0e35c7b0f%40mail.gmail.com In-Reply-To: ``` On 6/11/06, Linus Torvalds wrote: > > > On Sun, 11 Jun 2006, Jon Smirl wrote: > > > > I have Mozilla CVS in a SVN repository. I've been using git-svnimport > > to import it. This time I am letting it run to completion; but the > > import has been running for four days now and it is only up to 2004. > > The import task is stable at 570MB and it is using about 50% of my > > CPU. It is constantly spawning off git write-tree, read-tree, > > hash-object, update-index. It is not doing excessive disk activity. > > This sounds like _exactly_ what happens if you don't repack occasionally. > Expecially if you are using a filesystem without hashed filename lookup, > but it's true to some degree even with that - the filesystem tends to end > up spending tons of time in kernel space, trying to find a place to put > new objects. > > I don't think git-svnimport has the repack logic in it, so that would be > it. > > You can probably stop it with ^Z, do a "git repack -a -d", and then let it > continue. I have it stopped and I am running the repack. There are 1.27M files in my .git directory I ordered 2GB more RAM which should be here Tuesday. > (The only reason for stopping it is actually to let "git repack" remove > most of the object directories - many filesystems, including ext3, don't > even speed up all that much if the directories are emptied after they've > grown big, and it's much better if the object directories get totally > removed and re-created) > > Linus > -- Jon Smirl jonsmirl@gmail.com ``` ## Linus Torvalds, 2006-06-12 04:02 Subject: Re: svn to git, N-squared? Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0606112056440.5498%40g5.osdl.org In-Reply-To: <9e4733910606112039p7aff60c7w7a074d0e35c7b0f@mail.gmail.com> ``` On Sun, 11 Jun 2006, Jon Smirl wrote: > > I have it stopped and I am running the repack. > There are 1.27M files in my .git directory Yeah, that would do it. That's ~5000 files per object directory, so I assume that your directories are 200+kB in size, and for every new object added, you'll basically have to traverse the old directory fully in order to find an empty place for it (and without hashing, you'll traverse it _twice_ - first to look for it, then to look for the empty space). Btw, after repacking, if it still has lots of lose objects, and you still have several directories that are huge (because there are pending objects for a commit that didn't happen yet when you ^Z'd the svnimport), you'll literally get better performance if you do something like for i in ?? do cp -r $i $i.new rm -rf $i mv $i.new $i done in your .git/objects/ directory (CAREFUL! Any script that does "rm -rf" should be double- and triple-checked for sanity! ;) That should make sure that you don't still have huge directories. (And yes, this is a real problem at least with ext3). The git cvsimporter ends up repacking the archive every thousand commits. That's just a random number, but it's indicative of what we did there to handle large imports. I don't think anybody has done a large import using the git-svnimport before, so you're in new territory which explains some of the teething problems. Linus ``` ## Eric Wong, 2006-06-12 04:29 Subject: Re: svn to git, N-squared? Message-ID: <20060612042934.GA12083@hand.yhbt.net> URL: https://gitlist.dev/e/20060612042934.GA12083%40hand.yhbt.net In-Reply-To: <9e4733910606111902l709c71ccyf45070d55112739e@mail.gmail.com> ``` Jon Smirl wrote: > I have Mozilla CVS in a SVN repository. I've been using git-svnimport > to import it. This time I am letting it run to completion; but the > import has been running for four days now and it is only up to 2004. > The import task is stable at 570MB and it is using about 50% of my > CPU. It is constantly spawning off git write-tree, read-tree, > hash-object, update-index. It is not doing excessive disk activity. SVN itself seems to get much slower as you get towards newer revisions in a repository (FSFS) with lots of history. I've been experimenting a bit with a local copy of the gcc repo from November and git-svn SUCKED at importing it (it took over a week and I cancelled it out of frustration). I started repacking too, but, and it didn't help, Much of the performance defieciency was the svn sub process. being extremely slow at updating. I also tried git-svnimport, of course, but I only had 512M on that machine and the machine became unusable due to heavy swapping. > The import seems to be getting n-squared slower. It is still making > forward progress but the progress seems to be getting slower and > slower. > > It looks like it is doing write-tree, read-tree, hash-object, > update-index once or more per change set. If these commands are > n-proportional and they are getting run n times, then this is a > n-squared process. Projecting this out, the import may take 10 days or > more to completely finish. I'm working on some improvements to git-svn to make it a bit more spiffy. -- Eric Wong ``` ## Randal L. Schwartz, 2006-06-12 16:18 Subject: Re: svn to git, N-squared? Message-ID: <86irn6wdob.fsf@blue.stonehenge.com> URL: https://gitlist.dev/e/86irn6wdob.fsf%40blue.stonehenge.com In-Reply-To: ``` >>>>> "Linus" == Linus Torvalds writes: Linus> This sounds like _exactly_ what happens if you don't repack Linus> occasionally. Expecially if you are using a filesystem without hashed Linus> filename lookup, but it's true to some degree even with that - the Linus> filesystem tends to end up spending tons of time in kernel space, Linus> trying to find a place to put new objects. I'm using git-svn to do a similar thing with a 11K-commit history. It's now 4 days running, and yes, I'm repacking and deleting empty dirs every 200-300 commits, but I'm only up to commit 4000 or so. At this rate, I *may* finish by sometime next week. :( However, I notice one thing that can't be good: .git/git-svn/revs has one file per revision. Yes, I'll end up with 11000 files in a single directory. Ugh. -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training! ``` ## Randal L. Schwartz, 2006-06-12 16:25 Subject: Re: svn to git, N-squared? Message-ID: <867j3mwdcu.fsf@blue.stonehenge.com> URL: https://gitlist.dev/e/867j3mwdcu.fsf%40blue.stonehenge.com In-Reply-To: <86irn6wdob.fsf@blue.stonehenge.com> ``` >>>>> "Randal" == Randal L Schwartz writes: >>>>> "Linus" == Linus Torvalds writes: Linus> This sounds like _exactly_ what happens if you don't repack Linus> occasionally. Expecially if you are using a filesystem without hashed Linus> filename lookup, but it's true to some degree even with that - the Linus> filesystem tends to end up spending tons of time in kernel space, Linus> trying to find a place to put new objects. Randal> I'm using git-svn to do a similar thing with a 11K-commit history. It's now 4 Randal> days running, and yes, I'm repacking and deleting empty dirs every 200-300 Randal> commits, but I'm only up to commit 4000 or so. At this rate, I *may* finish Randal> by sometime next week. :( Randal> However, I notice one thing that can't be good: .git/git-svn/revs has one file Randal> per revision. Yes, I'll end up with 11000 files in a single directory. Ugh. Another contributing factor is that there's 2500 files in the repo (at revision 3931). I was recording 20 commits a minute in the early part of the cycle, and now I'm down to 1 commit every two minutes. Doing a bit of back-of-the-scribbled-on-envelope calcs, I won't be finished for another two weeks or so. :( -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training! ``` ## Yakov Lerner, 2006-06-12 19:04 Subject: Re: svn to git, N-squared? Message-ID: URL: https://gitlist.dev/e/f36b08ee0606121204q1f9dfb5dv3c09c4e9e6a16a0f%40mail.gmail.com In-Reply-To: ``` On 6/12/06, Linus Torvalds wrote: > On Sun, 11 Jun 2006, Jon Smirl wrote: > > I have it stopped and I am running the repack. > > There are 1.27M files in my .git directory > Yeah, that would do it. That's ~5000 files per object directory, so I > assume that your directories are 200+kB in size, and for every new object > added, you'll basically have to traverse the old directory fully in order > to find an empty place for it Is this related to 1-level dir tree for objects (12/object) vs 2-level dir tree (12/34/object) ? Does git employ more levels for object tree for large projects ? Yakov ``` ## Linus Torvalds, 2006-06-12 19:17 Subject: Re: svn to git, N-squared? Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0606121214420.5498%40g5.osdl.org In-Reply-To: ``` On Mon, 12 Jun 2006, Yakov Lerner wrote: > > Is this related to 1-level dir tree for objects (12/object) > vs 2-level dir tree (12/34/object) ? Does git employ more levels > for object tree for large projects ? The "more levels" approach was certainly an option early on, when we discussed how the objects should be spread out. It was basically made a non-issue by the pack-files. These days, the rule is really more along the lines of "if you ever have more than a few thousand files, you've not repacked properly". The git-svnimport script obviously doesn't do it right, but it should be trivial to fix. For the git cvsimporter, the fix was literally to just do $commitcount++; .. if (($commitcount & 1023) == 0) { system("git repack -a -d"); } when committing and that was it. It doesn't get much simpler than that, but the svnimporter just hasn't done it yet. Linus ```