{"thread":{"id":"9767","subject":"Calculating tree nodes","startedAt":"2007-09-04T02:13:26Z","lastAt":"2007-09-06T05:21:13Z","messageCount":27,"participants":["Jon Smirl","Shawn O. Pearce","Johannes Schindelin","David Tweed","Martin Langhoff","Junio C Hamano","Andreas Ericsson","Daniel Hulme"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"52382","messageId":"9e4733910709031913q278cb9dbp441756afb28607c6@mail.gmail.com","threadId":"9767","inReplyTo":null,"subject":"Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T02:13:26Z","receivedAt":"2007-09-04T02:13:26Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"When I change a file it creates a new object with a new SHA. This new\nSHA causes the tree node pointing to it to change. Changing the tree\nnode forces its parent to change and so on. Of course git batches all\nof the changes together into a commit so that this ripple effect\ndoesn't happen for every file. But every commit causes a new root tree\nnode to be created, right?\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52384","messageId":"20070904025153.GS18160@spearce.org","threadId":"9767","inReplyTo":"9e4733910709031913q278cb9dbp441756afb28607c6@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-09-04T02:51:54Z","receivedAt":"2007-09-04T02:51:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> When I change a file it creates a new object with a new SHA. This new\n> SHA causes the tree node pointing to it to change. Changing the tree\n> node forces its parent to change and so on. Of course git batches all\n> of the changes together into a commit so that this ripple effect\n> doesn't happen for every file. But every commit causes a new root tree\n> node to be created, right?\n\nOnly if at least one file (or tree) differed. This may not be the\ncase if you do a merge with the ours merge strategy, but these are\nvery rare. So you can pretty much just say that yes, every commit\ncauses a new root tree to be created.\n\nUsually the smallest number of objects created per commit is 3:\n\n - the new commit\n - the new root tree\n - the new blob for a file in the root directory\n\nThe number increases as more files are modified or if they are in\nsubdirectories of the root.\n\n-- \nShawn.\n"},{"id":"52386","messageId":"9e4733910709032026s7f94eed9h25d5165840cc38d2@mail.gmail.com","threadId":"9767","inReplyTo":"20070904025153.GS18160@spearce.org","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T03:26:30Z","receivedAt":"2007-09-04T03:26:30Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Are tree objects really needed?\n\n1) Make the path an attribute of the file object.\n2) Commits are simply a list of all the objects that make up the commit.\nSort the SHAs in the commit and delta them.\n\nThis is something that has always bugged me about file systems. File\nsystems force hierarchical naming due to their directory structure.\nThere is no reason they have to work that way. Google is an example of\na giant file system that works just fine without hierarchical\ndirectories. The full path should be just another attribute on the\nfile. If you want a hierarchical index into the file system you can\ngenerate it by walking the files or using triggers. But you could also\ndelete the hierarchical directory and replace it with something else\nlike a full text index. Directories would become a computationally\ngenerated cache, not a critical part of the file system. But this is a\ngit list so I shouldn't go too far off into file system design.\n\nGit has picked up the hierarchical storage scheme since it was built\non a hierarchical file system. I don't this this is necessarily a good\nthing moving forward.\n\nIf we really need tree objects they could become a new class of\ncomputationally generated objects that could be deleted out of the\ndatabase at any time and recreated. For example if you think of the\nfile objects as being in a table, inserting a new row into this table\nwould compute new tree objects (an index).\n\nIndex is the key here, we may want other kinds of indexes in the\nfuture. It was the mail about auto-generating the Maintainers list\nthat caused me to think about this. If file objects are a table with\ntriggers, building a hierarchical index for the Maintainers field\ndoesn't make sense.\n\nThese are just some initial thoughts on a different way to view the\ndata git is storing. Thinking about it as a database with fields and\nindexes built via triggers may change the way we want to structure\nthings.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52387","messageId":"Pine.LNX.4.64.0709040439070.28586@racer.site","threadId":"9767","inReplyTo":"9e4733910709032026s7f94eed9h25d5165840cc38d2@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-09-04T03:40:09Z","receivedAt":"2007-09-04T03:40:09Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 3 Sep 2007, Jon Smirl wrote:\n\n> Are tree objects really needed?\n\nYes. For performance reasons, since a simple commit would kill you in any \nreasonably sized repo.\n\nHth,\nDscho\n"},{"id":"52388","messageId":"9e4733910709032054y4407ce62o6b21935502bfacdb@mail.gmail.com","threadId":"9767","inReplyTo":"Pine.LNX.4.64.0709040439070.28586@racer.site","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T03:54:00Z","receivedAt":"2007-09-04T03:54:00Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/3/07, Johannes Schindelin wrote:\n> Hi,\n>\n> On Mon, 3 Sep 2007, Jon Smirl wrote:\n>\n> > Are tree objects really needed?\n>\n> Yes. For performance reasons, since a simple commit would kill you in any\n> reasonably sized repo.\n\nThat's not an obvious conclusion. A new commit is just a series of\nedits to the previous commit. Start with the previous commit, edit it,\ndelta it and store it. Storing of the file objects is the same. Why\nisn't this scheme fast than the current one?\n\n\n>\n> Hth,\n> Dscho\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52389","messageId":"e1dab3980709032119r381f7a91ia84ba09039c21be1@mail.gmail.com","threadId":"9767","inReplyTo":"9e4733910709032026s7f94eed9h25d5165840cc38d2@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2007-09-04T04:19:49Z","receivedAt":"2007-09-04T04:19:49Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On 9/4/07, Jon Smirl wrote:\n> Git has picked up the hierarchical storage scheme since it was built\n> on a hierarchical file system.\n\nFWIW my memory is that initial git used path-to-blob lists (as you're\ndescribing but without delta-ing) and tree nodes were added after a\ncouple of weeks, the motivation _at the time_ being they were a\nnatural way to dramatically reduce the size of repos.\n\nOne of the nice things about tree nodes is that for doing a diff\nbetween versions you can, to overwhelming probability, decide\nequality/inequality of two arbitrarily deep and complicated subtrees\nby comparing 40 characters, regardless of how remote and convoluted\ntheir common ancestry. With delta chains don't you end up having to\ntrace back to a common \"entry\" in the history? (Of course, I don't\nknow how packs affect this - presumably there's some delta chasing to\nget to the bare objects as well.)\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"we had no idea that when we added templates we were adding a Turing-\ncomplete compile-time language.\" -- C++ standardisation committee\n"},{"id":"52390","messageId":"46a038f90709032121v54454c6fi500ee15497eec85c@mail.gmail.com","threadId":"9767","inReplyTo":"9e4733910709032054y4407ce62o6b21935502bfacdb@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2007-09-04T04:21:47Z","receivedAt":"2007-09-04T04:21:47Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 9/4/07, Jon Smirl wrote:\n> > Yes. For performance reasons, since a simple commit would kill you in any\n> > reasonably sized repo.\n>\n> That's not an obvious conclusion. A new commit is just a series of\n\nHi Jon!\n\nIf you search the archives you'll find Linus explaining that the\ninitial git had all the directory structure in one single \"tree\"\nobject that held all the paths, not matter how deep. The problem with\nthat was taht every commit generated a huge new tree object, so he\nswitched to the current \"nested trees\" structure, which also has the\nnice feature of speeding up diffs/merges if whole subtrees haven't\nchanged.\n\n> edits to the previous commit. Start with the previous commit, edit it,\n> delta it and store it. Storing of the file objects is the same. Why\n> isn't this scheme fast than the current one?\n\nI think you're a bit confused between 2 different things:\n\n - git is _snapshot_ based, so every commit-tree-blob set is\ncompletely independent. The \"canonical\" storage is each of those\ngzipped in .git/objects\n - however, for performance and on-disk-footprint, we delta them (very\nefficiently I hear)\n\nSo if you ask the GIT APIs about a tree, you end up dealing with the\nnested trees I describe. Similarly, if you ask for a blob, you get the\nblob. But internally git _is_ delta-compressing them.\n\nIt's not compressing them immediately -- only when you run git gc. But\nfrom an API perspective, you don't have to worry about that.\n\nHTH\n\n\nmartin\n"},{"id":"52391","messageId":"7vmyw3835y.fsf@gitster.siamese.dyndns.org","threadId":"9767","inReplyTo":"9e4733910709032054y4407ce62o6b21935502bfacdb@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-04T04:28:41Z","receivedAt":"2007-09-04T04:28:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jon Smirl\" writes:\n\n>> Yes. For performance reasons, since a simple commit would kill you in any\n>> reasonably sized repo.\n>\n> That's not an obvious conclusion. A new commit is just a series of\n> edits to the previous commit. Start with the previous commit, edit it,\n> delta it and store it. Storing of the file objects is the same. Why\n> isn't this scheme fast than the current one?\n\nI think you seem to be forgetting about tree comparison.\n\nWith a large project that has a reasonable directory structure\n(i.e. not insanely narrow), a commit touches isolated subparts\nof the whole tree. Think of an architecture specific patch to\nthe Linux kernel touching only include/asm-i386 and arch/i386\ndirectories.\n\nBeing able to cull an entire subdirectory (e.g. drivers/ which\nhas 5700 files underneath) by only looking at the tree SHA-1 of\nthe containing tree is a _HUGE_ win.\n\nAnd this is not just about two tree comparison. When you say:\n\n\tgit log v2.6.20 -- arch/i386/\n\nwhat you are seeing is a simplified history that consists of\ncommits that touch only these paths. How would we determine if\na commit touch these paths efficiently? By comparing the \"i386\"\nentry in tree objects for $commit^:arch and $commit:arch. You\ndo not have to look inside arch/i386/ trees to see if any of the\n330 files in it is different. You just check a single SHA-1\npair.\n"},{"id":"52392","messageId":"9e4733910709032237y65ccafdai4889078533908fb0@mail.gmail.com","threadId":"9767","inReplyTo":"46a038f90709032121v54454c6fi500ee15497eec85c@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T05:37:23Z","receivedAt":"2007-09-04T05:37:23Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Martin Langhoff wrote:\n> On 9/4/07, Jon Smirl wrote:\n> > > Yes. For performance reasons, since a simple commit would kill you in any\n> > > reasonably sized repo.\n> >\n> > That's not an obvious conclusion. A new commit is just a series of\n>\n> Hi Jon!\n>\n> If you search the archives you'll find Linus explaining that the\n> initial git had all the directory structure in one single \"tree\"\n> object that held all the paths, not matter how deep. The problem with\n> that was taht every commit generated a huge new tree object, so he\n> switched to the current \"nested trees\" structure, which also has the\n> nice feature of speeding up diffs/merges if whole subtrees haven't\n> changed.\n\nIn my scheme the commit is only a list of SHA's. The paths are stored\nas attributes of the file objects. Commits are just edits to the list\nof SHA's in the commit objects. If these lists are kept sorted, then\nthe delta should be tiny. Just the info on the adds/deletes to the\nlist.\n\nThis is very different that a single tree blob that contains all of the paths.\n\nDiffing two trees in the scheme is quite fast. Just get their commit\nobjects into RAM and compare the lists of SHAs.\n\n> > edits to the previous commit. Start with the previous commit, edit it,\n> > delta it and store it. Storing of the file objects is the same. Why\n> > isn't this scheme fast than the current one?\n>\n> I think you're a bit confused between 2 different things:\n>\n> - git is _snapshot_ based, so every commit-tree-blob set is\n> completely independent. The \"canonical\" storage is each of those\n> gzipped in .git/objects\n> - however, for performance and on-disk-footprint, we delta them (very\n> efficiently I hear)\n\nThe systems are essential the same with a little reorganization. In\nthe current system the paths and SHA for a commit are spread over the\ntree nodes.\n\nIn my scheme the path info is moved into the file object nodes and the\nSHA list is in the commit node.\n\ngit still works exactly as it has before. I just moved things around\nin the storage system. The only thing that should be impacted is\nperformance.\n\n\n>\n> So if you ask the GIT APIs about a tree, you end up dealing with the\n> nested trees I describe. Similarly, if you ask for a blob, you get the\n> blob. But internally git _is_ delta-compressing them.\n>\n> It's not compressing them immediately -- only when you run git gc. But\n> from an API perspective, you don't have to worry about that.\n>\n> HTH\n>\n>\n> martin\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52396","messageId":"9e4733910709032250r1198379cmafd4e14fd330513b@mail.gmail.com","threadId":"9767","inReplyTo":"7vmyw3835y.fsf@gitster.siamese.dyndns.org","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T05:50:21Z","receivedAt":"2007-09-04T05:50:21Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Junio C Hamano wrote:\n> \"Jon Smirl\" writes:\n>\n> >> Yes. For performance reasons, since a simple commit would kill you in any\n> >> reasonably sized repo.\n> >\n> > That's not an obvious conclusion. A new commit is just a series of\n> > edits to the previous commit. Start with the previous commit, edit it,\n> > delta it and store it. Storing of the file objects is the same. Why\n> > isn't this scheme fast than the current one?\n>\n> I think you seem to be forgetting about tree comparison.\n>\n> With a large project that has a reasonable directory structure\n> (i.e. not insanely narrow), a commit touches isolated subparts\n> of the whole tree. Think of an architecture specific patch to\n> the Linux kernel touching only include/asm-i386 and arch/i386\n> directories.\n>\n> Being able to cull an entire subdirectory (e.g. drivers/ which\n> has 5700 files underneath) by only looking at the tree SHA-1 of\n> the containing tree is a _HUGE_ win.\n\nIn my scheme you have all of the SHAs for the commit in RAM because\nthe are contained in the commit and you have the commit in RAM. It\ntake microseconds to compare these two lists in RAM.\n\nThe current scheme is doing disk accesses to get those tree nodes so\nof course it is a win to cull the 5700 files.\n\n>\n> And this is not just about two tree comparison. When you say:\n>\n> git log v2.6.20 -- arch/i386/\n>\n> what you are seeing is a simplified history that consists of\n> commits that touch only these paths. How would we determine if\n> a commit touch these paths efficiently? By comparing the \"i386\"\n> entry in tree objects for $commit^:arch and $commit:arch. You\n> do not have to look inside arch/i386/ trees to see if any of the\n> 330 files in it is different. You just check a single SHA-1\n> pair.\n\nIt's more than just comparing a SHA, you have to do disk accesses to\nretrieve the SHA.\n\nI'm proposing that we only really need commit and file objects. I also\nmentioned that if you think of the file objects as a table you could\nuse triggers to build cached indexes. To get performance back to the\ncurrent level we may want to construct some of these indexes. We need\nto explore the scheme more before we can figure out the best cached\nindexes to build.\n\nRight now we only have a single index type, the tree nodes. And it's a\npermanent part of the storage not cached. A hierarchical index is not\nvery useful of indexing non file name attributes.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52398","messageId":"46DCF27A.4040804@op5.se","threadId":"9767","inReplyTo":"9e4733910709032237y65ccafdai4889078533908fb0@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T05:51:54Z","receivedAt":"2007-09-04T05:51:54Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, Martin Langhoff wrote:\n>> On 9/4/07, Jon Smirl wrote:\n>>>> Yes. For performance reasons, since a simple commit would kill you in any\n>>>> reasonably sized repo.\n>>> That's not an obvious conclusion. A new commit is just a series of\n>> Hi Jon!\n>>\n>> If you search the archives you'll find Linus explaining that the\n>> initial git had all the directory structure in one single \"tree\"\n>> object that held all the paths, not matter how deep. The problem with\n>> that was taht every commit generated a huge new tree object, so he\n>> switched to the current \"nested trees\" structure, which also has the\n>> nice feature of speeding up diffs/merges if whole subtrees haven't\n>> changed.\n> \n> In my scheme the commit is only a list of SHA's. The paths are stored\n> as attributes of the file objects. Commits are just edits to the list\n> of SHA's in the commit objects. If these lists are kept sorted, then\n> the delta should be tiny. Just the info on the adds/deletes to the\n> list.\n> \n\nIt will stop being fast when you need to apply (revisions*avg_num_files_changed)\npatches before you can start diffing things properly.\n\n> This is very different that a single tree blob that contains all of the paths.\n> \n> Diffing two trees in the scheme is quite fast. Just get their commit\n> objects into RAM and compare the lists of SHAs.\n> \n\nThat's not a very useful diff though. I'd run, screaming, from an SCM that didn't\ntell me *how* things have changed in addition to *what*.\n\n>>> edits to the previous commit. Start with the previous commit, edit it,\n>>> delta it and store it. Storing of the file objects is the same. Why\n>>> isn't this scheme fast than the current one?\n>> I think you're a bit confused between 2 different things:\n>>\n>> - git is _snapshot_ based, so every commit-tree-blob set is\n>> completely independent. The \"canonical\" storage is each of those\n>> gzipped in .git/objects\n>> - however, for performance and on-disk-footprint, we delta them (very\n>> efficiently I hear)\n> \n> The systems are essential the same with a little reorganization. In\n> the current system the paths and SHA for a commit are spread over the\n> tree nodes.\n> \n> In my scheme the path info is moved into the file object nodes and the\n> SHA list is in the commit node.\n> \n> git still works exactly as it has before. I just moved things around\n> in the storage system. The only thing that should be impacted is\n> performance.\n> \n\nPerhaps, but negatively so. Git is fast when applying patches, primarily\nbecause it can exclude entire subtrees. It knows it can exclude those\nsubtrees because their SHA1 hashes are identical. It wouldn't know that\nif there weren't the tree objects (well, it could, but walking all the\ncommits, counting changes and considering '0' to be \"no changes\" doesn't\nscale, so that's a moot point).\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52399","messageId":"9e4733910709032252x1fe6f436wdd13bcb1a6f76636@mail.gmail.com","threadId":"9767","inReplyTo":"e1dab3980709032119r381f7a91ia84ba09039c21be1@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T05:52:05Z","receivedAt":"2007-09-04T05:52:05Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, David Tweed wrote:\n> On 9/4/07, Jon Smirl wrote:\n> > Git has picked up the hierarchical storage scheme since it was built\n> > on a hierarchical file system.\n>\n> FWIW my memory is that initial git used path-to-blob lists (as you're\n> describing but without delta-ing) and tree nodes were added after a\n> couple of weeks, the motivation _at the time_ being they were a\n> natural way to dramatically reduce the size of repos.\n>\n> One of the nice things about tree nodes is that for doing a diff\n> between versions you can, to overwhelming probability, decide\n> equality/inequality of two arbitrarily deep and complicated subtrees\n> by comparing 40 characters, regardless of how remote and convoluted\n> their common ancestry. With delta chains don't you end up having to\n> trace back to a common \"entry\" in the history? (Of course, I don't\n> know how packs affect this - presumably there's some delta chasing to\n> get to the bare objects as well.)\n\nWhile it is a 40 character compare, how many disk accesses were needed\nto get those two SHAs into memory?\n\n>\n> --\n> cheers, dave tweed__________________________\n> david.tweed@gmail.com\n> Rm 124, School of Systems Engineering, University of Reading.\n> \"we had no idea that when we added templates we were adding a Turing-\n> complete compile-time language.\" -- C++ standardisation committee\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52400","messageId":"46DCF361.2090402@op5.se","threadId":"9767","inReplyTo":"9e4733910709032252x1fe6f436wdd13bcb1a6f76636@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T05:55:45Z","receivedAt":"2007-09-04T05:55:45Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, David Tweed wrote:\n>> On 9/4/07, Jon Smirl wrote:\n>>> Git has picked up the hierarchical storage scheme since it was built\n>>> on a hierarchical file system.\n>> FWIW my memory is that initial git used path-to-blob lists (as you're\n>> describing but without delta-ing) and tree nodes were added after a\n>> couple of weeks, the motivation _at the time_ being they were a\n>> natural way to dramatically reduce the size of repos.\n>>\n>> One of the nice things about tree nodes is that for doing a diff\n>> between versions you can, to overwhelming probability, decide\n>> equality/inequality of two arbitrarily deep and complicated subtrees\n>> by comparing 40 characters, regardless of how remote and convoluted\n>> their common ancestry. With delta chains don't you end up having to\n>> trace back to a common \"entry\" in the history? (Of course, I don't\n>> know how packs affect this - presumably there's some delta chasing to\n>> get to the bare objects as well.)\n> \n> While it is a 40 character compare, how many disk accesses were needed\n> to get those two SHAs into memory?\n> \n\nOne more than there would have been to read only the commit, and one more\nper level of recursion, assuming you never ever pack your repository.\n\nIf you *do* pack it, the tree(s) needed to compare are likely already\ninside the sliding packfile window. In that case, there are no extra\ndisk accesses.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52402","messageId":"20070904061611.GY18160@spearce.org","threadId":"9767","inReplyTo":"46DCF361.2090402@op5.se","subject":"Re: Calculating tree nodes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-09-04T06:16:11Z","receivedAt":"2007-09-04T06:16:11Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Andreas Ericsson wrote:\n> Jon Smirl wrote:\n> >On 9/4/07, David Tweed wrote:\n> >>On 9/4/07, Jon Smirl wrote:\n> >>>Git has picked up the hierarchical storage scheme since it was built\n> >>>on a hierarchical file system.\n...\n> >>One of the nice things about tree nodes is that for doing a diff\n> >>between versions you can, to overwhelming probability, decide\n> >>equality/inequality of two arbitrarily deep and complicated subtrees\n> >>by comparing 40 characters, regardless of how remote and convoluted\n> >>their common ancestry. With delta chains don't you end up having to\n> >>trace back to a common \"entry\" in the history? (Of course, I don't\n> >>know how packs affect this - presumably there's some delta chasing to\n> >>get to the bare objects as well.)\n> >\n> >While it is a 40 character compare, how many disk accesses were needed\n> >to get those two SHAs into memory?\n> \n> One more than there would have been to read only the commit, and one more\n> per level of recursion, assuming you never ever pack your repository.\n> \n> If you *do* pack it, the tree(s) needed to compare are likely already\n> inside the sliding packfile window. In that case, there are no extra\n> disk accesses.\n\nEven better, lets do some back of the napkin math on the Linux\nkernel tree. My local (out of date but close enough) copy has\n22,730 files in the tip revision. Values shown are uncompressed\nand compressed (gzip -9 | wc -c), but are excluding deltification.\n\n Current Scheme Jon's Flat Scheme\n ----------------- -----------------\ncommit raw 932 932 + 22,730*20 = 455,532\n(compressed) 521 456,338\n\nroot tree raw 876 0\n(compressed) 805 0\n\nI'm not even bothering with the individual subtrees. The numbers\nwill fall off quickly when you start to do subtree elimination and\nonly load the levels you need.\n\nYou are talking about doing disk IO for less than 4KiB with\nthe current scheme, and almost 456 KiB for the flat scheme.\nThat's before deltification. So if you also assume deltification\nits going to be higher as you need to read back to a base object\nthat is roughly the final size and then unpack the smaller deltas\nto reach the real commit.\n\nRemember, SHA-1s can be stored as 20 bytes of binary data but they\nare also generally uncompressible. That's why the root tree does\nnot compress very well, the SHA-1 data inside the tree cannot be\ncompressed and only the filenames have any shot at being compressed.\n\n-- \nShawn.\n"},{"id":"52403","messageId":"e1dab3980709032316l14b4f01gc7c71a750ed35a4@mail.gmail.com","threadId":"9767","inReplyTo":"9e4733910709032252x1fe6f436wdd13bcb1a6f76636@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2007-09-04T06:16:13Z","receivedAt":"2007-09-04T06:16:13Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On 9/4/07, Jon Smirl wrote:\n> On 9/4/07, David Tweed wrote:\n> > On 9/4/07, Jon Smirl wrote:\n> > > Git has picked up the hierarchical storage scheme since it was built\n> > > on a hierarchical file system.\n> >\n> > FWIW my memory is that initial git used path-to-blob lists (as you're\n> > describing but without delta-ing) and tree nodes were added after a\n> > couple of weeks, the motivation _at the time_ being they were a\n> > natural way to dramatically reduce the size of repos.\n> >\n> > One of the nice things about tree nodes is that for doing a diff\n> > between versions you can, to overwhelming probability, decide\n> > equality/inequality of two arbitrarily deep and complicated subtrees\n> > by comparing 40 characters, regardless of how remote and convoluted\n> > their common ancestry. With delta chains don't you end up having to\n> > trace back to a common \"entry\" in the history? (Of course, I don't\n> > know how packs affect this - presumably there's some delta chasing to\n> > get to the bare objects as well.)\n>\n> While it is a 40 character compare, how many disk accesses were needed\n> to get those two SHAs into memory?\n\nThat's a difficult question. Clearly if you're starting on a machine\nwithout anything cached, you're probably a bit worse off. If not and\nyou've got a \"wide, shallow tree where changes occur clustered within\ndirectories rather than spread uniformly throughout the tree\" then\nit's likely already there.\n\nBut it's all I suspect it should be looked at in relative terms: with\nthe respect to the delta-d list of SHA's, do you need to do more or\nless disk reads to be able to compare stuff? Dunno: I'd imagine this\ndepends on precisely what's delta'd against what and how many of those\nyou need to read in order to put two entries into a comparable form.\nThe key point I was making was not so much the 40 characters as that\n(at least with loose objects) if you can are given the top-level\nSHA's, you can efficiently decide equality (a key to efficient\ndiffing) _without having to care how those two are related in the\nhistory or read any extra history_.\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"we had no idea that when we added templates we were adding a Turing-\ncomplete compile-time language.\" -- C++ standardisation committee\n"},{"id":"52404","messageId":"20070904062629.GZ18160@spearce.org","threadId":"9767","inReplyTo":"9e4733910709032026s7f94eed9h25d5165840cc38d2@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-09-04T06:26:29Z","receivedAt":"2007-09-04T06:26:29Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> Index is the key here, we may want other kinds of indexes in the\n> future. It was the mail about auto-generating the Maintainers list\n> that caused me to think about this. If file objects are a table with\n> triggers, building a hierarchical index for the Maintainers field\n> doesn't make sense.\n\nThere's nothing stopping us from creating additional indexes.\n\nFor example we have been kicking around this idea of a \"note\"\nobject that can be attached to commits. Lightweight enough that one\ncould be attached to every commit, such as one way to implement the\n\"Signed-off-by\" lines. Notes can be looked up by commit SHA-1 using\na hash, giving near O(1) time to locate the note for any commit.\n\nBut we can also store the notes alongside the commits in the\npackfile, so that if the data for the commit has been paged in\nby the kernel then the note data is also most likely in memory,\nand if not, is in the read-ahead queue. Clustering the notes\nalongside the commits makes access to them even faster, as we\ndon't need to consult an external hash to locate the position.\n\nSo I guess where I'm going is additional indexes can be implemented,\nefficiently, without changing any of the core storage model in Git.\nWe just haven't made it easily user pluggable yet, because nobody\nhas really thought about the applications for such a function.\nAnd code hasn't been posted for it (with the exception of the\nnotes prototypes).\n\n-- \nShawn.\n"},{"id":"52417","messageId":"Pine.LNX.4.64.0709041131030.28586@racer.site","threadId":"9767","inReplyTo":"9e4733910709032237y65ccafdai4889078533908fb0@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-09-04T10:33:36Z","receivedAt":"2007-09-04T10:33:36Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Sep 2007, Jon Smirl wrote:\n\n> In my scheme the path info is moved into the file object nodes and the \n> SHA list is in the commit node.\n\nAnd how should this \"SHA list\" be any different from a single tree object, \nexcept that you now merge it with the commit object?\n\nReally, go back to the mail Martin mentioned. Having all objects in one \nlist kills performance.\n\n> Diffing two trees in the scheme is quite fast. Just get their commit\n> objects into RAM and compare the lists of SHAs.\n\nNo, it is not fast. Just loading the complete list into RAM is likely \nmuch, much slower than a simple diff _right_ _now_.\n\nHth,\nDscho\n"},{"id":"52447","messageId":"9e4733910709040719n135a1c2dw3a2d5c470b74791a@mail.gmail.com","threadId":"9767","inReplyTo":"20070904061611.GY18160@spearce.org","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T14:19:17Z","receivedAt":"2007-09-04T14:19:17Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Shawn O. Pearce wrote:\n> Andreas Ericsson wrote:\n> > Jon Smirl wrote:\n> > >On 9/4/07, David Tweed wrote:\n> > >>On 9/4/07, Jon Smirl wrote:\n> > >>>Git has picked up the hierarchical storage scheme since it was built\n> > >>>on a hierarchical file system.\n> ...\n> > >>One of the nice things about tree nodes is that for doing a diff\n> > >>between versions you can, to overwhelming probability, decide\n> > >>equality/inequality of two arbitrarily deep and complicated subtrees\n> > >>by comparing 40 characters, regardless of how remote and convoluted\n> > >>their common ancestry. With delta chains don't you end up having to\n> > >>trace back to a common \"entry\" in the history? (Of course, I don't\n> > >>know how packs affect this - presumably there's some delta chasing to\n> > >>get to the bare objects as well.)\n> > >\n> > >While it is a 40 character compare, how many disk accesses were needed\n> > >to get those two SHAs into memory?\n> >\n> > One more than there would have been to read only the commit, and one more\n> > per level of recursion, assuming you never ever pack your repository.\n> >\n> > If you *do* pack it, the tree(s) needed to compare are likely already\n> > inside the sliding packfile window. In that case, there are no extra\n> > disk accesses.\n>\n> Even better, lets do some back of the napkin math on the Linux\n> kernel tree. My local (out of date but close enough) copy has\n> 22,730 files in the tip revision. Values shown are uncompressed\n> and compressed (gzip -9 | wc -c), but are excluding deltification.\n>\n> Current Scheme Jon's Flat Scheme\n> ----------------- -----------------\n> commit raw 932 932 + 22,730*20 = 455,532\n> (compressed) 521 456,338\n>\n> root tree raw 876 0\n> (compressed) 805 0\n\nThis is not a fair comparison. The current scheme is effectively\ndiffed against the previous version. You aren't showing an equivalent\ndiff for the flat scheme. Both schemes are dealing with the same\n22,000 SHAs.\n\nThe size win is from diffing, not compressing.\n\n> I'm not even bothering with the individual subtrees. The numbers\n> will fall off quickly when you start to do subtree elimination and\n> only load the levels you need.\n>\n> You are talking about doing disk IO for less than 4KiB with\n> the current scheme, and almost 456 KiB for the flat scheme.\n> That's before deltification. So if you also assume deltification\n> its going to be higher as you need to read back to a base object\n> that is roughly the final size and then unpack the smaller deltas\n> to reach the real commit.\n>\n> Remember, SHA-1s can be stored as 20 bytes of binary data but they\n> are also generally uncompressible. That's why the root tree does\n> not compress very well, the SHA-1 data inside the tree cannot be\n> compressed and only the filenames have any shot at being compressed.\n>\n> --\n> Shawn.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52450","messageId":"9e4733910709040731s2695ab14kb9750923fcac007@mail.gmail.com","threadId":"9767","inReplyTo":"Pine.LNX.4.64.0709041131030.28586@racer.site","subject":"Re: Calculating tree nodes","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T14:31:35Z","receivedAt":"2007-09-04T14:31:35Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Johannes Schindelin wrote:\n> Hi,\n>\n> On Tue, 4 Sep 2007, Jon Smirl wrote:\n>\n> > In my scheme the path info is moved into the file object nodes and the\n> > SHA list is in the commit node.\n>\n> And how should this \"SHA list\" be any different from a single tree object,\n> except that you now merge it with the commit object?\n>\n> Really, go back to the mail Martin mentioned. Having all objects in one\n> list kills performance.\n\nYou are ignoring the fact the in this scheme temp indexes can be\ncreated as needed. These temp indexes could look just like tree nodes.\n\nI'm saying that it may be a mistake to be recording the indexes (aka\nfile names) as part of the commit when they really aren't. The\nessential part of the commit is the SHA1 list. The path names belong\nto the file objects and should be stored there.\n\n\n>\n> > Diffing two trees in the scheme is quite fast. Just get their commit\n> > objects into RAM and compare the lists of SHAs.\n>\n> No, it is not fast. Just loading the complete list into RAM is likely\n> much, much slower than a simple diff _right_ _now_.\n>\n> Hth,\n> Dscho\n>\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52452","messageId":"46DD6E8A.7000802@op5.se","threadId":"9767","inReplyTo":"9e4733910709040719n135a1c2dw3a2d5c470b74791a@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T14:41:14Z","receivedAt":"2007-09-04T14:41:14Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, Shawn O. Pearce wrote:\n>> Andreas Ericsson wrote:\n>>> Jon Smirl wrote:\n>>>> On 9/4/07, David Tweed wrote:\n>>>>> On 9/4/07, Jon Smirl wrote:\n>>>>>> Git has picked up the hierarchical storage scheme since it was built\n>>>>>> on a hierarchical file system.\n>> ...\n>>>>> One of the nice things about tree nodes is that for doing a diff\n>>>>> between versions you can, to overwhelming probability, decide\n>>>>> equality/inequality of two arbitrarily deep and complicated subtrees\n>>>>> by comparing 40 characters, regardless of how remote and convoluted\n>>>>> their common ancestry. With delta chains don't you end up having to\n>>>>> trace back to a common \"entry\" in the history? (Of course, I don't\n>>>>> know how packs affect this - presumably there's some delta chasing to\n>>>>> get to the bare objects as well.)\n>>>> While it is a 40 character compare, how many disk accesses were needed\n>>>> to get those two SHAs into memory?\n>>> One more than there would have been to read only the commit, and one more\n>>> per level of recursion, assuming you never ever pack your repository.\n>>>\n>>> If you *do* pack it, the tree(s) needed to compare are likely already\n>>> inside the sliding packfile window. In that case, there are no extra\n>>> disk accesses.\n>> Even better, lets do some back of the napkin math on the Linux\n>> kernel tree. My local (out of date but close enough) copy has\n>> 22,730 files in the tip revision. Values shown are uncompressed\n>> and compressed (gzip -9 | wc -c), but are excluding deltification.\n>>\n>> Current Scheme Jon's Flat Scheme\n>> ----------------- -----------------\n>> commit raw 932 932 + 22,730*20 = 455,532\n>> (compressed) 521 456,338\n>>\n>> root tree raw 876 0\n>> (compressed) 805 0\n> \n> This is not a fair comparison. The current scheme is effectively\n> diffed against the previous version. You aren't showing an equivalent\n> diff for the flat scheme. Both schemes are dealing with the same\n> 22,000 SHAs.\n> \n\nHow, with your scheme, would you solve\n\n\tgit diff -M master pu\n\nin the git repo?\n\nYou'd have to build both trees completely, utilizing the last known\ncomplete tree-listing (the root commit, since you propose to do away\nwith trees altogether) and then applying diffs on top of that to\nfinally generate an in-memory tree-structure in which you will have\nto compare every single file against every single other file to find\nout which code has been moved/copied/renamed/whatever.\n\nThat's (n*(n+1))/2 operations for file-level diffs alone. For the\nkernels 22730 files, you're looking at 258337815 file comparisons\nwithout the tree objects.\n\nSure, you can probably shave away quite a few of those comparisons\nat the expense of computing the tree-hashes on the fly, but in that\ncase, why get rid of them in the first place?\n\n> The size win is from diffing, not compressing.\n> \n\nIt was declared in May 2006 by someone insightful that diskspace\nand bandwidth are cheap, while human time is priceless.\n\nIOW, size wins had better be proportionally huge to justify slowing\ngit down and thereby taking more than necessary of the users' time.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52463","messageId":"Pine.LNX.4.64.0709041602230.28586@racer.site","threadId":"9767","inReplyTo":"9e4733910709040731s2695ab14kb9750923fcac007@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-09-04T15:05:08Z","receivedAt":"2007-09-04T15:05:08Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Sep 2007, Jon Smirl wrote:\n\n> On 9/4/07, Johannes Schindelin wrote:\n>\n> > On Tue, 4 Sep 2007, Jon Smirl wrote:\n> >\n> > > In my scheme the path info is moved into the file object nodes and \n> > > the SHA list is in the commit node.\n> >\n> > And how should this \"SHA list\" be any different from a single tree \n> > object, except that you now merge it with the commit object?\n> >\n> > Really, go back to the mail Martin mentioned. Having all objects in \n> > one list kills performance.\n> \n> You are ignoring the fact the in this scheme temp indexes can be\n> created as needed. These temp indexes could look just like tree nodes.\n> \n> I'm saying that it may be a mistake to be recording the indexes (aka\n> file names) as part of the commit when they really aren't.\n\nYou still have not acknowledged that you want to do (in essence) _exactly_ \nthe same. Your \"temp indexes\" awfully remind me of tree objects.\n\nAnd that is no wonder, since you _need_ something like that, however you \nwant to avoid it. Just admit it that you found -- again -- that flat \ndirectory structure does not work, and you therefore need some smaller \nstructures. We just happen to call them \"tree objects\", and for ease of \nconcept we wrap directories in them.\n\nHth,\nDscho\n"},{"id":"52466","messageId":"46DD7660.2030109@op5.se","threadId":"9767","inReplyTo":"9e4733910709040731s2695ab14kb9750923fcac007@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T15:14:40Z","receivedAt":"2007-09-04T15:14:40Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, Johannes Schindelin wrote:\n>> Hi,\n>>\n>> On Tue, 4 Sep 2007, Jon Smirl wrote:\n>>\n>>> In my scheme the path info is moved into the file object nodes and the\n>>> SHA list is in the commit node.\n>> And how should this \"SHA list\" be any different from a single tree object,\n>> except that you now merge it with the commit object?\n>>\n>> Really, go back to the mail Martin mentioned. Having all objects in one\n>> list kills performance.\n> \n> You are ignoring the fact the in this scheme temp indexes can be\n> created as needed. These temp indexes could look just like tree nodes.\n> \n\nWhat's the cost associated with creating such an index?\nWhat are the estimated savings in size?\nWhat other performance penalties will git take due to this?\n\nWhile I'm certainly interested in improving git (well, discussing its\nimprovements anyway - I write too shabby code to participate fully),\nI fail to see how this scheme of storing things could help doing that,\nseeing as it's already the fastest SCM out there and does an insanely\ngood job at storing large repositories packed up tight.\n\nWhat you're proposing would effectively shave off ~4kb or so of stored\ndata and save a *possible* disk access (note that there will most\nlikely be none, as most users pack large repos, and for small ones it\nshouldn't matter much either way). The way you propose to do so\ninvolves fundamental and backwards-incompatible alterations to the\nvery core of the git plumbing.\n\nYet you haven't shown a single estimate of how much diskspace would\nbe saved, or what other gains are to be had, let alone any code to \nimplement even a prototype of this new storage scheme.\n\nNote that I'm currently in a state of mind where I'm feeling inclined\nto whoop and cheer at every small suggestion that sounds even the\nslightest bit of fun. No, I'm not doing drugs, but I just met the \npossible love of my life, got a big fat raise and my stocks just\nwent ballistic. Someone less fortunate than I am right now is probably\ntoo bored to even argue against it.\n\n> I'm saying that it may be a mistake to be recording the indexes (aka\n> file names) as part of the commit when they really aren't.\n\nBut they are, since they're part of the snapshot.\n\n> The\n> essential part of the commit is the SHA1 list. The path names belong\n> to the file objects and should be stored there.\n> \n\nSorry, but it'll take code and benchmarks to convince me this is a\ngood idea. Not that it matters much what I think, but I've got an\ninkling Junio will need the same before he's swayed to your point\nof view.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52479","messageId":"20070904162019.GA10441@istic.org","threadId":"9767","inReplyTo":"9e4733910709032026s7f94eed9h25d5165840cc38d2@mail.gmail.com","subject":"Re: Calculating tree nodes","fromName":"Daniel Hulme","fromEmail":"st@istic.org","sentAt":"2007-09-04T16:20:19Z","receivedAt":"2007-09-04T16:20:19Z","isPatch":false,"sender":{"key":"st@istic.org","avatar":null},"body":"On Mon, Sep 03, 2007 at 11:26:30PM -0400, Jon Smirl wrote:\n> This is something that has always bugged me about file systems. File\n> systems force hierarchical naming due to their directory structure.\n> There is no reason they have to work that way. Google is an example of\n> a giant file system that works just fine without hierarchical\n> directories. The full path should be just another attribute on the\n> file. If you want a hierarchical index into the file system you can\n> generate it by walking the files or using triggers. But you could also\n> delete the hierarchical directory and replace it with something else\n> like a full text index. Directories would become a computationally\n> generated cache, not a critical part of the file system. But this is a\n> git list so I shouldn't go too far off into file system design.\n\nAm I the only one who thinks that this idea of moving filenames from\ntree objects into blobs does the *opposite* of what you're trying to\nachieve?\n\nIt seems, though I could be completely misinterpreting what you're\nsaying, that you want to be able to get rid of directories and replace\nthem with some other index into your files: maybe a full-text index,\nmaybe a spatial index for geographic data, maybe something else\nentirely. As things stand, you could do that by editing the core to\nintroduce a new object type 'fulltext' whose contents maybe look like\n\naardvark \nabacus \n...\nzebra \n\nor even something hierarchical, with each index mapping from the first\nletter of the index term to the sha1 of another index, which in term\nmaps second letters, and so on. Whatever. The point is, it works\nparallel to tree. You could have the blobs referenced by your fulltext\nobject also be referenced by a tree object. If you really don't like\ndirectory trees, you can dispense with tree objects in your repo\nentirely. Either way you have a mapping from keys to blobs.\n\nThen you could have your commits and tags include sha1's of fulltext\nobjects rather than (or as well as) tree objects, and you get your wish.\n\nOTOH, imagine if you move filenames into the blobs. Now, no matter what\nother index types you introduce, they'll always be secondary to the\ntraditional, path-and-filename method of finding files. Crucially, you\ncan't introduce new blobs into the repo without giving them filenames.\n\nAs you said in your other thread,\n\n> Integrating indexing into the data is not normally done in a database.\n\nBut isn't this exactly what integrating filenames into blobs would do?\n\n-- \nThere is no such thing as a small specification change.\nhttp://surreal.istic.org/ Forcing the lines through the snow.\n"},{"id":"52496","messageId":"7vbqcinxdb.fsf@gitster.siamese.dyndns.org","threadId":"9767","inReplyTo":"20070904062629.GZ18160@spearce.org","subject":"Re: Calculating tree nodes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-04T17:39:28Z","receivedAt":"2007-09-04T17:39:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> There's nothing stopping us from creating additional indexes.\n> ...\n> But we can also store the notes alongside the commits in the\n> packfile, so that if the data for the commit has been paged in\n> by the kernel then the note data is also most likely in memory,\n> and if not, is in the read-ahead queue. Clustering the notes\n> alongside the commits makes access to them even faster, as we\n> don't need to consult an external hash to locate the position.\n\nI would agree with your main thrust \"nobody prevents you from\nbuilding additional index\", but on a tangent, I am skeptical\nabout adding too much to pack v4. Especially \"clustering the\nnotes\" part.\n\nMany operations (like \"git log\" that is not path limited) do not\neven need trees. The current packfile format has commits at the\nbeginning without any associated trees, and they are stored in\ntraversal order (modulo delta-base requirements can move base\nobject earlier), which is geared toward optimizing such a common\ncase.\n\nNow, hopefully many operations do not need notes either,\nalthough notes themselves can store _anything_ so each of them\ncould be large and/or each commit could have large number of\nthem. I suspect clustering notes along with the commit they\nannotate would break the locality of access for common case.\n"},{"id":"52516","messageId":"46a038f90709041402k45d72dc6l59f93cd22b8c02e9@mail.gmail.com","threadId":"9767","inReplyTo":"46DD7660.2030109@op5.se","subject":"Re: Calculating tree nodes","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2007-09-04T21:02:59Z","receivedAt":"2007-09-04T21:02:59Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 9/5/07, Andreas Ericsson wrote:\n> Jon Smirl wrote:\n> > The\n> > essential part of the commit is the SHA1 list. The path names belong\n> > to the file objects and should be stored there.\n>\n> Sorry, but it'll take code and benchmarks to convince me this is a\n> good idea.\n\nSame here. But I do want to note that adding the pathname to the blob\n(and storing them on the combined SHA1 I assume) is broken, broken,\nbroken. It won't support any of the great semantics that git has\ntoday.\n\nJon: I think you need to think carefully about the key operations like\ndiff and log on paths on projects like linux or mozilla. Even better,\ncraft a proof-of-concept patch that shows how that'd work, and why\nit's faster/smaller.\n\ncheers,\n\n\n\nm\n"},{"id":"52681","messageId":"20070906032026.GO18160@spearce.org","threadId":"9767","inReplyTo":"7vbqcinxdb.fsf@gitster.siamese.dyndns.org","subject":"Re: Calculating tree nodes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-09-06T03:20:26Z","receivedAt":"2007-09-06T03:20:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> \"Shawn O. Pearce\" writes:\n> \n> > There's nothing stopping us from creating additional indexes.\n> > ...\n> > But we can also store the notes alongside the commits in the\n> > packfile, so that if the data for the commit has been paged in\n...\n> \n> I would agree with your main thrust \"nobody prevents you from\n> building additional index\", but on a tangent, I am skeptical\n> about adding too much to pack v4. Especially \"clustering the\n> notes\" part.\n...\n> Now, hopefully many operations do not need notes either,\n> although notes themselves can store _anything_ so each of them\n> could be large and/or each commit could have large number of\n> them. I suspect clustering notes along with the commit they\n> annotate would break the locality of access for common case.\n\nI'm inclined to agree.\n\nIts something I've thought about doing. I haven't even prototyped\ncode for it. Let alone shown numbers that say one way or the other.\n\nOne of the notes proposals was talking about having lots of different\nclasses of notes. E.g. a \"Signed-off-by\" class and a \"build and test\nlog results\" class.\n\nThe former would generally be very small and may even want to be\nshown most of the time the commit body is displayed (e.g. in gitk,\ngit-log). These would be good candidates to cluster alongside the\ncommit. Indeed they are clustered there today, just hung inside\nof the commit object itself. Nobody is bitching about the hit they\ncause on the common case of `pack-objects`. :)\n\nThe latter (build and test log) would generally be very large.\nWe would *not* want to cluster them. But we might want to store\nnext to the commit a very small pointer to the note itself. Such\nas the note's SHA-1. Or its offset within the packfile's index.\nThis would make locating those notes very cheap, while not having\na huge impact on the common case of commit traversal.\n\nLikewise we might want to pack a tag's SHA-1 alongside of the commit\nit points at, as parsing the commit would immediately give us all\nannotated tags that refer to that commit. Tags are (usually) few\nand far between. But tools like git-describe are commonly used and\nwould benefit from not needing to build the commit->tag hashtable.\nOK, well, git-describe cheats and uses the struct object hashtable,\nbut whatever.\n\nYou get my point. I think. And I got yours about not making the\ncommon case worse than it already is today.\n\n-- \nShawn.\n"},{"id":"52692","messageId":"7vhcm8e5di.fsf@gitster.siamese.dyndns.org","threadId":"9767","inReplyTo":"20070906032026.GO18160@spearce.org","subject":"Re: Calculating tree nodes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-06T05:21:13Z","receivedAt":"2007-09-06T05:21:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> The latter (build and test log) would generally be very large.\n> We would *not* want to cluster them. But we might want to store\n> next to the commit a very small pointer to the note itself. Such\n> as the note's SHA-1. Or its offset within the packfile's index.\n> This would make locating those notes very cheap, while not having\n> a huge impact on the common case of commit traversal.\n>\n> Likewise we might want to pack a tag's SHA-1 alongside of the commit\n> it points at, as parsing the commit would immediately give us all\n> annotated tags that refer to that commit. Tags are (usually) few\n> and far between. But tools like git-describe are commonly used and\n> would benefit from not needing to build the commit->tag hashtable.\n\nI am not so sure.\n\nIt is a good idea to have an internal API that takes an object\nand gives back a set of objects (be they notes to commit or tags\npoint at object) related to it, but you need to always deal with\nloose objects and v2 packs, so you will have to traverse all the\ntags and find what they point at _anyway_ to implement the API.\nHaving a specialized table in v4 does not mean you can look at\nthat table and nothing else, so I do not immediately see a gain.\n"}]}