{"thread":{"id":"31077","subject":"[GSoC] Designing a faster index format - Progress report week 14","startedAt":"2012-07-23T19:08:47Z","lastAt":"2012-07-24T07:52:52Z","messageCount":3,"participants":["Thomas Gummerer","Nguyen Thai Ngoc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"195555","messageId":"20120723190847.GA40532@tgummerer.surfnet.iacbox","threadId":"31077","inReplyTo":null,"subject":"[GSoC] Designing a faster index format - Progress report week 14","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-07-23T19:08:47Z","receivedAt":"2012-07-23T19:08:47Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"== Work done in the previous 13 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 equality comparison, but the plain data is\n 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- Read the on-disk index file format and translate it to the current\n in memory format. This doesn't include reading any of the current\n extensions, which are now part of the main index. The code again\n is on github. [4] Thanks for reviewing the first steps to Thomas\n Rast.\n- Read the cache-tree data (formerly an extension, now it's integrated\n with the rest of the directory data) from the new ondisk format.\n There are still a few optimizations to do in this algorithm.\n- Started implementing the API (suggested by Duy), but it's still\n in the very early stages. There is one commit for this on GitHub [1],\n but it's a very early work in progress.\n- Started implementing the writer, which extracts the directories from\n the in-memory format, and writes the header and the directories to\n disk. The algorithm uses a hash-table instead of a simple list,\n to avoid many corner cases.\n- Implemented writing the file block to disk, and basic tests from the\n test suite are running fine, not including tests that require\n conflicted data or the cache-tree to work, which both are not\n implemented yet.\n- Started implementing a patch to introduce a ce_namelen field in\n struct cache_entry and drop the name length from the flags. [5]\n Thanks to Junio, Duy and Thomas for reviews and suggestions for\n improving it.\n- Implemented the cache-tree and conflict data writing to the\n index-v5 file.\n\n== Work done in the last week ==\n\n- Fixed a few bugs in cache-tree and conflict writing in my index-v5\n code.\n- I visited Thomas in Zuerich this weekend, as some of you may\n have noticed on the mailing list, thanks a lot for the\n hospitality. And thanks also to Tomas for the company on saturday\n night.\n- With the help of Thomas I fixed the resolve undo data writing,\n and a couple more bugs in my code, so that the test suite passes\n with INDEX_VERSION_DEFAULT = 5.\n- We added a POC, for partial loading in git grep. This is still a\n pretty hacky implementation, but it demonstrates pretty well\n how much can be gained. Here are the timings Thomas posted on\n IRC yesterday. The improvements of ls-files are not drastic\n compared to index-v4, but git greps in subdirs benefit a lot\n from partial loading.\n\n Test this tree\n -----------------------------------------------------------\n 0002.2: v[23]: ls-files 0.13(0.11+0.02)\n 0002.3: v[23]: grep nonexistent -- subdir 0.12(0.10+0.02)\n 0002.5: v4: ls-files 0.11(0.09+0.01)\n 0002.6: v4: grep nonexistent -- subdir 0.10(0.08+0.02)\n 0002.8: v5: ls-files 0.10(0.07+0.02)\n 0002.9: v5: grep nonexistent -- subdir 0.01(0.00+0.00)\n\n- All changes again are in my repository on github, in case someone\n wants to try them out. [4]\n\n== Outlook for the next week ==\n\n- Refactoring of the code. There are still some code smells in the\n current code, which need to be refactored.\n- There are also still some possible optimizations for the code,\n which will be included.\n- I'll also bring the reader up to date again, and make it possible\n for it to update a single index entry, to test the implementation \n of rereading a entry when the crc is wrong (for the future partial\n write, both writer and reader side still have to be implemented).\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[4] https://github.com/tgummerer/git/tree/index-v5\n[5] http://thread.gmane.org/gmane.comp.version-control.git/200997\n"},{"id":"195597","messageId":"CACsJy8A8J-FXtJezOZrmqfUPX5unbGG15A6BuZnDW+164n6-kw@mail.gmail.com","threadId":"31077","inReplyTo":"20120723190847.GA40532@tgummerer.surfnet.iacbox","subject":"Re: [GSoC] Designing a faster index format - Progress report week 14","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-07-24T01:23:18Z","receivedAt":"2012-07-24T01:23:18Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jul 24, 2012 at 2:08 AM, Thomas Gummerer wrote:\n> - We added a POC, for partial loading in git grep. This is still a\n> pretty hacky implementation, but it demonstrates pretty well\n> how much can be gained. Here are the timings Thomas posted on\n> IRC yesterday. The improvements of ls-files are not drastic\n> compared to index-v4, but git greps in subdirs benefit a lot\n> from partial loading.\n>\n> Test this tree\n> -----------------------------------------------------------\n> 0002.2: v[23]: ls-files 0.13(0.11+0.02)\n> 0002.3: v[23]: grep nonexistent -- subdir 0.12(0.10+0.02)\n> 0002.5: v4: ls-files 0.11(0.09+0.01)\n> 0002.6: v4: grep nonexistent -- subdir 0.10(0.08+0.02)\n> 0002.8: v5: ls-files 0.10(0.07+0.02)\n> 0002.9: v5: grep nonexistent -- subdir 0.01(0.00+0.00)\n>\n\nIs ls-files improvement not drastic because you do not limit subdir\nlike grep? I see Thomas Rast put similar partial loading hack to\nls-files.c so I assume it can partial load too. Is partial loading\nstill fast with when a lot of unmerged entries are present?\n-- \nDuy\n"},{"id":"195610","messageId":"20120724075252.GB40532@tgummerer.surfnet.iacbox","threadId":"31077","inReplyTo":"CACsJy8A8J-FXtJezOZrmqfUPX5unbGG15A6BuZnDW+164n6-kw@mail.gmail.com","subject":"Re: [GSoC] Designing a faster index format - Progress report week 14","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-07-24T07:52:52Z","receivedAt":"2012-07-24T07:52:52Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 07/24, Nguyen Thai Ngoc Duy wrote:\n> On Tue, Jul 24, 2012 at 2:08 AM, Thomas Gummerer wrote:\n>\n> Is ls-files improvement not drastic because you do not limit subdir\n> like grep? I see Thomas Rast put similar partial loading hack to\n> ls-files.c so I assume it can partial load too. Is partial loading\n> still fast with when a lot of unmerged entries are present?\n> -- \n> Duy\n\nYes, exactly, the ls-files was to show the overall performance of the\nindex for a full read. The improvement when limiting it to a subdir\nis about the same as with git grep. Here are some more timings. I'm\nusing update-index instead of ls-files in this tests, with a\n--force-rewrite option I added which writes the index even if there\nare no changes, to test the performance of both the reader and the\nwriter.\n\nTest this tree \n-----------------------------------------------------------\n0002.2: v[23]: update-index 0.29(0.21+0.06)\n0002.3: v[23]: grep nonexistent -- subdir 0.13(0.12+0.01)\n0002.5: v4: update-index 0.26(0.20+0.05)\n0002.6: v4: grep nonexistent -- subdir 0.11(0.08+0.02)\n0002.7: v4: ls-files -- subdir 0.10(0.07+0.02)\n0002.9: v5: update-index 0.19(0.11+0.07)\n0002.10: v5: grep nonexistent -- subdir 0.01(0.00+0.00)\n0002.11: v5: ls-files -- subdir 0.01(0.00+0.00)\n\nPartial loading is still fast with unmerged entries, since we only\nneed to load files that belong to a specific directory there too.\nI've created about 15,000 conflicts on the webkit repository, and\ngot the following times:\n\nTest this tree \n-----------------------------------------------------------\n0002.2: v[23]: update-index 0.30(0.18+0.10)\n0002.3: v[23]: grep nonexistent -- subdir 0.13(0.09+0.04)\n0002.5: v4: update-index 0.26(0.22+0.04)\n0002.6: v4: grep nonexistent -- subdir 0.11(0.07+0.03)\n0002.7: v4: ls-files -- subdir 0.10(0.09+0.01)\n0002.9: v5: update-index 0.21(0.16+0.05)\n0002.10: v5: grep nonexistent -- subdir 0.01(0.00+0.00)\n0002.11: v5: ls-files -- subdir 0.01(0.00+0.00)\n\nI could create more conflicts (~180,000 files are in the index),\nbut I think 15,000 already is a number that's very unlikely to\nbe reached.\n"}]}