6 ms·

But it's not the fastest, it's actually incredibly slow and in general regexs are very slow. The key insight is that string processing in Python is very slow, a

by Kranar 1y ago

But it's not the fastest, it's actually incredibly slow and in general regexs are very slow. The key insight is that string processing in Python is very slow, and that regex here outperforms everything else because it's the only approach that is implemented in C. With that insight it should follow that using another implementation in C should outperform even the regex, and indeed the following simple Python method that this article for whatever reason ignored vastly outperforms everything: def contains_vowel_find(s): for c in "aeiouAEIOU": if s.find(c) != -1: return True return False That's because s.find(c) is implemented in C. In my benchmark this approach is 10 times faster than using a regex: https://gist.github.com/kranar/24323e81ea1c34fb56aff621f6c09e65 https://gist.github.com/kranar/24323e81ea1c34fb56aff621f6c09...

azhenley 1y ago
Very nice find (pun intended). I added an update at the end with your solution and a link to this comment.
jonstewart 1y ago
The more you learn about regexes, the more you learn that you can’t make general statements about their performance. Performance is contingent upon the engine, its algorithms, its implementation, the patterns, and the input.
ok_dad 1y ago
I've always found regexes to do a string search faster than other methods, but there is always more to learn! Thanks for the lesson today.
a_e_k 1y ago
Playing around, I found that the generator approach was competitive with this if you permuted the loop nest, and often even slightly faster (at the 1000 character length): def any_gen_perm(s): return any(c in s for c in "aeiouAEIOU") I think the crux is that you want the inner loop inside the fast C-implemented primitive to be the one iterating over the longer string, and to leave the outer loop in Python to iterate over the shorter string. With both my version and yours, the Python loop only iterates and calls into the C search loop 10 times, so there's less interpreter overhead. I suspect that permuting the loop nest in similar variations will also see a good speed up, and indeed trying just now: def loop_in_perm(s): for c in "aeiouAEIOU": if c in s: return True return False seems to give the fastest result yet. (Around twice as fast as the permuted generator expression and your find implementation on my machine, with 100 and 1000 character strings.)
- azhenley 1y ago
  This is beautiful!!! Adding it to the end of the post right now.
- IAmBroom 1y ago
  For English samples, this should prove faster: def loop_in_perm(s): for c in "eaoiuEAOIU": if c in s: return True return False
  - a_e_k 1y ago
    Oh, that's a nice optimization!
tylerhou 1y ago
> in general regexs are very slow I really don't think this is true. If you assume that the string is ASCII, a well-optimized regex for a pattern of this type should be a tight loop over a few instructions that loads the next state from a small array. The small array should fit completely in cache as well. This is basically branchless. I expect that you could process 1 character per cycle on modern CPUs. If the string is short (~100 characters or less, guessing), I expect this implementation to outperform the find() implementation by far as find() almost certainly will incur at least one more branch mispredict than the regex. For longer strings, it depends on the data, as the branchless regex implementation will scan through the whole string, so find() will be faster if there is an vowel early on in the string. Find still might be faster even if there are no vowels; the exact time in that case depends on microarchitecture. For non-ASCII, things are a bit trickier, but one can construct a state machine that is not too much larger.
- tylerhou 1y ago
  Putting benchmarks where my mouth is: https://github.com/tylerhou/benchmarks/blob/main/vowels-benchmark_test.cc https://github.com/tylerhou/benchmarks/blob/main/vowels-benc... Writing implementations in C++, using a reasonable encoding of how an efficient regex compiler might compile the vowel regex, the regex implementation outperforms the loop-based implementations significantly in all cases except for long strings with vowels on M1 Max MBP. Strings were generated randomly following the regex [0-9A-Za-z]. Short strings were between 5-20 chars. Long strings were 5000 chars. The speedups are: - Short strings & with vowels: regex is 2.6x faster - Short strings & no vowels: regex is 5.9x faster - Long strings & with vowels: loop is 329x faster. This is expected, as because the regex implementation is branchless, it must always search through the whole string. - Long strings & no vowels: regex is 1.5x faster. If you add an early return to the regex implementation, the regex with early return becomes strictly faster than the loop versions. The early return is slower than the no early return for the short strings & no vowels case because the extra branch has a cost. Full outputs in a comment at the bottom of the linked file.
  - SleepyMyroslav 1y ago
    Why do you loop over haystack multiple times though? If you iterate over long string once and write fixed loop with vowels checks in way that will be friendly to autovectorize optimization it might be faster and more idiomatic C or C++.

by Kranar 1y ago

azhenley 1y ago

Very nice find (pun intended). I added an update at the end with your solution and a link to this comment.

jonstewart 1y ago

The more you learn about regexes, the more you learn that you can’t make general statements about their performance. Performance is contingent upon the engine, its algorithms, its implementation, the patterns, and the input.

ok_dad 1y ago

I've always found regexes to do a string search faster than other methods, but there is always more to learn! Thanks for the lesson today.

a_e_k 1y ago

Playing around, I found that the generator approach was competitive with this if you permuted the loop nest, and often even slightly faster (at the 1000 character length): def any_gen_perm(s): return any(c in s for c in "aeiouAEIOU") I think the crux is that you want the inner loop inside the fast C-implemented primitive to be the one iterating over the longer string, and to leave the outer loop in Python to iterate over the shorter string. With both my version and yours, the Python loop only iterates and calls into the C search loop 10 times, so there's less interpreter overhead. I suspect that permuting the loop nest in similar variations will also see a good speed up, and indeed trying just now: def loop_in_perm(s): for c in "aeiouAEIOU": if c in s: return True return False seems to give the fastest result yet. (Around twice as fast as the permuted generator expression and your find implementation on my machine, with 100 and 1000 character strings.)

azhenley 1y ago
This is beautiful!!! Adding it to the end of the post right now.
IAmBroom 1y ago
For English samples, this should prove faster: def loop_in_perm(s): for c in "eaoiuEAOIU": if c in s: return True return False
- a_e_k 1y ago
  Oh, that's a nice optimization!

tylerhou 1y ago

> in general regexs are very slow I really don't think this is true. If you assume that the string is ASCII, a well-optimized regex for a pattern of this type should be a tight loop over a few instructions that loads the next state from a small array. The small array should fit completely in cache as well. This is basically branchless. I expect that you could process 1 character per cycle on modern CPUs. If the string is short (~100 characters or less, guessing), I expect this implementation to outperform the find() implementation by far as find() almost certainly will incur at least one more branch mispredict than the regex. For longer strings, it depends on the data, as the branchless regex implementation will scan through the whole string, so find() will be faster if there is an vowel early on in the string. Find still might be faster even if there are no vowels; the exact time in that case depends on microarchitecture. For non-ASCII, things are a bit trickier, but one can construct a state machine that is not too much larger.

tylerhou 1y ago
Putting benchmarks where my mouth is: https://github.com/tylerhou/benchmarks/blob/main/vowels-benchmark_test.cc https://github.com/tylerhou/benchmarks/blob/main/vowels-benc... Writing implementations in C++, using a reasonable encoding of how an efficient regex compiler might compile the vowel regex, the regex implementation outperforms the loop-based implementations significantly in all cases except for long strings with vowels on M1 Max MBP. Strings were generated randomly following the regex [0-9A-Za-z]. Short strings were between 5-20 chars. Long strings were 5000 chars. The speedups are: - Short strings & with vowels: regex is 2.6x faster - Short strings & no vowels: regex is 5.9x faster - Long strings & with vowels: loop is 329x faster. This is expected, as because the regex implementation is branchless, it must always search through the whole string. - Long strings & no vowels: regex is 1.5x faster. If you add an early return to the regex implementation, the regex with early return becomes strictly faster than the loop versions. The early return is slower than the no early return for the short strings & no vowels case because the extra branch has a cost. Full outputs in a comment at the bottom of the linked file.
- SleepyMyroslav 1y ago
  Why do you loop over haystack multiple times though? If you iterate over long string once and write fixed loop with vowels checks in way that will be friendly to autovectorize optimization it might be faster and more idiomatic C or C++.