The article thinks aeiou are all the vowels, and forgets about y.

Rust, Go, C?

   julia> using Random, BenchmarkTools
   julia> function isvowel(c)
            idx = (c | 0x20) - Int('a')
            return (0x00104111 & (1 << idx)) != 0
         end

   julia> hasvowel(str) = any(c -> isvowel(Int(c)), str)

   julia> @btime hasvowel(s) setup=(s=randstring("bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ0123456789", 10))
   15.739 ns (0 allocations: 0 bytes)
   false

some 77 thousand times faster

I was curious if there were any interesting bit-masking patterns in ASCII for vowels that could be exploited, so I shamelessly asked ChatGPT and it gave a pretty nice insight:

- Setting bit 5 high forces lowercase for the input letter

- masking with `& 31` gives an index from 0-25 for the input letter

Then you can the `bt` instruction (in x86_64) to bit-test against the set of bits for a,e,i,o,u (after lowercasing) and return whether it matches, in a single instruction.

It came up with this, which I thought was pretty nice: https://godbolt.org/z/KjMdz99be

I'm sure there's other cool ways to test multiple vowels at once using AVX2 or AVX-512, I didn't really get that far. I just thought the bit-test trick was pretty sweet.

Chat transcript is here (it failed pretty spectacularly the first couple times, tripping over AT&T syntax and getting an off-by-one error, but still pretty good) https://chatgpt.com/share/684c8b39-a9c4-8012-8bb6-74e1f8b6d0...

See my other comment.

You can do extremely trivial binary checks on ASCII, UTF-8 (and most? other) encoding schemes. All vowels including W and Y contain a 1 in the lowest bit. Then by comparing bits 1-4, you can do a trivial case-insensitive comparison. You detect case by checking bit 5. 0 is upper, 1 is lower.

The usual way to do this in SIMD is via vpermb(lut, str) == str, or potentially slightly faster vpshufb(str>>1, lut) == str.

str|0x32 if you want case-insensitive.

This works because the lowest five bits, more specifically bits two to five, of the vowels are distinct.

The lut is zeroed except for the indices corresponding to the vowels, which contain it self: lut[vowel&31]=vowel or lut[(vowel&31)>>1]=vowel

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

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.

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.

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.)

> 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.

It's worth noting here that Go has a notoriously slow regexp implementation.

Yes, that's it. Vectorized SIMD annihilates this problem, a space I've been working in since 2006 and it wasn't all that new even then. A close second would be a heavily optimized (pipelined and less branchy) table or bitvector lookup. Doing anything that involves lots of control flow, like the grandparent post, will be slow as a wet week with our without bit manipulation tricks due to the inherently unpredictable nature of the branches (subject to our input).