{"thread":{"id":"9113","subject":"Idea for git-fast-import","startedAt":"2007-07-20T06:59:23Z","lastAt":"2007-07-22T18:35:57Z","messageCount":3,"participants":["Michael Haggerty","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"47934","messageId":"46A05D4B.1050208@alum.mit.edu","threadId":"9113","inReplyTo":null,"subject":"Idea for git-fast-import","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2007-07-20T06:59:23Z","receivedAt":"2007-07-20T06:59:23Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I'm working on a git backend for cvs2svn and had an idea for\ngit-fast-import that would make life a tiny bit easier:\n\nCurrently, git-fast-import marks are positive integers.  But they are\nused for two things: marking single-file blobs, and marking commits.\n\nThis is a tiny bit awkward, because cvs2svn assigns small integer IDs to\nthese things too, but uses distinct (overlapping) integer series for the\ntwo concepts.  If it would be trivial to split the marks into two\n\"namespaces\" (one for single-file blobs and one for commits), that would\nmake things a little bit more natural.  I don't think commit marks can\nbe used interchangeably with blob marks anyway, so it wouldn't be a\nbackwards incompatibility.\n\nWithout this feature, I will have to assign a new \"mark\" integer series\nthat is unrelated to cvs2svn's IDs, which is no big deal at all but will\nmake debugging a little bit harder.  So only add this feature if it is\nreally easy for you.\n\nAlso, is there a big cost to using \"not-quite-consecutive\" integers as\nmarks?  cvs2svn's CVSRevision IDs are intermingled with IDs for\nCVSBranches and CVSTags, so the CVSRevisions alone probably only pack\nthe ID space 5%-50% full.\n\nIn fact, if there is a big cost to \"not-quite-consecutive\" integers,\nthen I withdraw my request for separate mark namespaces, since I would\nhave to reallocate mark numbers anyway :-)\n\nAnother thing that might help with debugging would be a \"comment\"\ncommand, which git-fast-import should ignore.  One could put text about\nthe source of a chunk of git-fast-import stream to relate it back to the\nfront-end concepts when debugging the stream contents by hand.\n\n[I will be out of town until Monday, so don't be surprised that I don't\nrespond right away :-) ]\n\nThanks,\nMichael\n"},{"id":"47939","messageId":"20070720072824.GP32566@spearce.org","threadId":"9113","inReplyTo":"46A05D4B.1050208@alum.mit.edu","subject":"Re: Idea for git-fast-import","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-07-20T07:28:24Z","receivedAt":"2007-07-20T07:28:24Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> I'm working on a git backend for cvs2svn and had an idea for\n> git-fast-import that would make life a tiny bit easier:\n\nCool!\n \n> Currently, git-fast-import marks are positive integers.  But they are\n> used for two things: marking single-file blobs, and marking commits.\n> \n> This is a tiny bit awkward, because cvs2svn assigns small integer IDs to\n> these things too, but uses distinct (overlapping) integer series for the\n> two concepts.  If it would be trivial to split the marks into two\n> \"namespaces\" (one for single-file blobs and one for commits), that would\n> make things a little bit more natural.  I don't think commit marks can\n> be used interchangeably with blob marks anyway, so it wouldn't be a\n> backwards incompatibility.\n\nThat's true, they aren't interchangeable.  fast-import pukes\nand dies if you try to use the wrong type at the wrong location.\nIt has been requested before that the two namespaces be split,\nand I just have been too lazy to do it.\n\n> Without this feature, I will have to assign a new \"mark\" integer series\n> that is unrelated to cvs2svn's IDs, which is no big deal at all but will\n> make debugging a little bit harder.  So only add this feature if it is\n> really easy for you.\n\nIts not that much code reorg, but there is some reorg required to\nmake it work.  Maybe only a few hundred line diff, so probably well\nwithin reason.  I'll look into it later.\n \n> Also, is there a big cost to using \"not-quite-consecutive\" integers as\n> marks?  cvs2svn's CVSRevision IDs are intermingled with IDs for\n> CVSBranches and CVSTags, so the CVSRevisions alone probably only pack\n> the ID space 5%-50% full.\n\nMarks cost exactly 1 pointer (4 or 8 bytes) as they are actually just\na pointer to the already-in-memory object metadata that fast-import\nuses for bookkeeping related to packfile generation.  Gaps in the\nmarks sequence also cost exactly 1 pointer, as they are just NULL.\n\nBut the marks table is actually a sparse array, using 1024 entries\nper block.  So if you assign a mark at :5, then another at say\n:1047000 you have only allocated 3 blocks and 12 KiB of memory\n(a root directory block at 4 KiB, two leafs at 4 KiB each).  A far\ncry from 4 MiB.\n\nIts not a binary tree, its a sparse digital index.  So going\nreally far out in the namespace with huge gaps will cost you some\nindex nodes.  Staying reasonably dense is actually quite efficient,\nwith pretty low directory overheads.\n\n> In fact, if there is a big cost to \"not-quite-consecutive\" integers,\n> then I withdraw my request for separate mark namespaces, since I would\n> have to reallocate mark numbers anyway :-)\n\nSee above.  5% full is really bad, because you are probably going to\nallocate nearly every block in the directory, and only fill each leaf\nblock at 5% full.  50% full is actually reasonable, as it means marks\nare only costing you about 2 pointers on average (8 or 16 bytes).\n\nI went with the sparse array/digital index approach because it is\nfairly compact code, quick store and lookup operations, and I figured\nmost frontends could get at least 50% full on their mark allocation.\nOn really dense allocations (>60%) the very low overhead per mark\nmakes it insanely efficient, even for a very large number of marks.\n\nJon Smirl was dumping marks sequentially from his hacked cvs2svn,\nthereby getting the marks table at 100% full.  Other recent import\nattempts with fast-import have also managed to keep their mark\nallocations pretty close (if not dead on) at 100% full.\n\nI can see how it might be convenient to have a very sparsely filled\nmark namespace.  Its also convenient to have a mark namespace that\nuses arbitrary strings.  Unfortunately I chose not to support\nthose very well (or at all!) for the sake of trying to keep the\nfast-import code more compact internally, and to simplify its\ninternal memory management.  You might be able to talk me into\nimproving on that however.  ;-)\n \n> Another thing that might help with debugging would be a \"comment\"\n> command, which git-fast-import should ignore.  One could put text about\n> the source of a chunk of git-fast-import stream to relate it back to the\n> front-end concepts when debugging the stream contents by hand.\n\nThis is an awesome idea, especially when combined with having a\nbuffer of the last few commands that fast-import saw right before\nit crashed.  I'll see what I can do.\n \n-- \nShawn.\n"},{"id":"48159","messageId":"46A3A38D.5020601@alum.mit.edu","threadId":"9113","inReplyTo":"20070720072824.GP32566@spearce.org","subject":"Re: Idea for git-fast-import","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2007-07-22T18:35:57Z","receivedAt":"2007-07-22T18:35:57Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Shawn O. Pearce wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>> Also, is there a big cost to using \"not-quite-consecutive\" integers as\n>> marks?  cvs2svn's CVSRevision IDs are intermingled with IDs for\n>> CVSBranches and CVSTags, so the CVSRevisions alone probably only pack\n>> the ID space 5%-50% full.\n> \n>> In fact, if there is a big cost to \"not-quite-consecutive\" integers,\n>> then I withdraw my request for separate mark namespaces, since I would\n>> have to reallocate mark numbers anyway :-)\n> \n> See above.  5% full is really bad, because you are probably going to\n> allocate nearly every block in the directory, and only fill each leaf\n> block at 5% full.  50% full is actually reasonable, as it means marks\n> are only costing you about 2 pointers on average (8 or 16 bytes).\n\nOK, then, never mind.  As I mentioned, it is not a big deal to have\ncvs2svn generate a separate integer series for marks.  If comments are\nimplemented, then the debugging disadvantage is also quite minor.\n\n>> Another thing that might help with debugging would be a \"comment\"\n>> command, which git-fast-import should ignore.  One could put text about\n>> the source of a chunk of git-fast-import stream to relate it back to the\n>> front-end concepts when debugging the stream contents by hand.\n> \n> This is an awesome idea, especially when combined with having a\n> buffer of the last few commands that fast-import saw right before\n> it crashed.  I'll see what I can do.\n\nThanks!\n\nMichael\n"}]}