{"thread":{"id":"52377","subject":"git-status performance with submodules","startedAt":"2019-12-02T06:20:04Z","lastAt":"2019-12-02T14:05:55Z","messageCount":3,"participants":["D. Ben Knoble","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"387387","messageId":"CALnO6CCoXOZTsfag6yN_Ffn+H7KE-KTzm+P-GqLKnDMg8j_Qmg@mail.gmail.com","threadId":"52377","inReplyTo":null,"subject":"git-status performance with submodules","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2019-12-02T06:19:49Z","receivedAt":"2019-12-02T06:20:04Z","isPatch":false,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"[If this has already gone through multiple times, I apologize for the\nrepetition; I have had a hard time getting GMail to send this. Past\nversions had attachments, which I believe contributed to failures.\nThis one has none, but has links to all the content.]\n\nHello all,\n\nI have a concern about the performance of git-status with many (~38)\nsubmodules. As part of a (large-scale) system dynamics class, I was tasked\nwith identifying a performance problem, tracing it using KUTrace(2)[3], and\nsubsequently investigating it. I ended up with some unique observations about\ngit-status and submodules[2].\n\nThe interactive HTML traces are available on Google Drive[4][5].\n\nI won't recreate all the details here, but I would encourage you to play with\nthe traces, or at least go through the slides.\n\n### The short-version\n\nGit status is slow(3).\n\n### Baseline\n\n- time git-status, with many submodules, and --ignore-submodules=none\n    0.497s\n- time git-status in non-submodule heavy repos\n    0.014s\n\n### What I consider a temporary fix\n\n- time git-status, with many submodules, and --ignore-submodules=all\n    0.026s\n\n### What I would like to see\n\nI would like to improve the git-status performance with this many submodules,\nso that I can remove diff.ignoreSubmodules=none from my config (it is useful\ninformation, and the flag affects many commands). I would be willing to work\non a discussed and designed fix.\n\n### What I am curious about\n\nFrom the traces (attached), it appears that git-status suffers from a lack of\n(possibly embarrassing) parallelism: I would expect each submodule to be\nindependently check-able, but the process section of the trace has them\nexecuting serially (for reasons unknown to me). The apparent need to fork/exec\nmany processes in this way appears to also be a source of latency, along with\nthe very large number of filesystem-related syscalls (if my understanding is\ncorrect).\n\nWhat can we do to fix this? Is there a reason for this (really terribly slow)\nserial execution? Is this something developers haven't bothered to optimize\n(\"unexpected use case\")? If so, I would like to discuss taking a crack at it,\nbecause I do have at least one repository with this many submodules, and I\ncare about its performance.\n\n---\n\nNotes\n\n1) All timings were taken with the https://github.com/benknoble/Dotfiles repo\nfrom around commit da194a8f4104a9fc74e8895ebc8512434f07d393\n\n2) KUTrace is a set of kernel patches and userspace programs that provide\nlow-overhead tracing, as well as post-processing those traces\n\n3) Timings taken on my machine (2012 macbook pro; can provide more details if\nrequested)\n\n---\n\nLinks\n\n[1]: https://docs.google.com/presentation/d/1z-6ffE9KY-Jswl2BiWzYV2DG6fOutgWSi_aZ5uql__s/edit?usp=sharing\n[2]: https://benknoble.github.io/blog/2019/11/07/git-stat/\n[3]: https://github.com/dicksites/KUtrace\n[4]: https://drive.google.com/file/d/1JyYO420yWp7XvNJJ8HLOPU0o6mesSKZf/view?usp=sharing\n[5]: https://drive.google.com/file/d/1BqqxH0PRCYz_vvYkBBFpbL5dkFTLPyuK/view?usp=sharing\n"},{"id":"387388","messageId":"xmqq5zizz0ei.fsf@gitster-ct.c.googlers.com","threadId":"52377","inReplyTo":"CALnO6CCoXOZTsfag6yN_Ffn+H7KE-KTzm+P-GqLKnDMg8j_Qmg@mail.gmail.com","subject":"Re: git-status performance with submodules","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-12-02T06:50:29Z","receivedAt":"2019-12-02T06:50:38Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"D. Ben Knoble\" <ben.knoble@gmail.com> writes:\n\n> ### What I am curious about\n>\n> From the traces (attached), it appears that git-status suffers from a lack of\n> (possibly embarrassing) parallelism: I would expect each submodule to be\n> independently check-able, ...\n> ...\n> What can we do to fix this? Is there a reason for this (really terribly slow)\n> serial execution? Is this something developers haven't bothered to optimize\n> (\"unexpected use case\")? If so, I would like to discuss taking a crack at it,\n> because I do have at least one repository with this many submodules, and I\n> care about its performance.\n\nNice to hear from somebody who cares about improving submodule\nsupport.  I offhand do not think of a reason why we inherently have\nto process them serially.\n\nBut the way \"git status\" code is structured, it probably takes a bit\nof preparatory refactoring.  If I recall correctly, it walks each\npath in the index in the superproject and notes how the file in the\nworking tree is different from that of the index and the HEAD, under\nthe assumption that inspection of each path is relatively cheap and\nat the same cost.  You'd first need to restructure that part so that\ninspecting groups of index entries can be sharded to separate\nsubprocesses while the parent process waits, and have them report to\nthe parent process, and let the parent process continue with the\naggregated result, or something like that.\n\nThanks.\n\n"},{"id":"387397","messageId":"20191202140552.GB16534@sigill.intra.peff.net","threadId":"52377","inReplyTo":"xmqq5zizz0ei.fsf@gitster-ct.c.googlers.com","subject":"Re: git-status performance with submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-02T14:05:52Z","receivedAt":"2019-12-02T14:05:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Dec 01, 2019 at 10:50:29PM -0800, Junio C Hamano wrote:\n\n> But the way \"git status\" code is structured, it probably takes a bit\n> of preparatory refactoring.  If I recall correctly, it walks each\n> path in the index in the superproject and notes how the file in the\n> working tree is different from that of the index and the HEAD, under\n> the assumption that inspection of each path is relatively cheap and\n> at the same cost.  You'd first need to restructure that part so that\n> inspecting groups of index entries can be sharded to separate\n> subprocesses while the parent process waits, and have them report to\n> the parent process, and let the parent process continue with the\n> aggregated result, or something like that.\n\nThere's some prior art for this approach in git-checkout, where we have\na similar problem with latency of filters (e.g., for LFS). There the\nindividual status for a path becomes a tri-state: success, error, or\ndeferred. And then we collect the results from the deferred ones in a\nloop.\n\nI think (but didn't look carefully) that this could be slotted into the\ndiff code pretty easily. After the tree-level diff we have a queue of\ncandidates in memory. At that point we should be able to kick off a\nprocess in parallel for each submodule, then wait for them all to finish\nbefore proceeding. Maybe even as a stage of diffcore_std(), but I'm not\nsure.\n\n(Hand-wavey, I know, but just trying to point interested folks in the\nright direction).\n\n-Peff\n"}]}