packs and trees

Converting from CVS would be a lot more efficient if all of revisions contained in a CVS file were written into git at the same time. So, if I extract complete revisions from 100 source files into git objects and then ask git to incremental pack, will git find all of the deltas and do a good job packing? Some of these files have thousands (50MB) of deltas. Also, note that I have not written any tree info into git yet.

After all of the revisions are into git, I will follow up with the tree info and then repack all. How will the pack end up grouped, chronologically or will it still be sorted by file? It is not clear to me how the tree info interacts with the magic packing sauce.

The plan is to modify rcs2git from parsecvs to create all of the git objects for the tree. It would be called by the cvs2svn code which would track the object IDs through the changeset generation process. At the end it will write all of the trees connecting the objects together.

cvs2svn seems to do a good job at generating the trees. I am not exactly sure how the changeset detection algorithms in the three apps compare, but cvs2svn is not having any trouble building changesets for Mozilla. The other two apps have some issues, cvsps throws away some of the branches and parsecvs can't complete the analysis.

On 6/20/06, Jon Smirl <jonsmirl@gmail.com> wrote:

Sounds like a good plan. Have you seen recent discussions about it being impossible to repack usefully when you don't have trees (and resulting performance problems on ext3).

No doubt. Gut the last stage, and use all the data in the intermediate DBs to run a git import. It's a great plan, and if you can understand that Python code... all yours ;-)

Have you tried a recent parsecvs from Keith's tree? There's been quite a bit of activity there too. And Keith's interested in sorting out incremental imports too, which you need for a reasonable Moz transition plan as well.

cheers,

martin

On 6/20/06, Martin Langhoff <martin.langhoff@gmail.com> wrote:

No, I will look back in the archives. If needed we can do a repack after each file is added. I would hope that git can handle a repack when the new stuff is 100% deltas from a single file.

If I can't pack the exploded deltas need about 35GB disk space. That is an awful lot to feed to pack all at once, but it will have trees,

How hard would it be to adjust cvsps to use cvs2svn's algorithm for grouping the changesets? I'd rather do this in a C app but I haven't figured out the guts of parsecvs or cvsps well enough to change the algorithms. There is no requirement to use external databases, sorting everything in RAM is fine.

If you are interested in changing the cvsps grouping algorithm I can look at moding it to write out the revisions as are they are parsed. Then you only need to save the git sha1 in memory instead of the file:rev when sorting.

Keith's parsecvs run ended up in a loop and mine hit a parsecvs error and then had memory corruption after about eight hours. That was last week, I just checked the logs and I don't see any comments about fixing it.

Even after spending eight hours building the changeset info iit is still going to take it a couple of days to retrieve the versions one at a time and write them to git. Reparsing 50MB delta files n^2/2 times is a major bottleneck for all three programs.

On Tue, 2006-06-20 at 10:35 -0400, Jon Smirl wrote:

Yeah, I'm rewriting the tool; the current codebase isn't supportable.

The eight hours in question *were* writing out the deltas and packing the resulting trees. All that remained was to construct actual commit objects and write them out.

The problem was that parsecvs's internals are structured so that this processes would take a large amount of memory, so I'm reworking the code to free stuff as it goes along.

With a rewritten parsecvs, I'm hoping to be able to steal the algorithms from cvs2svn and stick those in place. Then work on truncating the history so it can deal with incremental updates to the repository, which I think will be straightforward if we stick a few breadcrumbs in the git repository to recover state from.

On 6/20/06, Keith Packard <keithp@keithp.com> wrote:

How about writing out all of the revisions from the cvs file using the yacc code the first time the file is encountered and parsed. Then you only have to track git IDs and not all of those cumbersome CVS rev numbers. When I was profiling parsecvs the hottest parts of the code were extracting the revisions and comparing cvs rev numbers. Since the git IDs are fixed size they work well in arrays and with pointer compares for sorting. With the right data structure you should be able to eliminate the CVS rev numbers that are so slow to deal with.

There are about 1M revisions in moz cvs. At eight byes for an ID and eight bytes for a timestamp that is 16MB if ordering is achieved via arrays. All of the symbols fit into 400K including pointers to their revision. If the revs are written out as they are encountered there is no need to save file names, but you do need one rev structure per file. Throw in some more memory for relationship pointers. All of this should fit into less than 100MB RAM.

On Tue, 20 Jun 2006, Martin Langhoff wrote:

What do you mean?

Nicolas

On 6/21/06, Nicolas Pitre <nico@cam.org> wrote:

I was thinking of the "repacking disconnected objects" thread, but now I see it did have a solution in listing all the objects and paths. I take that back.

If you are asking about the ext3 performance problems, I think Linus discussed that a while ago, why unpacked repos are slow (in addition to huge), and there were some suggestions of using hashed directory indexes.

cheers,

martin

On Wed, 21 Jun 2006, Martin Langhoff wrote:

OK.

Nicolas

On Wed, 21 Jun 2006, Martin Langhoff wrote:

Yes. I think most distros still default to nonhashed directories, but for any large-directory case you really want to turn on hashing.

I forget the exact details, it's somethng like

	tune2fs -O dir_index

or something to turn it on (if I remember correctly, that will only affect any directories then created after that, but you can effect that by just doing a "git repack -a -d" which will remove all old object directories, and now subsequent directories will be done with indexing on).

Personally, I just ended up using packs extensively, so I think I'm still running without indexing on all my machines ;)

		Linus

there are performance penalties in some cases when you use directory hashing. I did some tests last year of lots of small files in a directory tree (X/X/X/XXX of 1k files) and I found that turning on directory hashing actually slowed down the creation of this tree from a tarball significantly (I also found that in this case the ext2 allocation strategy was significantly better then the ext3 one), so test on your system.

David Lang

  On Tue, 20 Jun 2006, Linus Torvalds wrote: