4

我试图弄清楚如何编写一个非常快速的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等），但它们与我的目标无关，所以我完全忽略他们暂时。

4

5 回答 5

2

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

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

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

于 2012-12-01T03:34:25.613 回答
2

@Mysticial 的评论以及一些调整似乎确实有所帮助。

首先我尝试了这个：

template<class Ch>
struct is_iequal
{
    std::ctype<Ch> const &ctype;
    is_iequal(std::ctype<Ch> const &ctype) : ctype(ctype) { }
    bool operator()(Ch const a, Ch const b) const
    {
        return a == b ||
            ('a' <= a && a <= 'z' || 'A' <= a && a <= 'Z') &&
            (a & ~('a' - 'A')) == (b & ~('a' - 'A')) ||
            a > SCHAR_MAX && b > SCHAR_MAX &&
            ctype.toupper(a) == ctype.toupper(b);
    }
};

这并没有多大帮助，但后来我想，嘿，为什么不交换两边&&？

template<class Ch>
struct is_iequal
{
    std::ctype<Ch> const &ctype;
    is_iequal(std::ctype<Ch> const &ctype) : ctype(ctype) { }
    bool operator()(Ch const a, Ch const b) const
    {
        return a == b ||
            (a & ~('a' - 'A')) == (b & ~('a' - 'A')) &&
            ('a' <= a && a <= 'z' || 'A' <= a && a <= 'Z') ||
            a > SCHAR_MAX && b > SCHAR_MAX &&
            ctype.toupper(a) == ctype.toupper(b);
    }
};

这使它下降到 138 毫秒！

于 2012-12-01T03:37:03.323 回答
2

128x128 查找表。始终进行此查找（屏蔽输入）。

这将你的分支减少到一个（你打电话给上层吗？）。不做 && 或 || 的情况下计算那个 - 使用无分支逻辑。

也许使表格成为一个完整的字节平方。还可以尝试使用更紧凑的查找表，在其中通过位旋转提取查找，并进行更多旋转以确定它是否被丢弃并使用 == 代替。 (a&b)|(c&~b)没有b?a:c分支。

分支预测失败很糟糕。

试验和测试后选择表尺寸。

所以我的表是bool equal[128][128] = {…}- 不是查找然后相等，而只是查找。

于 2012-12-01T04:04:31.513 回答
0

如果我更换，我会得到更快的结果：

('a' <= a && a <= 'z' || 'A' <= a && a <= 'Z') ||

...从您的回答中：

(unsigned char)((a & 0x20) - 'A') < 26 ||

会a & 0x20从小写转换为大写（它也会影响其他一些字符，但我们会在一秒钟内将它们屏蔽掉）。'A'如果折叠后的值小于 ，则减法会产生一个负数A。转换为无符号会减少模 UCHAR_MAX（通常为 255），因此负数变为大正数。然后只用一个测试，我们就可以发现它是以大写字母还是小写字母开头的。

于 2012-12-01T06:35:13.003 回答
0

我的回答是用 C 语言，但也许它对你仍然有用......

在编写更快（大约 3 倍）tolower 函数的过程中，我还在三台不同的机器上测试了各种形式的不区分大小写的 ascii 字符相等。这是我能得到的最快速度，令人惊讶的是，它比基于整数的位运算略快：

uint8_t is_eq_bsc(char c, char i){
    c |= (c | ' ');
    i |= (i | ' ');
    return c == i;
}

这是三台不同机器上的基准测试的要点和我测试的各种代码： https ://gist.github.com/benwills/5170f2e6adbb67e3ec4c

于 2015-02-14T06:35:40.093 回答