c ++检查char是元音还是辅音的最快方法

Question

我有一个问题，涉及使用回溯来找到一些具有各种规则的“单词”（它们不一定是真实的）。一些规则涉及我可以拥有的元音数量。

我知道我可以使用一个开关，或带有元音数组的for循环，然后说所有不是元音的字母字符都是辅音，但由于这个函数可能会被称为几千次，我想它要尽可能快。

检查char是元音还是辅音的最快方法是什么？

Answer 1

最快的方法是创建一个bool数组并使用字符值作为索引：

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

现在，对于任何非负char值ch，is_vowel[ch]如果是元音则为真，否则为假。

Answer 2

如果你有ASCII字符，并且你知道字符是一个字母（它的ASCII码大于或等于64），那么你可以这样做：

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

如果你在x86上，那么你甚至可以删除&0x1f部分（注意：根据标准，这是未定义的行为，但是当>>编译为SHR/SAR时，v将被自动屏蔽为0x1f）：

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

注意：这是一个“脏”的解决方案，但如果真的需要速度，有时脏解是最快的（基本上这个解决方案在魔术常量0x208222中存储一个32个元素的表：为wovel设置位。此外，它是利用大小写字符具有相同的5个最低位）。

注意2：仅当表指针不在时，此版本比表版本快。如果您进行了大量检查，并且表指针已经在寄存器中，并且表位于缓存中，则表版本更快。

Answer 3

我没有其他想法。

这个答案只是为了提供其他人的一些基准。

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)

我想没有什么可以击败@ pete-becker的表查找，但@ geza的hack非常引人注目，因为表查找分配了256个字节，而内在的全部是免费的！

godbolt.org/g/FajFXb

wandbox.org/permlink/Lf1mioQG8yanZtZn