4

他strlen()のほとんどのルーチンと比較して、優れたビット操作を実行し、毎回4バイトをチェックして関数を非常に高速にするglibcのように、アセンブリ内の2つの文字列を比較するこのようなものはありますか？文字列処理の部分に非常に興味を持っているC言語のコード実装に関するいくつかのページを読んでいますが、それでもこのようなものは見つかりませんでした。この関数は私のアプリケーションの心臓部であるため、できるだけ速くする必要があります（ハッシュテーブルはお勧めしません）

どんなアセンブラーでも大歓迎です。しかし、私はIntelのアセンブリ構文に少し精通しています。提供するアセンブリが異なる場合は、コメントしてください。

4

4 に答える 4

6

単語ごとに比較できます (たとえば、一度に 32 ビットまたは 64 ビット)。文字列の端を超えないように注意する必要があります。文字列を作成している場合は、単語サイズの倍数になるようにゼロを埋め込むことができます。チェックする必要さえありません。

于 2013-02-07T05:11:47.847 に答える
4

ゼロで終了する文字列を想定します（ただし、同じことが当てはまりますmemcmp()）。アセンブリで文字列比較を行う最速の方法は、文字列の長さ/秒と特定のCPUによって異なります。

一般に; SSEまたはAVXはセットアップコストが高くなりますが、実行後のスループットが速くなるため、非常に長い文字列を比較する場合（特に、ほとんどの文字が一致する場合）に最適です。

あるいは、汎用レジスタを使用して一度に1バイトを実行するものは、通常、セットアップコストが非常に低く、スループットが低いため、多数の小さな文字列（または多数の大きな文字列）を比較する場合に最適です。最初の数文字は異なる可能性があります）。

特定のアプリケーションに対してこれを行う場合は、比較される文字の平均数を決定し、その平均に最適なアプローチを見つけることができます。また、ケースごとに異なる機能を使用することもできます。たとえば、混合物がある場合はastrcmp_small()とaを実装します。strcmp_large()

これらすべてにもかかわらず、文字列比較のパフォーマンスが非常に重要である場合、文字列を比較する最も速い方法は、文字列をまったく比較しないことである可能性が非常に高くなります。基本的に、「アプリケーションの心臓部であるため、この機能をできるだけ速くする必要があります」という言葉は、アプリケーションを実装するためのより良い方法がなぜ不可能なのか、誰もが不思議に思うはずです。

于 2013-02-07T14:15:15.263 に答える
3

FreshLib / strlib.asmライブラリに実装されているStrCompCase（大文字と小文字を区別） 。

dword比較を使用するコードは次のとおりです。

それは最初に文字列の長さをチェックすることに注意してください。これは、前述のライブラリでは文字列に長さのプレフィックスが付いているため、StrLenはインスタントO（1）であり、終了NULLのスキャンはフォールバックとしてのみ提供されます（この回答の2番目の部分を参照）。

実際の比較の前に長さを比較すると、さまざまな文字列の速度をO（1）にすることができます。これにより、大きな配列を検索する場合に、パフォーマンスが大幅に向上する可能性があります。

次に、比較はdwordsで行われ、最後に、文字列の長さが4の乗算でない場合、残りの1..3バイトがバイトごとに比較されます。

proc StrCompCase, .str1, .str2
begin
        push    eax ecx esi edi

        mov     eax, [.str1]
        mov     ecx, [.str2]

        cmp     eax, ecx
        je      .equal

        test    eax, eax
        jz      .noteq

        test    ecx, ecx
        jz      .noteq

        stdcall StrLen, eax
        push    eax
        stdcall StrLen, ecx

        pop     ecx
        cmp     eax, ecx
        jne     .noteq

        stdcall StrPtr, [.str1]
        mov     esi,eax
        stdcall StrPtr, [.str2]
        mov     edi,eax

        mov     eax, ecx
        shr     ecx, 2
        repe cmpsd
        jne     .noteq
        mov     ecx, eax
        and     ecx, 3
        repe cmpsb
        jne     .noteq

.equal:
        stc
        pop     edi esi ecx eax
        return

.noteq:
        clc
        pop     edi esi ecx eax
        return
endp

StrLenコードについて：

これがStrLenの実装です。

可能であれば、長さのプレフィックス付き文字列を使用していることがわかります。これにより、実行時間がO（1）になります。これが不可能な場合は、1サイクルあたり8バイトをチェックするスキャンアルゴリズムにフォールバックし、かなり高速ですが、それでもO（n）です。

proc StrLen, .hString    ; proc StrLen [hString]
begin
        mov     eax, [.hString]
        cmp     eax, $c0000000
        jb      .pointer

        stdcall StrPtr, eax
        jc      .error

        mov     eax, [eax+string.len]
        clc
        return

.error:
        xor     eax, eax
        stc
        return

.pointer:
        push    ecx edx esi edi

; align on dword
.byte1:
        test    eax, 3
        jz      .scan

        cmp     byte [eax], 0
        je      .found

        inc     eax
        jmp     .byte1

.scan:
        mov     ecx, [eax]
        mov     edx, [eax+4]

        lea     eax, [eax+8]

        lea     esi, [ecx-$01010101]
        lea     edi, [edx-$01010101]

        not     ecx
        not     edx

        and     esi, ecx
        and     edi, edx

        and     esi, $80808080
        and     edi, $80808080

        or      esi, edi
        jz      .scan

        sub     eax, 9

; byte 0 was found: so search by bytes.
.byteloop:
        lea     eax, [eax+1]
        cmp     byte [eax], 0
        jne     .byteloop

.found:
        sub     eax, [.hString]
        clc
        pop     edi esi edx ecx
        return
endp

ゼロで終了する文字列には、パフォーマンスとセキュリティの両方の問題があることに注意してください。

サイズのプレフィックス付き文字列を使用することをお勧めします。たとえば、前述のライブラリは動的文字列を使用します。この場合、文字列には、文字列の現在の長さを含むオフセット-4（上記のコードではstring.len）にdwordフィールドが含まれます。

于 2013-02-07T08:34:07.983 に答える
3

バイトごとの比較よりも高速な最初のルールは、文字列または.align 16任意の定数文字列を malloc して確実にすることです。

  • セキュリティ違反に対する堅牢性 (過去の割り当て領域の読み取り)
  • xxm (または 64 ビット) 処理に最適な配置
于 2013-02-07T11:13:07.107 に答える