4

大文字と小文字を区別せずに 2 つの文字が等しいかどうかを比較するために、ASCII 用に最適化され た非常に高速な関数を作成する方法を見つけようとしています。is_iequal

最終的な目標は、このファンクターを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

128x128ルックアップテーブル。常にこのルックアップを実行します（入力をマスクします）。

それはあなたのブランチを1つに減らします（あなたはアッパーに電話しますか？）。&&または||を実行せずにそれを計算します -ブランチレスロジックを使用します。

たぶん、テーブルを1バイトの2乗にします。また、より厳密なルックアップテーブルを使用して、ビットをいじってルックアップを抽出し、さらにいじって、それがスローされ、代わりに==が使用されるかどうかを判断してみてください。 ブランチなしです(a&b)|(c&~b)。b?a:c

そして、分岐予測の失敗は最悪です。

実験とテストの後にテーブルサイズを選択します。

つまり、私のテーブルはbool equal[128][128] = {…}-ルックアップではなく、等しいものではなく、単なるルックアップです。

于 2012-12-01T04:04:31.513 に答える
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 に答える
0

次のものを置き換えると、より高速な結果が得られます。

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

...あなたの答えから：

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

はa & 0x20小文字から大文字に変換されます (他の文字にも影響しますが、すぐに除外します)。'A'縮小された値が より小さい場合、減算すると負の数が生成されAます。符号なしに変換すると、モジュロ UCHAR_MAX (通常は 255) が減少するため、負の数は大きな正の数になります。次に、たった 1 つのテストで、それが大文字または小文字のどちらで始まったかを調べます。

于 2012-12-01T06:35:13.003 に答える