14

背景: 私は、C の memchrとほぼ同じ機能の純粋な D 言語実装を作成しようとしていますが、ポインターの代わりに配列とインデックスを使用します。その理由は、 std.string がコンパイル時の関数評価で機能するようにするためです。D に不慣れな方のために説明すると、特定の制限が満たされていれば、コンパイル時に関数を評価できます。1 つの制限は、ポインターを使用できないことです。もう 1 つは、C 関数を呼び出したり、インライン アセンブリ言語を使用したりできないことです。コンパイル時に文字列ライブラリを機能させると、コンパイル時のコード生成ハックに役立ちます。

質問: memchr は内部でどのように動作して、これほど高速に動作するのですか? Win32 では、単純なループを使用して純粋な D で作成できたものはすべて、境界チェックの無効化、ループ展開などの明らかな最適化手法を使用しても、少なくとも 2 倍遅くなります。文字列内の文字を見つけるのと同じくらい簡単なことですか?

4

5 に答える 5

13

GNU libcのソースを見ることをお勧めします。ほとんどの関数と同様に、関数の一般的な最適化された C バージョンと、マシン固有のトリックを利用して、サポートされているできるだけ多くのアーキテクチャ用に最適化されたアセンブリ言語バージョンの両方が含まれます。

x86-64 SSE2 バージョンは、データのキャッシュ ライン全体 (4 つの 16B ベクトル) からの結果pcmpeqbを一度に組み合わせて、早期終了のオーバーヘッドを償却しますpmovmskb// 。testjcc

gcc と clang は現在、if() break早期終了条件でループを自動ベクトル化することができないため、明らかな C 実装から単純なバイト単位の asm を作成します。

于 2009-02-08T03:56:04.857 に答える
7

newlib からの memchr のこの実装は、誰かが memchr を最適化する一例です: 一度に 4 バイトを読み込んでテストしています (memchr を除いて、newlib ライブラリの他の関数はhere です)。

ちなみに、MSVC ランタイム ライブラリのソース コードのほとんどは、MSVC インストールのオプション部分として利用できます (そのため、それを確認できます)。

于 2009-02-08T03:59:58.717 に答える
6

これは、 memchr.cからの FreeBSD の (BSD ライセンス) memchr()です。FreeBSD のオンライン ソース コード ブラウザーは、長年の実績があり、BSD ライセンスのコード例を参照するのに適しています。

void *
memchr(s, c, n)
    const void *s;
    unsigned char c;
    size_t n;
{
    if (n != 0) {
        const unsigned char *p = s;

        do {
            if (*p++ == c)
                return ((void *)(p - 1));
        } while (--n != 0);
    }
    return (NULL);
}
于 2009-02-08T04:09:04.767 に答える
2

memset や memcpy のような memchr は、通常、かなり少量のマシン コードに削減されます。同様のアセンブリ コードをインライン化せずに、そのような速度を再現することはまずありません。実装で考慮すべき主要な問題の 1 つは、データの配置です。

使用できる可能性のある一般的な手法の 1 つは、検索対象の文字列の末尾に番兵を挿入することです。これにより、番兵が確実に見つかるようになります。文字列の終わりのテストをループ内からループの後に移動できます。

于 2009-02-08T05:15:06.600 に答える