c++ fastest way to check if char is vowel or consonant

Question

I have a problem that involves using backtrack to find a number of "words"(they don't have to be real) with various rules. Some of the rules involve the number of vowels that I can have after each other.

I know that I could use a switch, or a for loop with an array of vowels and then say that all alphabetic characters that are not vowels are consonants, but since this function is probably going to be called a few thousand times, I would like it to be as fast as possible.

What is the fastest possible way of checking if a char is a vowel or a consonant?

Solution 1

The fastest way is to create an array of bool and use the character value as an index:

bool is_vowel[CHAR_MAX] = { false }; // initializes all values to false
void init() {
    is_vowel['A'] = true;
    is_vowel['a'] = true;
    // etc.
}

Now, for any non-negative char value ch, is_vowel[ch] will be true if it's a vowel and false otherwise.

Solution 2

If you have ASCII chars, and you know that the character is a letter (its ASCII code is larger than or equal to 64), then you can do this:

// pre-condition: v is alphabetic ASCII, upper or lower case
bool isvowel(char v) {
    return (0x208222>>(v&0x1f))&1;
}

If you are on x86, then you can even remove the &0x1f part (note: according to the standard, this is undefined behavior, but as >> compiled down to SHR/SAR, for which v will be masked to 0x1f automatically):

bool isvowel_UB_for_dumb_compilers(char v) {
    return (0x208222>>v)&1;
}

Note: this is a "dirty" solution, but if one really needs speed, sometimes the dirty solution is the fastest one (basically this solution stores a 32 element table in the magic constant 0x208222: bits are set for wovels. Furthermore, it is exploited that lower and upper case characters have the same 5 lowest bits).

If your compiler is new enough, it knows how sar works and will optimize the &0x1f away. For example, gcc8 and newer omit any and edi,31 instruction. (Godbolt compiler explorer, including a naive if(v == 'a' || v == 'e' ...) which GCC compiles into some branching but also a bitmap check.

---

Note2: this version is faster than the table version only if the table pointer is not around. If you do a lot of checks, and the table pointer is already in a register, and table is in the cache, the table version is faster.

(Editor's note: the bitmap can auto-vectorize to check multiple characters at once, after unpacking to 32-bit SIMD elements. Table lookups can't.)

Solution 3

I have no other ideas.

This answer just to provide some benchmark of others.

bool undef_sarx_and(char v) {
    return (0x208222>>v)                            // sarx %edi, %eax, %eax
           &1;                                      // andl $1, %eax        
}

bool unsafe_one_load(char in) {
    return bool_table[in];                          // movsbq  %dil, %rdi     
}                                                   // movb   table(%rdi), %al

bool safe_one_load(char in) {
    auto index = static_cast<unsigned char>(in);    // movzbl  %dil, %edi     
    return bool_table[index];                       // movb   table(%rdi), %al
}

(iterate on data 1 MB for 800 times)
undef_sarx_and      209976800   2.71313 sec     309.185 MB/s
unsafe_one_load     209976800   2.4514 sec      342.197 MB/s
safe_one_load       209976800   2.18231 sec     384.391 MB/s

(iterate on data 100 MB for 8 times)
undef_sarx_and      209704768   3.76998 sec     222.511 MB/s
unsafe_one_load     209704768   3.72898 sec     224.957 MB/s
safe_one_load       209704768   3.72719 sec     225.065 MB/s

all with vectorization disabled (-fno-tree-vectorize)

I guess that nothing can beat @pete-becker's table lookup but @geza's hack is very compelling because table lookup allocates 256 bytes while the intrinsic is all free!

godbolt.org/g/FajFXb

wandbox.org/permlink/Lf1mioQG8yanZtZn

Comments

[user0042]

bool isvowel(char ch) { return (ch == 'a') || (ch == 'e') ||(ch == 'i') ||(ch == 'o') ||(ch == 'u'); }

[Mark Gardner]

Please could down-voters suggest improvements.

[Mark Gardner]

@user0042 that is still relatively slow, no? Also, it doesn't catch capitals. I would like it so that it doesn't have to check against every option for any option. Another nice feature would be for it to be good in other localizations to.

[user0042]

"that is still relatively slow, no?" I don't think so, it will be probably inlined by the compiler. A switch() statement alternatively?

[Mark Gardner]

@user0042 I explicitly said that I wanted to avoid switches, fors and other brute-force methods.

[user0042]

Show your attempts and observations with measurements please. As is your question is simply too broad, and missing enough context regarding your requirements.

[George]

I wouldn't vote this question either way, i'd imagine any dvs would come from people that think you should've posted an example and the question to the code review stack exchange (Though tbh the base of the problem is so trivial that I don't really think it needs an attempt as a show of effort). I would guess the given answer is correct, but this kind of question is not something to get hung up on (like wouldn't normally even be worth profiling).

[Mark Gardner]

I was thinking of something like a binary search, but this is much better! thanks!

[Pete Becker]

@MarkGardner - fwiw, this is essentially how all of the is_*** character classification functions in the C standard library are typically implemented: an array of bit values, one bit for each class.

[user0042]

@Pete Though the OP didn't note their requirements and constraints exactly, what's considered best and fastest, you might improve your asnswer by pointing out, how the emitted assembly of your proposal differs from inlined code as from a switch() statement.

[sandthorn]

This is so cool. I wonder why we can't have portable code for this!

[geza]

Thanks for the benchmark! But I think that this routine is cannot be really benchmarked. It's so simple, its speed depends on the lot of factors, a lot on the actual cpu, benchmark and compiler (for example, a really weird result: for a simple benchmark (checking a 4K buffer 10^6 times - so everything is in cache), clang compiles 3x slower code for my variant than GCC, and the table version is much faster. With GCC, my version faster). So I think that one has put put the variants into real code, and check out the results.

[geza]

And, there can be new tricks to apply. For example, one can reverse the bits in the magic constant, and use left shift. Then the result is in the CF flag, there's no need to &1. In certain circumstances, this can cause speed up. Unfortunately, the CF flag cannot be queried in C++. But maybe there's a compiler dependent trick to query it...

[sandthorn]

@geza There is, actually! You can play it with asm() { } block. By writing 2 raw asm lines. You can shift with shlx then you can check flag with setc. But I doubt it will beat the single load. You may get rid of and but you end up replacing it with setc %al anyway. Well, I dunno. Let'try.

[geza]

I meant, because the result in the CF, then it can be used to execute a branch/cmov already, there is no need to have an additional and. So basically, all the needed operation is just a shift. Of course, if one needs the result in a register, then it doesn't help.

[Peter Cordes]

@sandthorn: You don't need to remove the &0x1f ; modern compilers know how x86 sar works and will leave the masking to sar or sarx. For an efficient check for a character being ASCII alphabetic in the first place, see my answer on What is the idea behind ^= 32, that converts lowercase letters to upper and vice versa?. Note that the immediate bitmap trick only takes 1 asm instruction in x86: bt x,y implements CF = !!(x & (1<<y)) and runs in a single uop with 1 cycle latency. Unfortunately compilers are bad at using this peephole :(

[Peter Cordes]

e.g. my answer on User Appreciation Challenge #1: Dennis ♦ uses bt for a consonant bitmap. Also Where can the code be more efficient? has a Godbolt link that shows GCC using bt for a multi-case if statement, so you might not even need this.

[unkn0wn.dev]

I know this is somewhat old but I was wondering what exactly this piece of code does? I am fairly new to C++ and was hoping you could point me to what exactly this does or some resources that could help me understand. Thank you :)

[geza]

@unkn0wn.dev: which part do you not understand?

[unkn0wn.dev]

@geza I mean to be honest with you, none of it except that it returns true if the char is a vowel and false if it isn't.

[unkn0wn.dev]

@geza I am fairly new to C++ and open to learn everything I can

[geza]

@unkn0wn.dev: this little function would have the same logic in other programming languages too, it is not really C++ specific. I think if you learn about ASCII codes, bit operations (and, shift) then you should understand what this code does (or at least you would have a specific question that I can answer. Explaining all the little details would be a very large effort from me).

[unkn0wn.dev]

@geza Alright thank you as I do not know much about shoes lol. I'll look into them, thanks for the response :)

[unkn0wn.dev]

@geza I have done some research and now it is very clear what you are doing. Quite brilliant I must say

[geza]

@unkn0wn.dev: I'm glad to hear that!