c++ - 极快is_iequal？ (不区分大小写的相等比较)

Question

我想弄清楚如何编写一个非常快速的 is_iequal 函数，针对 ASCII 进行优化，以不区分大小写的方式比较两个字符是否相等.

最终目标是让这个仿函数与 boost::algorithm::starts_with 等一起使用

到目前为止，我的尝试产生了以下结果:

#include <locale>
unsigned long fast_rand(void);

template<class Ch> struct is_iequal
{
    std::ctype<Ch> const &ctype;
    is_iequal(std::ctype<Ch> const &ctype) : ctype(ctype) { }
    bool operator()(Ch const c1, Ch const c2) const
    {
        return c1 == c2 ||
            ('a' <= c1 && c1 <= 'z' && c1 - 'a' == c2 - 'A') ||
            ('A' <= c1 && c1 <= 'Z' && c1 - 'A' == c2 - 'a') ||
            !(c1 <= '\x7F' && c2 <= '\x7F') &&
            ctype.toupper(c1) == ctype.toupper(c2);
    }
};

int main()
{
    size_t const N = 1 << 26;
    typedef wchar_t TCHAR;
    std::locale loc;
    std::ctype<TCHAR> const &ctype = std::use_facet<std::ctype<TCHAR> >(loc);
    is_iequal<TCHAR> const is_iequal(ctype);  // Functor

    TCHAR *s1 = new TCHAR[N], *s2 = new TCHAR[N];
    for (size_t i = 0; i < N; i++) { s1[i] = fast_rand() & 0x7F; }
    for (size_t i = 0; i < N; i++) { s2[i] = fast_rand() & 0x7F; }

    bool dummy = false;
    clock_t start = clock();
    for (size_t i = 0; i < N; i++) { dummy ^= is_iequal(s1[i], s2[i]); }
    printf("%u ms\n", (clock() - start) * 1000 / CLOCKS_PER_SEC, dummy);
}

unsigned long fast_rand(void)  // Fast RNG for testing (xorshf96)
{
    static unsigned long x = 123456789, y = 362436069, z = 521288629;

    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;

    unsigned long t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;

    return z;
}

在我的电脑上，运行时间为 584 毫秒 (VC++ 2011 x64)。

虽然对于我的应用程序来说它仍然有点太慢了 -- 它仍然是我实际程序中的瓶颈，它会导致轻微的 UI 延迟，如果可能的话我想摆脱它。

如何在不更改其界面的情况下进一步优化 is_iequals？

---

注意:是的，我我知道此代码的各种问题(UTF-16 处理、迂腐的 C++ 隐式转换到/从 char 的问题 等...)，但它们与我的目标无关，所以我暂时完全忽略它们。

Answer 1

考虑为 c<127 内联 toLower - 内存成本将小到足以在缓存中，但速度可能更好:

char localToLow[128] =....
return c1 < 127 && c2 < 127 ? localToLow[c1]==localToLow[c2] :
    ctype.toupper(c1) == ctype.toupper(c2);

(< 127 可以替换为 ((c1 | c2) & ~127 ) :) )