{"thread":{"id":"17680","subject":"RFC: Flat directory for notes, or fan-out? Both!","startedAt":"2009-02-09T21:12:06Z","lastAt":"2009-02-11T23:05:30Z","messageCount":33,"participants":["Johannes Schindelin","Boyd Stephen Smith Jr.","Jeff King","Junio C Hamano","Shawn O. Pearce","Thomas Rast","Sam Vilain","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"103903","messageId":"alpine.DEB.1.00.0902092200170.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":null,"subject":"RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-09T21:12:06Z","receivedAt":"2009-02-09T21:12:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nShawn triggered some well needed thinking on my part about the notes \nimplementation. At the moment, we have flat directory structure, and read \nall of them in one go (when needed).\n\nI think we should support that, because it is relatively easy to generate \nthat kind of trees for small-scale applications.\n\nHowever, I think there is also a benefit to handle fan-out directory \nstructures, too: they scale much nicer.\n\nIf the commit name was not found as a filename, it could be searched in \nwhatever subdirectory whose name is a prefix of said commit name (first \nwins).\n\nSo I think it would be a sane plan to do the following when a commit note \nis requested:\n\n- If not done yet, read in the whole top-level directory of the notes ref.\n\n- If the commit name is not found, find the tree entries whose name is a \n prefix of the commit name (we can even use the same hashmap to store \n these \"incomplete\" names, as we use a linear hash, which we fill in \n ascending order),\n\n - read the trees one by one, until the commit name is found (or no tree \n entry is left), deleting the trees from the hashmap on the go.\n\nHow does that sound?\n\nCiao,\nDscho\n\n\t\n"},{"id":"103955","messageId":"200902100158.46884.bss@iguanasuicide.net","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902092200170.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Boyd Stephen Smith Jr.","fromEmail":"bss@iguanasuicide.net","sentAt":"2009-02-10T07:58:41Z","receivedAt":"2009-02-10T07:58:41Z","isPatch":false,"sender":{"key":"bss@iguanasuicide.net","avatar":"https://gravatar.com/avatar/84b95eeff194b816c1568b1339e63e4b229825298664a9037b9f1ec713ead1e3?d=mp&s=160"},"body":"On Monday 09 February 2009 15:12:06 Johannes Schindelin wrote:\n> So I think it would be a sane plan to do the following when a commit note\n> is requested:\n\nSo, something like a Trie data structure? I think that is a great way to \nstore fixed-length strings from a limited alphabet with arbitrary data \nattached.\n-- \nBoyd Stephen Smith Jr. ,= ,-_-. =.\nbss@iguanasuicide.net ((_/)o o(\\_))\nICQ: 514984 YM/AIM: DaTwinkDaddy `-'(. .)`-'\nhttp://iguanasuicide.net/ \\_/\n\n"},{"id":"103989","messageId":"20090210121833.GC15491@coredump.intra.peff.net","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902092200170.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-02-10T12:18:33Z","receivedAt":"2009-02-10T12:18:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 09, 2009 at 10:12:06PM +0100, Johannes Schindelin wrote:\n\n> Shawn triggered some well needed thinking on my part about the notes \n> implementation. At the moment, we have flat directory structure, and read \n> all of them in one go (when needed).\n> \n> I think we should support that, because it is relatively easy to generate \n> that kind of trees for small-scale applications.\n\nHmm. Do we really care about how easy it is to generate? Are we\nexpecting people to not use the command interface and instead check out\na notes tree and start putting stuff into $commit/foo?\n\nAnd if we are encouraging the dual possibilities, how do we handle the\ncase of merging two trees with equivalent but differently-formatted\ncontent?\n\nImagine I have three users, A, B, and C, all collaborating on a project\nwith notes. A and B use the \"git notes\" interface which generates a\nfan-out directory structure. C uses his own script that directly writes\nto the notes tree without fan-out.\n\nNow let's imagine A, B, and C all write a note for commit X, and A pulls\nfrom the other two. When he pulls from B, there is a file-level\nconflict, and he decides that his note is better and resolves in his\nfavor. But when he pulls from C, there is _no_ conflict, and now there\nare two notes for the same commit in his notes tree. You can give the\nmultiple notes some sane semantics (one trumps the other, or they are a\nlist, or whatever), but there is still an inconsistency: B's notes and\nC's notes behave differently. So now A has to start caring about how\nother people generate their notes.\n\nThe only two solutions I can think of are:\n\n - when A pulls notes, he does a specialized merge that normalizes the\n note trees\n\n - particular notes trees are specified as being in \"fan out\" or \"not\n fan out\" mode. But there is no place to specify that to enforce it.\n\n-Peff\n"},{"id":"103997","messageId":"alpine.DEB.1.00.0902101357140.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"20090210121833.GC15491@coredump.intra.peff.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-10T12:59:06Z","receivedAt":"2009-02-10T12:59:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 10 Feb 2009, Jeff King wrote:\n\n> On Mon, Feb 09, 2009 at 10:12:06PM +0100, Johannes Schindelin wrote:\n> \n> > Shawn triggered some well needed thinking on my part about the notes \n> > implementation. At the moment, we have flat directory structure, and read \n> > all of them in one go (when needed).\n> > \n> > I think we should support that, because it is relatively easy to generate \n> > that kind of trees for small-scale applications.\n> \n> Hmm. Do we really care about how easy it is to generate? Are we\n> expecting people to not use the command interface and instead check out\n> a notes tree and start putting stuff into $commit/foo?\n\nI wanted to be nice to existing users of the feature (it is in 'next', \nafter all, and Thomas has produced some awesome examples, that will \nhopefully show the scalability of the thing).\n\nBut you're right, it almost, but not quite, too late to switch.\n\n> And if we are encouraging the dual possibilities, how do we handle the \n> case of merging two trees with equivalent but differently-formatted \n> content?\n> \n> Imagine I have three users, A, B, and C, all collaborating on a project\n> with notes. A and B use the \"git notes\" interface which generates a\n> fan-out directory structure. C uses his own script that directly writes\n> to the notes tree without fan-out.\n> \n> Now let's imagine A, B, and C all write a note for commit X, and A pulls\n> from the other two. When he pulls from B, there is a file-level\n> conflict, and he decides that his note is better and resolves in his\n> favor. But when he pulls from C, there is _no_ conflict, and now there\n> are two notes for the same commit in his notes tree. You can give the\n> multiple notes some sane semantics (one trumps the other, or they are a\n> list, or whatever), but there is still an inconsistency: B's notes and\n> C's notes behave differently. So now A has to start caring about how\n> other people generate their notes.\n> \n> The only two solutions I can think of are:\n> \n> - when A pulls notes, he does a specialized merge that normalizes the\n> note trees\n> \n> - particular notes trees are specified as being in \"fan out\" or \"not\n> fan out\" mode. But there is no place to specify that to enforce it.\n\nYou're correct. This buys all kinds of trouble.\n\nCiao,\nDscho\n"},{"id":"104002","messageId":"20090210131029.GC17305@coredump.intra.peff.net","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902101357140.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-02-10T13:10:29Z","receivedAt":"2009-02-10T13:10:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 10, 2009 at 01:59:06PM +0100, Johannes Schindelin wrote:\n\n> > Hmm. Do we really care about how easy it is to generate? Are we\n> > expecting people to not use the command interface and instead check out\n> > a notes tree and start putting stuff into $commit/foo?\n> \n> I wanted to be nice to existing users of the feature (it is in 'next', \n> after all, and Thomas has produced some awesome examples, that will \n> hopefully show the scalability of the thing).\n> \n> But you're right, it almost, but not quite, too late to switch.\n\nOK. I think if you are seeing performance benefits from a 2-character\nfanout, then we should standardize on that (do you have new performance\nnumbers somewhere?).\n\nThe notes implementation is now in master. If it's about to change in an\nincompatible way, how do you want to handle it? I'm wary of a quick\npatch to change the format this late in the release cycle. We could hold\nit back from 1.6.2. Alternatively, we could let it release with a \"this\nis probably going to change\" warning.\n\nI think I favor holding it back, but I am not picky.\n\n> > multiple notes some sane semantics (one trumps the other, or they are a\n> > list, or whatever), but there is still an inconsistency: B's notes and\n> > C's notes behave differently. So now A has to start caring about how\n> > other people generate their notes.\n> > [...]\n> \n> You're correct. This buys all kinds of trouble.\n\nOne other thing to note: I think we discussed in the past other kinds of\n\"more than one way to store it\" strategies (e.g., letting a blob note be\nthe same as a tree note containing a blob \"default\"). They suffer from\nsome of the same issues (though not quite as badly, since you would at\nleast see that there was a conflict).\n\n-Peff\n"},{"id":"104003","messageId":"20090210131600.GD17305@coredump.intra.peff.net","threadId":"17680","inReplyTo":"200902100158.46884.bss@iguanasuicide.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-02-10T13:16:00Z","receivedAt":"2009-02-10T13:16:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 10, 2009 at 01:58:41AM -0600, Boyd Stephen Smith Jr. wrote:\n\n> On Monday 09 February 2009 15:12:06 Johannes Schindelin wrote:\n> > So I think it would be a sane plan to do the following when a commit note\n> > is requested:\n> \n> So, something like a Trie data structure? I think that is a great way to \n> store fixed-length strings from a limited alphabet with arbitrary data \n> attached.\n\nI don't think a Trie quite makes sense here. We still have to look\nlinearly through each git tree (an artifact of the tree implementation).\n\nYou could organize the tree into a deeper, more complex data structure\nthan just a simple fan-out. But remember that traditional data\nstructures are usually trying to save expensive comparisons, and\nfollowing a pointer is inexpensive. In the case of git trees, though,\nfollowing a pointer into a subtree is _very_ expensive, since you have\nto lookup and decompress the object.\n\nSo what we do now is read the tree into an associative hash.\nYou could replace the hash with a trie, but it is not really the\nperformance-critical part here. The issue is that without fan-out you\nhave to read the _whole_ tree into the hash. With a constant-sized\nfanout, you get to divide that work by a constant.\n\nOr did you mean something else entirely?\n\n-Peff\n"},{"id":"104006","messageId":"alpine.DEB.1.00.0902101427490.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"20090210131029.GC17305@coredump.intra.peff.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-10T13:32:22Z","receivedAt":"2009-02-10T13:32:22Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\n[Junio: seems like both Peff and me would like to hold the notes out of \n1.6.2, would you mind?]\n\nOn Tue, 10 Feb 2009, Jeff King wrote:\n\n> On Tue, Feb 10, 2009 at 01:59:06PM +0100, Johannes Schindelin wrote:\n> \n> > > Hmm. Do we really care about how easy it is to generate? Are we\n> > > expecting people to not use the command interface and instead check out\n> > > a notes tree and start putting stuff into $commit/foo?\n> > \n> > I wanted to be nice to existing users of the feature (it is in 'next', \n> > after all, and Thomas has produced some awesome examples, that will \n> > hopefully show the scalability of the thing).\n> > \n> > But you're right, it almost, but not quite, too late to switch.\n> \n> OK. I think if you are seeing performance benefits from a 2-character\n> fanout, then we should standardize on that (do you have new performance\n> numbers somewhere?).\n\nThe thing is: Shawn is correct when he says that a tree object to hold the \nnotes of all commits (which is not an unlikely scenario if you are \nthinking about corporate processes) would be huge.\n\n> The notes implementation is now in master. If it's about to change in an \n> incompatible way, how do you want to handle it? I'm wary of a quick \n> patch to change the format this late in the release cycle. We could hold \n> it back from 1.6.2. Alternatively, we could let it release with a \"this \n> is probably going to change\" warning.\n> \n> I think I favor holding it back, but I am not picky.\n\nYes, I am also in favor of holding it back.\n\n> > > multiple notes some sane semantics (one trumps the other, or they are a\n> > > list, or whatever), but there is still an inconsistency: B's notes and\n> > > C's notes behave differently. So now A has to start caring about how\n> > > other people generate their notes.\n> > > [...]\n> > \n> > You're correct. This buys all kinds of trouble.\n> \n> One other thing to note: I think we discussed in the past other kinds of\n> \"more than one way to store it\" strategies (e.g., letting a blob note be\n> the same as a tree note containing a blob \"default\"). They suffer from\n> some of the same issues (though not quite as badly, since you would at\n> least see that there was a conflict).\n\nActually, I do not see much of a problem there. If the entry \n(corresponding to the commit name) in the notes tree points to a blob, \nthen that is that, if it points to a tree, then we just read all of the \nobjects therein (or maybe at a later stage we allow restricting to a \ncertain file basename).\n\nThe point you raised earlier, that there would be a lot of ambiguity if \nwe allow both flat and fan-out directory structures, is a valid point, \nthough.\n\nCiao,\nDscho\n"},{"id":"104029","messageId":"7vprhqnv0c.fsf@gitster.siamese.dyndns.org","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902101427490.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-10T15:58:59Z","receivedAt":"2009-02-10T15:58:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n>> OK. I think if you are seeing performance benefits from a 2-character\n>> fanout, then we should standardize on that (do you have new performance\n>> numbers somewhere?).\n>\n> The thing is: Shawn is correct when he says that a tree object to hold the \n> notes of all commits (which is not an unlikely scenario if you are \n> thinking about corporate processes) would be huge.\n>\n>> The notes implementation is now in master. If it's about to change in an \n>> incompatible way, how do you want to handle it? I'm wary of a quick \n>> patch to change the format this late in the release cycle. We could hold \n>> it back from 1.6.2. Alternatively, we could let it release with a \"this \n>> is probably going to change\" warning.\n>> \n>> I think I favor holding it back, but I am not picky.\n>\n> Yes, I am also in favor of holding it back.\n\nI could do a revert on 'master' if it is really needed, but I found that\nthe above reasoning is a bit troublesome. The thing is, if a tree to hold\nthe notes would be huge to be unmanageable, then it would still be huge to\nbe unmanageable if you split it into 256 pieces.\n\nI'd rather prefer to see us first try to find a way to optimze the tree\nparser. Maybe packv4 or Linus's binary search (which IIRC you declared\nwould not work --- I recall I once thought about it myself but I do not\nrecall what my conclusions were) play a role in it.\n"},{"id":"104039","messageId":"20090210164430.GN30949@spearce.org","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902101427490.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-02-10T16:44:30Z","receivedAt":"2009-02-10T16:44:30Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> [Junio: seems like both Peff and me would like to hold the notes out of \n> 1.6.2, would you mind?]\n\nSorry I'm getting involved in this notes thing so late. I was way\ntoo focused on Gerrit2 and just didn't pay much attention to what\nwas on the git ML recently. Like Dscho and Peff, I think we may\nwant to hold notes out of 1.6.2.\n \n> On Tue, 10 Feb 2009, Jeff King wrote:\n> > On Tue, Feb 10, 2009 at 01:59:06PM +0100, Johannes Schindelin wrote:\n> \n> The thing is: Shawn is correct when he says that a tree object to hold the \n> notes of all commits (which is not an unlikely scenario if you are \n> thinking about corporate processes) would be huge.\n\nA notes tree entry requires 6+1+40+1+20=68 bytes per entry. If I\nuse it for what I want in Gerrit, which is to annotate every commit,\non a project like git.git with 17,491 commits we're talking about\na tree that is 1.13 MB.\n\nThat tree grows at a rate of 276 KB/year.\n\nI'm not sure I want to think about the cost to unpack that tree,\njust so I can look at \"git log --since=1.week.ago\".\n\nMy fear here is that over time we will be spending a lot of CPU\ntime unpacking and indexing the tree in memory, only to then pull\nout a handful of recent commits, and then see the pager abort and\nkill the revision walk.\n \n> The point you raised earlier, that there would be a lot of ambiguity if \n> we allow both flat and fan-out directory structures, is a valid point, \n> though.\n\nYup. The flat vs. fan-out is a problem. In a slightly unrelated\nthread offlist I have been talking with Sam Vilain about using Git\nas a database backend for tuple storage. There is a related issue\nthere about making the tree structure consistent, but never stored\nin a way that we wind up with these massive multi-megabyte objects.\n\nWe've only started to kick it around, but I think we are both in\nagreement that a \"database tree\" is owned by the database code\nand must not be twiddled manually. Not unless you can honor the\nformatting rules. Just like you shouldn't use \"git hash-object\"\nto create a tree, unless you can honor the basic formatting rules\nfor trees.\n\nThis also means that the \"database trees\" probably are not going\nto be mergeable with a basic merge-recursive sort of algorithm,\nbut instead need specialized handling to perform the combination.\n\nI think we're leaning in a direction of something more like this\nfor trees:\n\n- Tuples are stored under a path constructed from their primary key.\n The analog here is, the commit SHA-1 the note is annotating.\n\n- Trees are capped at some reasonable size limit. For sake of\n argument lets call that MAX_TREE. My feeling is this would be\n closer to the 16 KB side of the spectrum then to the 1 MB side.\n\n- Initially the database tree starts out as a single root tree that\n is empty.\n\n- Records are inserted, creating new tree entries, until MAX_TREE\n is reached for the root level tree. Up until this point it is\n a flat tree structure, like the current notes design.\n\n- Once MAX_TREE is reached the root is split, and ranges are used\n to point to the subtrees, which are now flat, and approximately\n are MAX_TREE/2 in size.\n\nEtc.\n\nThis would make the git-notes.sh code a *lot* more complex, as you\ncan't just toss everything into an index file and then update it with\na single update-index call. Doing a tree split is much more work and\nrequires removing and adding back all of the affected path names.\n(Its also perhaps unreasonable anyway to load 17,491 paths into a\ntemporary index just to twiddle a note for the latest commit.)\n\n\nNotes on commits though are a hell of a problem. SHA-1 is just so\nuniform at distributing the commits around the namespace that even\nwith just the 200 most recent commits we wind up with a commit in\nalmost every \"bucket\", assuming a two hex digit fan-out bucket like\nthe loose object directory.\n\nFor the \"git database\" thing above, I've been contemplating the\nidea of an index stored external from the Git object database.\nSam thinks indexes should be in the object database tree, but\nI'm considering storing them outside entirely because we can\nmake the indexes more easily searched by a hash or binary search,\nlike pack-*.idx. Whenever the \"database ref\" gets moved we'd need\nto run a \"sync\" utility to bring these external indexes current.\nBut they could also be more efficiently scanned.\n\nE.g. in the case of commit notes, we could just mmap() the index into\nmemory and perform our lookups through the mmap. Thus we wouldn't\npay massive penalities to index all 17,491 names just to access 200.\nThough we may wind up paging in a good part of the index due to\nthe random access nature, but we can't really do anything about that.\n\nKeeping the indexes current would perhaps mean teaching \"git fetch\"\nto run something after the fetch is complete. Rather trivial in\nthe grand scheme of things. I also liken the external index to the\npack-*.idx, in that its derived from the real sources in the object\ndatabase, and can always be generated client side. So making fetch\ndo it is really no different then making fetch run index-pack.\n\nEh. That wound up being a lot longer than I wanted it to be.\n\n\nSam and I may be putting some effort into this \"git as a database\"\nthing, and it could be used as an efficient notes store. Its just\na very complex notes store. Much more complex to implement than\nthe simple notes currently slated for 1.6.2.\n\n-- \nShawn.\n"},{"id":"104041","messageId":"20090210164809.GO30949@spearce.org","threadId":"17680","inReplyTo":"7vprhqnv0c.fsf@gitster.siamese.dyndns.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-02-10T16:48:09Z","receivedAt":"2009-02-10T16:48:09Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> \n> I could do a revert on 'master' if it is really needed, but I found that\n> the above reasoning is a bit troublesome. The thing is, if a tree to hold\n> the notes would be huge to be unmanageable, then it would still be huge to\n> be unmanageable if you split it into 256 pieces.\n> \n> I'd rather prefer to see us first try to find a way to optimze the tree\n> parser. Maybe packv4 or Linus's binary search (which IIRC you declared\n> would not work --- I recall I once thought about it myself but I do not\n> recall what my conclusions were) play a role in it.\n\npackv4 as proposed wouldn't help a notes tree. It relied on the fact\nthat we'd have no more than 64k unique file names in a repository,\nand any name which overflowed that 64k limit would force its tree\nto be a canonical format tree, which is what we are trying to\navoid here.\n\n-- \nShawn.\n"},{"id":"104040","messageId":"alpine.DEB.1.00.0902101743180.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"7vprhqnv0c.fsf@gitster.siamese.dyndns.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-10T16:48:20Z","receivedAt":"2009-02-10T16:48:20Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 10 Feb 2009, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> >> OK. I think if you are seeing performance benefits from a 2-character\n> >> fanout, then we should standardize on that (do you have new performance\n> >> numbers somewhere?).\n> >\n> > The thing is: Shawn is correct when he says that a tree object to hold the \n> > notes of all commits (which is not an unlikely scenario if you are \n> > thinking about corporate processes) would be huge.\n> >\n> >> The notes implementation is now in master. If it's about to change in an \n> >> incompatible way, how do you want to handle it? I'm wary of a quick \n> >> patch to change the format this late in the release cycle. We could hold \n> >> it back from 1.6.2. Alternatively, we could let it release with a \"this \n> >> is probably going to change\" warning.\n> >> \n> >> I think I favor holding it back, but I am not picky.\n> >\n> > Yes, I am also in favor of holding it back.\n> \n> I could do a revert on 'master' if it is really needed, but I found that\n> the above reasoning is a bit troublesome. The thing is, if a tree to hold\n> the notes would be huge to be unmanageable, then it would still be huge to\n> be unmanageable if you split it into 256 pieces.\n\nThe thing is, a tree object of 17 megabyte is unmanagably large if you \nhave to read it whenever you access even a single node. Having 256 trees \ninstead, each of which is about 68 kilobyte is much nicer.\n\n> I'd rather prefer to see us first try to find a way to optimze the tree \n> parser. Maybe packv4 or Linus's binary search (which IIRC you declared \n> would not work --- I recall I once thought about it myself but I do not \n> recall what my conclusions were) play a role in it.\n\nI declared it did not work, and showed an example here:\n\n\thttp://article.gmane.org/gmane.comp.version-control.git/103297\n\nNow, this example is so concocted that it is not even funny. For example, \nit falls flat down for notes, as the names never contain spaces there.\n\nI guess that we could detect possible false positives such as my example, \nby searching for NULs and spaces in the vicinity, and just search on if \nthere is a salmon of a doubt left.\n\nBut the worst part about it: we'd still have to unpack the whole tree \nobject to start bisecting (as described in said mail).\n\nCiao,\nDscho\n"},{"id":"104042","messageId":"20090210165610.GP30949@spearce.org","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902101743180.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-02-10T16:56:10Z","receivedAt":"2009-02-10T16:56:10Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> On Tue, 10 Feb 2009, Junio C Hamano wrote:\n> > \n> > I could do a revert on 'master' if it is really needed, but I found that\n> > the above reasoning is a bit troublesome. The thing is, if a tree to hold\n> > the notes would be huge to be unmanageable, then it would still be huge to\n> > be unmanageable if you split it into 256 pieces.\n> \n> The thing is, a tree object of 17 megabyte is unmanagably large if you \n> have to read it whenever you access even a single node. Having 256 trees \n> instead, each of which is about 68 kilobyte is much nicer.\n\nSee my other email on this thread; we'd probably need to unpack\nall 256 subtrees *anyway* due to the distribution of SHA-1 names\nfor commits.\n\n-- \nShawn.\n"},{"id":"104044","messageId":"alpine.DEB.1.00.0902101808310.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"20090210164430.GN30949@spearce.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-10T17:09:53Z","receivedAt":"2009-02-10T17:09:53Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 10 Feb 2009, Shawn O. Pearce wrote:\n\n> For the \"git database\" thing above, I've been contemplating the\n> idea of an index stored external from the Git object database.\n\nThe whole point of my exercise was to reuse as much as possible of Git's \nframework. After all, if you store an index external from Git's object \ndatabase, you go back to reimplementing the whole infrastructure for \nfetching/merging just for that index.\n\nCiao,\nDscho\n"},{"id":"104046","messageId":"20090210171751.GQ30949@spearce.org","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902101808310.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-02-10T17:17:51Z","receivedAt":"2009-02-10T17:17:51Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> On Tue, 10 Feb 2009, Shawn O. Pearce wrote:\n> \n> > For the \"git database\" thing above, I've been contemplating the\n> > idea of an index stored external from the Git object database.\n> \n> The whole point of my exercise was to reuse as much as possible of Git's \n> framework. After all, if you store an index external from Git's object \n> database, you go back to reimplementing the whole infrastructure for \n> fetching/merging just for that index.\n\nYea, I know.\n\nIt might just be easier to abandon everything in Git and start\nfrom scratch for the \"git database\" thing. But we'd lose the\nability to at least piggyback onto the existing Git transport.\nAnd it doesn't help the \"git notes\" feature we're talking about.\n\nMaybe I was viewing the external index as like the working tree,\nwhere you can't really access the data until the external indexes\nare current, just like you can't really (easily anyway) access the\nworking tree files until you bring the working tree current. But\nyea, it doesn't really use any of the existing machinary.\n\n-- \nShawn.\n"},{"id":"104049","messageId":"alpine.DEB.1.00.0902101810410.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"20090210165610.GP30949@spearce.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-10T17:31:34Z","receivedAt":"2009-02-10T17:31:34Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 10 Feb 2009, Shawn O. Pearce wrote:\n\n> Johannes Schindelin wrote:\n> > On Tue, 10 Feb 2009, Junio C Hamano wrote:\n> > > \n> > > I could do a revert on 'master' if it is really needed, but I found that\n> > > the above reasoning is a bit troublesome. The thing is, if a tree to hold\n> > > the notes would be huge to be unmanageable, then it would still be huge to\n> > > be unmanageable if you split it into 256 pieces.\n> > \n> > The thing is, a tree object of 17 megabyte is unmanagably large if you \n> > have to read it whenever you access even a single node. Having 256 trees \n> > instead, each of which is about 68 kilobyte is much nicer.\n> \n> See my other email on this thread; we'd probably need to unpack\n> all 256 subtrees *anyway* due to the distribution of SHA-1 names\n> for commits.\n\nNo, that is not true. It is only true if you show more than 94180 \ncommit, actually, as only then the probability that you hit all 256 \nbuckets is larger than 50 percent.\n\nIn general, you will look at only a few commits, though.\n\nCiao,\nDscho\n"},{"id":"104057","messageId":"7vocxam96s.fsf@gitster.siamese.dyndns.org","threadId":"17680","inReplyTo":"20090210165610.GP30949@spearce.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-10T18:35:39Z","receivedAt":"2009-02-10T18:35:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> Johannes Schindelin wrote:\n>> On Tue, 10 Feb 2009, Junio C Hamano wrote:\n>> > \n>> > I could do a revert on 'master' if it is really needed, but I found that\n>> > the above reasoning is a bit troublesome. The thing is, if a tree to hold\n>> > the notes would be huge to be unmanageable, then it would still be huge to\n>> > be unmanageable if you split it into 256 pieces.\n>> \n>> The thing is, a tree object of 17 megabyte is unmanagably large if you \n>> have to read it whenever you access even a single node. Having 256 trees \n>> instead, each of which is about 68 kilobyte is much nicer.\n>\n> See my other email on this thread; we'd probably need to unpack\n> all 256 subtrees *anyway* due to the distribution of SHA-1 names\n> for commits.\n\nI wonder if we can solve this by introducing a local cache that is a flat\nfile that looks like:\n\n magic number for /usr/bin/file\n tree object SHA-1 the file caches\n Number of entries in this file\n 256 fan-out offsets into this file\n N entries of , sorted\n Checksum of the file itself\n\nand use it when availble (otherwise optionally create it upon the first\nlookup). The file can be used by mmaping it and then doing a newton\nraphson or binary search similar to the way patch-ids.c does.\n\nThe top-level API for such a hash-map would perhaps look like:\n\n /*\n * take the object name a tree object that is a hash map,\n * return an opaque struct.\n */\n struct hashmap *hashmap_open(const unsigned char *);\n\n /*\n * find the value given the key and return 0, or return negative\n * if not found.\n */\n int hashmap_lookup(struct hashmap *map, const unsigned char *key,\n \t\t unsigned char *val);\n\n /* discard the thing */\n void hashmap_close(struct hashmap *map);\n\nWe should be able to use these in \"git log\" and friends where Dscho added\nthe hook in his git-notes topic.\n\nI am hoping that I could eventually rewrite rerere to use something like\nthis, so that rerere database can be shared, just like the way notes can\nbe shared, across repositories.\n"},{"id":"104061","messageId":"20090210190909.GS30949@spearce.org","threadId":"17680","inReplyTo":"7vocxam96s.fsf@gitster.siamese.dyndns.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-02-10T19:09:09Z","receivedAt":"2009-02-10T19:09:09Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> \n> I wonder if we can solve this by introducing a local cache that is a flat\n> file that looks like:\n> \n> magic number for /usr/bin/file\n\nDon't forget a version number. Waste 4 bytes now and its easier\nto change the format in the future if we need to.\n\n> tree object SHA-1 the file caches\n> Number of entries in this file\n> 256 fan-out offsets into this file\n> N entries of , sorted\n> Checksum of the file itself\n> \n> and use it when availble (otherwise optionally create it upon the first\n> lookup). The file can be used by mmaping it and then doing a newton\n> raphson or binary search similar to the way patch-ids.c does.\n\nYup. Sort of my thoughts when I was thinking about that external\nindex for a \"git database\".\n\nI was considering a much more complex file layout though; one that\nwould permit editing without completely recopying the file every\ntime something changes.\n\nMore or less a traditional block oriented on-disk M-tree, with\ncopy-on-write semantics for the blocks. This would permit us to\nquickly append onto the end of the file with new updates, and then\nperiodically copy and flatten out the the file as necessary to\nreclaim the prior dead space.\n\nE.g.:\n\n magic number\n version\n [intermediate blocks ...]\n [leaf blocks...]\n root block\n\nWriters would append modified leaf and intermediate blocks as\nnecessary to the end of the file, then append a new root block.\n\nReaders would read the file tail and verify it is a root, then scan\nwith a traditional M-tree search algorithm.\n\nIf the root block has a \"magic block header\" and a strong checksum\nat the tail of the block, readers can concurrently read while a\nwriter is appending. Any invalid root block just means the reader\nis seeing the middle of a write, or an aborted write, and should\nscan backwards to locate the prior valid root.\n\nIf the root block also has a commit SHA-1 indicating which commit\nthat root become valid under, a reader can decide if that root\nmight give it answers which aren't correct for the current value of\nthe notes history it is reading, and scan backwards for some older\nroot block. We could accelerate that by including the file offset\nof the prior root block in each new root.\n\nGC compacting the file is just a matter of write-locking the file\nto block out a new writer, then traversing the current root and\ncopying all blocks that are reachable.\n\n\n\n> I am hoping that I could eventually rewrite rerere to use something like\n> this, so that rerere database can be shared, just like the way notes can\n> be shared, across repositories.\n\nOoh, great idea. If we could toss rerere data into something that\ncan be transported around, and efficiently accessed. I like it.\n\n-- \nShawn.\n"},{"id":"104076","messageId":"alpine.DEB.1.00.0902102210140.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"7vocxam96s.fsf@gitster.siamese.dyndns.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-10T21:10:43Z","receivedAt":"2009-02-10T21:10:43Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 10 Feb 2009, Junio C Hamano wrote:\n\n> \"Shawn O. Pearce\" writes:\n> \n> > Johannes Schindelin wrote:\n> >> On Tue, 10 Feb 2009, Junio C Hamano wrote:\n> >> > \n> >> > I could do a revert on 'master' if it is really needed, but I found that\n> >> > the above reasoning is a bit troublesome. The thing is, if a tree to hold\n> >> > the notes would be huge to be unmanageable, then it would still be huge to\n> >> > be unmanageable if you split it into 256 pieces.\n> >> \n> >> The thing is, a tree object of 17 megabyte is unmanagably large if you \n> >> have to read it whenever you access even a single node. Having 256 trees \n> >> instead, each of which is about 68 kilobyte is much nicer.\n> >\n> > See my other email on this thread; we'd probably need to unpack\n> > all 256 subtrees *anyway* due to the distribution of SHA-1 names\n> > for commits.\n> \n> I wonder if we can solve this by introducing a local cache that is a flat\n> file that looks like:\n> \n> magic number for /usr/bin/file\n> tree object SHA-1 the file caches\n> Number of entries in this file\n> 256 fan-out offsets into this file\n> N entries of , sorted\n> Checksum of the file itself\n> \n> and use it when availble (otherwise optionally create it upon the first\n> lookup). The file can be used by mmaping it and then doing a newton\n> raphson or binary search similar to the way patch-ids.c does.\n\nOr we could use an on-disk hashmap. Oh, wait...\n\nCiao,\nDscho\n"},{"id":"104090","messageId":"200902102316.56348.trast@student.ethz.ch","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902102210140.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2009-02-10T22:16:49Z","receivedAt":"2009-02-10T22:16:49Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Johannes Schindelin wrote:\n> Or we could use an on-disk hashmap. Oh, wait...\n\nWhile reading this thread, I sure wondered ... why don't we use the\none on-disk fast access structure we already have: the index?\n\nSure, one problem is that the index reading code is inherently written\nfor a single index state. However, all notes consumers I can\ncurrently think of (show, log, anything that displays commit messages)\ndo not have to access the \"real\" index.\n\nWe'd immediately get lots of tool support for free. Presumably the\nreal index code has been optimized very well, so it should perform\nwell. Perhaps there could even be some definition of a NOTES_HEAD\nthat tracks the current (albeit not checked out, that would be insane)\nstate.\n\n\nOn a tangent, I'd really like to see a feature that lets us have\nseveral sets of notes (by whatever mechanism). Displaying them as\n\"Notes from remotes/trast/mailnotes\" or similar should be ok. Given\nthat even before notes are in any release we already have at least two\nprojects working with mass annotations, it doesn't take much of a\ncrystal ball to see that the current one-note restriction will be a\nlimitation.\n\nAt a (*very*) cursory glance at read-cache.c, it seems that there is\neven support for having several index structures in memory at once,\nmaking this easy. And it looks like reading the cache is more or less\nmemcpy() if xmmap() is fast (Windows would suffer once again).\n\n\nThen again I joined this discussion very late so feel free to ignore\nmy ramblings.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"104092","messageId":"200902102326.49780.trast@student.ethz.ch","threadId":"17680","inReplyTo":"200902102316.56348.trast@student.ethz.ch","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2009-02-10T22:26:46Z","receivedAt":"2009-02-10T22:26:46Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast wrote:\n> Sure, one problem is that the index reading code is inherently written\n> for a single index state. However, all notes consumers I can\n> currently think of (show, log, anything that displays commit messages)\n> do not have to access the \"real\" index.\n[...]\n> At a (*very*) cursory glance at read-cache.c, it seems that there is\n> even support for having several index structures in memory at once,\n> making this easy. And it looks like reading the cache is more or less\n> memcpy() if xmmap() is fast (Windows would suffer once again).\n\nNote to self: do not write mail on bus, then pick up later at home.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"104094","messageId":"7vljsdly7f.fsf@gitster.siamese.dyndns.org","threadId":"17680","inReplyTo":"200902102316.56348.trast@student.ethz.ch","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-10T22:32:52Z","receivedAt":"2009-02-10T22:32:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Johannes Schindelin wrote:\n>> Or we could use an on-disk hashmap. Oh, wait...\n>\n> While reading this thread, I sure wondered ... why don't we use the\n> one on-disk fast access structure we already have: the index?\n\nSince when the index has become a on-disk fast access structure?\n\n> Sure, one problem is that the index reading code is inherently written\n> for a single index state.\n\nThat's wrong, but because the index is not a on-disk fast access structure\nto begin with, the incorrect statement about it is excused ;-)\n"},{"id":"104131","messageId":"4992267E.6050707@vilain.net","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902092200170.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-02-11T01:14:38Z","receivedAt":"2009-02-11T01:14:38Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Hi,\n>\n> Shawn triggered some well needed thinking on my part about the notes \n> implementation. At the moment, we have flat directory structure, and read \n> all of them in one go (when needed).\n>\n> I think we should support that, because it is relatively easy to generate \n> that kind of trees for small-scale applications.\n>\n> However, I think there is also a benefit to handle fan-out directory \n> structures, too: they scale much nicer.\n>\n> If the commit name was not found as a filename, it could be searched in \n> whatever subdirectory whose name is a prefix of said commit name (first \n> wins).\n> \n\nGreat idea! Glad I thought of it! ;-)\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/106715/focus=107975\n\nI hoped my approach allowed for smarter things later, such as splitting\ninto smaller buckets whenever a directory gets more than N entries or\nperiodically rebalancing if required. But the initial version is at\nleast forward thinking to support reading it.\n\nMerging them will need to be savvy of this of course.\n\nSam.\n"},{"id":"104134","messageId":"200902101958.21284.bss@iguanasuicide.net","threadId":"17680","inReplyTo":"20090210131600.GD17305@coredump.intra.peff.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Boyd Stephen Smith Jr.","fromEmail":"bss@iguanasuicide.net","sentAt":"2009-02-11T01:58:15Z","receivedAt":"2009-02-11T01:58:15Z","isPatch":false,"sender":{"key":"bss@iguanasuicide.net","avatar":"https://gravatar.com/avatar/84b95eeff194b816c1568b1339e63e4b229825298664a9037b9f1ec713ead1e3?d=mp&s=160"},"body":"On Tuesday 10 February 2009 07:16:00 you wrote:\n> On Tue, Feb 10, 2009 at 01:58:41AM -0600, Boyd Stephen Smith Jr. wrote:\n> > On Monday 09 February 2009 15:12:06 Johannes Schindelin wrote:\n> > > So I think it would be a sane plan to do the following when a commit\n> > > note is requested:\n> >\n> > So, something like a Trie data structure? I think that is a great way to\n> > store fixed-length strings from a limited alphabet with arbitrary data\n> > attached.\n>\n> I don't think a Trie quite makes sense here. We still have to look\n> linearly through each git tree (an artifact of the tree implementation).\n\nPerhaps it's not a traditional trie structure but that was the closest analogy \nI could come up with. I was actually thinking of something between a trie and \na b-tree, I think. (It has been a long time since data structures class...)\n\nThe issue, as I understand it, it that we don't have gargantuan tree objects. \nReading and writing are slow and they'd also take up way to much memory if you \nare only trying to find a few commits.\n\nSo, we figure out a maximum tree size that is reasonable, figure out a fan-out \nthat prevents the tree from growing above that size, but *dynamically* apply \nthat fan-out. I.e. if the fanout is 2 characters, and we've added notes for \nboth ff82730c and ff23abc0, then our tree would have ff/ -> some_tree_sha, but \nif we had only a note for the one one our tree would have ff82730c... -> \nsome_note_sha. Unlike .git/objects, we should probably also do dynamic fanout \nin subtrees.\n\nYes, this would require a custom merge strategy for notes to flatten -> merge \n-> canonicalize.\n\n> Or did you mean something else entirely?\n\nYeah, that.\n\nWhile I'm throwing out crazy ideas, why not makes a notes tree look just like \n.git/objects, including info and pack directories?\n-- \nBoyd Stephen Smith Jr. ,= ,-_-. =.\nbss@iguanasuicide.net ((_/)o o(\\_))\nICQ: 514984 YM/AIM: DaTwinkDaddy `-'(. .)`-'\nhttp://iguanasuicide.net/ \\_/\n\n"},{"id":"104136","messageId":"alpine.LFD.2.00.0902101825360.3590@localhost.localdomain","threadId":"17680","inReplyTo":"200902101958.21284.bss@iguanasuicide.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-02-11T02:35:52Z","receivedAt":"2009-02-11T02:35:52Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Feb 2009, Boyd Stephen Smith Jr. wrote:\n> \n> Yes, this would require a custom merge strategy for notes to flatten -> merge \n> -> canonicalize.\n\nThat sounds unnecessarily complicated. It also really sucks for the case \nyou want to optimize: small differences between trees, where you don't \nneed to even linearize the common parts.\n\nWhy not make it just a straight fixed 12-bit prefix, single-level trie.\n\nSure, if you have less than 4k objects, it's going to add an unnecessary \nindirection, and close to an extra tree object for each object. But it \nshould scale pretty well to a fairly huge numbe of notes. IOW, if you have \nless than 2^24 notes (16 million), you'll never have a tree object with \nmore than 4k entries.\n\nAnd with each tree being ~70 bytes/object (40 bytes name, 20 bytes SHA1 + \noverhead), the individual tree objects will still be a reasonable(ish) \nsize. And the fixed depth and prefix size means that merging is trivial \nand can use the normal tree merge that avoids touching common subtrees.\n\nThe default .git/objects fan-out of just 8 bits might work too, but if \nwe're thinking millions of notes (which is not entirely unreasonable), it \ngets ugly pretty fast. The reason it works ok for git is the repacking.\n\n\t\t\tLinus\n"},{"id":"104139","messageId":"499243BF.1010701@catalyst.net.nz","threadId":"17680","inReplyTo":"20090210164430.GN30949@spearce.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Sam Vilain","fromEmail":"sam.vilain@catalyst.net.nz","sentAt":"2009-02-11T03:19:27Z","receivedAt":"2009-02-11T03:19:27Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Shawn O. Pearce wrote:\n>> The point you raised earlier, that there would be a lot of ambiguity if \n>> we allow both flat and fan-out directory structures, is a valid point, \n>> though.\n> \n> Yup. The flat vs. fan-out is a problem.\n [...]\n> Notes on commits though are a hell of a problem. SHA-1 is just so\n> uniform at distributing the commits around the namespace that even\n> with just the 200 most recent commits we wind up with a commit in\n> almost every \"bucket\", assuming a two hex digit fan-out bucket like\n> the loose object directory.\n\nI think my patch from 1 Feb addressed this, at least for the operations\nit implemented.\n\nI just don't see why you need to decide up front what the split is going\nto be. Just read the next tree, descend into the closest matching tree\nuntil you find the record you are looking for and that's it. Sure, my\npatch just loads it all and throws it into a hash - this should still be\nefficient for short log operations even if the hash table ends up 1MB.\nBut why take my guess. Let's stress test it.\n\n'lorem' is the binary in the Text::Lorem Perl module. It generates a\nparagraph of random Latin text.\n\n wilber:~/src/git$ time git-log | wc -l\n 256072\n\n real 0m0.709s\n user 0m0.608s\n sys 0m0.116s\n wilber:~/src/git$ git rev-list HEAD | wc -l\n 17678\n wilber:~/src/git$ cat > my-editor\n #!/bin/sh\n\n ( lorem; echo ) > $1\n wilber:~/src/git$ chmod +x my-editor\n wilber:~/src/git$ export EDITOR=`pwd`/my-editor\n wilber:~/src/git$ export GIT_NOTES_SPLIT=2\n wilber:~/src/git$ time git-rev-list HEAD | while read rev\n > do ./git-notes.sh edit $rev; done\n fatal: unable to create '.git/refs/notes/commits.lock': File exists\n error: Ref refs/notes/commits is at\n5f0732975b4acf237912a31e7ce14aa86d2e8179 but expected\n725a2d119d2725e7d821906ad085bfbadbf43c8e\nfatal: Cannot lock the ref 'refs/notes/commits'.\n [...]\n fatal: unable to write new index file\n Could not read index\n fatal: unable to write new index file\n Could not read index\n fatal: unable to write new index file\n Could not read index\n fatal: unable to write new index file\n Could not read index\n fatal: unable to write new index file\n Could not read index\n\n real 76m16.927s\n user 43m55.909s\n sys 19m33.005s\n\nOo. Nasty errors there but never mind that for now. Obviously some\nremaining issues in the shell script.\n\nWhat did I get out of that?\n\n wilber:~/src/git$ git-ls-tree -r refs/notes/commits | wc\n 12043 48172 1144085\n wilber:~/src/git$\n\nHey well that's not too bad. Enough to be a good test. How long does\n\"git-log\" take now?\n\n wilber:~/src/git$ time ./git-log | wc -l\n 292201\n\n real 0m13.740s\n user 0m0.852s\n sys 0m0.716s\n wilber:~/src/git$ time ./git-log | wc -l\n 292201\n\n real 0m1.335s\n user 0m0.856s\n sys 0m0.512s\n\nNot bad! Cool cache performance sucked there but only a 50% slowdown\nfor reading almost twice the number of objects. Let's try 200 commits:\n\n wilber:~/src/git$ time git-log -200 | wc -l\n 2877\n\n real 0m0.027s\n user 0m0.008s\n sys 0m0.020s\n\n wilber:~/src/git$ time ./git-log -200 | wc -l\n 3477\n\n real 0m0.081s\n user 0m0.056s\n sys 0m0.020s\n\nQuite a big slowdown proportionally, but not a huge amount in absolute\nterms. And we didn't even make the builtin-log machinery smart enough\nto skip unneeded trees!\n\n> In a slightly unrelated\n> thread offlist I have been talking with Sam Vilain about using Git\n> as a database backend for tuple storage.\n [...]\n> This would make the git-notes.sh code a *lot* more complex, as you\n> can't just toss everything into an index file and then update it with\n> a single update-index call. Doing a tree split is much more work and\n> requires removing and adding back all of the affected path names.\n> (Its also perhaps unreasonable anyway to load 17,491 paths into a\n> temporary index just to twiddle a note for the latest commit.)\n\nHehe, horribly overcomplicated for this use case... many applicable\nideas though.\n\n> For the \"git database\" thing above, I've been contemplating the\n> idea of an index stored external from the Git object database.\n> Sam thinks indexes should be in the object database tree, but\n> I'm considering storing them outside entirely because we can\n> make the indexes more easily searched by a hash or binary search,\n> like pack-*.idx. Whenever the \"database ref\" gets moved we'd need\n> to run a \"sync\" utility to bring these external indexes current.\n> But they could also be more efficiently scanned.\n\nWell either way it's a file you've got to scan somehow ... guess it\ndoesn't matter much whether it's in-tree or not. I was actually saying\nthat there are some use cases where you might want to keep indexes in\nthe history and some where you don't. Keeping them in-tree is not\nnormalised, but there are good use cases for it - eg efficient retrieval\nof pre-computed aggregates that don't need to be up to the second, or\nfor instances where you want your nodes to be able to \"hit the ground\nrunning\" after synchronisation without having to reindex.\n\nFor the use case we originally talked about I don't think you'd want any\nindexes in-tree at all.\n\nBut I'd like to steer this thread well away from the database stuff I'm\ndrafting ... it's a lot more comprehensive, notes are a very simple hash\nrelationship.\n-- \nSam Vilain, Perl Hacker, Catalyst IT (NZ) Ltd.\nphone: +64 4 499 2267 PGP ID: 0x66B25843\n"},{"id":"104138","messageId":"49924642.6000609@vilain.net","threadId":"17680","inReplyTo":"alpine.LFD.2.00.0902101825360.3590@localhost.localdomain","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-02-11T03:30:10Z","receivedAt":"2009-02-11T03:30:10Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> That sounds unnecessarily complicated. It also really sucks for the case \n> you want to optimize: small differences between trees, where you don't \n> need to even linearize the common parts.\n>\n> Why not make it just a straight fixed 12-bit prefix, single-level trie.\n> \n\nMy solution suffers from that problem too, but I personally still don't\nthink that the answer is to fix the trie boundary.\n\nThe only case where it hurts is when you want to merge. Nothing else\nshould care. So, if a merge of these note trees sees two different trie\nsizes then it can convert the shorter one to the longer length first,\nand then try the merge again. So you get the pain, but only once. And\nwhen a project decides that its split is too small, it can split then\nand it should \"silently\" spread out to others.\n\nSam.\n"},{"id":"104140","messageId":"alpine.LFD.2.00.0902101953170.3590@localhost.localdomain","threadId":"17680","inReplyTo":"49924642.6000609@vilain.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-02-11T03:54:39Z","receivedAt":"2009-02-11T03:54:39Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 11 Feb 2009, Sam Vilain wrote:\n> \n> The only case where it hurts is when you want to merge. Nothing else\n> should care. So, if a merge of these note trees sees two different trie\n> sizes then it can convert the shorter one to the longer length first,\n> and then try the merge again. So you get the pain, but only once. And\n> when a project decides that its split is too small, it can split then\n> and it should \"silently\" spread out to others.\n\nBut what's the advantage of the added complexity?\n\nThe non-fixed trie only helps for the case that doesn't matter - just a \nfew annotations. If you have a thousand annotations or less, you _really_ \ndon't care. Whatever you do will be fine.\n\nSo the whole thing only matters once you have tens of thousands of \nentries, and then you do want to have fan-out. No?\n\n\t\t\tLinus\n"},{"id":"104141","messageId":"49925CAB.505@vilain.net","threadId":"17680","inReplyTo":"alpine.LFD.2.00.0902101953170.3590@localhost.localdomain","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-02-11T05:05:47Z","receivedAt":"2009-02-11T05:05:47Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Linus Torvalds wrote:\n>> The only case where it hurts is when you want to merge. Nothing else\n>> should care. So, if a merge of these note trees sees two different trie\n>> sizes then it can convert the shorter one to the longer length first,\n>> and then try the merge again. So you get the pain, but only once. And\n>> when a project decides that its split is too small, it can split then\n>> and it should \"silently\" spread out to others.\n>> \n>\n> But what's the advantage of the added complexity?\n>\n> The non-fixed trie only helps for the case that doesn't matter - just a \n> few annotations. If you have a thousand annotations or less, you _really_ \n> don't care. Whatever you do will be fine.\n>\n> So the whole thing only matters once you have tens of thousands of \n> entries, and then you do want to have fan-out. No?\n> \n\nYeah. I see your point and you may be right, that a 12/28 split hurts\nno-one, if we take this to the benchmarks. There's certainly savings in\nterms of total object count for the small users by using a smaller split.\n\nI just already wrote the code to handle an arbitrary split for the\nfeatures written so far[1]. If *I* can write it, in C, it means it must\nnot be that complicated ;-)\n\nSo it comes down to how complicated things are when merging happens. If\n12 is fixed in stone this is simple, because there are no chances for\ndiscrepancies. But refs/notes/commits still needs special treatment to\nbe fetched, because it is not under refs/heads/* and you wouldn't\nnormally have a working tree to resolve conflicts.\n\nSo I think probably the most productive thing to do is for me to write\nthe code to handle the merge as I described above, once the code to\nhandle pulling in - and merging - notes at 'git fetch' time is written.\nThen we can see whether it's that much of a complication.\n\nTo bench this we need the current builtin-log implementation to be\nre-written to be lazy. Which means we can't put it in the next release\nunless someone writes that. However my proposal means that we can\nrelease as we are and not care, and let some code - which I hope I have\nshown isn't *that* complicated, really - deal with it in a later\nrelease, and not break backwards compatibility.\n\nSam.\n\n1. see message <1233455960.17688.122.camel@maia.lan>\n"},{"id":"104180","messageId":"alpine.DEB.1.00.0902111329030.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"49925CAB.505@vilain.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-11T12:35:12Z","receivedAt":"2009-02-11T12:35:12Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 11 Feb 2009, Sam Vilain wrote:\n\n> I just already wrote the code to handle an arbitrary split for the \n> features written so far[1]. If *I* can write it, in C, it means it must \n> not be that complicated ;-)\n\nI think I either missed your mail or had to ignore it due to too much day \njob work.\n\nIt is a good first step, of course the next step would be to load the \ntrees on-demand.\n\nOh, and the best approach to handle the \"to Trie or not to Trie\" question \nwould be to be strict in what we emit (12/28 it seems, by authority of \nLinus), and liberal in what we accept, IMHO. That is, accept whatever \npartition of the SHA-1, stopping on the first we found (smaller number of \nslashes, or when that is equal, the smaller first prefixes).\n\nWe can always discuss ways to handle merging later, I guess.\n\nCiao,\nDscho\n"},{"id":"104287","messageId":"20090211200227.GA27961@coredump.intra.peff.net","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902102210140.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-02-11T20:02:27Z","receivedAt":"2009-02-11T20:02:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 10, 2009 at 10:10:43PM +0100, Johannes Schindelin wrote:\n\n> > I wonder if we can solve this by introducing a local cache that is a flat\n> > file that looks like:\n> [...]\n> Or we could use an on-disk hashmap. Oh, wait...\n\nThat was my first thought, as well. Maybe your original implementation\nwasn't so bad, after all. :)\n\nI searched through the archive to find a list of criticisms, but I\ndidn't see any. So I guess the problem was just a concern that it might\nend up too complex.\n\n-Peff\n"},{"id":"104294","messageId":"alpine.DEB.1.00.0902112152270.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"20090211200227.GA27961@coredump.intra.peff.net","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-11T20:57:23Z","receivedAt":"2009-02-11T20:57:23Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 11 Feb 2009, Jeff King wrote:\n\n> On Tue, Feb 10, 2009 at 10:10:43PM +0100, Johannes Schindelin wrote:\n> \n> > > I wonder if we can solve this by introducing a local cache that is a flat\n> > > file that looks like:\n> > [...]\n> > Or we could use an on-disk hashmap. Oh, wait...\n> \n> That was my first thought, as well. Maybe your original implementation\n> wasn't so bad, after all. :)\n> \n> I searched through the archive to find a list of criticisms, but I\n> didn't see any. So I guess the problem was just a concern that it might\n> end up too complex.\n\nNope, the issue was that it would take too long to recreate IIRC.\n\nBTW I am no longer a fan of the on-disk cache; I think it is an ugly \nsolution to a problem that should be solved without ugliness using a \nflexible directory layout in the note ref' tree.\n\nI mean, we really can allow different directory layouts as Sam described, \nwith a few benefits, and only slight downsides. If we support multiple \nlevels anyway, the code to allow arbitrary splits is not complicated (see \nSam's patch).\n\nEven the merging should not pose any problem at all; we need a custom \nmerge driver anyway, and there is no reason whatsoever why we should not \njust teach the merge driver to remove the slashes before comparing the \nfilie names.\n\nAt edit time, we can afford to perform a check that is a little more \nexpensive than it would have been otherwise.\n\nCiao,\nDscho\n"},{"id":"104299","messageId":"7vljscd695.fsf@gitster.siamese.dyndns.org","threadId":"17680","inReplyTo":"alpine.DEB.1.00.0902112152270.10279@pacific.mpi-cbg.de","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-11T21:16:06Z","receivedAt":"2009-02-11T21:16:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Even the merging should not pose any problem at all; we need a custom \n> merge driver anyway, and there is no reason whatsoever why we should not \n> just teach the merge driver to remove the slashes before comparing the \n> filie names.\n\nOnce you start talking about \"remove the slashes\", you are assuming that\nthe custom merge algorithm must look at *all the paths* in the two trees\nbeing merged, and it is a sign that your thinking is so trapped in the\ninefficient way the current merge-recursive and unpack-trees based merge\nworks, and cannot think about the possibility that there could be more\nefficient way to do merges. Not very good.\n\nIf you have a fixed boundary and if most subtrees are the same between two\nnotes during a merge, we can do the same optimization as we do for two\ninput \"diff-tree\" codepath. If the top of a subtree matches, we do not\neven have to look at their subtree. But that is true only if you do not\nremove the slashes and allow a random hierarchy.\n"},{"id":"104312","messageId":"alpine.DEB.1.00.0902120002241.10279@pacific.mpi-cbg.de","threadId":"17680","inReplyTo":"7vljscd695.fsf@gitster.siamese.dyndns.org","subject":"Re: RFC: Flat directory for notes, or fan-out? Both!","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-11T23:05:30Z","receivedAt":"2009-02-11T23:05:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 11 Feb 2009, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > Even the merging should not pose any problem at all; we need a custom \n> > merge driver anyway, and there is no reason whatsoever why we should \n> > not just teach the merge driver to remove the slashes before comparing \n> > the filie names.\n> \n> Once you start talking about \"remove the slashes\", you are assuming that \n> the custom merge algorithm must look at *all the paths* in the two trees \n> being merged, and it is a sign that your thinking is so trapped in the \n> inefficient way the current merge-recursive and unpack-trees based merge \n> works, and cannot think about the possibility that there could be more \n> efficient way to do merges. Not very good.\n> \n> If you have a fixed boundary and if most subtrees are the same between \n> two notes during a merge, we can do the same optimization as we do for \n> two input \"diff-tree\" codepath. If the top of a subtree matches, we do \n> not even have to look at their subtree. But that is true only if you do \n> not remove the slashes and allow a random hierarchy.\n\nWell, I think in the case of notes, we have to optimize for random access \nof dozens of blobs rather than for merging. I was well aware that the \nmerging is more expensive when the hierarchy is not defined a priori.\n\nCiao,\nDscho\n"}]}