7

I need a comparison function for blocks of memory for doing binary searches on arrays of bytes in the D programming language. It does not need to have any useful semantics. It only needs to be fast and be a valid comparison function (one that produces a total ordering). The blocks of memory to be compared are already known to be the same length.

C's memcmp is actually pretty slow because it tries to preserve useful string comparison semantics, which I don't need. Below is the best I've come up with so far. Does anyone know of anything better, preferably w/o dipping into non-portable CPU-specific instructions?

// Faster than C's memcmp because it doesn't preserve any meaningful
// semantics.  It's just a completely arbitrary, but really fast,
// comparison function.
int memoryCompare(const(void)* lhs, const(void)* rhs, size_t n) {
    for(; n >= uint.sizeof; n -= uint.sizeof) {
        if( *(cast(uint*) lhs) < *(cast(uint*) rhs)) {
            return -1;
        } else if( *(cast(uint*) lhs) > *(cast(uint*) rhs)) {
            return 1;
        }
        lhs += uint.sizeof;
        rhs += uint.sizeof;
    }

    for(; n >= ubyte.sizeof; n -= ubyte.sizeof) {
        if( *(cast(ubyte*) lhs) < *(cast(ubyte*) rhs)) {
            return -1;
        } else if( *(cast(ubyte*) lhs) > *(cast(ubyte*) rhs)) {
            return 1;
        }
        lhs += ubyte.sizeof;
        rhs += ubyte.sizeof;
    }

    return 0;
}

Edit: I've read up on SSE and I don't want to use it for 3 reasons:

  1. It's not portable.
  2. It requires programming in ASM.
  3. The comparison instructions assume your data is floating points, which might be problematic if some data happens to match the pattern for a NaN.
4

6 に答える 6

3

あなたは試すことができます：

  • uintがターゲットCPUに適合する最大のタイプであるかどうかを確認します（ulongsはネイティブレジスタに適合する可能性があります）
  • そのタイプの2つのポインターを使用します
  • * p ++を使用して2つのローカル変数を使用します（1つの値に対してポインターを2回逆参照しないでください）
  • 最初のループのカウンターを前もって分割します（while（counter--）を使用します）
  • 2番目のループをスイッチに置き換えて展開します（sizeof（レジスターに収まるタイプ）がわかっていて、常に同じである場合）。

編集：最初のループがボトルネックである場合は、展開が答えになる可能性があります。値が等しい場合に条件の数を半分にすることと組み合わせると、4回展開すると、次のようになります。

uint* lp = (uint*)lhs;
uint* rp = (uint*)rhs;
uint  l;
uint  r;
int count = (n / uint.sizeof) / 4;

while (count--) {
    if( (l = *lp++) != (r = *rp++) {
        return (l < r) ? -1 : 1;
    }
    if( (l = *lp++) != (r = *rp++) {
        return (l < r) ? -1 : 1;
    }
    if( (l = *lp++) != (r = *rp++) {
        return (l < r) ? -1 : 1;
    }
    if( (l = *lp++) != (r = *rp++) {
        return (l < r) ? -1 : 1;
    }
}

もちろん(n / uint.sizeof) % 4、スイッチをインターリーブすることでこのループに混ぜることができる反復を残します。私はそれを読者の邪悪な笑顔の練習として残しました。

于 2009-11-06T10:25:20.250 に答える
2

私はそれについてあまり知りませんが、一度に多くのバイトに命令を適用できるベクトル命令があります。これらの結果を使用して、非常に高速な memcmp を実行できます。どの手順が必要かわかりませんが、Larrabee New Instructions を調べるか、この記事をチェックすると、探しているものが見つかるかもしれませんhttp://www.ddj.com/architect/216402188

注: この CPU は ATM AFAIK ではありません

-編集- 現在、整列されている場合に16バイトを一度に比較できる命令セット（SSEまたはSSE2を調べてみてください）があると確信しています。

この純粋な C++ コードを試すことができます。

template<class T>
int memoryCompare(const T* lhs, const T * rhs, size_t n) {
    const T* endLHS = lhs + n/sizeof(T);
    while(lhs<endLHS) {
        int i = *lhs - *rhs;
        if(i != 0) return i > 0 ? 1 : -1;
        lhs++;
        rhs++;
    }
    //more code for the remaining bytes or call memoryCompare<char>(lhs, rhs, n%sizeof(T));
    return 0;
}

ここでの利点は、ポインターを増やして、ポインターを逆参照してインデックスを適用しないようにすることです (その ptr_offset[index] 対 ptr_offset)。上記はテンプレートを使用しているため、64 ビット マシンで 64 ビットを使用できます。アセンブリのCMPは、実際にはNフラグとZフラグをチェックする減算です。N を比較して N を減らす代わりに、私のバージョンで比較するだけです。

于 2009-11-06T22:34:47.107 に答える
1

データ型に関係なく、バイトごとの比較を行うように memcmp が指定されていると思います。コンパイラの実装が文字列セマンティクスを保持していると確信していますか? すべきではありません。

于 2009-11-06T22:20:01.967 に答える
1

この質問に対する答えは、まったく役に立ちますか?

コンパイラが memcmp() を組み込み/組み込み関数として実装することをサポートしている場合、それを打ち負かすのは難しいようです。

私は D についてほとんど知らないことを認めなければならないので、D コンパイラが組み込み関数をサポートしているかどうかはわかりません。

于 2009-11-06T23:27:03.157 に答える