{"thread":{"id":"7279","subject":"Re: tree sorting..","startedAt":"2007-03-16T23:13:29Z","lastAt":"2007-03-16T23:35:49Z","messageCount":2,"participants":["Shawn O. Pearce","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37284","messageId":"20070316231329.GA4508@spearce.org","threadId":"7279","inReplyTo":"Pine.LNX.4.64.0703160941290.3816@woody.linux-foundation.org","subject":"Re: tree sorting..","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-16T23:13:29Z","receivedAt":"2007-03-16T23:13:29Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"[adding in the list]\nLinus Torvalds <torvalds@linux-foundation.org> wrote:\n> On irc:\n> \n>   spearce: personally the utf-8 commit encoding mess is less of a mess \n> \tthen the \"lets sort trees with / after their name, but not store \n> \tthem that way!\".\n> \n> umm, we *do* store them that way, so I'm a bit confused?\n\nSorry, hasty IRC messages don't always read very well.  What I was\ntrying to say was that the decision to sort entries in the tree\nthe way that they are sorted is an annoying problem.\n\nEntries in a tree must be unique by their name; that is I cannot have\n\"foo\" as both a file and as a subtree.  An excellent constraint\nto have.  But the position of the entry \"foo\" is different for a\nfile than for a subtree, as the subtree \"foo\" is sorted as though\nit were \"foo/\" while the file \"foo\" is sorted by just \"foo\".\n\nSo there's additional complexity imposed.  I cannot just binary\nsearch a tree and locate \"foo\", as \"foo\" could appear at one of two\ndifferent positions in that tree.  Sure I might know that the user\nis asking for \"foo/\" (as the input was \"foo/bar\"); but what if I\nsearch for \"foo/\" and in this particular tree there is a \"foo\",\nbut its a file?  I cannot conclude that foo doesn't exist here\nwithout searching *again* for \"foo\" on its own.  Likewise if the\nuser asks for \"foo\" (no trailing slash).\n\n\nThe entire reason this happened is hysterical raisins.  Your first\ndraft of Git had trees as one flat structure, sorting complete\npaths by their memcmp result.  Which is dead simple and worked.\n\nBut folks pointed out it would be more scalable to store each\ndirectory on its own, as not every directory changes on each commit.\nSo you split the trees up in the object database, but you left the\nindex as-is.\n\nThis meant that as you were walking the index you found the subtree\n\"foo\" where \"foo/\" appears, not where \"foo\" appears.  In my opinion\nit is a *BUG* that you did not correct the sorting to remove the\ntrailing slash when you split the index down into individual tree\nobjects.\n\nNow we are stuck with it.\n\nAnd that flat index?  It worked well to get us started, sure, but\nthe whole cache_tree thing that Junio wedged in was specifically to\naddress the scability of the index on larger repositories.  We don't\nneed to recreate (or examine) trees for parts that didn't change.\n\nWasn't that the original scability argument as to *why* you broke\nout the tree objects in the ODB apart?  How was the index exempt\nfrom that?\n\nBasically you cut a corner way back by not also splitting the\nindex up by subtree when you split the ODB \"tree\" up by subtree,\nand we've been paying for it ever since.\n\n\nI'm personally annoyed about it because I've fought this problem\nseveral times.  In jgit (my Java Git implementation) I can't do a\nsimple binary search on a tree's contents, because of the issues\nstated above.  In git-fast-import I can't do a simple binary search,\nbecause of the issues stated above.  There I also have to resort a\ntree *twice* to generate the delta, because a path name might have\nchanged type and thus changed positions within the tree.\n\nLast night we found a bug where you can't do a two-head merge with\n`read-tree -m` when \"A\" is a subdirectory in this branch but is a\nfile in the branch you are switching to.  This is difficult to fix\nbecause within the index we cannot simply do a type comparsion of\n\"A\" and \"A\" to see if they are the same...  Junio is trying to\npatch around it, but it ain't pretty.\n\nWith the new pack v4 concept of a 6 byte fixed-width tree record,\nwe could actually do binary search within a tree, rather than\nlinear search.  But again, its uh, more difficult than it probably\nshould be.\n\n\nWe all do things that in hindsight could have been done differently.\nI *definately* would rather have the Git we have today, than to\nnot have one at all.  I'm extremely grateful that you and several\nothers took time away from Linux kernel hacking to get this project\nstarted, and kept a practical focus throughout, ensuring we would\nhave a useful tool.\n\nI just get frustrated with it sometimes.  ;-)\n\n-- \nShawn.\n"},{"id":"37289","messageId":"Pine.LNX.4.64.0703161632270.3910@woody.linux-foundation.org","threadId":"7279","inReplyTo":"20070316231329.GA4508@spearce.org","subject":"Re: tree sorting..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T23:35:49Z","receivedAt":"2007-03-16T23:35:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Shawn O. Pearce wrote:\n> \n> The entire reason this happened is hysterical raisins.  Your first\n> draft of Git had trees as one flat structure, sorting complete\n> paths by their memcmp result.  Which is dead simple and worked.\n\nNo. \n\nIt's *not* historical reasons. That's what I tried to explain.\n\nIt's absolutely *required*. Not because of the old flat layout, but \nbecause we want read-tree to translate 1:1 into the index.\n\nAnd the index is a flat file. And it *needs* to be a flat file, because we \nneed to open it and read it efficiently. If it wasn't a flat file, we'd \nhave all the index operations taking as long as the tree operations take.\n\n> Now we are stuck with it.\n\nNo. How you need to accept it. It's that easy. It's not \"stuck\". It's \n\"correct\".\n\nThat's why I reacted to your irc thing. You seemed to think (and still \napparently do) that the sorting is some messy mistake. It's anything but.\n\nSo yes, \"foo\" is *different* from \"foo/\". You just need to realize that \nthey are two totally different entries. They have absolutely no \nrelationship what-so-ever with each other, except that you obviously must \nnot add one when the other exists.\n\n\t\tLinus\n"}]}