{"thread":{"id":"30011","subject":"[GSoC] Designing a faster index format","startedAt":"2012-03-20T21:17:48Z","lastAt":"2012-04-20T20:02:43Z","messageCount":36,"participants":["Thomas Gummerer","Nguyen Thai Ngoc Duy","Thomas Rast","Junio C Hamano","Michael Haggerty","david@lang.hm","Noel Grandin","Shawn Pearce","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"187359","messageId":"F9D452C3-B11E-4915-A0F2-B248F92CE5DE@gmail.com","threadId":"30011","inReplyTo":null,"subject":"[GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-20T21:17:48Z","receivedAt":"2012-03-20T21:17:48Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"Hello,\n\nI'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old from Italy. I'm currently a 3rd year Bachelor student in Applied Computer Science at the Free University of Bolzano. I started programming in High School about 8 years ago with Pascal and then learned C and Java. For some of my projects you can visit my homepage (http://tgummerer.com/projects), most of them are from university and some personal projects I did in my free time. My blog is also on the same homepage, but not really active. Unfortunately I couldn't yet participate in any bigger open source project, although I'm interested in it basically since I started programming. \n\nI would be interested in the Designing a faster index format project for Google Summer of Code. I'm using git for every project where it is possible after switching to it 2-3 years ago from svn. It would be awesome to be able to contribute to it and make it faster. I think this project could be a good fit for me, because I like trying to optimize data structures and algorithms for the best performance possible.\n\nThere are some questions I would have about the project.\nHas there already been any development or thoughts in that direction?\nIn the description databases are mentioned, but that would probably make it harder to read for other .git-reading programs?\n\nThanks,\nThomas Gummerer\n"},{"id":"187375","messageId":"CACsJy8CKqv2P2Co9MKpePfOTwe4fu-wxAYiigbYt3YHTxZ6wWQ@mail.gmail.com","threadId":"30011","inReplyTo":"F9D452C3-B11E-4915-A0F2-B248F92CE5DE@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-21T01:29:50Z","receivedAt":"2012-03-21T01:29:50Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 21, 2012 at 4:17 AM, Thomas Gummerer wrote:\n> There are some questions I would have about the project.\n> Has there already been any development or thoughts in that direction?\n\nTree-based format seems to be favored by core developers, for example\nin the footnote in [1]. But there have been no attempts to realize it.\nYou may want to search mail archive for more.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/190016\n-- \nDuy\n"},{"id":"187378","messageId":"8D287169-1AD9-4586-BDBC-F820220328FC@gmail.com","threadId":"30011","inReplyTo":"CACsJy8CKqv2P2Co9MKpePfOTwe4fu-wxAYiigbYt3YHTxZ6wWQ@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-21T09:22:30Z","receivedAt":"2012-03-21T09:22:30Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\nOn Mar 21, 2012, at 2:29 AM, Nguyen Thai Ngoc Duy wrote:\n\n> On Wed, Mar 21, 2012 at 4:17 AM, Thomas Gummerer wrote:\n>> There are some questions I would have about the project.\n>> Has there already been any development or thoughts in that direction?\n> \n> Tree-based format seems to be favored by core developers, for example\n> in the footnote in [1]. But there have been no attempts to realize it.\n> You may want to search mail archive for more.\n> \n\nThanks for your answer, so I would probably implement a tree based structure.\nHowever I got one more question, since I'm not yet really familiar with the\ncode and internal structure of git, what exactly does the SHA1 over the\nindex exactly achieve? Is it only for checking if the index is still correct\nfor the next time it is used and has not been changed or is there a more\nimportant function of it?\n\n--\nThomas Gummerer\n"},{"id":"187381","messageId":"CACsJy8D2RwG-Nr5btcQj0f9=JACvH6mf7LNi=Jnb_y+j4_2u0A@mail.gmail.com","threadId":"30011","inReplyTo":"8D287169-1AD9-4586-BDBC-F820220328FC@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-21T10:34:15Z","receivedAt":"2012-03-21T10:34:15Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 21, 2012 at 4:22 PM, Thomas Gummerer wrote:\n>\n> On Mar 21, 2012, at 2:29 AM, Nguyen Thai Ngoc Duy wrote:\n>\n>> On Wed, Mar 21, 2012 at 4:17 AM, Thomas Gummerer wrote:\n>>> There are some questions I would have about the project.\n>>> Has there already been any development or thoughts in that direction?\n>>\n>> Tree-based format seems to be favored by core developers, for example\n>> in the footnote in [1]. But there have been no attempts to realize it.\n>> You may want to search mail archive for more.\n>>\n>\n> Thanks for your answer, so I would probably implement a tree based structure.\n\nThere may be a better approach, maybe a simple database format that we\ncould immitate. It's up to you to find out :)\n\n> However I got one more question, since I'm not yet really familiar with the\n> code and internal structure of git, what exactly does the SHA1 over the\n> index exactly achieve? Is it only for checking if the index is still correct\n> for the next time it is used and has not been changed or is there a more\n> important function of it?\n\nIt makes sure the index is not corrupt (by disk faults for example). I\ndon't think it is used for anything else. Cheaper checksum can be used\nif good enough for the index. See\nhttp://thread.gmane.org/gmane.comp.version-control.git/190016 and the\nfollowing reply.\n-- \nDuy\n"},{"id":"187386","messageId":"CACsJy8Aga7OYfAL0X+SyHxaF4gzGs+cvqfX+DZNXCua8c9XMig@mail.gmail.com","threadId":"30011","inReplyTo":"CALgYhfPOJpKbM__iU4KvChWeXWyyhWb2ocR-SLvrQQHNw5F5dQ@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-21T11:18:39Z","receivedAt":"2012-03-21T11:18:39Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 21, 2012 at 6:08 PM, Thomas Gummerer wrote:\n>> > However I got one more question, since I'm not yet really familiar with\n>> > the\n>> > code and internal structure of git, what exactly does the SHA1 over the\n>> > index exactly achieve? Is it only for checking if the index is still\n>> > correct\n>> > for the next time it is used and has not been changed or is there a more\n>> > important function of it?\n>>\n>> It makes sure the index is not corrupt (by disk faults for example). I\n>> don't think it is used for anything else. Cheaper checksum can be used\n>> if good enough for the index. See\n>> http://thread.gmane.org/gmane.comp.version-control.git/190016 and the\n>> following reply.\n>\n> Ok thanks. I guess that could be another way to speed things up, but for\n> really big repositories probably it won't be enough and the reduction of the\n> complexity as described in the proposal is the way to go.\n\nYeah. A good format should not require checksuming the whole index, if\nwe only need to read/verify a few entries, I think.\n\n> Is the current complexity O(n)?\n\nI think so. Have a look at read-cache.c, read_index_from for reading\nand write_index for writing, as a starting point.\n-- \nDuy\n"},{"id":"187393","messageId":"871uomrubl.fsf@thomas.inf.ethz.ch","threadId":"30011","inReplyTo":"CACsJy8D2RwG-Nr5btcQj0f9=JACvH6mf7LNi=Jnb_y+j4_2u0A@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-21T12:51:10Z","receivedAt":"2012-03-21T12:51:10Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> On Wed, Mar 21, 2012 at 4:22 PM, Thomas Gummerer wrote:\n>>\n>> On Mar 21, 2012, at 2:29 AM, Nguyen Thai Ngoc Duy wrote:\n>>\n>> However I got one more question, since I'm not yet really familiar with the\n>> code and internal structure of git, what exactly does the SHA1 over the\n>> index exactly achieve? Is it only for checking if the index is still correct\n>> for the next time it is used and has not been changed or is there a more\n>> important function of it?\n>\n> It makes sure the index is not corrupt (by disk faults for example). I\n> don't think it is used for anything else. Cheaper checksum can be used\n> if good enough for the index. See\n> http://thread.gmane.org/gmane.comp.version-control.git/190016 and the\n> following reply.\n\nNote that switching the checksum used already requires a\nbackwards-incompatible change of the index format. If we are going to\ndo that, I'm somewhat opposed to not also revising it along the lines\nsketched by Shawn (at least).\n\nSee my reply to Elton Sky\n\n http://thread.gmane.org/gmane.comp.version-control.git/193550/focus=193571\n\nfor links to some threads you may want to look at.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"187400","messageId":"8901F6B5-7396-44E1-9687-20BF95114728@gmail.com","threadId":"30011","inReplyTo":"871uomrubl.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-21T15:43:15Z","receivedAt":"2012-03-21T15:43:15Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\nOn Mar 21, 2012, at 1:51 PM, Thomas Rast wrote:\n\n> Nguyen Thai Ngoc Duy writes:\n> \n>> On Wed, Mar 21, 2012 at 4:22 PM, Thomas Gummerer wrote:\n>>> \n>>> On Mar 21, 2012, at 2:29 AM, Nguyen Thai Ngoc Duy wrote:\n>>> \n>>> However I got one more question, since I'm not yet really familiar with the\n>>> code and internal structure of git, what exactly does the SHA1 over the\n>>> index exactly achieve? Is it only for checking if the index is still correct\n>>> for the next time it is used and has not been changed or is there a more\n>>> important function of it?\n>> \n>> It makes sure the index is not corrupt (by disk faults for example). I\n>> don't think it is used for anything else. Cheaper checksum can be used\n>> if good enough for the index. See\n>> http://thread.gmane.org/gmane.comp.version-control.git/190016 and the\n>> following reply.\n> \n> Note that switching the checksum used already requires a\n> backwards-incompatible change of the index format. If we are going to\n> do that, I'm somewhat opposed to not also revising it along the lines\n> sketched by Shawn (at least).\n> \n> See my reply to Elton Sky\n> \n> http://thread.gmane.org/gmane.comp.version-control.git/193550/focus=193571\n> \n> for links to some threads you may want to look at.\n\nWhile reworking the index into a tree (not to mention if it's in database format), \nthe backward compatibility would be broken anyway from what I understood?\nTherefore taking Shawns thoughts into account should not be a lot more work\nand should make it also easier to implement for the .git reading programs,\nsince it's easier to parse for the core it should also be easier to parse for them.\n\nThen if changing the checksum algorithm can bring some advantage I think\nit should be well worth the extra work while we break compatibility in any case.\n\n--\nThomas Gummerer\n"},{"id":"187401","messageId":"871uomq64c.fsf@thomas.inf.ethz.ch","threadId":"30011","inReplyTo":"8901F6B5-7396-44E1-9687-20BF95114728@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-03-21T16:19:15Z","receivedAt":"2012-03-21T16:19:15Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Gummerer writes:\n\n> While reworking the index into a tree (not to mention if it's in database format), \n> the backward compatibility would be broken anyway from what I understood?\n> Therefore taking Shawns thoughts into account should not be a lot more work\n> and should make it also easier to implement for the .git reading programs,\n> since it's easier to parse for the core it should also be easier to parse for them.\n>\n> Then if changing the checksum algorithm can bring some advantage I think\n> it should be well worth the extra work while we break compatibility in any case.\n\nAFAICS we are in agreement. I was saying it's not worth breaking\ncompatibility for *only* the checksum change. You are coming from the\nother side: \"once all the rest is done, the checksum change is easy\",\nwhich is probably true.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"187535","messageId":"BDFA27C9-C999-4C95-8804-5E7B3B3D1BFD@gmail.com","threadId":"30011","inReplyTo":"871uomq64c.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-22T22:51:37Z","receivedAt":"2012-03-22T22:51:37Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"As suggested on IRC, here is my first draft proposal. Should the proposal \ninclude more more technical material already, or just the general sketch of \nthe project?\n\nDesigning a faster index format\n\n-- Problem --\nThe current git index is pretty slow when working with large git repositories,\nbecause the whole index has to be rewritten for nearly every operation. For\nexample for adding a single file with git add, even though only one single blob\nsha-1 is changed in the index, the way it's currently implemented git will need\nto recompute a new hash over the whole index.\n\n-- Proposed solution --\nThe proposed solution is to rework the index, in order to make it possible to\nhave a complexity of O(log(n)), where n is the number of index entries, for \nsimple operations like adding files. \n\nThe data format will also be easily parsable in order to make it easier for\nprograms, that read the index (like jgit or libgit2), to adapt to the new \nformat.\n\nThe solution would consist of two steps. In the first step the index on the\nfilesystem would be replaced, but not mmap'd for direct access, which would \nmainly save on I/O operations. In the second step the core parts would also be\nmade aware of the new index, as it would be mmap'd for direct access.\n\nAnother way to speed up the hashing would be to exchange the SHA-1 hash for\nsomething faster. That may however not be feasible when keeping the current\nin-memory structure.\n\nTo make the project feasible for Google Summer of Code, the plan is to\nimplement the first part and if this goes smoother then expected and there is\nstill time left, the second part should also be implemented as extra work.\n\n-- Timeline --\n24/04 - 12/05: Getting familiar with the old index\n13/05 - 26/05: Come up with a exact plan for the new index and document it.\nCheck feasibility of exchanging SHA-1 with a faster checksum algorithm.\n27/05 - 30/06: Writing the new index format to disk and making it only rewrite \nthe parts that really need to be changed (Should be less writes then currently\nnecessary).\n/* Development work will be a bit slower from 18/06 to 21/07 because at my\n * University there are exams in this period. I probably will only be able to\n * work half the hours. I'll be back up to full speed after that. */\n31/06 - 28/07: Parse the index from the disk to the current in-memory format.\n29/07 - 13/08: Optimize the algorithm and profile the gains. \n\n-- Why git --\nI'm using git since about 2-3 years and wanted to contribute to it earlier, but\ncouldn't find the time to do it. I would also like to continue contributing\nonce the Summer of Code is over."},{"id":"187560","messageId":"878virfx11.fsf@thomas.inf.ethz.ch","threadId":"30011","inReplyTo":"BDFA27C9-C999-4C95-8804-5E7B3B3D1BFD@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-23T10:10:18Z","receivedAt":"2012-03-23T10:10:18Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi Thomas,\n\nThomas Gummerer writes:\n\n> 24/04 - 12/05: Getting familiar with the old index\n\nI am aware that this falls into the period for \"getting up to speed\",\nhowever I think if you spend a day or so *now* reading through\nread_index, write_index and the relevant docs. We can then give you the\nbrief rundown on cache_tree, and you'll have a much clearer picture of\nhow things fall together.\n\nI think that should lead to a lot of enlightenment and a greatly\nimproved proposal.\n\n- Thomas\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"187665","messageId":"82A01AF9-D38E-4AC4-89C5-21A01232A88A@gmail.com","threadId":"30011","inReplyTo":"878virfx11.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-25T01:28:25Z","receivedAt":"2012-03-25T01:28:25Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"I have now read through the methods and understand the cache_tree a bit \nbetter (thanks Thomas for the explanation :) ) and have rewritten my proposal \ndraft. Any suggestions are very welcome.\n\nDesigning a faster index format\n\n-- Problem --\nThe current git index is pretty slow when working with large git repositories,\nbecause the whole index has to be rewritten for nearly every operation. For\nexample for adding a single file with git add, even though logically only one \nsingle blob sha-1 is changed in the index, git has to recompute the hash over \nthe whole index and rewrite the index file.\n\n-- Proposed solution --\nThe proposed solution is to rework the index, in order to make it possible to\nhave a complexity of O(log(n)), where n is the number of index entries, for \nsimple operations like adding files. More complex operations shall also\nbenefit from the new index format, although O(log(n)). While it may not be\npossible to get to a complexity of O(log(n)), while keeping the index format\nstill easy enough to parse for other programs that read the index, the amount of\ndata for which that the hash will be computed shall be log(n).\n\nThe problem will be solved in two phases. \n\nIn phase one the pysical index format shall be replaced with the new index \nformat, which doesn't require a full recalculation of the sha-1 hash and a full\nrewrite to the disk. The new index format will be mapped to the current\nin-memory structure, which will only be changed in phase two. For further \noptimization the cache-tree the sha-1 hashes shall be mapped to the index, which\nshould avoid cache-tree invalidations. In phase the savings will mainly be on\ndisk I/O.\n\nIn phase two the core parts of git would be made aware of the new index format,\nchanging the current in-memory structure. The in-memory structure will be left\nuntouched in phase one, to allow for more testing and to make sure there won't\nbe any problems with the new index. After this phase git takes full advantage\nof the features of the new index.\n\nAnother way to speed up the hashing would be to exchange the SHA-1 hash for\nsomething faster. That may however not be feasible when keeping the current\nin-memory structure.\n\nTo make the project feasible for Google Summer of Code, the plan is to\nimplement phase one and if this goes smoother then expected and there is\nstill time left, phase two should also be implemented as bonus work.\n\n-- Timeline --\n24/04 - 12/05: Getting familiar with the old index\n24/04 - 05/05: Decide on the data structure for the new index format and \ndocument it. Check the feasibility of exchanging SHA-1 with a faster hash\nalgorithm.\n06/05 - 26/05: Map the current internal structure to the new index format.\n27/05 - 23/06: Tie the cache-tree hashes to the index hashes.\n24/06 - 21/07: Write the index to disk in the new format and make sure only the\nchanged parts are really written to disk.\n/* Development work will be a bit slower from 18/06 to 21/07 because at my\n * University there are exams in this period. I probably will only be able to\n * work half the hours. I'll be back up to full speed after that. */\n22/06 - 04/08: Parse the index from the disk to the current in-memory format.\n05/08 - 13/08: Optimize the algorithm and profile the gains. \n\n-- Why git --\nI'm using git since about 2-3 years and wanted to contribute to it earlier, but\ncouldn't find the time to do it. I would also like to continue contributing\nonce the Summer of Code is over.\n\n-- About me --\nI'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old\nfrom Italy. I'm currently a 3rd year Bachelor student in Applied Computer \nScience at the Free University of Bolzano. I started programming in High School \nabout 8 years ago with Pascal and then learned C and Java. For some of my\nprojects you can visit my homepage (http://tgummerer.com/projects), most of them\nwere for university and some personal projects I did in my free time. My blog is\nalso on the same homepage, but not really active. Unfortunately I couldn't yet \nparticipate in any bigger open source project, although I'm interested in\nit basically since I started programming. \nOn Mar 23, 2012, at 11:10 AM, Thomas Rast wrote:\n\n> Hi Thomas,\n> \n> Thomas Gummerer writes:\n> \n>> 24/04 - 12/05: Getting familiar with the old index\n> \n> I am aware that this falls into the period for \"getting up to speed\",\n> however I think if you spend a day or so *now* reading through\n> read_index, write_index and the relevant docs. We can then give you the\n> brief rundown on cache_tree, and you'll have a much clearer picture of\n> how things fall together.\n> \n> I think that should lead to a lot of enlightenment and a greatly\n> improved proposal.\n> \n> - Thomas\n> \n> -- \n> Thomas Rast\n> trast@{inf,student}.ethz.ch\n"},{"id":"187783","messageId":"2A61C352-5C71-4EDF-9DBE-01CC09AE03A5@gmail.com","threadId":"30011","inReplyTo":"878virfx11.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-26T20:35:07Z","receivedAt":"2012-03-26T20:35:07Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\nOn Mar 23, 2012, at 11:10 AM, Thomas Rast wrote:\n\n> Hi Thomas,\n> \n> Thomas Gummerer writes:\n> \n>> 24/04 - 12/05: Getting familiar with the old index\n> \n> I am aware that this falls into the period for \"getting up to speed\",\n> however I think if you spend a day or so *now* reading through\n> read_index, write_index and the relevant docs. We can then give you the\n> brief rundown on cache_tree, and you'll have a much clearer picture of\n> how things fall together.\n> \n> I think that should lead to a lot of enlightenment and a greatly\n> improved proposal.\n\nI've updated my proposal draft, which now includes a idea of backward\ncompatibility and some changes for language problems. Any comments or\nsuggestions are greatly appreciated.\n\nDesigning a faster index format\n\n-- Problem --\nThe current git index is pretty slow when working with large git repositories,\nbecause the whole index has to be rewritten for nearly every operation. For\nexample for adding a single file with git add, even though logically only one \nsingle blob sha-1 is changed in the index, git has to recompute the hash over \nthe whole index and rewrite the index file.\n\n-- Proposed solution --\nThe proposed solution is to rework the index, in order to make it possible to\nhave a complexity of O(log(n)), where n is the number of index entries, for \nsimple operations like adding files. More complex operations shall also\nbenefit from the new index format, although a complexity of O(log(n)) might not\nbe reached, while keeping the index format easy enough to parse for .git reading\nprograms. The amount of data for which that the hash will be computed however\nshall be log(n). N is the number of entries in the index.\n\nThe problem will be solved in two phases. \n\nIn phase one the pysical index format shall be replaced with the new index \nformat, which does neither require a full recalculation of the sha-1 hash nor a\nfull rewrite of the index to the disk. The new index format will be mapped to \nthe current in-memory structure, which will only be changed in phase two. For \nfurther optimization the cache-tree sha-1 hashes shall be mapped to the new \nindex format, which should avoid cache-tree invalidations. In phase one the \nsavings will mainly be on disk I/O and commands that usually cause a lot of \ncache-tree invalidations. To ensure backward compatibility, git shall keep the\nability able to read version 2/3 of the index. The user shall also have the \npossibility to configure git to write the index in either the new or the old \nformat. While this will produce some code overhead, it will make the life of git \nusers which don't use core git exclusively easier in the transition phase. \nIf the user sets the write format to the new format and the repository is a \nalready existing version 2/3 repository, the old index will be transformed to \nthe new format.\n\nIn phase two the core parts of git would be made aware of the new index format,\nchanging the current in-memory structure. The in-memory structure will be left\nuntouched in phase one, to allow for more testing and to make sure there won't\nbe any problems with the new index. After this phase git is able to take full \nadvantage of the features of the new index.\n\nAnother way to speed up the hashing would be to exchange the SHA-1 hash for\nsomething faster. That may however not be feasible while keeping the current\nin-memory structure.\n\nTo make the project feasible for Google Summer of Code, the plan is to\nimplement phase one and if this goes smoother then expected and there is\nstill time left, phase two should also be implemented as bonus work.\n\n-- Timeline --\n24/04 - 12/05: Getting familiar with the old index\n24/04 - 05/05: Decide on the data structure for the new index format and \ndocument it. Check the feasibility of exchanging SHA-1 with a faster hash\nalgorithm.\n06/05 - 26/05: Map the current internal structure to the new index format.\n27/05 - 23/06: Tie the cache-tree hashes to the index hashes.\n24/06 - 21/07: Write the index to disk in both the old and the new format\ndepending on the choice of the user and make sure only the changed parts are \nreally written to disk in the new format.\n/* Development work will be a bit slower from 18/06 to 21/07 because at my\n * University there are exams in this period. I probably will only be able to\n * work half the hours. I'll be back up to full speed after that. */\n22/06 - 04/08: Parse the index from the disk to the current in-memory format.\n05/08 - 10/08: Make sure the converstion from the old format to the new format\nworks without problems.\n11/08 - 13/08: Test the new index and profile the gains compared to the old\nformat.\n\n-- Why git --\nI'm using git since about 2-3 years and wanted to contribute to it earlier, but\ncouldn't find the time to do it. I would also like to continue contributing\nonce the Summer of Code is over.\n\n-- About me --\nI'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old\nfrom Italy. I'm currently a 3rd year Bachelor student in Applied Computer \nScience at the Free University of Bolzano. I started programming in High School \nabout 8 years ago with Pascal and then learned C and Java. For some of my\nprojects you can visit my homepage (http://tgummerer.com/projects), most of them\nwere for university and some personal projects I did in my free time. My blog is\nalso on the same homepage, but not really active. Unfortunately I couldn't yet \nparticipate in any bigger open source project, although I'm interested in\nit basically since I started programming.\n\n--\nThomas Gummerer\n"},{"id":"187786","messageId":"7vd37znjyo.fsf@alter.siamese.dyndns.org","threadId":"30011","inReplyTo":"2A61C352-5C71-4EDF-9DBE-01CC09AE03A5@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-26T21:14:23Z","receivedAt":"2012-03-26T21:14:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Gummerer writes:\n\n> The proposed solution is to rework the index, in order to make it possible to\n> have a complexity of O(log(n)), where n is the number of index entries, for \n> simple operations like adding files. More complex operations shall also\n> benefit from the new index format, although a complexity of O(log(n)) might not\n> be reached, while keeping the index format easy enough to parse for .git reading\n> programs. The amount of data for which that the hash will be computed however\n> shall be log(n). N is the number of entries in the index.\n\nWhere does log(N) come from, and is that a hard requirement?\n\nRephrasing your problem description, you want to address the inefficiency\nthat we have to write the full 1m entries to a new file in order to update\nonly one file when the index tracks 1m paths. \n\nWouldn't the goal be more in line with that problem statement if you\ninstead aim to make the cost proportional to the number of entries that\nare updated, regardless of how many entries exist in the index?\n\n> In phase one the pysical index format shall be replaced with the new index \n> format, which does neither require a full recalculation of the sha-1 hash nor a\n> full rewrite of the index to the disk. The new index format will be mapped to \n> the current in-memory structure, which will only be changed in phase two. For \n> further optimization the cache-tree sha-1 hashes shall be mapped to the new \n> index format, which should avoid cache-tree invalidations.\n\nIt is unclear what you meant by the last sentence. The cache-tree\ninvalidation is a critical part of the machinery that allows later\nwrite-tree to reuse the already computed subtree object names, without\nhaving to recompute subtree object names until they are really necessary\n(i.e. when writing a tree out). By \"avoiding\" it, are you going to make\nwrite-tree always recompute all the subtree object names? Or are you\nplanning to keep the cached tree information always up to date by\nrecomputing subtree object names and keeping them in the index even when\nthey are not yet needed? If the latter, how would you handle when a part\nof the index contains unmerged entries?\n\nRight now, the code that updates the in-core index records \"Is the in-core\nindex clean, or modified?\" bit and nothing else. Without updating the\nin-core structure and the codepaths that access it, how is it possible for\nyour phase I to selectively write out only the modified (either added,\nupdated or removed) part of it? In other words, I do not think it is\nrealistic to expect that the core parts to stay oblivious to the new index\nsemantics during the \"phase one\".\n\n> -- Timeline --\n> 24/04 - 12/05: Getting familiar with the old index\n\nIt might make more sense to write the \"proposed solution\" *after* this\nstep is done; otherwise you wouldn't even know the problems you are trying\nto solve. That may mean that this part of the schedule may need to be\nshortened or started way before the beginning of GSoC.\n"},{"id":"187846","messageId":"BC3319C2-EBDD-4E08-9FEE-88920409C537@gmail.com","threadId":"30011","inReplyTo":"7vd37znjyo.fsf@alter.siamese.dyndns.org","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-27T11:08:30Z","receivedAt":"2012-03-27T11:08:30Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\nOn Mar 26, 2012, at 11:14 PM, Junio C Hamano wrote:\n\n> Thomas Gummerer writes:\n> \n>> The proposed solution is to rework the index, in order to make it possible to\n>> have a complexity of O(log(n)), where n is the number of index entries, for \n>> simple operations like adding files. More complex operations shall also\n>> benefit from the new index format, although a complexity of O(log(n)) might not\n>> be reached, while keeping the index format easy enough to parse for .git reading\n>> programs. The amount of data for which that the hash will be computed however\n>> shall be log(n). N is the number of entries in the index.\n> \n> Where does log(N) come from, and is that a hard requirement?\n\nThe log(n) comes from the plan to implement the index in a tree-like structure. It\nisn't a hard requirement, but it certainly shouldn't be much slower than that, otherwise\nthe change wouldn't make sense.\n\n> Rephrasing your problem description, you want to address the inefficiency\n> that we have to write the full 1m entries to a new file in order to update\n> only one file when the index tracks 1m paths. \n> \n> Wouldn't the goal be more in line with that problem statement if you\n> instead aim to make the cost proportional to the number of entries that\n> are updated, regardless of how many entries exist in the index?\n\nMaking the cost proportional to the number of entries that are updated would\nbe the superior solution, but probably not possible to achieve.\n\n> \n>> In phase one the pysical index format shall be replaced with the new index \n>> format, which does neither require a full recalculation of the sha-1 hash nor a\n>> full rewrite of the index to the disk. The new index format will be mapped to \n>> the current in-memory structure, which will only be changed in phase two. For \n>> further optimization the cache-tree sha-1 hashes shall be mapped to the new \n>> index format, which should avoid cache-tree invalidations.\n> \n> It is unclear what you meant by the last sentence. The cache-tree\n> invalidation is a critical part of the machinery that allows later\n> write-tree to reuse the already computed subtree object names, without\n> having to recompute subtree object names until they are really necessary\n> (i.e. when writing a tree out). By \"avoiding\" it, are you going to make\n> write-tree always recompute all the subtree object names? Or are you\n> planning to keep the cached tree information always up to date by\n> recomputing subtree object names and keeping them in the index even when\n> they are not yet needed? If the latter, how would you handle when a part\n> of the index contains unmerged entries?\n\nThe plan was to do the latter, if it is feasible to keep them always up to date,\nwithout slowing other commands down. For the unmerged entries, I don't\nhave a plan yet, but I'll try to come up with one, when understanding the\nsource code better.\n\n> Right now, the code that updates the in-core index records \"Is the in-core\n> index clean, or modified?\" bit and nothing else. Without updating the\n> in-core structure and the codepaths that access it, how is it possible for\n> your phase I to selectively write out only the modified (either added,\n> updated or removed) part of it? In other words, I do not think it is\n> realistic to expect that the core parts to stay oblivious to the new index\n> semantics during the \"phase one\".\n\nWhen it's impossible to write only the modified part of the index without\nchanging the in-core parts, the in-core parts will only changed in the\nminimal possible way, adding only a flag for the changed parts, so only\nthose can be effectively written to disk.\n\n>> -- Timeline --\n>> 24/04 - 12/05: Getting familiar with the old index\n> \n> It might make more sense to write the \"proposed solution\" *after* this\n> step is done; otherwise you wouldn't even know the problems you are trying\n> to solve. That may mean that this part of the schedule may need to be\n> shortened or started way before the beginning of GSoC.\n\nYes, I'm currently on this, reading through documentation and source code.\n"},{"id":"187847","messageId":"87r4we9sfo.fsf@thomas.inf.ethz.ch","threadId":"30011","inReplyTo":"2A61C352-5C71-4EDF-9DBE-01CC09AE03A5@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-27T11:47:23Z","receivedAt":"2012-03-27T11:47:23Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi Thomas\n\nThomas Gummerer writes:\n\n> -- Proposed solution --\n> The proposed solution is to rework the index, in order to make it possible to\n> have a complexity of O(log(n)), where n is the number of index entries, for \n> simple operations like adding files. More complex operations shall also\n> benefit from the new index format, although a complexity of O(log(n)) might not\n> be reached, while keeping the index format easy enough to parse for .git reading\n> programs. The amount of data for which that the hash will be computed however\n> shall be log(n). N is the number of entries in the index.\n\nCan you phrase this in terms of three variables: the number of entries\n'n' in the index, the number of entries 'k' (or in the case of\nextensions, the amount of data) that must be changed, and the size of\nthe index 's'?\n\nBear in mind that the current code uses a lock-write-rename scheme and\nI'm not sure we can (or for that matter want to) change that.\n\nThat should clear up the picture somewhat and also answer Junio's concerns.\n\n> In phase one the pysical index format shall be replaced with the new index \n> format, which does neither require a full recalculation of the sha-1 hash nor a\n> full rewrite of the index to the disk. The new index format will be mapped to \n> the current in-memory structure, which will only be changed in phase two. For \n> further optimization the cache-tree sha-1 hashes shall be mapped to the new \n> index format, which should avoid cache-tree invalidations. In phase one the \n> savings will mainly be on disk I/O and commands that usually cause a lot of \n> cache-tree invalidations. To ensure backward compatibility, git shall keep the\n> ability able to read version 2/3 of the index. The user shall also have the \n> possibility to configure git to write the index in either the new or the old \n> format. While this will produce some code overhead, it will make the life of git \n> users which don't use core git exclusively easier in the transition phase. \n> If the user sets the write format to the new format and the repository is a \n> already existing version 2/3 repository, the old index will be transformed to \n> the new format.\n\nCan you split this somewhat? My wall-of-text-detector is complaining.\n\n- Backwards compatibility: good. What happens after stage two, are we\n still going to support writing the old format? If not, why?\n\n- cache-tree: I'm not sure you can skip the invalidations, at least not\n without the tie-in. We primarily want to be able to change the\n cache-tree data -- or for that matter any extension data -- cheaply\n without rewriting (or rehashing, see the s/n/k issue) the entire\n index.\n\n- cache-tree tie-in: I realize I tossed this in the air without any\n hints on how you could achieve it, but since you also allocate quite\n some development time to it I think you should outline a plan on how\n to do this.\n\n- I'm sure you can find another point :-)\n\n> Another way to speed up the hashing would be to exchange the SHA-1 hash for\n> something faster. That may however not be feasible while keeping the current\n> in-memory structure.\n\nHum, if you look where and over what this hash is currently computed,\nyou'll see what the right answer to that last non-question is...\n\n> 24/04 - 12/05: Getting familiar with the old index\n\nWhat Junio said. On top of that, I think this shouldn't take three\nweeks even if you still spend some time within the project.\n\n> 24/06 - 21/07: Write the index to disk in both the old and the new format\n> depending on the choice of the user and make sure only the changed parts are \n> really written to disk in the new format.\n\nWhat's interesting here is how you determine the changed part. Are you\nplanning to change all users to properly mark changed entries, so that\neveryone benefits (at a huge amount of code churn) or do you want to\ntake another approach?\n\n> /* Development work will be a bit slower from 18/06 to 21/07 because at my\n> * University there are exams in this period. I probably will only be able to\n> * work half the hours. I'll be back up to full speed after that. */\n\nOut of curiosity, what courses are you taking exams in?\n\n> 22/06 - 04/08: Parse the index from the disk to the current in-memory format.\n> 05/08 - 10/08: Make sure the converstion from the old format to the new format\n> works without problems.\n> 11/08 - 13/08: Test the new index and profile the gains compared to the old\n> format.\n\nI see this is partially overlaps the entries before it. What's the plan here?\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"188066","messageId":"5CE5AEC7-22C8-4911-A79E-11F2F3D902A2@gmail.com","threadId":"30011","inReplyTo":"87r4we9sfo.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-03-29T15:21:53Z","receivedAt":"2012-03-29T15:21:53Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"After the discussion on IRC and the taking your suggestions into account\nI've rewritten my proposal draft as follows.\n\n(@Thomas Rast: Since you asked, here are the courses I'm currently \ntaking: \nTeam Work Management\nCommunication and Presentation skills\n(Those are general skills, we have to do two of them)\n\nIntroduction to Artificial Intelligence\nFunctional and Logic Programming Languages)\n\nDesigning a faster index format\n\n-- Problem --\nThe current git index is pretty slow when working with large git repositories,\nbecause the whole index has to be rewritten for nearly every operation. For\nexample for adding a single file with git add, even though logically only one \nsingle blob sha-1 is changed in the index, git has to recompute the hash over \nthe whole index and rewrite the index file.\n\n-- Proposed solution --\nThe proposed solution is to rework the index, using a append-only data\nstructure. That shall allow for changes to the index in O(k) time, with k being\nthe number of files that changed. To reach this goal, the first part of the\nindex will be sorted and changes will always be written to the end, in the order\nin which the changes occured. This last part of the index will be merged with\nthe rest using a heuristic, which will be the execution of git commit and git\nstatus.\n\nTo make sure the index isn't corrupted, without calculating the sha-1 hash for\nthe whole index file every time something is changed. The hash is always\ncalculated for the whole index when merging, but when a file is changed the\nsha-1 hash is only calculated for the last entry. This has some cost when\nreading the index, but the performance improvements when writing the index\nshould more then make up for that. \n\nThe index format shall also save on file size, by storing the paths only once,\nwhich currently are stored for every file. This can make a big difference\nespecially for repositories with deep directory structures. (e.g. in the webkit\nrepository this change can save about 10MB on the index). In addition to that it\ncan also give the index a structure, which in turn makes it easier to search\nthrough. Except for the appended part, but that will never grow big enough to\nmake going through it costly.\n\nThis structure in the index could also help implement fast partial loading, from\nwhich git status and git diff could benefit from. This benefit would be fully\nexplored by a implementation with inotify, which Thomas Rast is working on.\n\nIn order to be able to only rewrite a part the way the lock file currently works\nhas to be changed. Currently the new index is always written into the lock file,\nwhich then is renamed once the writing is complete. Since we now change to an\nappend only format, if the operation fails, only the last record in the index\nis corrupted and we can easily recover by removing the corrupt record. When the\nis merged the old lock file algorithm will be used.\n\nTo maintain the speed even if a file is already in the index, git will always\nappend a new record on the end, instead of finding the record in the index and\nchanging it. This will give us a lot of benefit in terms of speed, since\notherwise we would have to search the record (log(n)), change it (1) and update\nthe sha-1 hash over the whole file (n).\n\nThe current in-memory structure of git would only have to be slightly changed,\nadding a flag or keeping a list of the changed files. The rest of it could be\nchanged in an other step, to better represent the new structure of the index.\n\nThe extensions (cache-tree and resolve undo at the moment) will be handled the\nsame way, adding changes to the end and merging at the same time when the rest\nof the index is merged. This will give changing extension entries a complexity\nof O(1) and will not be much slower when reading. Because merging will happen\nat the same time as merging the rest of the index, it won't affect performance\na lot either.\n\nTo ensure backward compatibility, git shall keep the ability able to read \nversion 2/3 of the index. The user shall also have the possibility to configure\ngit to write the index in either the new or the old format. While this will\nproduce some code overhead, it will make the life of git users which don't use \ncore git exclusively easier in the transition phase. If the user sets the write \nformat to the new format and the repository is a already existing version 2/3 \nrepository, the old index will be transformed to the new format. \n\nBackward compatibility will be broken (at least for write) once the in-memory\nstructure is changed. Git could still keep compatibility for reading the index\nand converting it to the new in-memory format, but keeping write compatibility\nwould slow down the operation and mess up the code.\n\nThere were also other formats considered for the usage in the index, which I\nwill list below with their advantages and disadvantages.\n\n- Database format\nHaving the index in a database format would be very efficient in terms of speed.\nThe integrity check also wouldn't be neccessary or rather could be handled by\nthe database. The disadvantage of using the database format however would be the\nneed to use a external library (or writing one, but that wouldn't make any\nsense). Another problem with the database are programs like jgit and libgit2 \nwould probably more problems implementing it and it would make backward\ncompatibility unreasonably hard and mess up source code at the same time.\n\n- Tree structure\nThe advantage of the tree structure over the append-only data structure that was\nproposed would be that it would not require any merge or other maintainance work\nwork after a change of a file. The disadvantage however is that changing a file\nwould always require log(n) changes to the index, where n is the number of\nentries in the index. Another problem might be the integrity check, which would\nneed either to use a hash over the whole index file or a hash on the tree,\nwhich would however take more time for checking.\n\n- Padded structure\nAnother index format that was taken into consideration was to create a padded\nstructure. Basically that would be an append-only like structure, but split into\nsection, where every section would leave some space at the end for appending.\nThis structure would not bring many advantages (probably the only advantage\nbeing a bit speed up on merging and maybe slightly faster for partial-reading)\ncompared to the append-only structure. In the meanwhile it would probably lead\nto messier code and it would be harder to parse for other programs that use\n.git.\n\nTo make the project feasible for Google Summer of Code, all the features above\nwill be implemented, except for the partial-reading and the current in-memory\nstructure will be kept, ecept for the changes necessary to keep track of the\nchanges.\n\n-- Timeline --\n24/04 - 29/04: Document the new index format.\n30/04 - 15/05: Map the current internal structure to the new index format.\n16/05 - 02/06: Change the current in-memory structure to keep track of the\nchanged files.\n02/06 - 16/06: Write the index to disk in both the old and the new format\ndepending on the choice of the user and make sure only the changed parts are \nreally written to disk in the new format.\n17/06 - 21/07: Parse the index from disk to the current in-memory format.\n/* Development work will be a bit slower from 18/06 to 21/07 because at my\n * University there are exams in this period. I probably will only be able to\n * work half the hours. I'll be back up to full speed after that. */\n22/07 - 10/08: Merge appended changes with the rest of the index.\n11/08 - 13/08: Test the new index and profile the gains compared to the old\nformat.\n\n-- Why git --\nI'm using git since about 2-3 years and wanted to contribute to it earlier, but\ncouldn't find the time to do it. I would also like to continue contributing\nonce the Summer of Code is over.\n\n-- About me --\nI'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old\nfrom Italy. I'm currently a 3rd year Bachelor student in Applied Computer \nScience at the Free University of Bolzano. I started programming in High School \nabout 8 years ago with Pascal and then learned C and Java. For some of my\nprojects you can visit my homepage (http://tgummerer.com/projects), most of them\nwere for university and some personal projects I did in my free time. My blog is\nalso on the same homepage, but not really active. Unfortunately I couldn't yet \nparticipate in any bigger open source project, although I'm interested in\nit basically since I started programming. \n"},{"id":"188095","messageId":"7vk423qfps.fsf@alter.siamese.dyndns.org","threadId":"30011","inReplyTo":"5CE5AEC7-22C8-4911-A79E-11F2F3D902A2@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-29T21:06:55Z","receivedAt":"2012-03-29T21:06:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Gummerer writes:\n\n> After the discussion on IRC and the taking your suggestions into account\n> I've rewritten my proposal draft as follows.\n\nJust a few comments after a cursory review over the draft.\n\n> -- Problem --\n> The current git index is pretty slow when working with large git repositories,\n> because the whole index has to be rewritten for nearly every operation. For\n> example for adding a single file with git add, even though logically only one \n> single blob sha-1 is changed in the index, git has to recompute the hash over \n> the whole index and rewrite the index file.\n\nIs it really the time consuming part in the overall picture? Do you have\nvital statistics for various pieces to justify that you are solving the\nright problem? E.g. (not exhaustive)\n\n - read_index(): overhead to\n - validate the checksum of the whole index;\n - extract entries into the_index.cache[] array;\n\n - write_index(): overhead to\n - serialize entries into the on-disk format;\n - compute the checksum over the entire index;\n - write the whole index to disk;\n\n - frequency of the above two operations. \n\nI think the current code tries to do the checksumming, in both read and\nwrite directions, in line with the actual I/O operation, not as a separate\nphase. You may have to instrument (read: butcher) the current code to\nreplace the streaming checksum code with no-op to measure the checksum\noverhead. In other words, running \"time git update-index foo\" from the\ncommand line and subtracting \"time sha1sum .git/index\" would not be a\nright way to compute it (it subtracts both disk I/O and checksum\noverhead).\n\nAlso, optimizing the write codepath by penalizing the read codepath is a\nwrong trade-off if the index is read far more often than it is written\nduring a single day of a developer.\n\n> -- Proposed solution --\n> The proposed solution is to rework the index, using a append-only data\n> structure. That shall allow for changes to the index in O(k) time, with k being\n> the number of files that changed. To reach this goal, the first part of the\n> index will be sorted and changes will always be written to the end, in the order\n> in which the changes occured. This last part of the index will be merged with\n> the rest using a heuristic, which will be the execution of git commit and git\n> status.\n>\n> To make sure the index isn't corrupted, without calculating the sha-1 hash for\n> the whole index file every time something is changed.\n\nThis is not a sentence. \"do Z\" in \"To do X without Y, do Z\" is missing.\n\n> The hash is always\n> calculated for the whole index when merging, but when a file is changed the\n> sha-1 hash is only calculated for the last entry.\n\nI know this is still a loosely written draft, but \"only calculated for the\nlast entry\" is very disturbing. When we say \"entry\" in the context of\nindex we always mean a single cache entry, but obviously that is not what\nyou are using this word for. You mean the last \"batch\" of entries in a\nlog structured index file format.\n\nThe new batch in the log structured file, if it were to be protected with\nthe checksum, should take the checksum of the previous part into account\nwhen computing the checksum of the new part, by chaining. Imagine an\nindex file that was written twice, consisting of parts A and B, in an\nappend-only fashion. Somewhere in part A (probably near the end but it\ndoes not have to be), there is a checksum to verify part A's consistency.\nIf the checksum for B is derived solely on the data in B, a bug could\nreplace the part B with different data C that satisfy its self consistency\ncheck, but when you take A followed by C together, the result may not make\nsense. One technique to avoid such mistakes is to use checksum in A and\ndata in B to compute checksum for B.\n\n> This has some cost when\n> reading the index, but the performance improvements when writing the index\n> should more then make up for that. \n\nObviously, \"should more than make up\" needs substanciation.\n\n> ... In addition to that it\n> can also give the index a structure, which in turn makes it easier to search\n> through.\n\nI do not think you are saying \"The current index does not have a structure\nso it is hard to search through. Let's give it a structure to make it easy\nto search.\", but then it becomes unclear what the purpose of saying \"give\nthe index a structure\" here. The sentences in this paragraph may need to\nbe reworked somewhat.\n\n> In order to be able to only rewrite a part the way the lock file currently works\n> has to be changed. Currently the new index is always written into the lock file,\n> which then is renamed once the writing is complete. Since we now change to an\n> append only format, if the operation fails, only the last record in the index\n> is corrupted and we can easily recover by removing the corrupt record.\n\nCareful.\n\nTwo processes trying to append to the same index at the same time still\nneeds to be coordinated via some kind of lock.\n\n> When the\n> is merged the old lock file algorithm will be used.\n\n-ECANNOTPARSE.\n\n> To maintain the speed even if a file is already in the index, git will always\n> append a new record on the end, instead of finding the record in the index and\n> changing it.\n\nThis makes it sound as if you think you can append without reading, but I\ndo not think that is what you meant. You would need to know what is in the\nindex to deal with D/F conflicts, so you need to \"find\" the entry (and\npaths related to it) first. The append-only arrangement allows you to\navoid updating in place, which is the plus (i.e. \"changing it\" part in the\nabove sentence is valid, \"finding\" is not).\n\n> This will give us a lot of benefit in terms of speed, since\n> otherwise we would have to search the record (log(n)), change it (1) and update\n> the sha-1 hash over the whole file (n).\n\nSee the comment about on \"search the record\" part.\n\nOf course the reader suffers because it needs to read more to learn what\nthe end result of replaying all the log records. The question is by how\nmuch.\n\nAlso you would need to worry about the case where an index entry is\nremoved (your log record needs to be able to express \"remove this path\").\n\n> Backward compatibility will be broken (at least for write) once the in-memory\n> structure is changed.\n\nThat is totally backwards, isn't it?\n\nThe in-memory structure can be improved in new implementation without any\ncompatibility issues as long as the on-disk format is not changed.\n\n> Git could still keep compatibility for reading the index\n> and converting it to the new in-memory format, but keeping write compatibility\n> would slow down the operation and mess up the code.\n\nThe new on-disk format is poorly designed if that has to happen.\n\n> -- Timeline --\n> 24/04 - 29/04: Document the new index format.\n> 30/04 - 15/05: Map the current internal structure to the new index format.\n\nThat sounds very aggressive, as I am assuming that by Apr 29 you will have\nall the data that justifies the \"new index format\" will solve whatever\nproblem you are solving and also justifies the \"problem\" you are solving\nis really what we want to solve (e.g. optimizing for writers by penalizing\nreaders, when readers are predominant, is not solving the right problem).\n"},{"id":"188126","messageId":"CACsJy8Ag9yvGwKE_oiW8T+hR2hN_fzXvGCdOJ_H44DCOm9RF0Q@mail.gmail.com","threadId":"30011","inReplyTo":"7vk423qfps.fsf@alter.siamese.dyndns.org","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-30T05:19:48Z","receivedAt":"2012-03-30T05:19:48Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Mar 30, 2012 at 4:06 AM, Junio C Hamano wrote:\n> Is it really the time consuming part in the overall picture?  Do you have\n> vital statistics for various pieces to justify that you are solving the\n> right problem?  E.g. (not exhaustive)\n>\n>  - read_index(): overhead to\n>   - validate the checksum of the whole index;\n>   - extract entries into the_index.cache[] array;\n>\n>  - write_index(): overhead to\n>   - serialize entries into the on-disk format;\n>   - compute the checksum over the entire index;\n>   - write the whole index to disk;\n>\n>  - frequency of the above two operations.\n\nAlso maybe the frequency of entry updates vs additions/removals. I\nsuspect refresh operation in some case can update a lot of entries. If\nthat's the case (and happens often), we may need special treatment for\nit because simply appending entries might be costly.\n\n> Also, optimizing the write codepath by penalizing the read codepath is a\n> wrong trade-off if the index is read far more often than it is written\n> during a single day of a developer.\n\nI suspect so too, but some measurement has to be done there. It'd be\ngood if you provide a patch to collect index operation statistics.\nSome of us can try it on for a few weeks. That would give us a better\npicture.\n\nOn Thu, Mar 29, 2012 at 10:21 PM, Thomas Gummerer wrote:\n> - Tree structure\n> The advantage of the tree structure over the append-only data structure that was\n> proposed would be that it would not require any merge or other maintainance work\n> work after a change of a file. The disadvantage however is that changing a file\n> would always require log(n) changes to the index, where n is the number of\n> entries in the index. Another problem might be the integrity check, which would\n> need either to use a hash over the whole index file or a hash on the tree,\n> which would however take more time for checking.\n\nI'd say it takes less time for checksuming because we only verify the\ntrees we read. And tree-based structure allows us to read just a\nsubdirectory, an advantage for multi-project repositories where people\nstay in a subdir most of the time. Shawn suspected crc32 checksum over\na large chunk of data may be insufficient. By hashing tree by tree,\nthe chunks are significantly shorter, making crc32 viable and cheap\ncandidate compared to sha-1 (also note that crc32 is used to verify\ncompressed objects in a pack)\n-- \nDuy\n"},{"id":"188352","messageId":"1604FE70-8B77-4EC1-823A-DC1F0334CD3A@gmail.com","threadId":"30011","inReplyTo":"CACsJy8Ag9yvGwKE_oiW8T+hR2hN_fzXvGCdOJ_H44DCOm9RF0Q@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"italyhockeyfeed@gmail.com","sentAt":"2012-04-02T21:02:39Z","receivedAt":"2012-04-02T21:02:39Z","isPatch":false,"sender":{"key":"italyhockeyfeed@gmail.com","avatar":null},"body":"After taking into consideration Junios and Duys comments, and some more\ndiscussion on IRC, I have written a new draft of the proposal. The proposed\nsolution is based on a tree-structure, as the append only structure penalizes\nthe read path, which after doing some measurements isn't the right tradeoff.\n\nIncluded in this proposal are also the index formats that were taken into\nconsideration but scrapped for one or another reason.\n\nFirst I'd like to thank all those who helped me by discussing the ideas here\non the mailing list or over at the #git-devel irc channel. \n\n-- Credits --\nBig thanks for discussing the ideas with me on IRC goes to charon, jast,\nmhagger, shruggar, GitZilla, andrew_sayers and barrbrain. Hope I didn't forget \nanyone. Thanks also to those who discussed my ideas with me on the mailing list\n(Nguyen Thai Ngoc Duy, Thomas Rast, Junio C Hamano)\n\nAnd here is the proposal:\nDesigning a faster index format\n\n-- Problem --\nThe current git index is pretty slow when working with large git repositories,\nbecause the whole index has to be rewritten for nearly every operation. For\nexample for adding a single file with git add, even though logically only one \nsingle blob sha-1 is changed in the index, git has to recompute the hash over \nthe whole index and rewrite the index file. In addition to that the speed up \nfor writing the index can not come to the expense of the read operation, since \nit is executed more often throughout a normal developers day compared to\nwriting the index. The current index also doesn't allow simple partial reading,\nwhich could help speed up some commands, like git status and git diff, which \noften don't need the whole index.\n\n-- Proposed solution --\nThe proposed solution is to redesign the index to a B-tree based format. This\nallows changes to the index in O(log(n)) time, with n being the number of\nentries in the index. \n\nThe sha1 hash, to verify the index isn't corrupted, will have to be computed \nover log(s) data in the worst case, where s is the size of the index, which \nwill be bigger then the number of entries because of the structure of the \nb-tree.\n\nThe new index format will also save on the size of each entry, by storing each\npath only once, and using it for all files in the same path. This will reduce\nthe amount of data we have to calculate the hash over, when both reading and\nwriting the index, thus having faster operations especially on repositories\nwith deep directory structures.\n\nThe tree structure will also allow for fast partial loading of the index. Since\nevery bucket of the tree will have it's own hash, the hash will only need to be\ncalculated for the parts we load. This reduces the amount of data for which the\nhash will need to be calculated. Commands like git status and git diff will\nbenefit from this. The benefit could be fully explored by a implementation with \ninotify, of which Thomas Rast created a POC. \n(https://github.com/trast/git/commit/6c9825fdca76d01fb5a83923558831743ae477bc)\n\nIn order to be able to only rewrite the parts of the index that really changed,\nthe current lock file structure will have to be changed. The new lock file\nwill keep a journal of the changes, to be able to recover in case of a crash.\nDeleting the lockfile \"commits\" the changes.\n\nThe in-memory structure will be modified in two steps. In the first step it\nwill only be modified to keep track of the changes, in order to be able to only\nwrite the changes to disk and eliminate the need to rewrite the whole tree. In \nthe second step the in-memory structure will be changed to reflect the tree \nformat, getting the full benefits from the new format.\n\nTo ensure backward compatibility, git shall keep the ability to read version \n2/3 of the index. The user shall also have the possibility to configure git to \nwrite the index in either the new or the old format. While this will produce \nsome code overhead, it will make the life of git users which don't use core git \nexclusively easier in the transition phase. If the user sets the write format to\nthe new format and the repository is a already existing version 2/3 repository, \nthe old index will be transformed to the new format. Transformations in the \nother direction will also be possible, since the in-memory format is the same.\n\nOnce the in-memory structure is changed, making git backward compatible will\nstill be possible, even though it will come at the expense of the \nreading/writing time of the old index, since the tree will have to be \nconstructed in memory from the on disk format, and transformed back to the flat\nformat when writing it back to disk.\n\nTo make the project feasible for Google Summer of Code the in-meory structure\nwill only be modified to keep track of the changes, not making it \ntree-structured yet and the partial loading will not be implemented.\n\n\n-- Solutions that were also considered --\nThese solutions will not be described in as much detail as the tree-structure,\nbut they were also considered in the process of chosing the best index format\nand will be described below.\n\n- Append-only data structure\nAn append-only data structure will allow for changes to the index in O(k) time, \nwith k being the number of files that changed. To reach this goal, the first \npart of the index will be sorted and changes will always be written to the end, \nin the order in which the changes occured. This last part of the index will be \nmerged with the rest using a heuristic, which will be the execution of git \ncommit and git status.\n\nTo make sure the index isn't corrupted, without calculating the sha1 hash for\nthe whole index file every time something is changed, the hash is always\ncalculated for the whole index when merging, but when only a single entry is \nchanged the sha-1 hash is only calculated for the last change. This will \nincrease the cost for reading the index to log(n) + k * log(k) where n is the \nnumber of entries in the sorted part of the index and k is the number of entries\nin the unsorted part of the index, which will have to be merged with the rest \nof the index.\n\nThe index format shall also save on file size, by storing the paths only once,\nwhich currently are stored for every file. This can make a big difference\nespecially for repositories with deep directory structures. (e.g. in the webkit\nrepository this change can save about 10MB on the index). In addition to that it\ncan also give the index a structure, which in turn makes it easier to search\nthrough. Except for the appended part, but that should never grow big enough to\nmake a linear search through it costly.\n\nWith this index format the lock file could be a simple empty file, since if a\noperation fails, only the last entry would be corrupted making it easy to\nrecover.\n\nThe current in-memory structure of git would only have to be slightly changed,\nadding a flag or keeping a list of the changed files. The rest of it could be\nchanged in an other step, to better represent the new structure of the index.\n\nTo ensure backward compatibility, git shall keep the ability able to read \nversion 2/3 of the index. The user shall also have the possibility to configure\ngit to write the index in either the new or the old format. While this will\nproduce some code overhead, it will make the life of git users which don't use \ncore git exclusively easier in the transition phase. If the user sets the write \nformat to the new format and the repository is a already existing version 2/3 \nrepository, the old index will be transformed to the new format. \n\nThis idea was dropped, because as mentioned in the problem description reads\nare more common then writes and therefore trading write speed for read speed\nis not a good tradeoff.\n\n- Database format\nA database format as index structure will allow for changes to the index in\nO(log(n)) time for a single change, with n always being the number of entries\nin the index, assuming a b-tree index on the path in the database.\n\nThe check for the index corruption could be left to the database, which would\nhave about the same cost as the check in the tree-structure, in the read and\nwrite direction. Partial loading with the right indices would also have the \nsame cost as the tree-structure, by executing a simple select query.\n\nThe drawback of this solution however would be the introduction of a database\nlibrary (one could also write one, but that certainly would be overkill).\nAnother drawback would be that it's harder to read for programs like libgit2\nand jgit and the codebase certainly wouldn't get any cleaner.\n\n- Padded structure\nAnother index format that was taken into consideration was to create a padded\nstructure. Basically that would be an append-only like structure, but split into\nsections, where every section would leave some space at the end for appending\nchanges. This would leave us with a complexity of O(k) where k is the number of\nsections. \n\nThis structure will bring advantages for faster partial loading, when splitting\nthe sections in the right way. \n\nThe structure was however only briefly taken into consideration, since it would\nhave close to no advantages (except for the partial loading) compared to the\nappend-only structure, would make the index file larger due to the spaces for\nappending and have the same drawbacks as the append-only structure.\n\n-- Timeline --\n24/04 - 01/05: Document the new index format.\n02/05 - 21/05: Map the current internal structure to the new index format.\n22/05 - 07/06: Change the current in-memory structure to keep track of the\nchanged files.\n08/06 - 16/06: Write the index to disk in both the old and the new format\ndepending on the choice of the user and make sure only the changed parts are \nreally written to disk in the new format.\n17/06 - 21/07: Parse the index from disk to the current in-memory format.\n/* Development work will be a bit slower from 18/06 to 21/07 because at my\n * University there are exams in this period. I probably will only be able to\n * work half the hours. I'll be back up to full speed after that. */\n22/07 - 10/08: Read the new structure and map it to the current in meory format.\nMake sure the old format still gets read correctly.\n11/08 - 13/08: Test the new index and profile the gains compared to the old\nformat.\n\n-- Why git --\nI'm using git since about 2-3 years and wanted to contribute to it earlier, but\ncouldn't find the time to do it. I would also like to continue contributing\nonce the Summer of Code is over.\n\n-- About me --\nI'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old\nfrom Italy. I'm currently a 3rd year Bachelor student in Applied Computer \nScience at the Free University of Bolzano. I started programming in High School \nabout 8 years ago with Pascal and then learned C and Java. For some of my\nprojects you can visit my homepage (http://tgummerer.com/projects), most of them\nwere for university and some personal projects I did in my free time. My blog is\nalso on the same homepage, but not really active. Unfortunately I couldn't yet \nparticipate in any bigger open source project, although I'm interested in\nit basically since I started programming. \n"},{"id":"188396","messageId":"4F7ABA19.7040408@alum.mit.edu","threadId":"30011","inReplyTo":"1604FE70-8B77-4EC1-823A-DC1F0334CD3A@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-03T08:51:37Z","receivedAt":"2012-04-03T08:51:37Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/02/2012 11:02 PM, Thomas Gummerer wrote:\n> And here is the proposal:\n> Designing a faster index format\n> \n> -- Problem --\n> The current git index is pretty slow when working with large git repositories,\n> because the whole index has to be rewritten for nearly every operation. For\n> example for adding a single file with git add, even though logically only one \n> single blob sha-1 is changed in the index, git has to recompute the hash over \n> the whole index and rewrite the index file. In addition to that the speed up \n> for writing the index can not come to the expense of the read operation, since \n> it is executed more often throughout a normal developers day compared to\n> writing the index. The current index also doesn't allow simple partial reading,\n> which could help speed up some commands, like git status and git diff, which \n> often don't need the whole index.\n> \n> -- Proposed solution --\n> The proposed solution is to redesign the index to a B-tree based format. This\n> allows changes to the index in O(log(n)) time, with n being the number of\n> entries in the index. \n\nI thought that the index lock currently only blocks writers, not readers\n(am I wrong?). So given that you want to be able to mutate the index\nfile without rewriting the whole file, it seems to me that you have to\npick from one of these alternatives:\n\n1. Change the locking semantics so that readers also block when the file\nis locked. This choice would have some important consequences: (a)\nreaders will also have to obtain a lock before starting to read. (b) to\navoid deadlock, it will become crucial that the lock is never held\nacross the execution of any other git (sub-)commands that might want to\nread the index.\n\n2. Implement a file format that can be read even while it is being\nmutated. If so, please explain the data file format in more detail; in\nparticular, how do you plan to mutate the file in a way that does not\ndisturb readers? How do you plan to read the whole index efficiently (I\nimagine that reading the whole index will remain a frequent operation)?\n\nI encourage you to include an analysis of the number of disk seeks when\nyou are analyzing the cost of read/write operations on the index. This\nwill have a strong effect on the time for working with the index when\nthe disk cache is cold. The current index requires O(1) seeks for\nreading and writing, which I believe is a big part of the reason that\nthe current read-the-whole-index/write-the-whole-index design performs\nexcellently despite the amount of data that it is touching.\n\n> [...]\n> - Append-only data structure\n> An append-only data structure will allow for changes to the index in O(k) time, \n> with k being the number of files that changed. To reach this goal, the first \n> part of the index will be sorted and changes will always be written to the end, \n> in the order in which the changes occured. This last part of the index will be \n> merged with the rest using a heuristic, which will be the execution of git \n> commit and git status.\n> \n> To make sure the index isn't corrupted, without calculating the sha1 hash for\n> the whole index file every time something is changed, the hash is always\n> calculated for the whole index when merging, but when only a single entry is \n> changed the sha-1 hash is only calculated for the last change. This will \n> increase the cost for reading the index to log(n) + k * log(k) where n is the \n> number of entries in the sorted part of the index and k is the number of entries\n> in the unsorted part of the index, which will have to be merged with the rest \n> of the index.\n\nI don't understand this analysis of the reading time. I suppose you are\nassuming that you want to read the status of a single file. But in that\ncase, it is enough to find the entry in the old index (O(log(n))\nassuming some sort of tree structure) plus do a linear scan through the\nunsorted entries (i.e., O(k), not O(k log(k))).\n\n> [...]\n> This [append-only] idea was dropped, because as mentioned in the problem description reads\n> are more common then writes and therefore trading write speed for read speed\n> is not a good tradeoff.\n\nThe amount of read speed that would have to be sacrificed depends on the\nsize of k and n. Under the assumption that k << n, the read speed of an\nappend-only index file format (with periodic compaction) would be close\nto optimal. For the append-only format, k is the number of files that\nhave been changed since the index was last rewritten (including\nduplicates if a file has been changed more than once). Supposing that\nthe index is compacted on branch changes and \"occasionally\" when k grows\ntoo large, I have the feeling that k will typically be quite small in\ncomparison to n, especially in the huge repositories that need this\noptimization.\n\nRemember that a full index rewrite/compaction will only take as long as\nit currently takes for *any* change to the index (which is not *that*\nterrible). It would also be easy to estimate the size of k and n on\nevery operation. Therefore, if an operation is expected to force a\nlarge fraction of index file entries to be invalidated, it is OK for it\nto force an index compaction to keep subsequent read operations fast.\nAnd even if, once in a blue moon, somebody changes *all* of the files in\nhis huge repository while somehow evading compaction, the time to read\nthe full index would still only be a factor of two slower than the\ncurrent design. (Granted, the time to read a single entry in this\nscenario would be much longer than the log(n) that would be possible\ngiven a pure-tree-based design.)\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"188407","messageId":"CACsJy8AbRsVq0b=K+=vqfpQOMuduNBDwignfAiiV+cvpFeS3jQ@mail.gmail.com","threadId":"30011","inReplyTo":"4F7ABA19.7040408@alum.mit.edu","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T12:28:41Z","receivedAt":"2012-04-03T12:28:41Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 3, 2012 at 3:51 PM, Michael Haggerty wrote:\n>> -- Proposed solution --\n>> The proposed solution is to redesign the index to a B-tree based format. This\n>> allows changes to the index in O(log(n)) time, with n being the number of\n>> entries in the index.\n>\n> I thought that the index lock currently only blocks writers, not readers\n> (am I wrong?).\n\nI think you are right.\n\n> So given that you want to be able to mutate the index\n> file without rewriting the whole file, it seems to me that you have to\n> pick from one of these alternatives:\n>\n> 1. Change the locking semantics so that readers also block when the file\n> is locked.  This choice would have some important consequences: (a)\n> readers will also have to obtain a lock before starting to read.  (b) to\n> avoid deadlock, it will become crucial that the lock is never held\n> across the execution of any other git (sub-)commands that might want to\n> read the index.\n>\n> 2. Implement a file format that can be read even while it is being\n> mutated.  If so, please explain the data file format in more detail; in\n> particular, how do you plan to mutate the file in a way that does not\n> disturb readers?  How do you plan to read the whole index efficiently (I\n> imagine that reading the whole index will remain a frequent operation)?\n\nCopy-on-write B-trees, aka btrfs. Does anybody like to go that route ;)\n\n> I encourage you to include an analysis of the number of disk seeks when\n> you are analyzing the cost of read/write operations on the index.  This\n> will have a strong effect on the time for working with the index when\n> the disk cache is cold.  The current index requires O(1) seeks for\n> reading and writing, which I believe is a big part of the reason that\n> the current read-the-whole-index/write-the-whole-index design performs\n> excellently despite the amount of data that it is touching.\n-- \nDuy\n"},{"id":"188428","messageId":"C15BAB9A-EAFA-4EA4-85B2-0E0C5FF473E9@gmail.com","threadId":"30011","inReplyTo":"4F7ABA19.7040408@alum.mit.edu","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"italyhockeyfeed@gmail.com","sentAt":"2012-04-03T19:07:35Z","receivedAt":"2012-04-03T19:07:35Z","isPatch":false,"sender":{"key":"italyhockeyfeed@gmail.com","avatar":null},"body":"\nOn Apr 3, 2012, at 10:51 AM, Michael Haggerty wrote:\n\n> On 04/02/2012 11:02 PM, Thomas Gummerer wrote:\n>> And here is the proposal:\n>> Designing a faster index format\n>> \n>> -- Problem --\n>> The current git index is pretty slow when working with large git repositories,\n>> because the whole index has to be rewritten for nearly every operation. For\n>> example for adding a single file with git add, even though logically only one \n>> single blob sha-1 is changed in the index, git has to recompute the hash over \n>> the whole index and rewrite the index file. In addition to that the speed up \n>> for writing the index can not come to the expense of the read operation, since \n>> it is executed more often throughout a normal developers day compared to\n>> writing the index. The current index also doesn't allow simple partial reading,\n>> which could help speed up some commands, like git status and git diff, which \n>> often don't need the whole index.\n>> \n>> -- Proposed solution --\n>> The proposed solution is to redesign the index to a B-tree based format. This\n>> allows changes to the index in O(log(n)) time, with n being the number of\n>> entries in the index. \n> \n> I thought that the index lock currently only blocks writers, not readers\n> (am I wrong?). So given that you want to be able to mutate the index\n> file without rewriting the whole file, it seems to me that you have to\n> pick from one of these alternatives:\n> \n> 1. Change the locking semantics so that readers also block when the file\n> is locked. This choice would have some important consequences: (a)\n> readers will also have to obtain a lock before starting to read. (b) to\n> avoid deadlock, it will become crucial that the lock is never held\n> across the execution of any other git (sub-)commands that might want to\n> read the index.\n> \n> 2. Implement a file format that can be read even while it is being\n> mutated. If so, please explain the data file format in more detail; in\n> particular, how do you plan to mutate the file in a way that does not\n> disturb readers? How do you plan to read the whole index efficiently (I\n> imagine that reading the whole index will remain a frequent operation)?\n\nDid not think about this first, but I will use the first alternative. The most\nimportant thing about this project is the speed and it will be best kept with\nthe first alternative. I am thinking about two different kind of locks, the read\nlock, which blocks writing, but not other reading processes and a write lock,\nwhich will block both other processes to read and write.\n\n> I encourage you to include an analysis of the number of disk seeks when\n> you are analyzing the cost of read/write operations on the index. This\n> will have a strong effect on the time for working with the index when\n> the disk cache is cold. The current index requires O(1) seeks for\n> reading and writing, which I believe is a big part of the reason that\n> the current read-the-whole-index/write-the-whole-index design performs\n> excellently despite the amount of data that it is touching.\n\nSeeking took: 429430 (cold)\nReading took: 581 (hot)\n\nReading took: 1031357 (cold)\nReading took: 53850 (hot)\n\nWriting took: 524909\n\nThis is just from a short test program I wrote. Just reads the index, and seeks\nover it (obviously not directly one after another but in different scripts). The\nwriting time is for writing the index that was read back to disk. And this is with\na highly exaggerated number of seeks (1000). \n\nAlso to take into consideration is that the disk cache will (nearly) never be \ncold since git always reads the index first.\n\n> \n>> [...]\n>> - Append-only data structure\n>> An append-only data structure will allow for changes to the index in O(k) time, \n>> with k being the number of files that changed. To reach this goal, the first \n>> part of the index will be sorted and changes will always be written to the end, \n>> in the order in which the changes occured. This last part of the index will be \n>> merged with the rest using a heuristic, which will be the execution of git \n>> commit and git status.\n>> \n>> To make sure the index isn't corrupted, without calculating the sha1 hash for\n>> the whole index file every time something is changed, the hash is always\n>> calculated for the whole index when merging, but when only a single entry is \n>> changed the sha-1 hash is only calculated for the last change. This will \n>> increase the cost for reading the index to log(n) + k * log(k) where n is the \n>> number of entries in the sorted part of the index and k is the number of entries\n>> in the unsorted part of the index, which will have to be merged with the rest \n>> of the index.\n> \n> I don't understand this analysis of the reading time. I suppose you are\n> assuming that you want to read the status of a single file. But in that\n> case, it is enough to find the entry in the old index (O(log(n))\n> assuming some sort of tree structure) plus do a linear scan through the\n> unsorted entries (i.e., O(k), not O(k log(k))).\n\nThe current way git operates it always reads the whole index, making it necessary\nto merge the unsorted entries with the sorted part. Thinking about it it would even\nbe O(k log(n)), because the appended part is unsorted.\nO(log(n)) + O(k) would be the complexity for loading only a single entry from the\nindex.\n\n> \n>> [...]\n>> This [append-only] idea was dropped, because as mentioned in the problem description reads\n>> are more common then writes and therefore trading write speed for read speed\n>> is not a good tradeoff.\n> \n> The amount of read speed that would have to be sacrificed depends on the\n> size of k and n. Under the assumption that k << n, the read speed of an\n> append-only index file format (with periodic compaction) would be close\n> to optimal. For the append-only format, k is the number of files that\n> have been changed since the index was last rewritten (including\n> duplicates if a file has been changed more than once). Supposing that\n> the index is compacted on branch changes and \"occasionally\" when k grows\n> too large, I have the feeling that k will typically be quite small in\n> comparison to n, especially in the huge repositories that need this\n> optimization.\n> \n> Remember that a full index rewrite/compaction will only take as long as\n> it currently takes for *any* change to the index (which is not *that*\n> terrible). It would also be easy to estimate the size of k and n on\n> every operation. Therefore, if an operation is expected to force a\n> large fraction of index file entries to be invalidated, it is OK for it\n> to force an index compaction to keep subsequent read operations fast.\n> And even if, once in a blue moon, somebody changes *all* of the files in\n> his huge repository while somehow evading compaction, the time to read\n> the full index would still only be a factor of two slower than the\n> current design. (Granted, the time to read a single entry in this\n> scenario would be much longer than the log(n) that would be possible\n> given a pure-tree-based design.)\n\nLets take another scenario. Someone changes a lot of files and then executes\nsome commands which would usually only read the index. In that case either you\nwould need the load time (O(n)) plus the time for merging (O(k*log(n)), as\ndescribed above plus the time for writing the index (O(n)) which usually wouldn't\nbe necessary.\n\nIn addition to that it would also be more complicated and slower to realize\nthe partial loading, which would be beneficial to a lot of commands. Taking that\ninto account the tree-based structure will be more future proof, and faster (if \nthere are enough changes in a repository) then the append-only structure."},{"id":"188431","messageId":"alpine.DEB.2.02.1204031313170.10782@asgard.lang.hm","threadId":"30011","inReplyTo":"C15BAB9A-EAFA-4EA4-85B2-0E0C5FF473E9@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"","fromEmail":"david@lang.hm","sentAt":"2012-04-03T20:15:50Z","receivedAt":"2012-04-03T20:15:50Z","isPatch":false,"sender":{"key":"david@lang.hm","avatar":null},"body":"On Tue, 3 Apr 2012, Thomas Gummerer wrote:\n\n> Lets take another scenario. Someone changes a lot of files and then executes\n> some commands which would usually only read the index. In that case either you\n> would need the load time (O(n)) plus the time for merging (O(k*log(n)), as\n> described above plus the time for writing the index (O(n)) which usually wouldn't\n> be necessary.\n\nnote that in a large repository you are not that likely to change a very \nlarge percentage of the files with one update. yes, there are some use \ncases where this happens, but in general, the number of files changed in a \nchangeset grows at a much slower rate than the total number of files in a \nrepository. As projects get big they tend to get fewer across-the-board \nchanges.\n\nDavid Lang\n"},{"id":"188522","messageId":"D97085E6-2B9F-42C5-A06D-B53422034071@gmail.com","threadId":"30011","inReplyTo":"alpine.DEB.2.02.1204031313170.10782@asgard.lang.hm","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Gummerer","fromEmail":"italyhockeyfeed@gmail.com","sentAt":"2012-04-04T20:05:49Z","receivedAt":"2012-04-04T20:05:49Z","isPatch":false,"sender":{"key":"italyhockeyfeed@gmail.com","avatar":null},"body":"This is another small revision of my proposal draft, taking into consideration\nMichael Haggerty and David Langs comments. \n\nFirst I would again like to mention the people which helped me discussing the\nideas and gave me valuable input. \n\n-- Credits --\nBig thanks for discussing the ideas with me on IRC goes to charon, jast,\nmhagger, shruggar, GitZilla, andrew_sayers and barrbrain. Hope I didn't forget \nanyone. Thanks also to those who discussed my ideas with me on the mailing list\n(Nguyen Thai Ngoc Duy, Thomas Rast, Junio C Hamano, Michael Haggerty, \nDavid Lang)\n\nDesigning a faster index format\n\n-- Problem --\nThe current git index is pretty slow when working with large git repositories,\nbecause the whole index has to be rewritten for nearly every operation. For\nexample for adding a single file with git add, even though logically only one \nsingle blob sha-1 is changed in the index, git has to recompute the hash over \nthe whole index and rewrite the index file. In addition to that the speed up \nfor writing the index can not come to the expense of the read operation, since \nit is executed more often throughout a normal developers day compared to\nwriting the index. The current index also doesn't allow simple partial reading,\nwhich could help speed up some commands, like git status and git diff, which \noften don't need the whole index.\n\n-- Proposed solution --\nThe proposed solution is to redesign the index to a B-tree based format. This\nallows changes to the index in O(log(n)) time, with n being the number of\nentries in the index. \n\nThe sha1 hash, to verify the index isn't corrupted, will have to be computed \nover log(s) data in the worst case, where s is the size of the index, which \nwill be bigger then the number of entries because of the structure of the \nb-tree.\n\nThe new index format will also save on the size of each entry, by storing each\npath only once, and using it for all files in the same path. This will reduce\nthe amount of data we have to calculate the hash over, when both reading and\nwriting the index, thus having faster operations especially on repositories\nwith deep directory structures.\n\nThe tree structure will also allow for fast partial loading of the index. Since\nevery bucket of the tree will have it's own hash, the hash will only need to be\ncalculated for the parts we load. This reduces the amount of data for which the\nhash will need to be calculated. Commands like git status and git diff will\nbenefit from this. The benefit could be fully explored by a implementation with \ninotify, of which Thomas Rast created a POC. \n(https://github.com/trast/git/commit/6c9825fdca76d01fb5a83923558831743ae477bc)\n\nIn order to be able to only rewrite the parts of the index that really changed,\nthe current lock file structure will have to be changed. The new lock file\nwill keep a journal of the changes, to be able to recover in case of a crash.\nDeleting the lockfile \"commits\" the changes. To ensure that the readers never\nread a partially mutated file, reading the index will respect the write lock.\nReaders will also have a \"read lock\", which is respected by operations that\nwrite on the index, but can be ignored by operations that read the index, such\nthat simultaneous reads are still possible.\n\nThe in-memory structure will be modified in two steps. In the first step it\nwill only be modified to keep track of the changes, in order to be able to only\nwrite the changes to disk and eliminate the need to rewrite the whole tree. In \nthe second step the in-memory structure will be changed to reflect the tree \nformat, getting the full benefits from the new format.\n\nTo ensure backward compatibility, git shall keep the ability to read version \n2/3 of the index. The user shall also have the possibility to configure git to \nwrite the index in either the new or the old format. While this will produce \nsome code overhead, it will make the life of git users which don't use core git \nexclusively easier in the transition phase. If the user sets the write format to\nthe new format and the repository is a already existing version 2/3 repository, \nthe old index will be transformed to the new format. Transformations in the \nother direction will also be possible, since the in-memory format is the same.\n\nOnce the in-memory structure is changed, making git backward compatible will\nstill be possible, even though it will come at the expense of the \nreading/writing time of the old index, since the tree will have to be \nconstructed in memory from the on disk format, and transformed back to the flat\nformat when writing it back to disk.\n\nTo make the project feasible for Google Summer of Code the in-meory structure\nwill only be modified to keep track of the changes, not making it \ntree-structured yet and the partial loading will not be implemented.\n\n\n-- Solutions that were also considered --\nThese solutions will not be described in as much detail as the tree-structure,\nbut they were also considered in the process of chosing the best index format\nand will be described below.\n\n- Append-only data structure\nAn append-only data structure will allow for changes to the index in O(k) time, \nwith k being the number of files that changed. To reach this goal, the first \npart of the index will be sorted and changes will always be written to the end, \nin the order in which the changes occured. This last part of the index will be \nmerged with the rest using a heuristic, which will be the execution of git \ncommit and git status.\n\nTo make sure the index isn't corrupted, without calculating the sha1 hash for\nthe whole index file every time something is changed, the hash is always\ncalculated for the whole index when merging, but when only a single entry is \nchanged the sha-1 hash is only calculated for the last change. This will \nincrease the cost for reading the index to log(n) + k * log(n) where n is the \nnumber of entries in the sorted part of the index and k is the number of entries\nin the unsorted part of the index, which will have to be merged with the rest \nof the index.\n\nThe index format shall also save on file size, by storing the paths only once,\nwhich currently are stored for every file. This can make a big difference\nespecially for repositories with deep directory structures. (e.g. in the webkit\nrepository this change can save about 10MB on the index). In addition to that it\ncan also give the index a structure, which in turn makes it easier to search\nthrough. Except for the appended part, but that should never grow big enough to\nmake a linear search through it costly.\n\nWith this index format the lock file could be a simple empty file, since if a\noperation fails, only the last entry would be corrupted making it easy to\nrecover.\n\nThe current in-memory structure of git would only have to be slightly changed,\nadding a flag or keeping a list of the changed files. The rest of it could be\nchanged in an other step, to better represent the new structure of the index.\n\nTo ensure backward compatibility, git shall keep the ability able to read \nversion 2/3 of the index. The user shall also have the possibility to configure\ngit to write the index in either the new or the old format. While this will\nproduce some code overhead, it will make the life of git users which don't use \ncore git exclusively easier in the transition phase. If the user sets the write \nformat to the new format and the repository is a already existing version 2/3 \nrepository, the old index will be transformed to the new format. \n\nThis idea was dropped, because as mentioned in the problem description reads\nare more common then writes and therefore trading write speed for read speed\nis not a good tradeoff. The slowdown depends mostly on the size of the appended\n(unsorted) part, which in most cases will be much less then the size of the\nsorted part, but in other cases might grow quite big. I think it is preferrable\nto have a structure that is usually faster on the read operation and where the\nread speed will not depend on the way the user works. This is worth the slight\ntrade-off in write speed. In addition to that the tree-structure will also allow\nfaster partial loading, which makes it more future-proof.\n\n- Database format\nA database format as index structure will allow for changes to the index in\nO(log(n)) time for a single change, with n always being the number of entries\nin the index, assuming a b-tree index on the path in the database.\n\nThe check for the index corruption could be left to the database, which would\nhave about the same cost as the check in the tree-structure, in the read and\nwrite direction. Partial loading with the right indices would also have the \nsame cost as the tree-structure, by executing a simple select query.\n\nThe drawback of this solution however would be the introduction of a database\nlibrary (one could also write one, but that certainly would be overkill).\nAnother drawback would be that it's harder to read for programs like libgit2\nand jgit and the codebase certainly wouldn't get any cleaner.\n\n- Padded structure\nAnother index format that was taken into consideration was to create a padded\nstructure. Basically that would be an append-only like structure, but split into\nsections, where every section would leave some space at the end for appending\nchanges. This would leave us with a complexity of O(k) where k is the number of\nsections. \n\nThis structure will bring advantages for faster partial loading, when splitting\nthe sections in the right way. \n\nThe structure was however only briefly taken into consideration, since it would\nhave close to no advantages (except for the partial loading) compared to the\nappend-only structure, would make the index file larger due to the spaces for\nappending and have the same drawbacks as the append-only structure.\n\n-- Timeline --\n24/04 - 01/05: Document the new index format.\n02/05 - 21/05: Map the current internal structure to the new index format.\n22/05 - 07/06: Change the current in-memory structure to keep track of the\nchanged files.\n08/06 - 16/06: Write the index to disk in both the old and the new format\ndepending on the choice of the user and make sure only the changed parts are \nreally written to disk in the new format.\n17/06 - 21/07: Parse the index from disk to the current in-memory format.\n/* Development work will be a bit slower from 18/06 to 21/07 because at my\n * University there are exams in this period. I probably will only be able to\n * work half the hours. I'll be back up to full speed after that. */\n22/07 - 10/08: Read the new structure and map it to the current in meory format.\nMake sure the old format still gets read correctly.\n11/08 - 13/08: Test the new index and profile the gains compared to the old\nformat.\n\n-- Why git --\nI'm using git since about 2-3 years and wanted to contribute to it earlier, but\ncouldn't find the time to do it. I would also like to continue contributing\nonce the Summer of Code is over.\n\n-- About me --\nI'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old\nfrom Italy. I'm currently a 3rd year Bachelor student in Applied Computer \nScience at the Free University of Bolzano. I started programming in High School \nabout 8 years ago with Pascal and then learned C and Java. For some of my\nprojects you can visit my homepage (http://tgummerer.com/projects), most of them\nwere for university and some personal projects I did in my free time. My blog is\nalso on the same homepage, but not really active. Unfortunately I couldn't yet \nparticipate in any bigger open source project, although I'm interested in\nit basically since I started programming. \n"},{"id":"188554","messageId":"4F7D7759.6020603@alum.mit.edu","threadId":"30011","inReplyTo":"C15BAB9A-EAFA-4EA4-85B2-0E0C5FF473E9@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-05T10:43:37Z","receivedAt":"2012-04-05T10:43:37Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/03/2012 09:07 PM, Thomas Gummerer wrote:\n> On Apr 3, 2012, at 10:51 AM, Michael Haggerty wrote:\n>> On 04/02/2012 11:02 PM, Thomas Gummerer wrote:\n>>> - Append-only data structure\n>>> [...]\n>>> To make sure the index isn't corrupted, without calculating the sha1 hash for\n>>> the whole index file every time something is changed, the hash is always\n>>> calculated for the whole index when merging, but when only a single entry is \n>>> changed the sha-1 hash is only calculated for the last change. This will \n>>> increase the cost for reading the index to log(n) + k * log(k) where n is the \n>>> number of entries in the sorted part of the index and k is the number of entries\n>>> in the unsorted part of the index, which will have to be merged with the rest \n>>> of the index.\n>>\n>> I don't understand this analysis of the reading time. I suppose you are\n>> assuming that you want to read the status of a single file. But in that\n>> case, it is enough to find the entry in the old index (O(log(n))\n>> assuming some sort of tree structure) plus do a linear scan through the\n>> unsorted entries (i.e., O(k), not O(k log(k))).\n> \n> The current way git operates it always reads the whole index, making it necessary\n> to merge the unsorted entries with the sorted part. Thinking about it it would even\n> be O(k log(n)), because the appended part is unsorted.\n> O(log(n)) + O(k) would be the complexity for loading only a single entry from the\n> index.\n\nI was confused because in your original mail you seemed to claim that\nreading the whole sorted part of the index scales like O(log(n)), where\nit certainly scales at least like O(n).\n\nTo read the whole index if using an append-only data structure, I would\ndo the following:\n\n1. Read the file header to find where the addenda begin: one seek plus O(1).\n2. Read the addenda in order (I assume each addendum to be sorted on\ndisk), and merge-sort the addenda together, discarding the earlier of\nany duplicates: one seek plus O(k) I/O plus O(k log k) computation (this\nis the worst case, if each addendum contains a single file).\n3. Read the sorted part of the file in order, while merging it together\nwith the combined addenda: one seek plus O(n) I/O plus O(n + k) computation.\n\nTotal: 3 seeks plus O(n+k) I/O plus O(n + k log(k)) computation.\n\nWhereas for a B-tree, it is hard to estimate the complexity because you\nhave provided very little detail about how you want to lay the data\nstructure out on disk. But presumably the number of seeks will be\nsignificantly larger. And if you are not careful, the number of seeks\nwill approach the number of nodes in the index O(n) or perhaps the\nnumber of added nodes (not files!) which could go something like O(k\nlog(k)).\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"188565","messageId":"4F7DAEB2.8080006@gmail.com","threadId":"30011","inReplyTo":"D97085E6-2B9F-42C5-A06D-B53422034071@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Noel Grandin","fromEmail":"noelgrandin@gmail.com","sentAt":"2012-04-05T14:39:46Z","receivedAt":"2012-04-05T14:39:46Z","isPatch":false,"sender":{"key":"noelgrandin@gmail.com","avatar":"https://gravatar.com/avatar/b685e19fd968554f6be11c7ce8f8bca0b38b6b22e3e07504f7aefae16a234374?d=mp&s=160"},"body":"\n\nOn 2012-04-04 22:05, Thomas Gummerer wrote:\n> -- Proposed solution --\n> The proposed solution is to redesign the index to a B-tree based format. This\n> allows changes to the index in O(log(n)) time, with n being the number of\n> entries in the index.\n>\nSounds like you're re-inventing one of these:\nhttp://code.google.com/p/leveldb/\nhttp://code.google.com/p/high-concurrency-btree/\n"},{"id":"188598","messageId":"87r4w1vofu.fsf@thomas.inf.ethz.ch","threadId":"30011","inReplyTo":"D97085E6-2B9F-42C5-A06D-B53422034071@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-04-05T21:49:57Z","receivedAt":"2012-04-05T21:49:57Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Gummerer writes:\n\n> -- Proposed solution --\n> The proposed solution is to redesign the index to a B-tree based format. This\n> allows changes to the index in O(log(n)) time, with n being the number of\n> entries in the index. \n\n> -- Solutions that were also considered --\n> - Append-only data structure\n> - Database format\n> - Padded structure\n\nThis is quite complete already, which I think is great, but it's still\nmissing one \"obvious\" approach: a directory-tree based layout that uses\n\"flat\" storage. That is, the entries grouped by directory and thus\narranged into the \"natural\" tree, so as to allow parsing only part of\nit. But not pulling any tricks to make it easy to change; a nontrivial\nchange would mean a rewrite. How good do you think that could be?\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"188626","messageId":"CAJo=hJssfTvGqzQtaAj+Dk_R2oU5BwY=sQQuH3=SFTf+Zcp=3A@mail.gmail.com","threadId":"30011","inReplyTo":"87r4w1vofu.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-06T03:22:26Z","receivedAt":"2012-04-06T03:22:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Apr 5, 2012 at 14:49, Thomas Rast wrote:\n> Thomas Gummerer writes:\n>\n>> -- Proposed solution --\n>> The proposed solution is to redesign the index to a B-tree based format. This\n>> allows changes to the index in O(log(n)) time, with n being the number of\n>> entries in the index.\n>\n>> -- Solutions that were also considered --\n>> - Append-only data structure\n>> - Database format\n>> - Padded structure\n>\n> This is quite complete already, which I think is great, but it's still\n> missing one \"obvious\" approach: a directory-tree based layout that uses\n> \"flat\" storage.  That is, the entries grouped by directory and thus\n> arranged into the \"natural\" tree, so as to allow parsing only part of\n> it.  But not pulling any tricks to make it easy to change; a nontrivial\n> change would mean a rewrite.  How good do you think that could be?\n\nI have been wondering this myself. Aren't most updates to the index\njust updating the stat information of an existing entry?\n\nIf so we could structure the index as flat lists for each directory\nsimilar to a canonical tree, but with a wider field to hold not just\nthe SHA-1 but also the stat information of each file. If the entry is\njust the component name (\"foo.c\" and not \"src/foo.c\") and the SHA-1\nand stat data, you can probably protect the entire entry with a CRC-32\nfor each entry. Updates can be performed in place by taking the write\nlock with index.lock as an empty file, then overwriting the SHA-1 and\nstat field followed, by updating the CRC-32. Readers that see the\nwrong CRC-32 for an entry can sleep for a short period, retry the\nread, and fail after some number of attempts if they cannot get a\nvalid read of that entry.\n\nAdding a new file or deleting an existing file from the index would\nrequire a full rewrite.\n\nWithin a single tree/directory entry, it probably doesn't have to be\nbinary searchable. Canonical trees aren't. Linear scans through a\ndirectory is OK, so long as the scans are broken up by the directory\ntree structure just like they are in canonical trees.\n\nDealing with the conflict stages during merges (1, 2, 3) could be\nhandled by appending the conflict data at the end of the index file,\nwhen conflicts are resolved this tail region could be truncated back\nto the real end of the file. A bit could be set on the normal entry in\nthe trees to denote there is a conflict, and additional stage data is\nexpected in the tail region of the file.\n"},{"id":"188657","messageId":"CACsJy8DaBxCtU7UQcc510J71zk95DMMsWdr9S3eYTupdRLjWBg@mail.gmail.com","threadId":"30011","inReplyTo":"CAJo=hJssfTvGqzQtaAj+Dk_R2oU5BwY=sQQuH3=SFTf+Zcp=3A@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-06T15:11:49Z","receivedAt":"2012-04-06T15:11:49Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Apr 6, 2012 at 10:22 AM, Shawn Pearce wrote:\n> On Thu, Apr 5, 2012 at 14:49, Thomas Rast wrote:\n>> This is quite complete already, which I think is great, but it's still\n>> missing one \"obvious\" approach: a directory-tree based layout that uses\n>> \"flat\" storage.  That is, the entries grouped by directory and thus\n>> arranged into the \"natural\" tree, so as to allow parsing only part of\n>> it.  But not pulling any tricks to make it easy to change; a nontrivial\n>> change would mean a rewrite.  How good do you think that could be?\n>\n> I have been wondering this myself. Aren't most updates to the index\n> just updating the stat information of an existing entry?\n>\n> If so we could structure the index as flat lists for each directory\n> similar to a canonical tree, but with a wider field to hold not just\n> the SHA-1 but also the stat information of each file. If the entry is\n> just the component name (\"foo.c\" and not \"src/foo.c\") and the SHA-1\n> and stat data, you can probably protect the entire entry with a CRC-32\n> for each entry. Updates can be performed in place by taking the write\n> lock with index.lock as an empty file, then overwriting the SHA-1 and\n> stat field followed, by updating the CRC-32. Readers that see the\n> wrong CRC-32 for an entry can sleep for a short period, retry the\n> read, and fail after some number of attempts if they cannot get a\n> valid read of that entry.\n\nBut does that mean the reader can have some old entries (because the\nwriter has not updated them yet by the time of reading) mixed with new\nones, i.e. inconsistent data?\n\n\n> Adding a new file or deleting an existing file from the index would\n> require a full rewrite.\n>\n> Within a single tree/directory entry, it probably doesn't have to be\n> binary searchable. Canonical trees aren't. Linear scans through a\n> directory is OK, so long as the scans are broken up by the directory\n> tree structure just like they are in canonical trees.\n>\n> Dealing with the conflict stages during merges (1, 2, 3) could be\n> handled by appending the conflict data at the end of the index file,\n> when conflicts are resolved this tail region could be truncated back\n> to the real end of the file. A bit could be set on the normal entry in\n> the trees to denote there is a conflict, and additional stage data is\n> expected in the tail region of the file.\n\n\n\n-- \nDuy\n"},{"id":"188658","messageId":"878vi8sx1x.fsf@thomas.inf.ethz.ch","threadId":"30011","inReplyTo":"CACsJy8DaBxCtU7UQcc510J71zk95DMMsWdr9S3eYTupdRLjWBg@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-04-06T15:24:26Z","receivedAt":"2012-04-06T15:24:26Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> On Fri, Apr 6, 2012 at 10:22 AM, Shawn Pearce wrote:\n>> On Thu, Apr 5, 2012 at 14:49, Thomas Rast wrote:\n>>> This is quite complete already, which I think is great, but it's still\n>>> missing one \"obvious\" approach: a directory-tree based layout that uses\n>>> \"flat\" storage.  That is, the entries grouped by directory and thus\n>>> arranged into the \"natural\" tree, so as to allow parsing only part of\n>>> it.  But not pulling any tricks to make it easy to change; a nontrivial\n>>> change would mean a rewrite.  How good do you think that could be?\n>>\n>> I have been wondering this myself. Aren't most updates to the index\n>> just updating the stat information of an existing entry?\n>>\n>> If so we could structure the index as flat lists for each directory\n>> similar to a canonical tree, but with a wider field to hold not just\n>> the SHA-1 but also the stat information of each file. If the entry is\n>> just the component name (\"foo.c\" and not \"src/foo.c\") and the SHA-1\n>> and stat data, you can probably protect the entire entry with a CRC-32\n>> for each entry. Updates can be performed in place by taking the write\n>> lock with index.lock as an empty file, then overwriting the SHA-1 and\n>> stat field followed, by updating the CRC-32. Readers that see the\n>> wrong CRC-32 for an entry can sleep for a short period, retry the\n>> read, and fail after some number of attempts if they cannot get a\n>> valid read of that entry.\n>\n> But does that mean the reader can have some old entries (because the\n> writer has not updated them yet by the time of reading) mixed with new\n> ones, i.e. inconsistent data?\n\nThat can be fixed with another CRC or hash covering the CRCs for the\nentries, so that a reader can notice a partial update.\n\nBut even so: do we make any promises that (say) git-add is atomic in the\nsense that a reader always gets the before-update results or the\nafter-update results? Non-builtins (e.g. git add -p) may make small\nincremental updates to the index, so they wouldn't be atomic anyway.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"188660","messageId":"CACsJy8AkFiiaKnqqyLEZfa+DJsRyKd6dGEN71c3q=6j3fo8jww@mail.gmail.com","threadId":"30011","inReplyTo":"878vi8sx1x.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-06T15:44:39Z","receivedAt":"2012-04-06T15:44:39Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Apr 6, 2012 at 10:24 PM, Thomas Rast wrote:\n> But even so: do we make any promises that (say) git-add is atomic in the\n> sense that a reader always gets the before-update results or the\n> after-update results?  Non-builtins (e.g. git add -p) may make small\n> incremental updates to the index, so they wouldn't be atomic anyway.\n\nTake git-checkout. I'm ok with it writing to worktree all old entries,\nor all new ones, but please not a mix.\n-- \nDuy\n"},{"id":"188665","messageId":"CAJo=hJsfXd8J3ndLTMSUFRaH4FG+4YDXdnfFZ13bC+hoA3GE8g@mail.gmail.com","threadId":"30011","inReplyTo":"CACsJy8AkFiiaKnqqyLEZfa+DJsRyKd6dGEN71c3q=6j3fo8jww@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-06T17:13:45Z","receivedAt":"2012-04-06T17:13:45Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Apr 6, 2012 at 08:44, Nguyen Thai Ngoc Duy wrote:\n> On Fri, Apr 6, 2012 at 10:24 PM, Thomas Rast wrote:\n>> But even so: do we make any promises that (say) git-add is atomic in the\n>> sense that a reader always gets the before-update results or the\n>> after-update results?  Non-builtins (e.g. git add -p) may make small\n>> incremental updates to the index, so they wouldn't be atomic anyway.\n>\n> Take git-checkout. I'm ok with it writing to worktree all old entries,\n> or all new ones, but please not a mix.\n\nWhy, what is the big deal? git-checkout has already written the file\nto the local working tree. Its now just reflecting the updated stat\ninformation in the index. If it does that after each file was touched,\nand it aborts, you still have a partially updated working tree and the\nindex will show some updated files as stat clean, but staged relative\nto HEAD. I don't think that is any better or worse than the current\nsituation where the working tree is shown as locally dirty but the\nindex has no staged files. Either way you have an aborted checkout to\nrecover from by retrying, or git reset --hard HEAD.\n\nIn the retry case, checkout actually has less to do because the files\nit already cleanly updated match where its going, and thus it doesn't\nhave to touch them again.\n"},{"id":"188668","messageId":"CACsJy8A2AKApvWJ4JqQn0e=KE1-bx_A9cmCCLxG4A7VkeOrRsg@mail.gmail.com","threadId":"30011","inReplyTo":"CAJo=hJsfXd8J3ndLTMSUFRaH4FG+4YDXdnfFZ13bC+hoA3GE8g@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-06T17:23:28Z","receivedAt":"2012-04-06T17:23:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Apr 7, 2012 at 12:13 AM, Shawn Pearce wrote:\n> On Fri, Apr 6, 2012 at 08:44, Nguyen Thai Ngoc Duy wrote:\n>> On Fri, Apr 6, 2012 at 10:24 PM, Thomas Rast wrote:\n>>> But even so: do we make any promises that (say) git-add is atomic in the\n>>> sense that a reader always gets the before-update results or the\n>>> after-update results?  Non-builtins (e.g. git add -p) may make small\n>>> incremental updates to the index, so they wouldn't be atomic anyway.\n>>\n>> Take git-checkout. I'm ok with it writing to worktree all old entries,\n>> or all new ones, but please not a mix.\n>\n> Why, what is the big deal? git-checkout has already written the file\n> to the local working tree. Its now just reflecting the updated stat\n> information in the index. If it does that after each file was touched,\n> and it aborts, you still have a partially updated working tree and the\n> index will show some updated files as stat clean, but staged relative\n> to HEAD. I don't think that is any better or worse than the current\n> situation where the working tree is shown as locally dirty but the\n> index has no staged files. Either way you have an aborted checkout to\n> recover from by retrying, or git reset --hard HEAD.\n>\n> In the retry case, checkout actually has less to do because the files\n> it already cleanly updated match where its going, and thus it doesn't\n> have to touch them again.\n\nOK, what about git-commit? If I read your description correctly, you\ncan update entry sha-1 in place too. Running cache-tree on half old\nhalf new index definitely creates a broken commit.\n\nA command can also read (which does not require lock), update its\ninternal index, then lock and write. At that time, it may accidentally\noverwrite whatever another command wrote while it was still preparing\nthe index in memory.\n-- \nDuy\n"},{"id":"188670","messageId":"CAJo=hJu_6zW3X8WtHVC6P5k14muGM_t4w_cU7Em+Y_ogJm91eA@mail.gmail.com","threadId":"30011","inReplyTo":"CACsJy8A2AKApvWJ4JqQn0e=KE1-bx_A9cmCCLxG4A7VkeOrRsg@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-06T17:56:38Z","receivedAt":"2012-04-06T17:56:38Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Apr 6, 2012 at 10:23, Nguyen Thai Ngoc Duy wrote:\n> On Sat, Apr 7, 2012 at 12:13 AM, Shawn Pearce wrote:\n>> On Fri, Apr 6, 2012 at 08:44, Nguyen Thai Ngoc Duy wrote:\n>>> On Fri, Apr 6, 2012 at 10:24 PM, Thomas Rast wrote:\n>>>> But even so: do we make any promises that (say) git-add is atomic in the\n>>>> sense that a reader always gets the before-update results or the\n>>>> after-update results?  Non-builtins (e.g. git add -p) may make small\n>>>> incremental updates to the index, so they wouldn't be atomic anyway.\n>>>\n>>> Take git-checkout. I'm ok with it writing to worktree all old entries,\n>>> or all new ones, but please not a mix.\n>>\n>> Why, what is the big deal? git-checkout has already written the file\n>> to the local working tree. Its now just reflecting the updated stat\n>> information in the index. If it does that after each file was touched,\n>> and it aborts, you still have a partially updated working tree and the\n>> index will show some updated files as stat clean, but staged relative\n>> to HEAD. I don't think that is any better or worse than the current\n>> situation where the working tree is shown as locally dirty but the\n>> index has no staged files. Either way you have an aborted checkout to\n>> recover from by retrying, or git reset --hard HEAD.\n>>\n>> In the retry case, checkout actually has less to do because the files\n>> it already cleanly updated match where its going, and thus it doesn't\n>> have to touch them again.\n>\n> OK, what about git-commit? If I read your description correctly, you\n> can update entry sha-1 in place  too.\n\nYes.\n\n> Running cache-tree on half old\n> half new index definitely creates a broken commit.\n\nHow is that possible? Each tree also has its own SHA-1 field. A\nprocess trying to update a tree's SHA-1 will have to snapshot the\ntree's contents from the index by copying the data into its own memory\nbuffer so it can compute the canonical tree data buffer, write the\nobject to the repository, and get the tree's SHA-1. It writes that\ntree's SHA-1 back to the index as of that snapshot. If there were\nconcurrent updates at the same time as git commit running, its the\nsame race condition that already exists. You don't know exactly where\nin the execution of `git commit` it takes the snapshot of the index\nthat it uses to make the commit by opening the file. Allowing in place\nupdates means the snapshot time within git commit expands to be a\nlarger portion of its running time.\n\nBasically I would argue it is already not safe to be modifying the\nindex while git commit is running. You don't know if git commit has\nalready opened the index file, or will open it after the edit. The\nonly way to be sure right now is to make your own copy of the index\nand use GIT_INDEX_FILE environment variable to make sure git commit\nuses the exact index you want.\n\n> A command can also read (which does not require lock), update its\n> internal index, then lock and write. At that time, it may accidentally\n> overwrite whatever another command wrote while it was still preparing\n> the index in memory.\n\nThis hypothetical command already has the bug you mention. It should\nbe fixed no matter what we do with regards to the index format.\n\nThe *only* safe way to update the index and prevent losing\nmodifications made by another process is to lock the index *then* read\nit, update, write back out. If you read before you take the write\nlock, you can discard edits made by another process. This is\npreciously the reason why the JGit library always opens, reads, then\ncloses the index anytime the process wants to access an entry. We need\nto make sure we are viewing the correct current version. Its even more\ncritical when the process wants to update the index, it *must* discard\nany in-memory cached data it has and re-read the index *after* the\nwrite lock has been successfully acquired.\n\n\nIMHO the risks to the update in place approach is a few things, but\nnone of them really are a problem:\n\n* Readers *must* use the retry algorithm when looking at each record\nanytime the CRC-32 on an individual entry doesn't match. Retry\nrequires using some form of backoff, because the concurrent writer\nneeds to be given time to finish the writes to the storage file. If a\nreader doesn't correctly implement a retry, they could see corruption.\n\n* Readers *must* check the CRC-32 of any entry. In fact the best way\nto read an entry is memcpy() the entry's stat/SHA-1/CRC-32 from the\nindex into another memory buffer, compute the checksum there, and\ncompare. This way the reader can be certain the entry isn't mutated\nafter it checked the CRC-32 but before it examined a particular stat\nfield. Again a buggy implementation reading from the index might not\nimplement this strategy and complain about corruption, or silently\nprocess data with corruption.\n\n* A partial write will leave a corrupted index. E.g. a process\nwriting a record is killed before it has a chance to fully write out\nthe record's data. Nobody can read that record until it is repaired.\nRepair should be possible with a combination of git reset --soft to\ncopy the SHA-1 from HEAD and recomputing the working tree's SHA-1 to\nsee if the file is really clean or not. It probably isn't, and the\nstat data will reflect it as dirty after the repair. We may have to\nput this sort of repair logic into `git status` and `git diff` as part\nof the normal \"fix clean stat\" pass.\n\n* Appending conflicting stage information to the end of the file\nduring a merge can be risky. The append might be partial. This can be\nfixed by the user by `git reset --hard HEAD` to abort the merge. A\npartial append is probably only likely when the git merge aborted\nanyway and hasn't even really left you with a sane state to try and\nresolve conflicts in.\n\n* Truncating away the conflicting stage information on the end of the\nfile can be risky, if the file system doesn't truncate back correctly.\nBut I think we can detect this and repair. If every record has a\n\"conflict\" bit set to 0 and all records CRC-32s are valid, and we hold\nthe write lock, we know any conflict data on the end is bogus and\nshould be truncated away, so we truncate again. If truncation isn't\nworking correctly on this filesystem, we rewrite the entire index\nfile.\n"},{"id":"189692","messageId":"CACsJy8ChA2ko0ox730iqP5W17U6ybm7s-CDMnEkce9J4R2o+5A@mail.gmail.com","threadId":"30011","inReplyTo":"8D2805A4-9C5F-43A9-B3ED-0DB77341A03C@gmail.com","subject":"Re: [GSoC] Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-19T10:49:47Z","receivedAt":"2012-04-19T10:49:47Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Apr 19, 2012 at 5:25 PM, Thomas Gummerer wrote:\n> As Thomas Rast pointed out on IRC today, it would be better to first\n>  implement a simple converter of the old index to the new format,\n> and then implement a faster reader for the midterm, so we have a\n> \"future-proof\" index format at the midterm and a fast reader.\n\nYou can skip the old-index reading code in the converter by writing a\ngit test command and reuse git code. It's really simple: modify\nMakefile, add your command name, say test-index-converter, to\nTEST_PROGRAMS_NEED_X, then create test-index-converter.c with this:\n\n#include \"cache\"\n\nint main(int ac, char **av)\n{\n setup_git_directory();\n read_cache();\n for (i = 0; i < cache_nr; i++) {\n struct cache_entry *ce = active_cache[i];\n /* process the entry and produce new format here */\n }\n return 0;\n}\n\n\"make test-index-converter\" will give you the command.\n\nOf course it also comes at a cost because C may be slower to write\nthan Python for new-index constructing code. Or just output something\neasy to parse in Python and write the Python converter from there.\n--\nDuy - Python ignorant\n\n> The new\n>  writing algorithm will then be implemented in the second part of the\n> Summer of Code.\n>\n> I'll just post the update on the timeline and the midterm evaluation here.\n>\n> -- Timeline --\n> 24/04 - 01/05: Document the new index format.\n> 02/05 - 11/05: Create a converter of the old index format to the new format in\n> python.\n> 12/05 - 18/06: Parse the index from disk to the current in-memory format. The\n> old index format shall still be readable.\n> 19/06 - 09/07: Implement the re-reading of a single record, if the crc32 doesn't\n> match (Meaning the record has been changed under the reader).\n> - Midterm evaluation -\n> 10/07 - 21/07:  Map the current internal structure to the new index format.\n> 22/07 - 31/07: Change the current in-memory structure to keep track of the\n> changed files.\n> 01/08 - 13/08: Write the index to disk in both the old and the new format\n> depending on the choice of the user and make sure only the changed parts are\n> really written to disk in the new format.\n> 11/08 - 13/08: Test the new index and profile the gains compared to the old\n> format.\n> /* Development work will be a bit slower from 18/06 to 21/07 because at my\n>  * University there are exams in this period. I probably will only be able to\n>  * work half the hours. I'll be back up to full speed after that. */\n>\n> -- Midterm evaluation --\n> At the midterm, there will be a python prototype for the conversion of the old\n> index format to the new \"future-proof\" index format and a faster reader for the\n> new format. The native write part will be completed in the second part of the\n> Summer of Code.\n"},{"id":"189774","messageId":"20120420200243.GA12578@sigill.intra.peff.net","threadId":"30011","inReplyTo":"877gxcoron.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-20T20:02:43Z","receivedAt":"2012-04-20T20:02:43Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 19, 2012 at 02:02:32PM +0200, Thomas Rast wrote:\n\n> > At the midterm, there will be a python prototype for the conversion of the old\n> > index format to the new \"future-proof\" index format and a faster reader for the\n> > new format. The native write part will be completed in the second part of the\n> > Summer of Code.\n> \n> I think this is the most important bit, and I'm curious if there are any\n> objections/concerns on this.\n> \n> It basically splits the project into\n> \n> - first half: design, reader, raciness/locking issues\n> - second half: writer, changes to take advantage of partial writing\n\nI am OK with prototyping, and I'm OK with doing a throw-away prototype\nin a different language. But doing a throw-away prototype that lasts\nthrough the whole first half of the project makes me a little nervous.\nI'm worried that the conversion from a python prototype to actual git\ncode in the second half is going to go badly and end up in either:\n\n 1. A half-finished implementation, because the integration means we\n have to go back and re-visit assumptions made in the prototype that\n aren't valid in git itself.\n\n 2. A conversion from python to C that is rushed and ends up doing\n things in a way that makes the conversion easier, but long term\n maintenance hard. Merge-recursive was originally written in python\n and converted to C, and it shows in the code. It's brittle, buggy,\n and hard to maintain (though that is just one data point; maybe it\n was just poorly written in the first place).\n\nSo I'd be more comfortable with the prototype being just for the design\nphase, and developing the real reader and writer simultaneously in C.\nThose implementations will also start as prototypes, but they can be\niterated on, rather than being throw-aways.\n\n-Peff\n"}]}