{"thread":{"id":"34701","subject":"Understanding Git Under The Hood: Trees","startedAt":"2013-08-15T10:29:13Z","lastAt":"2013-08-16T13:13:06Z","messageCount":6,"participants":["Erik Bernoth","Andreas Ericsson","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"225256","messageId":"CAB46HOnsOdYyt3sEe=iv3AJu_BDpTqCLKUpTBFQSnVGMZc8r8A@mail.gmail.com","threadId":"34701","inReplyTo":null,"subject":"Understanding Git Under The Hood: Trees","fromName":"Erik Bernoth","fromEmail":"erik.bernoth@gmail.com","sentAt":"2013-08-15T10:29:13Z","receivedAt":"2013-08-15T10:29:13Z","isPatch":false,"sender":{"key":"erik.bernoth@gmail.com","avatar":null},"body":"Hi,\n\nI'm currently trying to understand the inner workings of git better by\nwriting a git clone in Python. I find it rather hard to understand how\nto efficiently use trees.\n\nWhat I understand is this: Trees are in essence blobs with a specific\ncontent. The content is a relation between other blobs names, types\nand modes. With these lines they can refer to other blobs and trees\nand thus make a tine filesystem.\n\nNow I constructed a system to read and write blobs and have an index\nfile that potentially references to a top tree object, which\nrepresents the currently cached repository state. I can add and remove\nfiles from the index manually, by creating the blob of the file and\nworking my way up adding or updating trees until I hit the one\nreferenced in INDEX. My algorithm to automate it is really ugly, error\nprone and inefficient, though. I also have a hard time to find my way\naround in C files, so maybe some people here in the list could explain\nthe algorithm in Git to me.\n\nsuppose we have the following Index:\n\nINDEX\n -> tree\n       -> tree \"a/\"\n           -> blob \"b.txt\"\n       -> tree \"c/\"\n           -> blob \"d.txt\"\n\nNow you want to stage a file with the following reference \"a/e/g.txt\".\n\nOne approach would be to walk top-down, splitting the path into its\nelements and looking for the corresponding trees, either retrieving an\nexisting tree or creating a new one. Then finally create the blob\n\"g.txt\" and be done with it. This seems rather inefficient, though,\nbecause each created or updated tree means that all trees way back up\nneed to be updated as well, once for every step in the loop.\n\nThe other way is to go bottom-up, first creating the blob, then\ncreating trees up to the project root folder. But then I don't see a\nway to find which tree elements already exist and need to be updated.\n\nSo the only algorithm I can come up with is this:\n 1. walk down the tree with help of the path string to the tree that\nis closest to the file I want to store. On the way remember all the\ntrees on the path from INDEX to the resulting file. (In the example\nabove I'd like to get the hash of the \"a/\" tree)\n 2. create the blob (in the example with the context of g.txt)\n 3. create the trees bottom-up until one step before the tree found in\n1. (in the example create a \"e/\" tree, containing the \"g.txt\"'s blob)\n 4. Add the resulting tree from 3. to the one found in 1. and create\nthe updated hash\n 5. Now with help of the list from 1. walk the existing trees\nbottom-up and update each one with the new hashes until INDEX is hit.\n 6. Update INDEX.\n\n\nAlltogether the idea of trees looked really simple and recursive which\nmakes me quite unhappy with the algorithm I came up with.\n\n\nWhat is the algorithm to stage single files in Git itself?\nHow\n\nAlso: I thought to myself, why not just make a function that returns\nthe relative path to the repository root folder and consider that\nstring the file name, drop the idea of trees at all and add the\ninformation that is traditionally stored in tree objects directly in a\ncommit object. Wouldn't that be much simpler and still accomplish the\nsame? I think the idea of keeping information in separate small files\ninstead of single big files was dropped at one point anyway, when\npack-files were introduced.\n\n\nCheers\nErik\n"},{"id":"225261","messageId":"520CCC53.4090308@op5.se","threadId":"34701","inReplyTo":"CAB46HOnsOdYyt3sEe=iv3AJu_BDpTqCLKUpTBFQSnVGMZc8r8A@mail.gmail.com","subject":"Re: Understanding Git Under The Hood: Trees","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2013-08-15T12:40:51Z","receivedAt":"2013-08-15T12:40:51Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 2013-08-15 12:29, Erik Bernoth wrote:\n> Hi,\n>\n> I'm currently trying to understand the inner workings of git better by\n> writing a git clone in Python. I find it rather hard to understand how\n> to efficiently use trees.\n>\n> What I understand is this: Trees are in essence blobs with a specific\n> content. The content is a relation between other blobs names, types\n> and modes. With these lines they can refer to other blobs and trees\n> and thus make a tine filesystem.\n>\n> Now I constructed a system to read and write blobs and have an index\n> file that potentially references to a top tree object, which\n> represents the currently cached repository state. I can add and remove\n> files from the index manually, by creating the blob of the file and\n> working my way up adding or updating trees until I hit the one\n> referenced in INDEX. My algorithm to automate it is really ugly, error\n> prone and inefficient, though. I also have a hard time to find my way\n> around in C files, so maybe some people here in the list could explain\n> the algorithm in Git to me.\n>\n> suppose we have the following Index:\n>\n> INDEX\n>   -> tree\n>         -> tree \"a/\"\n>             -> blob \"b.txt\"\n>         -> tree \"c/\"\n>             -> blob \"d.txt\"\n>\n> Now you want to stage a file with the following reference \"a/e/g.txt\".\n>\n> One approach would be to walk top-down, splitting the path into its\n> elements and looking for the corresponding trees, either retrieving an\n> existing tree or creating a new one. Then finally create the blob\n> \"g.txt\" and be done with it. This seems rather inefficient, though,\n> because each created or updated tree means that all trees way back up\n> need to be updated as well, once for every step in the loop.\n>\n> The other way is to go bottom-up, first creating the blob, then\n> creating trees up to the project root folder. But then I don't see a\n> way to find which tree elements already exist and need to be updated.\n>\n> So the only algorithm I can come up with is this:\n>   1. walk down the tree with help of the path string to the tree that\n> is closest to the file I want to store. On the way remember all the\n> trees on the path from INDEX to the resulting file. (In the example\n> above I'd like to get the hash of the \"a/\" tree)\n>   2. create the blob (in the example with the context of g.txt)\n>   3. create the trees bottom-up until one step before the tree found in\n> 1. (in the example create a \"e/\" tree, containing the \"g.txt\"'s blob)\n>   4. Add the resulting tree from 3. to the one found in 1. and create\n> the updated hash\n>   5. Now with help of the list from 1. walk the existing trees\n> bottom-up and update each one with the new hashes until INDEX is hit.\n>   6. Update INDEX.\n>\n>\n> Alltogether the idea of trees looked really simple and recursive which\n> makes me quite unhappy with the algorithm I came up with.\n>\n>\n> What is the algorithm to stage single files in Git itself?\n\nYou seem to believe that the in-memory representation of trees have to\nbe the same as the on-disk one. That's simply not true. Git cheats\noutrageously with internal formats for pretty much everything in order\nto squeeze out more performance.\n\nYou also seem to believe that a tree is more than one directory.\nThat's not true either.\n\nSo... Each tree that's updated can (and does) have an in-memory link\nto its parent directory. Whenever we update a directory and create a\ncommit from it, we make sure to write them out from right to left (ie, \nchildren before parents), so that we're never in a state where a tree on \ndisk can't find any of its content blobs in the same object storage.\n\nWith that information in hand, I'm sure you can quite easily create an\nalgorithm that turns out a bit prettier than what you have now.\n\n>\n> Also: I thought to myself, why not just make a function that returns\n> the relative path to the repository root folder and consider that\n> string the file name, drop the idea of trees at all and add the\n> information that is traditionally stored in tree objects directly in a\n> commit object.\n\nBecause commit objects must have parents and things like that. Also,\nthe idea of trees containing trees saves a *huge* amount of disk I/O\nand space when updating a project with many subdirectories.\n\n> Wouldn't that be much simpler and still accomplish the\n> same?\n\nSimpler; Yes. More efficient; No.\n\nThe commit that changed the tree structure from flat to hierarchical\ndates back to April of 2005. It's commit number 25 in the history of\ngit and solves one of the first real problems from live-testing git\non the kernel repository, which was that tree-files got so huge when\nthey had to be rewritten in their entirety that creating a new commit\ntook several seconds.\n\n> I think the idea of keeping information in separate small files\n> instead of single big files was dropped at one point anyway, when\n> pack-files were introduced.\n>\n\nNot really. We strive hard to minimize disk I/O whenever we can. The\npackfiles actually reduce I/O, since it lets the kernel use the disk's\nbuiltin caches a lot better, and read-ahead works to our advantage.\n\nBtw, when I say \"minimize disk I/O\", I really mean \"minimize user wait\",\nalthough disk I/O is certainly (often) the largest part of that.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"225268","messageId":"7vwqnmrhbw.fsf@alter.siamese.dyndns.org","threadId":"34701","inReplyTo":"520CCC53.4090308@op5.se","subject":"Re: Understanding Git Under The Hood: Trees","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T17:31:47Z","receivedAt":"2013-08-15T17:31:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Ericsson <ae@op5.se> writes:\n\n> You seem to believe that the in-memory representation of trees have to\n> be the same as the on-disk one. That's simply not true. Git cheats\n> outrageously with internal formats for pretty much everything in order\n> to squeeze out more performance.\n\nWhile the last statement applies to other parts of the system, it is\nnot true for the in-core index design.  We always had a flat index,\nand it is not cheating at all.  The original \"tree\" was also a flat\nrepresentation of everything under the sun, and hierarchical tree\nobjects came much later.\n"},{"id":"225277","messageId":"CAB46HOmVpMFsu9dWwB+TZW+DQmE-5XOZqJf62Ufz7ak0eGxP5g@mail.gmail.com","threadId":"34701","inReplyTo":"7vwqnmrhbw.fsf@alter.siamese.dyndns.org","subject":"Re: Understanding Git Under The Hood: Trees","fromName":"Erik Bernoth","fromEmail":"erik.bernoth@gmail.com","sentAt":"2013-08-15T19:32:07Z","receivedAt":"2013-08-15T19:32:07Z","isPatch":false,"sender":{"key":"erik.bernoth@gmail.com","avatar":null},"body":"On Thu, Aug 15, 2013 at 7:31 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> While the last statement applies to other parts of the system, it is\n> not true for the in-core index design.  We always had a flat index,\n> and it is not cheating at all.  The original \"tree\" was also a flat\n> representation of everything under the sun, and hierarchical tree\n> objects came much later.\n\nTo some degree that revalidates my interpretation of Andreas'\nstatements. If I understand it correctly eacht time a shell command is\nexecuted, which requires tree interaction, the corresponding tree is\nread from filesystem to memory completely before anything is done? So\nif I git-add a file, the whole index is read first, then the memory\nobject is changed and then the resulting change is written to disk\nbottom-up from the point of view of the tree?\n"},{"id":"225318","messageId":"520DECF0.9080501@op5.se","threadId":"34701","inReplyTo":"CAB46HOmVpMFsu9dWwB+TZW+DQmE-5XOZqJf62Ufz7ak0eGxP5g@mail.gmail.com","subject":"Re: Understanding Git Under The Hood: Trees","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2013-08-16T09:12:16Z","receivedAt":"2013-08-16T09:12:16Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 2013-08-15 21:32, Erik Bernoth wrote:\n> On Thu, Aug 15, 2013 at 7:31 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>> While the last statement applies to other parts of the system, it is\n>> not true for the in-core index design.  We always had a flat index,\n>> and it is not cheating at all.  The original \"tree\" was also a flat\n>> representation of everything under the sun, and hierarchical tree\n>> objects came much later.\n>\n> To some degree that revalidates my interpretation of Andreas'\n> statements. If I understand it correctly eacht time a shell command is\n> executed, which requires tree interaction, the corresponding tree is\n> read from filesystem to memory completely before anything is done?\n\n\nMore or less, yes, but please don't confuse \"directory tree\" with \"git\ntree\". They're not the same. A directory tree can contain multiple\nlevels of directories, whereas a git tree can only contain a list\nof objects. The index (aka \"staging area\") represents a directory tree, \nbut when it gets stored on-disk a directory tree gets broken down into\nas many git trees as is necessary.\n\nThe index is just a cache though. Until changes have been staged to it\nin preparation for the next commit, it can be recreated exactly from\nthe currently checked out commit. As Junio pointed out, the index has \nbeen flat from the very beginning. Don't confuse the index with the\ngit tree objects found in the object storage though, or the working tree\nwith git trees. They're really not the same.\n\nTo illustrate the differences, here's a few commands and what they do\nand operate on, with regards to the three different kinds of trees that\nhave come up in this discussion.\n\n\nIgnore everything git-related and only print the worktree:\n   find .\n\nIgnores everything index- and worktree-related and only print the root\ngit tree of the currently checked out commit. You won't see any\nrelative paths or directories in there; Just a list of trees and blobs:\n   git cat-file -p $(git cat-file -p HEAD | sed -n 's/^tree //p;q')\n\n\nList staged files only, regardless of what you have in the worktree or\nwhat the latest commit looks like. This will look pretty much like the\nlast command, but with files located in subdirectories as well, and an\nadditional field where the \"index-state\" is stored:\n   git ls-files -s\n\n\n > So\n > if I git-add a file, the whole index is read first, then the memory\n > object is changed and then the resulting change is written to disk\n > bottom-up from the point of view of the tree?\n >\n\nWhen you git-add a file, we read in the index, update it with the new\ncontents of the file you pointed to, or add the new file to it if the\nfile isn't known to us since before. We also add the blob to the\nobject store and write out the new tree(s) to the object store as well.\nThen we write out the new index, and then we're done. We do all that\nbottom up, as you say, or the object store will be inconsistent after\nwe started writing root objects but before we're done writing leaf\nobjects.\n\nFor a simple \"git-add\", that's it, and you'll now see \"git status\" list\nfiles as added to the index without being committed. They're what we\ncall \"staged\" at this point.\n\nIf you also do \"git commit\" after having done \"git-add\", we write out a\ncommit object, pointing to its parent commit and the root tree we\ncreated in the \"git-add\" stage. \"git cat-file -p HEAD\" will give you an\nidea of how that looks.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"225338","messageId":"CAB46HOkJhRdrkVdFv0g2Foj+K_9mXP-muAy_K8kY=3FPqwHSnw@mail.gmail.com","threadId":"34701","inReplyTo":"520DECF0.9080501@op5.se","subject":"Re: Understanding Git Under The Hood: Trees","fromName":"Erik Bernoth","fromEmail":"erik.bernoth@gmail.com","sentAt":"2013-08-16T13:13:06Z","receivedAt":"2013-08-16T13:13:06Z","isPatch":false,"sender":{"key":"erik.bernoth@gmail.com","avatar":null},"body":"Hi Andreas,\n\nyou gave me a lot of new insight and keywords I can google (Junio as\nwell!). Thanks a lot!\n\nOn Fri, Aug 16, 2013 at 11:12 AM, Andreas Ericsson <ae@op5.se> wrote:\n> More or less, yes, but please don't confuse \"directory tree\" with \"git\n> tree\". They're not the same. A directory tree can contain multiple\n> levels of directories, whereas a git tree can only contain a list\n> of objects. The index (aka \"staging area\") represents a directory tree, but\n> when it gets stored on-disk a directory tree gets broken down into\n> as many git trees as is necessary.\n\nI was confusing it in a way, that I didn't even realize that it was\nconfusion. I thought from the Git-Book chapter 9 that the index itself\nwould store a git-tree reference, like a commit does. Therefore in my\nown git add implementation I always started with reading and writing\ngit-trees without any cache in the middle. With a simple, flat index\nin the middle of course the whole problem becomes much simpler!\n\nAlso after working through the man files of the plumbing commands you\nshowed I can use that much better in my daily git usage. Can't thank\nyou guys enough!\n\nI think I start my python-git from scratch again, now that I\nunderstand everything much better. For now I assume the following\nalgorithms:\n\n a) git add path/to/file\n\n   1. read the index into a memory object (probably a dictionary like\n\"index = { 'path/to/file' : (mode, sha1), ... }\")\n   2. write a blob of path/to/file to the object store\n   3. update index[\"path/to/file\"] with the new sha1\n   4. write updated index to filesystem\n\nb) git commit -m <msg>\n\n   1. read index to memory\n   2. recursively create memory git-tree objects top-down\n   3. write git-tree objects to object store recursively bottom-up,\ntracking the sha1 of child trees for parent trees\n   4. add root-sha1 and commit-msg to memory commit object (author,\ncommitter and so on can be added later)\n   5. write commit object to object store\n   6. update HEAD (branches will be added later)\n   7. clean index (\"index = {}\")\n   8. write empty index to filesystem\n\nCheers\nErik\n"}]}