{"thread":{"id":"45695","subject":"Index files autocompletion too slow in big repositories (w / suggestion for improvement)","startedAt":"2017-04-14T20:06:43Z","lastAt":"2017-04-17T08:04:05Z","messageCount":10,"participants":["Carlos Pita","Ævar Arnfjörð Bjarmason","Jacob Keller","Junio C Hamano","Johannes Sixt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"316849","messageId":"CAELgYhf1s43p62t6W14S=nDt-O247cPqsPMUDfye1OTnDND3Gg@mail.gmail.com","threadId":"45695","inReplyTo":null,"subject":"Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Carlos Pita","fromEmail":"carlosjosepita@gmail.com","sentAt":"2017-04-14T20:06:15Z","receivedAt":"2017-04-14T20:06:43Z","isPatch":false,"sender":{"key":"carlosjosepita@gmail.com","avatar":"https://gravatar.com/avatar/cf95d94f5258e3cbf21c26fb6fee0d7b16a1b26b6a19e33c805527c598197321?d=mp&s=160"},"body":"Hi all,\n\nI'm currently using git annex to manage my entire file collection\n(including tons of music and books) and I noticed how slow\nautocompletion has become for files in the index (say for git add).\nThe main offender is a while-read-case-echo bash loop in\n__git_index_files that can be readily substituted with a much faster\nsed invocation, although I guess you didn't want the sed dependency in\nthe first place. Anyway, here is my benchmark:\n\n__git_index_files ()\n{\n    local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n    if [ -d \"$dir\" ]; then\n        __git_ls_files_helper \"$root\" \"$1\" | while read -r file; do\n            case \"$file\" in\n                ?*/*)\n                    echo \"${file%%/*}\"\n                ;;\n                *)\n                    echo \"$file\"\n                ;;\n            esac;\n        done | sort | uniq;\n    fi\n}\n\ntime __git_index_files > /dev/null\n\n\n__git_index_files ()\n{\n    local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n    if [ -d \"$dir\" ]; then\n        __git_ls_files_helper \"$root\" \"$1\" | \\\n            sed -r 's@^\"?([^/]+)/.*$@\\1@' | sort | uniq\n    fi\n}\n\ntime __git_index_files > /dev/null\n\nreal    0m0.830s\nuser    0m0.597s\nsys    0m0.310s\n\nreal    0m0.345s\nuser    0m0.357s\nsys    0m0.000s\n\nNotice I'm also excluding the beginning double quote that appears in\nescaped path names.\n\nBest regards\n--\nCarlos\n"},{"id":"316863","messageId":"CAELgYhfwwLZXGN9yHZ04koDwGn3=KbuJOxhLM-+PCbumTmMunw@mail.gmail.com","threadId":"45695","inReplyTo":"CAELgYhf1s43p62t6W14S=nDt-O247cPqsPMUDfye1OTnDND3Gg@mail.gmail.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Carlos Pita","fromEmail":"carlosjosepita@gmail.com","sentAt":"2017-04-14T22:08:25Z","receivedAt":"2017-04-14T22:08:51Z","isPatch":false,"sender":{"key":"carlosjosepita@gmail.com","avatar":"https://gravatar.com/avatar/cf95d94f5258e3cbf21c26fb6fee0d7b16a1b26b6a19e33c805527c598197321?d=mp&s=160"},"body":"This is much faster (below 0.1s):\n\n__git_index_files ()\n{\n    local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n    if [ -d \"$dir\" ]; then\n        __git_ls_files_helper \"$root\" \"$1\" | \\\n            sed -r 's@/.*@@' | uniq | sort | uniq\n    fi\n}\n\ntime __git_index_files\n\nreal    0m0.075s\nuser    0m0.083s\nsys    0m0.010s\n\nMost of the improvement is due to the simpler, non-grouping, regex.\nSince I expect most of the common prefixes to arrive consecutively,\nrunning uniq before sort also improves things a bit. I'm not removing\nleading double quotes anymore (this isn't being done by the current\nversion, anyway) but this doesn't seem to hurt.\n\nDespite the dependence on sed this is ten times faster than the\noriginal, maybe an option to enable fast index completion or something\nlike that might be desirable.\n\nBest regards\n--\nCarlos\n"},{"id":"316864","messageId":"CACBZZX7Ajf1c9YKP=MO0T9SV7d0-XZsT=RthJocqZw4_TcCcQw@mail.gmail.com","threadId":"45695","inReplyTo":"CAELgYhfwwLZXGN9yHZ04koDwGn3=KbuJOxhLM-+PCbumTmMunw@mail.gmail.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-04-14T22:33:44Z","receivedAt":"2017-04-14T22:34:12Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com> wrote:\n> This is much faster (below 0.1s):\n>\n> __git_index_files ()\n> {\n>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>     if [ -d \"$dir\" ]; then\n>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>             sed -r 's@/.*@@' | uniq | sort | uniq\n>     fi\n> }\n>\n> time __git_index_files\n>\n> real    0m0.075s\n> user    0m0.083s\n> sys    0m0.010s\n>\n> Most of the improvement is due to the simpler, non-grouping, regex.\n> Since I expect most of the common prefixes to arrive consecutively,\n> running uniq before sort also improves things a bit. I'm not removing\n> leading double quotes anymore (this isn't being done by the current\n> version, anyway) but this doesn't seem to hurt.\n>\n> Despite the dependence on sed this is ten times faster than the\n> original, maybe an option to enable fast index completion or something\n> like that might be desirable.\n>\n> Best regards\n\nIt's fine to depend on sed, these shell-scripts are POSIX compatible,\nand so is sed, we use sed in a lot of the built-in shellscripts.\n\nI think you should submit this as a patch, see Documentation/SubmittingPatches.\n"},{"id":"316869","messageId":"CA+P7+xoBYApdmucEpdxT8qHJ0HP5RR2gOkStykd5Fq=8qsZxZQ@mail.gmail.com","threadId":"45695","inReplyTo":"CACBZZX7Ajf1c9YKP=MO0T9SV7d0-XZsT=RthJocqZw4_TcCcQw@mail.gmail.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2017-04-15T01:37:08Z","receivedAt":"2017-04-15T01:37:36Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Fri, Apr 14, 2017 at 3:33 PM, Ævar Arnfjörð Bjarmason\n<avarab@gmail.com> wrote:\n> On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com> wrote:\n>> This is much faster (below 0.1s):\n>>\n>> __git_index_files ()\n>> {\n>>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>>     if [ -d \"$dir\" ]; then\n>>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>>             sed -r 's@/.*@@' | uniq | sort | uniq\n>>     fi\n>> }\n>>\n>> time __git_index_files\n>>\n>> real    0m0.075s\n>> user    0m0.083s\n>> sys    0m0.010s\n>>\n>> Most of the improvement is due to the simpler, non-grouping, regex.\n>> Since I expect most of the common prefixes to arrive consecutively,\n>> running uniq before sort also improves things a bit. I'm not removing\n>> leading double quotes anymore (this isn't being done by the current\n>> version, anyway) but this doesn't seem to hurt.\n>>\n>> Despite the dependence on sed this is ten times faster than the\n>> original, maybe an option to enable fast index completion or something\n>> like that might be desirable.\n>>\n>> Best regards\n>\n> It's fine to depend on sed, these shell-scripts are POSIX compatible,\n> and so is sed, we use sed in a lot of the built-in shellscripts.\n>\n> I think you should submit this as a patch, see Documentation/SubmittingPatches.\n\nYea it should be fine to use sed.\n\nThanks,\nJake\n"},{"id":"316872","messageId":"xmqqr30um7k8.fsf@gitster.mtv.corp.google.com","threadId":"45695","inReplyTo":"CA+P7+xoBYApdmucEpdxT8qHJ0HP5RR2gOkStykd5Fq=8qsZxZQ@mail.gmail.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-15T07:52:23Z","receivedAt":"2017-04-15T07:52:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller <jacob.keller@gmail.com> writes:\n\n> On Fri, Apr 14, 2017 at 3:33 PM, Ævar Arnfjörð Bjarmason\n> <avarab@gmail.com> wrote:\n>> On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com> wrote:\n>>> This is much faster (below 0.1s):\n>>>\n>>> __git_index_files ()\n>>> {\n>>>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>>>     if [ -d \"$dir\" ]; then\n>>>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>>>             sed -r 's@/.*@@' | uniq | sort | uniq\n>>>     fi\n>>> }\n>>>\n>>> time __git_index_files\n>>>\n>>> real    0m0.075s\n>>> user    0m0.083s\n>>> sys    0m0.010s\n>>>\n>>> Most of the improvement is due to the simpler, non-grouping, regex.\n>>> Since I expect most of the common prefixes to arrive consecutively,\n>>> running uniq before sort also improves things a bit. I'm not removing\n>>> leading double quotes anymore (this isn't being done by the current\n>>> version, anyway) but this doesn't seem to hurt.\n>>>\n>>> Despite the dependence on sed this is ten times faster than the\n>>> original, maybe an option to enable fast index completion or something\n>>> like that might be desirable.\n>>>\n>>> Best regards\n>>\n>> It's fine to depend on sed, these shell-scripts are POSIX compatible,\n>> and so is sed, we use sed in a lot of the built-in shellscripts.\n>>\n>> I think you should submit this as a patch, see Documentation/SubmittingPatches.\n>\n> Yea it should be fine to use sed.\n\nAs long as the use of \"sed\" is in line with POSIX.1; I do not think\nyou need the non-portable \"-r\" merely to strip out everything that\nfollow the first slash, so perhaps \"s|-r|-e|\" with the above (and do\nnot write backslash after pipe at the end of the line---shell knows\nyou haven't finished talking to it yet if you end a line with a\npipe, and there is no need for backslash), you'd be golden.\n"},{"id":"316888","messageId":"7a07a2a8-07a6-4342-80d0-7684e6242326@kdbg.org","threadId":"45695","inReplyTo":"CACBZZX7Ajf1c9YKP=MO0T9SV7d0-XZsT=RthJocqZw4_TcCcQw@mail.gmail.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-04-15T11:59:34Z","receivedAt":"2017-04-15T11:59:43Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Cc Gábor.\n\nAm 15.04.2017 um 00:33 schrieb Ævar Arnfjörð Bjarmason:\n> On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com> wrote:\n>> This is much faster (below 0.1s):\n>>\n>> __git_index_files ()\n>> {\n>>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>>     if [ -d \"$dir\" ]; then\n>>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>>             sed -r 's@/.*@@' | uniq | sort | uniq\n>>     fi\n>> }\n>>\n>> time __git_index_files\n>>\n>> real    0m0.075s\n>> user    0m0.083s\n>> sys    0m0.010s\n>>\n>> Most of the improvement is due to the simpler, non-grouping, regex.\n>> Since I expect most of the common prefixes to arrive consecutively,\n>> running uniq before sort also improves things a bit. I'm not removing\n>> leading double quotes anymore (this isn't being done by the current\n>> version, anyway) but this doesn't seem to hurt.\n>>\n>> Despite the dependence on sed this is ten times faster than the\n>> original, maybe an option to enable fast index completion or something\n>> like that might be desirable.\n>\n> It's fine to depend on sed, these shell-scripts are POSIX compatible,\n> and so is sed, we use sed in a lot of the built-in shellscripts.\n\nThis is about command line completion. We go a long way to avoid forking \nprocesses there. What is 10x faster on Linux despite of forking a \nprocess may not be so on Windows.\n\n(I'm not using bash command line completion on Windows, so I can't tell \nwhat the effect of your suggested change is on Windows. I hope Gábor can \ncomment on it.)\n\n-- Hannes\n\n"},{"id":"316891","messageId":"3711baf1-af54-b5c9-25e8-9613312c536a@kdbg.org","threadId":"45695","inReplyTo":"CACBZZX7Ajf1c9YKP=MO0T9SV7d0-XZsT=RthJocqZw4_TcCcQw@mail.gmail.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-04-15T12:30:39Z","receivedAt":"2017-04-15T12:30:45Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Cc Gábor, resent with working email (hopefully); please follow-up on \nthis mail.\n\nAm 15.04.2017 um 00:33 schrieb Ævar Arnfjörð Bjarmason:\n> On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com> wrote:\n>> This is much faster (below 0.1s):\n>>\n>> __git_index_files ()\n>> {\n>>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>>     if [ -d \"$dir\" ]; then\n>>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>>             sed -r 's@/.*@@' | uniq | sort | uniq\n>>     fi\n>> }\n>>\n>> time __git_index_files\n>>\n>> real    0m0.075s\n>> user    0m0.083s\n>> sys    0m0.010s\n>>\n>> Most of the improvement is due to the simpler, non-grouping, regex.\n>> Since I expect most of the common prefixes to arrive consecutively,\n>> running uniq before sort also improves things a bit. I'm not removing\n>> leading double quotes anymore (this isn't being done by the current\n>> version, anyway) but this doesn't seem to hurt.\n>>\n>> Despite the dependence on sed this is ten times faster than the\n>> original, maybe an option to enable fast index completion or something\n>> like that might be desirable.\n>\n> It's fine to depend on sed, these shell-scripts are POSIX compatible,\n> and so is sed, we use sed in a lot of the built-in shellscripts.\n\nThis is about command line completion. We go a long way to avoid forking \nprocesses there. What is 10x faster on Linux despite of forking a \nprocess may not be so on Windows.\n\n(I'm not using bash command line completion on Windows, so I can't tell \nwhat the effect of your suggested change is on Windows. I hope Gábor can \ncomment on it.)\n\n-- Hannes\n"},{"id":"316902","messageId":"CA+P7+xo+wiTkByd_BrLUEyGc9z7USYT8Joo7OhjrYCUmbHjZ0Q@mail.gmail.com","threadId":"45695","inReplyTo":"7a07a2a8-07a6-4342-80d0-7684e6242326@kdbg.org","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2017-04-16T00:31:40Z","receivedAt":"2017-04-16T00:32:08Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Sat, Apr 15, 2017 at 4:59 AM, Johannes Sixt <j6t@kdbg.org> wrote:\n> Cc Gábor.\n>\n> Am 15.04.2017 um 00:33 schrieb Ævar Arnfjörð Bjarmason:\n>>\n>> On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com>\n>> wrote:\n>>>\n>>> This is much faster (below 0.1s):\n>>>\n>>> __git_index_files ()\n>>> {\n>>>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>>>     if [ -d \"$dir\" ]; then\n>>>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>>>             sed -r 's@/.*@@' | uniq | sort | uniq\n>>>     fi\n>>> }\n>>>\n>>> time __git_index_files\n>>>\n>>> real    0m0.075s\n>>> user    0m0.083s\n>>> sys    0m0.010s\n>>>\n>>> Most of the improvement is due to the simpler, non-grouping, regex.\n>>> Since I expect most of the common prefixes to arrive consecutively,\n>>> running uniq before sort also improves things a bit. I'm not removing\n>>> leading double quotes anymore (this isn't being done by the current\n>>> version, anyway) but this doesn't seem to hurt.\n>>>\n>>> Despite the dependence on sed this is ten times faster than the\n>>> original, maybe an option to enable fast index completion or something\n>>> like that might be desirable.\n>>\n>>\n>> It's fine to depend on sed, these shell-scripts are POSIX compatible,\n>> and so is sed, we use sed in a lot of the built-in shellscripts.\n>\n>\n> This is about command line completion. We go a long way to avoid forking\n> processes there. What is 10x faster on Linux despite of forking a process\n> may not be so on Windows.\n>\n> (I'm not using bash command line completion on Windows, so I can't tell what\n> the effect of your suggested change is on Windows. I hope Gábor can comment\n> on it.)\n>\n> -- Hannes\n>\n\nIn cases like this, might it be worth somehow splitting it so Linux\ncan use the best thing, and Windows can continue using what's best for\nit, since it is a pretty significant advantage on Linux.\n\nThanks,\nJake\n"},{"id":"316984","messageId":"xmqqefwrk7ao.fsf@gitster.mtv.corp.google.com","threadId":"45695","inReplyTo":"7a07a2a8-07a6-4342-80d0-7684e6242326@kdbg.org","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-17T04:05:35Z","receivedAt":"2017-04-17T04:05:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt <j6t@kdbg.org> writes:\n\n> Cc Gábor.\n>\n> Am 15.04.2017 um 00:33 schrieb Ævar Arnfjörð Bjarmason:\n>> On Sat, Apr 15, 2017 at 12:08 AM, Carlos Pita <carlosjosepita@gmail.com> wrote:\n>>> This is much faster (below 0.1s):\n>>>\n>>> __git_index_files ()\n>>> {\n>>>     local dir=\"$(__gitdir)\" root=\"${2-.}\" file;\n>>>     if [ -d \"$dir\" ]; then\n>>>         __git_ls_files_helper \"$root\" \"$1\" | \\\n>>>             sed -r 's@/.*@@' | uniq | sort | uniq\n>>>     fi\n>>> }\n>>>\n>>> time __git_index_files\n>>>\n>>> real    0m0.075s\n>>> user    0m0.083s\n>>> sys    0m0.010s\n>>>\n>>> Most of the improvement is due to the simpler, non-grouping, regex.\n>>> Since I expect most of the common prefixes to arrive consecutively,\n>>> running uniq before sort also improves things a bit. I'm not removing\n>>> leading double quotes anymore (this isn't being done by the current\n>>> version, anyway) but this doesn't seem to hurt.\n>>>\n>>> Despite the dependence on sed this is ten times faster than the\n>>> original, maybe an option to enable fast index completion or something\n>>> like that might be desirable.\n>>\n>> It's fine to depend on sed, these shell-scripts are POSIX compatible,\n>> and so is sed, we use sed in a lot of the built-in shellscripts.\n>\n> This is about command line completion. We go a long way to avoid\n> forking processes there. What is 10x faster on Linux despite of\n> forking a process may not be so on Windows.\n\nDoesn't this depend on how many paths there are?  If there are only\na few paths, the loop in shell would beat a pipe into sed even on\nLinux, I suspect, and if there are tons of paths, at some number,\nloop in shell would become slower than a single spawning of sed on\nplatforms with slower fork, no?\n"},{"id":"316996","messageId":"2304c00a-ed87-7119-3753-95f61bcf28f6@kdbg.org","threadId":"45695","inReplyTo":"xmqqefwrk7ao.fsf@gitster.mtv.corp.google.com","subject":"Re: Index files autocompletion too slow in big repositories (w / suggestion for improvement)","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-04-17T08:03:56Z","receivedAt":"2017-04-17T08:04:05Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 17.04.2017 um 06:05 schrieb Junio C Hamano:\n> Johannes Sixt <j6t@kdbg.org> writes:\n>> This is about command line completion. We go a long way to avoid\n>> forking processes there. What is 10x faster on Linux despite of\n>> forking a process may not be so on Windows.\n>\n> Doesn't this depend on how many paths there are?  If there are only\n> a few paths, the loop in shell would beat a pipe into sed even on\n> Linux, I suspect, and if there are tons of paths, at some number,\n> loop in shell would become slower than a single spawning of sed on\n> platforms with slower fork, no?\n\nAbsolutely. I just want to make sure a suggested change takes into \naccount the situation on Windows, not only the \"YESSSS!\" and \"VERY \nWELL!\" votes of Linux users ;)\n\n-- Hannes\n\n"}]}