{"thread":{"id":"53333","subject":"all memory consuming `git diff-tree` bug","startedAt":"2020-04-28T00:28:30Z","lastAt":"2020-04-28T04:18:50Z","messageCount":3,"participants":["Dale Henrichs","Jeff King","Antoine Pelisse"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"396419","messageId":"5e00fe77-3f72-0729-2b30-9f4f98a28b1c@gemtalksystems.com","threadId":"53333","inReplyTo":null,"subject":"all memory consuming `git diff-tree` bug","fromName":"Dale Henrichs","fromEmail":"dale.henrichs@gemtalksystems.com","sentAt":"2020-04-28T00:28:26Z","receivedAt":"2020-04-28T00:28:30Z","isPatch":false,"sender":{"key":"dale.henrichs@gemtalksystems.com","avatar":null},"body":"When I execute the follow set of commands, the `git diff-tree` command \nwill go on to consume all 30G of ram and then 30G of swap on a system \nrunning Ubuntu 18.04.\n\ngit clone git@github.com:GemTalk/Rowan.git\ncd Rowan\ngit checkout c70f69b50dc90c0a6207a5aa36705b71b59b92b3\ngit diff-tree -r -p --textconv --submodule -C --cc --no-commit-id -U3 \n--root c70f69b50dc90c0a6207a5aa36705b71b59b92b3\n\nI'm running git 2.26.2 (built from source). The git command line was \ngenerated by gitk. It originally showed up in 2.17.1, but reproduced in \nthe latest version of git.\n\nClicking nearby commits (ccffec29f977f9324e8120bf550c745189e76f70 and \n8b08cec96bbb74b54046abbdb49a5bbd2f82fc3b finish almost immediately, so \nthere seems to be something special about that particular commit.\n\nDale\n\n\n\n"},{"id":"396430","messageId":"20200428041010.GA2371637@coredump.intra.peff.net","threadId":"53333","inReplyTo":"5e00fe77-3f72-0729-2b30-9f4f98a28b1c@gemtalksystems.com","subject":"Re: all memory consuming `git diff-tree` bug","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-04-28T04:10:10Z","receivedAt":"2020-04-28T04:10:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 27, 2020 at 05:28:26PM -0700, Dale Henrichs wrote:\n\n> When I execute the follow set of commands, the `git diff-tree` command will\n> go on to consume all 30G of ram and then 30G of swap on a system running\n> Ubuntu 18.04.\n> \n> git clone git@github.com:GemTalk/Rowan.git\n> cd Rowan\n> git checkout c70f69b50dc90c0a6207a5aa36705b71b59b92b3\n> git diff-tree -r -p --textconv --submodule -C --cc --no-commit-id -U3 --root\n> c70f69b50dc90c0a6207a5aa36705b71b59b92b3\n\nInteresting case. To narrow it down a bit, the problem is in the\ncombined diff of this file:\n\n $ git diff-tree -r --raw -c c70f69b50dc\n [...]\n ::100644 100644 000000 3d41426ebb801416ec0941d8b9cffdd53c300e43 7aa23a5f12ca31523c999d8eff767d0e2923a76f 0000000000000000000000000000000000000000 DD\tplatforms/gemstone/topaz/3.5.0/project_src_v2/ComponentV2.gs\n\nwhere two different versions of it were resolved as a deletion. Doing\nthe content-level diff shows the problem:\n\n git diff-tree -p -c c70f69b50dc -- platforms/gemstone/topaz/3.5.0/project_src_v2/ComponentV2.gs\n [hangs, allocating tons of memory until I kill it]\n\nThe allocations all happen in combine-diff:coalesce_lines(). I don't\nknow the combined-diff code very well, but it looks like this:\n\n for (i = 0; i < origbaselen + 1; i++) {\n lcs[i] = xcalloc(st_add(lennew, 1), sizeof(int));\n directions[i] = xcalloc(st_add(lennew, 1), sizeof(enum coalesce_direction));\n directions[i][0] = BASE;\n }\n\nis essentially quadratic in the number of lines in the file (well,\nreally m*n, but it's common for them to be the same order of magnitude).\nHere the files are 186991 and 114598 lines respectively. So that's 20GB\ntimes the size of the ints and enum (probably 8 bytes or so), plus\nmalloc overhead. I'd guess you need on the order of 200GB, if the\nquadratic run-time didn't just kill you.\n\nThat code comes from:\n\n commit 99d3206010ba1fcc9311cbe8376c0b5e78f4a136\n Author: Antoine Pelisse \n Date: Sat Mar 23 18:23:28 2013 +0100\n\n combine-diff: coalesce lost lines optimally\n \n This replaces the greedy implementation to coalesce lost lines by using\n dynamic programming to find the Longest Common Subsequence.\n \n The O(n²) time complexity is obviously bigger than previous\n implementation but it can produce shorter diff results (and most likely\n easier to read).\n \n List of lost lines is now doubly-linked because we reverse-read it when\n reading the direction matrix.\n\nSo it looks like the issue was known, but the author did not anticipate\ninput this large. An amusing quote from the email thread[1]:\n\n Unfortunately on a commit that would remove A LOT of lines (10000)\n from 7 parents, the times goes from 0.01s to 1.5s... I'm pretty sure\n that scenario is quite uncommon though.\n\nWithout engaging my brain to think about what this code is doing or\nwhether there might be clever solutions, it really sounds like we might\nconsider using this quadratic code for small cases if it produces better\nresults, and then switching to the less-accurate greedy implementation\nwhen we need to.\n\n-Peff\n\n[1] https://lore.kernel.org/git/CALWbr2yfgA8kvtn4yxzPD5cencAPmwMqx=A6n4ohsjdzfAE1bQ@mail.gmail.com/\n"},{"id":"396431","messageId":"CALWbr2zjL5pKrvk1pRXUKgOLE+kVKzLjR3ofUOhRruAbiVVovg@mail.gmail.com","threadId":"53333","inReplyTo":"20200428041010.GA2371637@coredump.intra.peff.net","subject":"Re: all memory consuming `git diff-tree` bug","fromName":"Antoine Pelisse","fromEmail":"apelisse@gmail.com","sentAt":"2020-04-28T04:18:36Z","receivedAt":"2020-04-28T04:18:50Z","isPatch":false,"sender":{"key":"apelisse@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1929644?v=4"},"body":"On Mon, Apr 27, 2020 at 9:10 PM Jeff King wrote:\n> Without engaging my brain to think about what this code is doing or\n> whether there might be clever solutions, it really sounds like we might\n> consider using this quadratic code for small cases if it produces better\n> results, and then switching to the less-accurate greedy implementation\n> when we need to.\n\nI remember having the exact same thought at the time I wrote this, but\nmy limited tests with 10k lines files were fine so I discarded it.\n\nFalling-back on the greedy algorithm seems reasonable in that case.\n\nAntoine\n"}]}