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

Question

我有一个问题，涉及使用回溯查找具有各种规则的许多“单词”（它们不必是真实的）。一些规则涉及我可以在彼此之后拥有的元音数量。

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

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

Answer 1

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

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

如果你是在x86，那么你甚至可以去除&0x1f部分（注：按标准，这是不确定的行为，但作为>>编译成SHR/SAR，为此，v将被自动屏蔽，以0x1F的）：

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

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

如果您的编译器足够新，它就知道如何sar工作并将优化&0x1f掉。例如，gcc8 和更新版本省略任何and edi,31指令。（Godbolt编译器资源管理器，包括一个天真的if(v == 'a' || v == 'e' ...)GCC 编译成一些分支，但也有位图检查。

注意2：只有当表指针不在时，此版本才比表版本快。如果你做了很多检查，并且表指针已经在寄存器中，并且表在缓存中，则表版本更快。

（编者注：位图可以在解压为 32 位 SIMD 元素后自动矢量化以一次检查多个字符。表查找不能。）

Answer 2

我没有其他想法。

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

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

Answer 3

最快的方法是创建一个数组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]它是元音，则为 true，否则为 false。