{"thread":{"id":"29812","subject":"[git wiki PATCH 3/3] \"Improving the `git add -p` interface\" project","startedAt":"2012-03-02T11:05:45Z","lastAt":"2012-03-03T03:30:17Z","messageCount":8,"participants":["Thomas Rast","Jeff King","Nguyen Thai Ngoc Duy","James Pickens","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"185903","messageId":"57e8b4eb7a98af33982c2f3a763e18f62b1d6d6d.1330686331.git.trast@student.ethz.ch","threadId":"29812","inReplyTo":"20120302091114.GA3984@sigill.intra.peff.net","subject":"[git wiki PATCH 1/3] \"Improving parallelism in various commands\" project","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-02T11:05:45Z","receivedAt":"2012-03-02T11:05:45Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"---\n SoC-2012-Ideas.md |   31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/SoC-2012-Ideas.md b/SoC-2012-Ideas.md\nindex 29a374a..145b379 100644\n--- a/SoC-2012-Ideas.md\n+++ b/SoC-2012-Ideas.md\n@@ -68,3 +68,34 @@ work to be done:\n    and only accessed on demand.\n \n Proposed mentor: Jeff King\n+\n+Improving parallelism in various commands\n+-----------------------------------------\n+\n+Git is mostly written single-threaded, with a few commands having\n+bolted-on extensions to support parallel operation (notably git-grep,\n+git-pack-objects and the core.preloadIndex feature).\n+\n+We have recently looked into some of these areas and made a few\n+optimizations, but a big roadblock is that pack access is entirely\n+single-threaded.  The project would consist of the following steps:\n+\n+ * In preparation (the half-step): identify commands that could\n+   benefit from parallelism.  `git grep --cached` and `git grep\n+   COMMIT` come to mind, but most likely also `git diff` and `git log\n+   -p`.  You can probably find more.\n+\n+ * Rework the pack access mechanisms to allow the maximum possible\n+   parallel access.\n+\n+ * Rework the commands found in the first step to use parallel pack\n+   access if possible.  Along the way, document the improvements with\n+   performance tests.\n+\n+The actual programming must be done in C using pthreads for obvious\n+reasons.  At the very least you should not be scared of low-level\n+programming.  Prior experience and access to one or more multi-core\n+computers is a plus.\n+\n+Proposed by: Thomas Rast\n+Possible mentor(s): Thomas Rast\n-- \n1.7.9.2.467.g7fee4\n"},{"id":"185904","messageId":"afdfa68348d8d98f2cb604d9c17dad6cd764066e.1330686331.git.trast@student.ethz.ch","threadId":"29812","inReplyTo":"57e8b4eb7a98af33982c2f3a763e18f62b1d6d6d.1330686331.git.trast@student.ethz.ch","subject":"[git wiki PATCH 2/3] \"Designing a faster index format\" project","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-02T11:05:46Z","receivedAt":"2012-03-02T11:05:46Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"---\n SoC-2012-Ideas.md |   41 +++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 41 insertions(+)\n\ndiff --git a/SoC-2012-Ideas.md b/SoC-2012-Ideas.md\nindex 145b379..59d1baf 100644\n--- a/SoC-2012-Ideas.md\n+++ b/SoC-2012-Ideas.md\n@@ -99,3 +99,44 @@ computers is a plus.\n \n Proposed by: Thomas Rast\n Possible mentor(s): Thomas Rast\n+\n+Designing a faster index format\n+-------------------------------\n+\n+Git is pretty slow when managing huge repositories in terms of files\n+in any given tree, as it needs to rewrite the index (in full) on\n+pretty much every operation.  For example, even though _logically_\n+`git add already_tracked_file` only changes a single blob SHA-1 in the\n+index, Git will verify index correctness during loading and recompute\n+the new hash during writing _over the whole index_.  It thus ends up\n+spending a large amount of time simply on hashing the index.\n+\n+A carefully designed index format could help in several ways.  (For the\n+complexity estimates below, let n be the number of index entries or\n+the size of the index, which is roughly the same.)\n+\n+ * The work needed for something as simple as entering a new blob into\n+   the index, which is possibly the most common operation in git\n+   (think `git add -p` etc.) should be at most log(n).\n+\n+ * The work needed for a more complex operation that changes the\n+   number of index entries will have to be larger unless we get into\n+   database land.  However the amount of data that we SHA-1 over\n+   should still be log(n).\n+\n+ * It may be possible to store the cache-tree data directly as part of\n+   the index, always keeping it valid, and using that to validate\n+   index consistency throughout.  If so, this would be a big boost to\n+   other git operations that currently suffer from frequent cache-tree\n+   invalidation.\n+\n+Note that there are other criteria than speed: the format should also\n+be as easy to parse as possible, so as to simplify work for the other\n+.git-reading programs (such as jgit and libgit2).  For the same\n+reason, you will also have to show a significant speed boost as\n+otherwise the break in compatibility is not worth the fallout.\n+\n+The programming work will be in C, as it replaces a core part of git.\n+\n+Proposed by: Thomas Rast\n+Possible mentor(s): Thomas Rast\n-- \n1.7.9.2.467.g7fee4\n"},{"id":"185902","messageId":"544c3150818d928e14f40b362feb6dbabb348c9f.1330686331.git.trast@student.ethz.ch","threadId":"29812","inReplyTo":"57e8b4eb7a98af33982c2f3a763e18f62b1d6d6d.1330686331.git.trast@student.ethz.ch","subject":"[git wiki PATCH 3/3] \"Improving the `git add -p` interface\" project","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-02T11:05:47Z","receivedAt":"2012-03-02T11:05:47Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"---\n SoC-2012-Ideas.md |   41 +++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 41 insertions(+)\n\ndiff --git a/SoC-2012-Ideas.md b/SoC-2012-Ideas.md\nindex 59d1baf..b2cc475 100644\n--- a/SoC-2012-Ideas.md\n+++ b/SoC-2012-Ideas.md\n@@ -140,3 +140,44 @@ The programming work will be in C, as it replaces a core part of git.\n \n Proposed by: Thomas Rast\n Possible mentor(s): Thomas Rast\n+\n+Improving the `git add -p` interface\n+------------------------------------\n+\n+The interface behind `git {add|commit|stash|reset} {-p|-i}` is shared\n+and called `git-add--interactive.perl`.    This project would mostly\n+focus on the `--patch` side, as that seems to be much more widely\n+used; however, improvements to `--interactive` would probably also be\n+welcome.\n+\n+The `--patch` interface suffers from some design flaws caused largely\n+by how the script grew:\n+\n+ * Application is not atomic: hitting Ctrl-C midway through patching\n+   may still touch files.\n+\n+ * The terminal/line-based interface becomes a problem if diff hunks\n+   are too long to fit in your terminal.\n+\n+ * Cannot go back and forth between files.\n+\n+ * Cannot reverse the direction of the patch.\n+\n+ * Cannot look at the diff in word-diff mode (and apply it normally).\n+\n+Due to the current design it is also pretty hard to add these features\n+without adding to the mess.  Thus the project consists of:\n+\n+ * Come up with more ideas for features/improvements and discuss them\n+   with users.\n+\n+ * Cleanly redesigning the main interface loop to allow for the above\n+   features.\n+\n+ * Implement the new features.\n+\n+As the existing code is written in Perl, that is what you will use for\n+this project.\n+\n+Proposed by: Thomas Rast\n+Possible mentor(s): Thomas Rast\n-- \n1.7.9.2.467.g7fee4\n"},{"id":"185907","messageId":"20120302110844.GA5748@sigill.intra.peff.net","threadId":"29812","inReplyTo":"afdfa68348d8d98f2cb604d9c17dad6cd764066e.1330686331.git.trast@student.ethz.ch","subject":"Re: [git wiki PATCH 2/3] \"Designing a faster index format\" project","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-03-02T11:08:45Z","receivedAt":"2012-03-02T11:08:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 02, 2012 at 12:05:46PM +0100, Thomas Rast wrote:\n\n> ---\n>  SoC-2012-Ideas.md |   41 +++++++++++++++++++++++++++++++++++++++++\n>  1 file changed, 41 insertions(+)\n\nThanks, I've applied and pushed all three (but the index one is my\nfavorite).\n\n-Peff\n"},{"id":"185924","messageId":"CACsJy8APtrw-6umkr3=yrG3wfye96=z=CvfWj0tnghfDcDWFzg@mail.gmail.com","threadId":"29812","inReplyTo":"57e8b4eb7a98af33982c2f3a763e18f62b1d6d6d.1330686331.git.trast@student.ethz.ch","subject":"Re: [git wiki PATCH 1/3] \"Improving parallelism in various commands\" project","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-02T14:29:22Z","receivedAt":"2012-03-02T14:29:22Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Mar 2, 2012 at 6:05 PM, Thomas Rast <trast@student.ethz.ch> wrote:\n> + * In preparation (the half-step): identify commands that could\n> +   benefit from parallelism.  `git grep --cached` and `git grep\n> +   COMMIT` come to mind, but most likely also `git diff` and `git log\n> +   -p`.  You can probably find more.\n\nI just had a thought this afternoon whether \"git add\" may benefit from\nparallelism. It's most likely I/O-bound, although I think if we add a\nbunch of large files, it might become CPU-bound. To generalize,\nanything that calls hash_sha1_file() might benefit from parallelism.\n\nAnother candidate may be git-apply. Actually I just want to speed up\ngit-rebase and think git-apply may be the culprit. Or it could be\nunpack-trees code..\n-- \nDuy\n"},{"id":"185932","messageId":"CAJMEqRAXa+qdXa_6S1PieD2SwcSDo5kkCwe3_PedTRet-vk-Fw@mail.gmail.com","threadId":"29812","inReplyTo":"57e8b4eb7a98af33982c2f3a763e18f62b1d6d6d.1330686331.git.trast@student.ethz.ch","subject":"Re: [git wiki PATCH 1/3] \"Improving parallelism in various commands\" project","fromName":"James Pickens","fromEmail":"jepicken@gmail.com","sentAt":"2012-03-02T17:35:24Z","receivedAt":"2012-03-02T17:35:24Z","isPatch":true,"sender":{"key":"jepicken@gmail.com","avatar":null},"body":"[Resend since the first try had HTML and the list rejected it]\n\nOn Fri, Mar 2, 2012, Thomas Rast <trast@student.ethz.ch> wrote:\n+ * In preparation (the half-step): identify commands that could\n+   benefit from parallelism.  `git grep --cached` and `git grep\n+   COMMIT` come to mind, but most likely also `git diff` and `git log\n+   -p`.  You can probably find more.\n\nFor those of us who must work on NFS for various reasons, it would help\ntremendously to write out work tree files in parallel, during 'git clone',\n'git reset --hard', and any other command that writes lots of files to the\nwork tree.  You can get a huge speedup (benchmarked at ~3.5x) without even\nunpacking those files in parallel; unpacking them serially and writing them\nto disk in parallel is sufficient.\n\nI submitted a patch [1] ~2 years ago that added that capability.  It was\nnot accepted, but it did demonstrate the huge potential speedup on NFS, and\nthe pitfall of degrading performance on a local drive.  The patch itself is\nprobably not useful any more, but it includes some benchmarks, and the\ndiscussion may be helpful.\n\nJames\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/103489\n"},{"id":"185934","messageId":"7vobseeu9i.fsf@alter.siamese.dyndns.org","threadId":"29812","inReplyTo":"afdfa68348d8d98f2cb604d9c17dad6cd764066e.1330686331.git.trast@student.ethz.ch","subject":"Re: [git wiki PATCH 2/3] \"Designing a faster index format\" project","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-02T18:24:09Z","receivedAt":"2012-03-02T18:24:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Having harder and more ambitious ones in the mix is OK, but I suspect this\none is probably a bit too ambitious to be realistic for a student project\nthat lasts only 3 months.\n\nThis proposal is about a change that touches core parts of the system that\nhas the chance of inflicting permanent damage to end users' histories.\nI'd have a hard time reviewing and convincing myself that the change is\ngood, if such a change were done by somebody new to the system, even if\nthe work were mentored very closely by one of our top 15 committers.\n"},{"id":"185973","messageId":"CACsJy8DWKaZZfp4kyj3bkBVF3yzzFa24uMDfoxVc=ATWs1uRew@mail.gmail.com","threadId":"29812","inReplyTo":"7vobseeu9i.fsf@alter.siamese.dyndns.org","subject":"Re: [git wiki PATCH 2/3] \"Designing a faster index format\" project","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-03T03:30:17Z","receivedAt":"2012-03-03T03:30:17Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 3, 2012 at 1:24 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Having harder and more ambitious ones in the mix is OK, but I suspect this\n> one is probably a bit too ambitious to be realistic for a student project\n> that lasts only 3 months.\n>\n> This proposal is about a change that touches core parts of the system that\n> has the chance of inflicting permanent damage to end users' histories.\n> I'd have a hard time reviewing and convincing myself that the change is\n> good, if such a change were done by somebody new to the system, even if\n> the work were mentored very closely by one of our top 15 committers.\n\nI was comparing the excitement of seeing this implemented vs packv4,\nthen realised the complexity of work may be more or less the same.\nBut, if the new format is not mmap'd for direct access, we can\nreconstruct \"struct cache_entry*\" exactly as it is now from new\nformat. That makes it less sensitive to the core parts and we still\nhopefully benefit from new format (mostly I/O I guess). Phase 2 could\ncome later to make core parts aware of new format.\n-- \nDuy\n"}]}