{"thread":{"id":"30598","subject":"[GSoC] Designing a faster index format - Progress report","startedAt":"2012-05-23T12:21:35Z","lastAt":"2012-05-29T18:33:59Z","messageCount":13,"participants":["Thomas Gummerer","Thomas Rast","Junio C Hamano","Nguyen Thai Ngoc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"191978","messageId":"20120523122135.GA58204@tgummerer.unibz.it","threadId":"30598","inReplyTo":null,"subject":"[GSoC] Designing a faster index format - Progress report","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-23T12:21:35Z","receivedAt":"2012-05-23T12:21:35Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nmhagger@alum.mit.edu, pclouds@gmail.com\nBcc: \nSubject: [GSoC] Designing a new index format - Progress update\nReply-To: \n\nAs Thomas Rast suggested yesterday on IRC, I'll give you a quick\noverview of the work that has already been done in my GSoC project.\n\n\n== Work done in the past 5 weeks ==\n\n- Definition of a tentative index file v5 format [1]. This differs\n  from the proposal in making it possible to bisect the directory\n  entries and file entries, to do a binary search. The exact bits\n  for each section were also defined. To further compress the index,\n  along with prefix compression, the stat data is hashed, since\n  it's only used for comparison, but the plain data is never used.\n  Thanks to Michael Haggerty, Nguyen Thai Ngoc Duy, Thomas Rast\n  and Robin Rosenberg for feedback.\n- Prototype of a converter from the index format v2/v3 to the index\n  format v5. [2] The converter reads the index from a git repository,\n  can output parts of the index (header, index entries as in\n  git ls-files --debug, cache tree as in test-dump-cache-tree, or\n  the reuc data). Then it writes the v5 index file format to\n  .git/index-v5. Thanks to Michael Haggerty for the code review.\n- Prototype of a reader for the new index file format. [3] The\n  reader has mainly the purpose to show the algorithm used to read\n  the index lexicographically sorted after the full name which is\n  required by the current internal memory format. Big thanks for\n  reviewing this code and giving me advice on refactoring goes\n  to Michael Haggerty.\n\n== Outlook for the next week ==\n\n- Start working on actual git code\n- Read the header of the new format\n\n[1] https://github.com/tgummerer/git/wiki/Index-file-format-v5\n[2] https://github.com/tgummerer/git/blob/pythonprototype/git-convert-index.py\n[3] https://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py\n"},{"id":"192104","messageId":"87vcjll554.fsf@thomas.inf.ethz.ch","threadId":"30598","inReplyTo":"20120523122135.GA58204@tgummerer.unibz.it","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-24T20:01:59Z","receivedAt":"2012-05-24T20:01:59Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas asked for feedback on IRC, and Michael requested that I put it in\nemail for posterity, so here goes.\n\nThis is referring to 0c9214a from git://github.com/tgummerer/git.git,\nwhere Thomas put the very early beginnings of wiring v5 parsing code\ninto read_index_from().\n\n* On the high-level history making side of things: You structured your\n  commits by \"steps of implementation\", but that sometimes does not give\n  very useful intermediate steps. for example, now your index-v5~1 just\n  prints \"Header verified\". That means it cannot be meaningfully tested,\n  or judged by tests, or some such.\n\n  That's ok as long as you are still drafting up things, but from\n  experience the most workable approach is refactor-patch-improve (or\n  sometimes patch-refactor-improve).  That is, you proceed in up to\n  three steps, each spelled as one or more commits:\n\n  - (Optionally, but in this case crucially) refactor the existing code\n    into a shape where your feature patches become simpler.  This should\n    be a true refactoring, i.e., not changing any observable behavior.\n\n  - Optionally fix any bugs you encounter along the way.\n\n  - Patch in your shiny new feature.\n\n  (Tests should of course go with the last two steps.)\n\n  This tends to make the feature patches simpler, and thus easier to\n  review.  For a long project like yours, you may end up having several\n  feature patches or even several iterations of this approach.\n\n  For a great example of just this happening, consider Junio's index-v4\n  series:\n\n  - Preparations:\n    varint: make it available outside the context of pack\n    cache.h: hide on-disk index details\n    read-cache.c: allow unaligned mapping of the index file\n    read-cache.c: make create_from_disk() report number of bytes it consumed\n\n  - Bugfix (ok, it only makes the error better)\n    read-cache.c: report the header version we do not understand\n\n  - Refactoring:\n    read-cache.c: move code to copy ondisk to incore cache to a helper function\n    read-cache.c: move code to copy incore to ondisk cache to a helper function\n\n  - The feature itself:\n    read-cache.c: read prefix-compressed names in index on-disk version v4\n    read-cache.c: write prefix-compressed names in the index\n\n  - The supporting mini-features required to use it:\n    update-index: upgrade/downgrade on-disk index version\n    unpack-trees: preserve the index file version of original\n\n  - The docs:\n    index-v4: document the entry format\n\n  Ok, you can already see that the reality is not quite as simple as my\n  initial explanations...\n\n\n* The code structure itself:\n\n  I like the split you made in the verify_hdr_* family, like so:\n\n    -static int verify_hdr(struct cache_header *hdr, unsigned long size)\n    +static int verify_hdr_version(struct cache_header *hdr, unsigned long size)\n     {\n    -       git_SHA_CTX c;\n    -       unsigned char sha1[20];\n            int hdr_version;\n     \n            if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))\n                    return error(\"bad signature\");\n            hdr_version = ntohl(hdr->hdr_version);\n    -       if (hdr_version < 2 || 4 < hdr_version)\n    +       if (hdr_version < 2 || 5 < hdr_version)\n                    return error(\"bad index version %d\", hdr_version);\n    +       return 0;\n    +}\n    +\n    +static int verify_hdr(struct cache_header *hdr, unsigned long size)\n    +{\n    +       git_SHA_CTX c;\n    +       unsigned char sha1[20];\n    +\n            git_SHA1_Init(&c);\n            git_SHA1_Update(&c, hdr, size - 20);\n            git_SHA1_Final(sha1, &c);\n\n  since it decouples version checking from the checksumming.  (Without\n  the change to make 5 an acceptable version, this could actually go in\n  a refactoring patch.)\n\n  On the other hand the read_index_from() changes show none of that\n  \"function modularity\".  Your results would be much better if you first\n  refactored the meat of read_index_from to read_index_v2_from(),\n  so that read_index_from() is essentially:\n\n    mmap();\n    verify_hdr();\n    read_index_v2_from(...);\n    munmap();\n\n  Then, in another patch, wire in your shiny new read_index_v5_from()\n  function.  Then change required to read_index_from() will be a\n  two-liner, which makes it *much* easier to see what is going on,\n  especially if you compare with your f50c747b\n\n     read-cache.c | 118 ++++++++++++++++++++++++++++++++++--------------------\n\n  80% of that is just reindentation because you are wrapping things in a\n  version test!\n\n* There's little code at this point, but I like the general direction\n  you are taking: for now, start with a flat array of index entries and\n  slurp everything in there, like the v3 code does.  Later patches can\n  then improve on that to use the features of the new format.\n\n* The struct{} layout should be such that it is not a pure coincidence\n  that hdr_version has the same position in all structures.  You\n  basically have two options to achieve this:\n\n  - You write it as a concatenation of two structs, such as\n\n      struct cache_version_header { unsigned hdr_signature, hdr_version; }\n      struct cache_header_v2      { unsigned hdr_entries; }\n\n    and similarly for v5.  The code then just reads the first struct,\n    and dispatches to read the second one depending.\n\n  - You write it as a struct-within-a-struct, so that the generic header\n    becomes a part of the version-specific ones, like\n\n      struct cache_header_v2 {\n        struct cache_version_header foo;\n        unsigned hdr_entries;\n      }\n\n    Finding a good substitute for \"foo\" is left as an exercise for the\n    reader.\n\n* Finally, on style: Your indentation is off in parts, please use a\n  tab-width of 8 spaces and use tabs for the leading indentation.\n\nCheers,\nThomas\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"192121","messageId":"7vhav5wb3j.fsf@alter.siamese.dyndns.org","threadId":"30598","inReplyTo":"87vcjll554.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-24T20:57:52Z","receivedAt":"2012-05-24T20:57:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> Thomas asked for feedback on IRC, and Michael requested that I put it in\n> email for posterity, so here goes.\n\nI agree with everything you said in your review.\n\nAs to the example index-v4 series, it needs to be stressed that the series\ndid *not* happen in the order it was presented.  While the series was\nbeing written, it looked pretty much \"Ok, now we can read the header but\nnothing else works\" kind of \"implemetation steps\".  Only very few people\ncan write a series in the right presentation order from the beginning.\n\nThanks for a nice summary of what is happening.\n"},{"id":"192160","messageId":"CACsJy8As2SQwEi2vHAQA+OeH+TjoCzzcknFbQ2tGXaWX7zsHVA@mail.gmail.com","threadId":"30598","inReplyTo":"20120523122135.GA58204@tgummerer.unibz.it","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-25T11:31:14Z","receivedAt":"2012-05-25T11:31:14Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, May 23, 2012 at 7:21 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:\n> == Outlook for the next week ==\n>\n> - Start working on actual git code\n> - Read the header of the new format\n\nI know it's out of scope, but it would be great if you could make\nls-files read the new index format directly. Having something that\nactual works will ensure we don't overlook anything in the new format.\nWe can then learn from ls-files lesson (especially how to handle both\nnew/old format) and come up with api/in-core structures for the rest\nof git later.\n-- \nDuy\n"},{"id":"192205","messageId":"20120525201547.GB86874@tgummerer","threadId":"30598","inReplyTo":"CACsJy8As2SQwEi2vHAQA+OeH+TjoCzzcknFbQ2tGXaWX7zsHVA@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-25T20:15:47Z","receivedAt":"2012-05-25T20:15:47Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 05/25, Nguyen Thai Ngoc Duy wrote:\n> On Wed, May 23, 2012 at 7:21 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:\n> > == Outlook for the next week ==\n> >\n> > - Start working on actual git code\n> > - Read the header of the new format\n> \n> I know it's out of scope, but it would be great if you could make\n> ls-files read the new index format directly. Having something that\n> actual works will ensure we don't overlook anything in the new format.\n> We can then learn from ls-files lesson (especially how to handle both\n> new/old format) and come up with api/in-core structures for the rest\n> of git later.\n\nThanks for your suggestion. How did you think this should be done?\nWriting a extra function in ls-files, just for outputting? I don't\nthink it is necessary to write a extra function, since the result\nfrom the read_index_from function in read-cache is used for that\nanyway. Or did you have something different in mind, that I'm missing\nhere?\n\n--\nThomas\n"},{"id":"192221","messageId":"CACsJy8BRWmqz+2_A5_=1S9_sxOQa9GXnPQ7J1Y6id0_vh2-=+Q@mail.gmail.com","threadId":"30598","inReplyTo":"20120525201547.GB86874@tgummerer","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-26T04:09:07Z","receivedAt":"2012-05-26T04:09:07Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, May 26, 2012 at 3:15 AM, Thomas Gummerer <t.gummerer@gmail.com> wrote:\n> On 05/25, Nguyen Thai Ngoc Duy wrote:\n>> On Wed, May 23, 2012 at 7:21 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:\n>> > == Outlook for the next week ==\n>> >\n>> > - Start working on actual git code\n>> > - Read the header of the new format\n>>\n>> I know it's out of scope, but it would be great if you could make\n>> ls-files read the new index format directly. Having something that\n>> actual works will ensure we don't overlook anything in the new format.\n>> We can then learn from ls-files lesson (especially how to handle both\n>> new/old format) and come up with api/in-core structures for the rest\n>> of git later.\n>\n> Thanks for your suggestion. How did you think this should be done?\n> Writing a extra function in ls-files, just for outputting? I don't\n> think it is necessary to write a extra function, since the result\n> from the read_index_from function in read-cache is used for that\n> anyway. Or did you have something different in mind, that I'm missing\n> here?\n\nNo, read_index_from would go through the normal tree->list conversion.\nWhat I'd like to see is what it looks like when a command accesses\nindex v5 directly in tree form, taking all advantages that tree-form\nprovides, and how we should deal with old index versions while still\nsupporting index v5 (without losing tree advantages)\n-- \nDuy\n"},{"id":"192263","messageId":"20120527090407.GD86874@tgummerer","threadId":"30598","inReplyTo":"CACsJy8BRWmqz+2_A5_=1S9_sxOQa9GXnPQ7J1Y6id0_vh2-=+Q@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-27T09:04:07Z","receivedAt":"2012-05-27T09:04:07Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/26, Nguyen Thai Ngoc Duy wrote:\n> On Sat, May 26, 2012 at 3:15 AM, Thomas Gummerer <t.gummerer@gmail.com> wrote:\n> > On 05/25, Nguyen Thai Ngoc Duy wrote:\n> >> On Wed, May 23, 2012 at 7:21 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:\n> >> > == Outlook for the next week ==\n> >> >\n> >> > - Start working on actual git code\n> >> > - Read the header of the new format\n> >>\n> >> I know it's out of scope, but it would be great if you could make\n> >> ls-files read the new index format directly. Having something that\n> >> actual works will ensure we don't overlook anything in the new format.\n> >> We can then learn from ls-files lesson (especially how to handle both\n> >> new/old format) and come up with api/in-core structures for the rest\n> >> of git later.\n> >\n> > Thanks for your suggestion. How did you think this should be done?\n> > Writing a extra function in ls-files, just for outputting? I don't\n> > think it is necessary to write a extra function, since the result\n> > from the read_index_from function in read-cache is used for that\n> > anyway. Or did you have something different in mind, that I'm missing\n> > here?\n> \n> No, read_index_from would go through the normal tree->list conversion.\n> What I'd like to see is what it looks like when a command accesses\n> index v5 directly in tree form, taking all advantages that tree-form\n> provides, and how we should deal with old index versions while still\n> supporting index v5 (without losing tree advantages)\n\nAh ok, thanks for the clarification, I understand what you meant now.\nI think however, that it's not very beneficial to do this conversion\nnow. git ls-files needs the whole index file anyway, so it's probably\nnot a very good test.\n"},{"id":"192264","messageId":"7vbolaotwj.fsf@alter.siamese.dyndns.org","threadId":"30598","inReplyTo":"20120527090407.GD86874@tgummerer","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-27T09:27:56Z","receivedAt":"2012-05-27T09:27:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Gummerer <t.gummerer@gmail.com> writes:\n\n>> No, read_index_from would go through the normal tree->list conversion.\n>> What I'd like to see is what it looks like when a command accesses\n>> index v5 directly in tree form, taking all advantages that tree-form\n>> provides, and how we should deal with old index versions while still\n>> supporting index v5 (without losing tree advantages)\n>\n> Ah ok, thanks for the clarification, I understand what you meant now.\n> I think however, that it's not very beneficial to do this conversion\n> now. git ls-files needs the whole index file anyway, so it's probably\n> not a very good test.\n\nThink about \"git ls-files t/\" and \"git ls-files -u\".  \n\nThe former obviously does *not* have to look at the whole thing, even\nthough the current code assumes the in-core data structure that has the\nwhole thing in a flat array.  IIRC, you had unmerged entries tucked at the\nend outside the main index data, so the latter is also an interesting\ndemonstration of how wonderful the new data format could be.\n\nUnlike other commands like status and diff that may need to look at things\nother than the index, the core functionalitly of ls-files is purely about\nthe index.  I do not understand why you think it is not a good test case.\nIf an updated index structure cannot even improve ls-files, there is no\nhope it can improve other more complex commands that need to walk the\nindex and something else in parallel.\n"},{"id":"192266","messageId":"CACsJy8D+WgEr4i2H-1oiBLY5oLurM0aNxGovbVEZDvr7OGgknw@mail.gmail.com","threadId":"30598","inReplyTo":"7vbolaotwj.fsf@alter.siamese.dyndns.org","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-27T12:23:07Z","receivedAt":"2012-05-27T12:23:07Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, May 27, 2012 at 4:27 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Thomas Gummerer <t.gummerer@gmail.com> writes:\n>\n>>> No, read_index_from would go through the normal tree->list conversion.\n>>> What I'd like to see is what it looks like when a command accesses\n>>> index v5 directly in tree form, taking all advantages that tree-form\n>>> provides, and how we should deal with old index versions while still\n>>> supporting index v5 (without losing tree advantages)\n>>\n>> Ah ok, thanks for the clarification, I understand what you meant now.\n>> I think however, that it's not very beneficial to do this conversion\n>> now. git ls-files needs the whole index file anyway, so it's probably\n>> not a very good test.\n>\n> Think about \"git ls-files t/\" and \"git ls-files -u\".\n\nOr harder things like \"ls-files -- 't/*.sh'\"\n\n> The former obviously does *not* have to look at the whole thing, even\n> though the current code assumes the in-core data structure that has the\n> whole thing in a flat array.  IIRC, you had unmerged entries tucked at the\n> end outside the main index data, so the latter is also an interesting\n> demonstration of how wonderful the new data format could be.\n\nand \"ls-files -uc\" can show how you combine unmerged entries back.\nThere's also entry existence check deep in \"ls-files -o\" that you can\nshow how good bsearch on trees is, though that might be going too far\nfor an experiment because the call chain is really deep, way outside\nls-files.c:\n\nshow_files (builtin/ls-files.c)\n fill_directory (dir.c)\n  read_directory\n   read_directory_recursive\n    treat_path\n     treat_one_path\n      treat_directory\n       directory_exists_in_index\n        cache_pos_name (read-cache.c)\n\nI just want to make sure that by exercising the new format with some\nreal problems, we are certain we don't overlook anything in designing\nthe format (or else could be fixed before finalizing it).\n-- \nDuy\n"},{"id":"192313","messageId":"20120528082633.GA6449@tgummerer","threadId":"30598","inReplyTo":"CACsJy8D+WgEr4i2H-1oiBLY5oLurM0aNxGovbVEZDvr7OGgknw@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-28T08:26:33Z","receivedAt":"2012-05-28T08:26:33Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/27, Nguyen Thai Ngoc Duy wrote:\n> On Sun, May 27, 2012 at 4:27 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> > Thomas Gummerer <t.gummerer@gmail.com> writes:\n> >\n> >>> No, read_index_from would go through the normal tree->list conversion.\n> >>> What I'd like to see is what it looks like when a command accesses\n> >>> index v5 directly in tree form, taking all advantages that tree-form\n> >>> provides, and how we should deal with old index versions while still\n> >>> supporting index v5 (without losing tree advantages)\n> >>\n> >> Ah ok, thanks for the clarification, I understand what you meant now.\n> >> I think however, that it's not very beneficial to do this conversion\n> >> now. git ls-files needs the whole index file anyway, so it's probably\n> >> not a very good test.\n> >\n> > Think about \"git ls-files t/\" and \"git ls-files -u\".\n> \n> Or harder things like \"ls-files -- 't/*.sh'\"\n> \n> > The former obviously does *not* have to look at the whole thing, even\n> > though the current code assumes the in-core data structure that has the\n> > whole thing in a flat array.  IIRC, you had unmerged entries tucked at the\n> > end outside the main index data, so the latter is also an interesting\n> > demonstration of how wonderful the new data format could be.\n> \n> and \"ls-files -uc\" can show how you combine unmerged entries back.\n> There's also entry existence check deep in \"ls-files -o\" that you can\n> show how good bsearch on trees is, though that might be going too far\n> for an experiment because the call chain is really deep, way outside\n> ls-files.c:\n> \n> show_files (builtin/ls-files.c)\n>  fill_directory (dir.c)\n>   read_directory\n>    read_directory_recursive\n>     treat_path\n>      treat_one_path\n>       treat_directory\n>        directory_exists_in_index\n>         cache_pos_name (read-cache.c)\n> \n> I just want to make sure that by exercising the new format with some\n> real problems, we are certain we don't overlook anything in designing\n> the format (or else could be fixed before finalizing it).\n\nOk, that makes sense. I just thought of git ls-files alone, for which\nit wouldn't make a lot of sense. I'll try implementing this as next\nstep.\n"},{"id":"192416","messageId":"87vcjfi09m.fsf@thomas.inf.ethz.ch","threadId":"30598","inReplyTo":"CACsJy8D+WgEr4i2H-1oiBLY5oLurM0aNxGovbVEZDvr7OGgknw@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-29T13:29:09Z","receivedAt":"2012-05-29T13:29:09Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n\n> On Sun, May 27, 2012 at 4:27 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>> Thomas Gummerer <t.gummerer@gmail.com> writes:\n>>\n>>> Ah ok, thanks for the clarification, I understand what you meant now.\n>>> I think however, that it's not very beneficial to do this conversion\n>>> now. git ls-files needs the whole index file anyway, so it's probably\n>>> not a very good test.\n>>\n>> Think about \"git ls-files t/\" and \"git ls-files -u\".\n>\n> Or harder things like \"ls-files -- 't/*.sh'\"\n>\n>> The former obviously does *not* have to look at the whole thing, even\n>> though the current code assumes the in-core data structure that has the\n>> whole thing in a flat array.  IIRC, you had unmerged entries tucked at the\n>> end outside the main index data, so the latter is also an interesting\n>> demonstration of how wonderful the new data format could be.\n>\n> and \"ls-files -uc\" can show how you combine unmerged entries back.\n> There's also entry existence check deep in \"ls-files -o\" that you can\n> show how good bsearch on trees is, though that might be going too far\n> for an experiment because the call chain is really deep, way outside\n> ls-files.c:\n>a\n> show_files (builtin/ls-files.c)\n>  fill_directory (dir.c)\n>   read_directory\n>    read_directory_recursive\n>     treat_path\n>      treat_one_path\n>       treat_directory\n>        directory_exists_in_index\n>         cache_pos_name (read-cache.c)\n>\n> I just want to make sure that by exercising the new format with some\n> real problems, we are certain we don't overlook anything in designing\n> the format (or else could be fixed before finalizing it).\n\nI envision an index API that more strictly controls access to the index.\nRight now the API consists largely of read_index, write_index and the\nflat the_index->cache array of entries.  Eventually it will have to be a\nfamily of calls that support the v5 format, and boil down to suitable\nwrappers for older ones.  For example (just tossing up ideas):\n\n  index_open(struct index_state *index, int fd):\n    initialization, checking, leaves the \"real\" data fields empty\n\n  index_load_filtered(..., const char **pathspec):\n    load everything needed to satisfy queries filtered by 'pathspec'\n\n  index_for_each_entry(..., void (*callback)(struct cache_entry *ent)):\n    like the current hand-rolled looping\n\n  index_for_each_entry_filtered(..., void (*callback)(struct cache_entry *ent), char **pathspec):\n    ditto but for a pathspec lookup\n\netc.\n\nThen I will twist Duy's words to mean that you should make git-ls-files\nthe poster child of this new API for development and profiling purposes\n:-)\n\nActually converting the rest of the git code base to such an API is too\nbig an undertaking for the summer, so please don't stray on that path.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"192417","messageId":"CACsJy8C1j6MT9ho2TRUKBG0bpB+hg8rhiAE4QEsf-_X-55c59A@mail.gmail.com","threadId":"30598","inReplyTo":"87vcjfi09m.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-29T13:43:52Z","receivedAt":"2012-05-29T13:43:52Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, May 29, 2012 at 8:29 PM, Thomas Rast <trast@student.ethz.ch> wrote:\n> I envision an index API that more strictly controls access to the index.\n> Right now the API consists largely of read_index, write_index and the\n> flat the_index->cache array of entries.  Eventually it will have to be a\n> family of calls that support the v5 format, and boil down to suitable\n> wrappers for older ones.  For example (just tossing up ideas):\n>\n>  index_open(struct index_state *index, int fd):\n>    initialization, checking, leaves the \"real\" data fields empty\n>\n>  index_load_filtered(..., const char **pathspec):\n>    load everything needed to satisfy queries filtered by 'pathspec'\n>\n>  index_for_each_entry(..., void (*callback)(struct cache_entry *ent)):\n>    like the current hand-rolled looping\n>\n>  index_for_each_entry_filtered(..., void (*callback)(struct cache_entry *ent), char **pathspec):\n>    ditto but for a pathspec lookup\n>\n> etc.\n\nI'm towards readdir interface with filter flags (e.g. staged entries\nonly, unmerged only, all...) for serial access and something like\nstat() for one-file check. That may be enough for ls-files conversion.\nWith readdir-like interface where entries are sorted, I can help add\npathspec support to tree_entry_interesting(). This function can be\nused by new ls-files to filter pathspec instead of the list-based\npathspec_matches().\n\nOne thing to consider is, will this new API work with old versions too\n(i.e. can conversion be hidden behind the scene without significant\nperformance loss)? If it does, great we only have to maintain one API,\nthe future is bright. Otherwise, I don't know..\n\n> Actually converting the rest of the git code base to such an API is too\n> big an undertaking for the summer, so please don't stray on that path.\n\nAgreed.\n-- \nDuy\n"},{"id":"192423","messageId":"7vzk8q4z1k.fsf@alter.siamese.dyndns.org","threadId":"30598","inReplyTo":"87vcjfi09m.fsf@thomas.inf.ethz.ch","subject":"Re: [GSoC] Designing a faster index format - Progress report","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-29T18:33:59Z","receivedAt":"2012-05-29T18:33:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> Then I will twist Duy's words to mean that you should make git-ls-files\n> the poster child of this new API for development and profiling purposes\n> :-)\n\nExactly.\n\n> Actually converting the rest of the git code base to such an API is too\n> big an undertaking for the summer, so please don't stray on that path.\n\nDidn't I say that this topic is too big for a GSoC task _way_ before\nGSoC organization application started?  Without meaningful portion\nof the codebase using the newly proposed data stracture and giving\ndemonstratably better performance figure, it is very hard to justify\nthat the project completed successfully at the end of the summer.\n"}]}