{"thread":{"id":"30076","subject":"Clarifications on the \"faster index format\" project","startedAt":"2012-03-28T00:36:49Z","lastAt":"2012-03-28T00:36:49Z","messageCount":1,"participants":["Thomas Rast"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"187908","messageId":"878vilr272.fsf@thomas.inf.ethz.ch","threadId":"30076","inReplyTo":null,"subject":"Clarifications on the \"faster index format\" project","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-03-28T00:36:49Z","receivedAt":"2012-03-28T00:36:49Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Dear students,\n\nThe proposal \"Designing a faster index format\" has attracted quite a bit\nmore attention that we expected.  We would like to emphasize that it is\nnot an easy project.\n\nI have myself only found out about most of the points I am listing here\nthrough interaction with students.  My apologies for this.  Take them as\na (non-exhaustive!) list of concerns.  The more of them you can address\nin your proposal, the better.\n\nIssues with the original project idea:\n\n- Further timings have shown that even on humongous indexes such as\n  Webkit's (roughly 25MB), git-add is still pretty fast.  It is a good\n  baseline for what index-changing commands need to do however.  Judge\n  from your own timings and state what case you want to optimize.\n\n- The notation is confusing.  Asymptotics noted in the proposal should\n  distinguish the variables \"# index entries\" (n), \"# changed entries\",\n  and depending on the application also \"size of index file\" (though\n  this is fairly tightly coupled with n) or other variables.\n\nSome hardnesses that we expect:\n\n- Without prior knowledge of the index, it is hard to see how a new\n  format must be designed to stay within the requirements.\n\n- The index format is closely tied to a lot of core git's code.  The\n  main work of git-ls-files, git-status, git-read-tree, git-add,\n  git-diff etc. all directly accesses the index memory structure.  This\n  means that changing the in-memory structure is a lot of work.\n\n- Changing the in-memory structure also makes conversion between the old\n  and new format more difficult.\n\n- Writing out only the changed entries would save a lot of time.\n  However there are many code paths that change/add/remove index\n  entries, and they must all record what to write in some way.\n\n- Cutting down the amount of verification going on is very tempting, but\n  needs careful design to keep the chances of a bit error propagating\n  all the way into the repository small.\n\nThere are many tradeoffs to be made, which must be evaluated carefully:\n\n- If the current lock-rewrite-rename scheme remains in place, any change\n  only affects the in-core work done.  If the lock scheme is changed,\n  there are many different cases of corruption/partial writes that must\n  be handled.\n\n- There may be ways to reduce the data written (and thus checksummed) at\n  the cost of extra work.  Similarly, a more complex data structure may\n  or may not pay off depending on the extra space taken (or saved) and\n  extra bookkeeping done.\n\n- Some improvements would be possible by using techniques from database\n  libraries.  However, this either means an external dependency or a lot\n  of extra work.  It may also come with extra startup costs.\n\n- Using database libraries may be a deal-breaker for git's own\n  portability or the other readers (libgit2 and jgit, mainly).\n\nThe format should cope with requirements that are not clearly specified\nat this time.  For example:\n\n- The existing code also assumes that iterating over an index is not a\n  problem.  For possible future work, the format should allow for\n  iterating over only a select part of the index (known, e.g., from an\n  inotify daemon or a pathspec) quickly.\n\nFinally I have a request not related to project hardness: please Cc the\nproposed mentors for discussions on the respective projects :-)\n\nThanks for reading,\n\nThomas\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"}]}