3 ms·

> 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

> 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++.
  - tylerhou 1y ago
    Thanks for reminding me, I meant to also benchmark the interchanged version. I updated the file above with the new benchmark results. The original commenter called `find()` once per vowel, so that's why I benchmarked the regex against the less-idiomatic code. The interchanged version (loop over haystack outside, over vowels inside) is (mildly) faster than all the regex versions except for short strings & no vowels. One thing to note is that all the loop versions are not easily generalizable to non-ASCII strings, while the regex version is fairly easily.
    - SleepyMyroslav 1y ago
      I poked that loop in compiler explorer for few minutes and I think its allergic to autovectorization. Lets assume that properly vectorized regexp from proper language in the future wins :)
Kranar 1y ago
Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, you can make something that outperforms what is kind of a dumb algorithm. But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Certainly, in principle a regex is neither fast or slow, it's a declarative description of a set of strings. Any claim about its performance rests on particular implementations. For example you wrote out a benchmark that presumably is a lot faster than a naive search... but notice you didn't use the standard library <regex>, instead you manually implemented an algorithm to perform a search and then just decided that this is what a regex implementation would have done anyways (ignoring that by implementing it directly in source code, the optimizer can then fine tune it). So now... there is a 10% chance that you genuinely didn't know that C++ has a <regex> library that you could have used, or you did in fact know that C++ has such a library and you chose not to you use it because... you also know it's very slow. I did the benchmark myself using the standard library regex, boost regex, and PCRE2 regex, and all of them are about 5-15x slower than the simple loop: https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4c07 https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4...
- tylerhou 1y ago
  > Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, But that's not what is happening. The only thing that the optimizer does is unrolls the loop that advances the state. Otherwise, the sequence of instructions is standard: two loads and some pointer arithmetic. There is no finely tuned algorithm. https://godbolt.org/z/fqdb5bssc https://godbolt.org/z/fqdb5bssc > But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Yes, most regex implementations are not designed to be efficient, they are designed for ergonomics (including supporting exponential-time features like lookaround). (Both boost::regex and PCRE2 support exponential-time features; std::regex is just not optimized at all.) This is well-known. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html. That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized! Maybe this is a semantic distinction between what you and I consider a "regex." I interpreted "regex" as how people in CS theory understand it; i.e., a finite automata that decides whether a string is in a given language. I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. I think it's reasonable for me to use a (not hand-optimized) implementation that obeys that definition in my comparison.

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++.
- tylerhou 1y ago
  Thanks for reminding me, I meant to also benchmark the interchanged version. I updated the file above with the new benchmark results. The original commenter called `find()` once per vowel, so that's why I benchmarked the regex against the less-idiomatic code. The interchanged version (loop over haystack outside, over vowels inside) is (mildly) faster than all the regex versions except for short strings & no vowels. One thing to note is that all the loop versions are not easily generalizable to non-ASCII strings, while the regex version is fairly easily.
  - SleepyMyroslav 1y ago
    I poked that loop in compiler explorer for few minutes and I think its allergic to autovectorization. Lets assume that properly vectorized regexp from proper language in the future wins :)

Kranar 1y ago

Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, you can make something that outperforms what is kind of a dumb algorithm. But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Certainly, in principle a regex is neither fast or slow, it's a declarative description of a set of strings. Any claim about its performance rests on particular implementations. For example you wrote out a benchmark that presumably is a lot faster than a naive search... but notice you didn't use the standard library <regex>, instead you manually implemented an algorithm to perform a search and then just decided that this is what a regex implementation would have done anyways (ignoring that by implementing it directly in source code, the optimizer can then fine tune it). So now... there is a 10% chance that you genuinely didn't know that C++ has a <regex> library that you could have used, or you did in fact know that C++ has such a library and you chose not to you use it because... you also know it's very slow. I did the benchmark myself using the standard library regex, boost regex, and PCRE2 regex, and all of them are about 5-15x slower than the simple loop: https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4c07 https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4...

tylerhou 1y ago
> Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, But that's not what is happening. The only thing that the optimizer does is unrolls the loop that advances the state. Otherwise, the sequence of instructions is standard: two loads and some pointer arithmetic. There is no finely tuned algorithm. https://godbolt.org/z/fqdb5bssc https://godbolt.org/z/fqdb5bssc > But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Yes, most regex implementations are not designed to be efficient, they are designed for ergonomics (including supporting exponential-time features like lookaround). (Both boost::regex and PCRE2 support exponential-time features; std::regex is just not optimized at all.) This is well-known. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html. That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized! Maybe this is a semantic distinction between what you and I consider a "regex." I interpreted "regex" as how people in CS theory understand it; i.e., a finite automata that decides whether a string is in a given language. I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. I think it's reasonable for me to use a (not hand-optimized) implementation that obeys that definition in my comparison.