<div dir="ltr">grep is slow when the number of patterns is large.<div><br></div><div>We have some tests that use `grep -v -f $file1 $file2` to check if $file1 is a superset of $file2, and if not, then generate a report of what is in $file2 but not $file1.</div><div>The command completes reasonably fast on desktop linux (grep (GNU grep) 3.7), but very slow on CI. Digging further shows that CI uses toybox grep.</div><div><br></div><div>For who's interested, this is the test script (<a href="https://cs.android.com/android/platform/superproject/+/master:development/gki/kmi_abi_chk/kmi_compatibility_test.sh">https://cs.android.com/android/platform/superproject/+/master:development/gki/kmi_abi_chk/kmi_compatibility_test.sh</a>).</div><div>Or just use this command to reproduce:</div><div>```</div><div>for i in {1..10000}; do<br>  xxd -p -c 0 -l 40 /dev/urandom<br>done >test_large_10000<br></div><div>time toybox grep -f test_large_10000 test_large_10000<br></div><div>```</div><div>(This runs for ~50s on my linux desktop)</div><div><br></div><div>The issue is that for each pattern (-e arg and _lines_ in -f arg), toybox regcomp a standalone regex object. For each input line, the entire list of regex objects are looped over to find the longest match [1], and looped multiple times to find all matches [2].</div><div>This means regexec would be called O(L x N) times, where L is number of patterns, N is number of input lines.</div><div>[1]: <a href="https://cs.android.com/android/platform/superproject/+/master:external/toybox/toys/posix/grep.c;l=212">https://cs.android.com/android/platform/superproject/+/master:external/toybox/toys/posix/grep.c;l=212</a></div><div>[2]: <a href="https://cs.android.com/android/platform/superproject/+/master:external/toybox/toys/posix/grep.c;l=167">https://cs.android.com/android/platform/superproject/+/master:external/toybox/toys/posix/grep.c;l=167</a></div><div><br></div><div><div>A simple optimization would be to concat all patterns into one huge regex pattern with '|'. I've hacked something together locally to do this, and the improvement is evident (runtime reduced to ~2s).</div><div>But this also had some potential problems:</div></div><div>1. Does regexec always return the left-most longest match? `man 7 regex` says yes, but `man regexec` says nothing about this guarantee. I think it does guarantee "left-most" match, but it might not always return the longest match if multiple alternative patterns (patterns joined with |) are provided. I'm afraid this might be implementation dependent and some regcomp/regexec impl could return the "first matched alternative pattern" instead.</div><div>2. One large pattern might be problematic. `man 7 regex` threatens that patterns larger than 256 bytes might not be supported by all regcomp implementations.</div><div><br></div><div>Thoughts on how risky this change could be? I could start sending you the patches if you think the pros outweigh the potential cons?</div><div><br></div><div>Yi-yo</div></div>