2

私は何百万ものモジュラー追加を実行するプログラムを書いています。より効率的にするために、私はマシンレベルの命令を使用してモジュラー追加を実装する方法について考え始めました。

マシンのワードサイズをwとします（通常、32ビットまたは64ビット）。モジュラスを2^wとすると、モジュラー加算を非常に高速に実行できます。加数を加算し、キャリーを破棄するだけで十分です。

次のCコードを使用してアイデアをテストしました。

#include <stdio.h>
#include <time.h>

int main()
{
    unsigned int x, y, z, i;
    clock_t t1, t2;

    x = y = 0x90000000;

    t1 = clock();

    for(i = 0; i <20000000 ; i++)
        z = (x + y) % 0x100000000ULL;

    t2 = clock();

    printf("%x\n", z);
    printf("%u\n", (int)(t2-t1));

    return 0;
}

次のオプションを指定してGCCを使用してコンパイルします（-O0GCCがループを展開しないようにするために使用しました）。

-S -masm=intel -O0

結果のアセンブリコードの関連部分は次のとおりです。

    mov DWORD PTR [esp+36], -1879048192
    mov eax, DWORD PTR [esp+36]
    mov DWORD PTR [esp+32], eax
    call    _clock
    mov DWORD PTR [esp+28], eax
    mov DWORD PTR [esp+40], 0
    jmp L2
L3:
    mov eax, DWORD PTR [esp+36]
    mov edx, DWORD PTR [esp+32]
    add eax, edx
    mov DWORD PTR [esp+44], eax
    inc DWORD PTR [esp+40]
L2:
    cmp DWORD PTR [esp+40], 19999999
    jbe L3
    call    _clock

明らかなように、モジュラー演算は一切含まれていません。

ここで、Cコードのモジュラー加算行を次のように変更すると、次のようになります。

z = (x + y) % 0x0F0000000ULL;

アセンブリコードは次のように変更されます（関連する部分のみが表示されます）。

    mov DWORD PTR [esp+36], -1879048192
    mov eax, DWORD PTR [esp+36]
    mov DWORD PTR [esp+32], eax
    call    _clock
    mov DWORD PTR [esp+28], eax
    mov DWORD PTR [esp+40], 0
    jmp L2
L3:
    mov eax, DWORD PTR [esp+36]
    mov edx, DWORD PTR [esp+32]
    add edx, eax
    cmp edx, -268435456
    setae   al
    movzx   eax, al
    mov DWORD PTR [esp+44], eax
    mov ecx, DWORD PTR [esp+44]
    mov eax, 0
    sub eax, ecx
    sal eax, 28
    mov ecx, edx
    sub ecx, eax
    mov eax, ecx
    mov DWORD PTR [esp+44], eax
    inc DWORD PTR [esp+40]
L2:
    cmp DWORD PTR [esp+40], 19999999
    jbe L3
    call    _clock

明らかに、への2つの呼び出しの間に多数の命令が追加されました_clock。

組み立て説明書の数が増えたことを考えると、モジュラスを適切に選択することによるパフォーマンスの向上は、少なくとも100％になると予想しました。ただし、出力を実行すると、速度が10％しか増加しないことに気付きました。OSがマルチコアCPUを使用してコードを並列実行しているのではないかと思いましたが、プロセスのCPUアフィニティを1に設定しても何も変わりませんでした。

説明をお願いします。

編集： VC ++ 2010で例を実行すると、期待どおりの結果が得られました。2番目のコードは最初の例よりも約12倍遅くなっています。

4

2 に答える 2

2

アート はそれを釘付けにしました。

-O02の累乗係数の場合、とで生成された計算のコード-O3は同一であり、違いはループ制御コードであり、実行時間は3倍異なります。

他のモジュラスについては、ループ制御コードの違いは同じですが、計算のコードは完全に同一ではありません（最適化されたコードは少し速いはずですが、アセンブリまたは確かに私のプロセッサ）。最適化されていないコードと最適化されたコードの実行時間の差は約2倍です。

両方の係数の実行時間は、最適化されていないコードと同様です。モジュラスなしの実行時間とほぼ同じです。生成されたアセンブリから計算を削除して取得した実行可能ファイルの実行時間とほぼ同じです。

したがって、実行時間はループ制御コードによって完全に支配されます

    mov DWORD PTR [esp+40], 0
    jmp L2
L3:
    # snip
    inc DWORD PTR [esp+40]
L2:
    cmp DWORD PTR [esp+40], 19999999
    jbe L3

最適化をオンにすると、ループカウンターはレジスター（ここ）に保持されてデクリメントされ、ジャンプ命令はになりjneます。そのループ制御は非常に高速であるため、モジュラス計算は実行時間のかなりの部分を占めるようになり、生成されたアセンブリから計算を削除すると、実行時間がそれぞれ3分の1に短縮されます。2.2。

したがって、を使用してコンパイルすると-O0、計算の速度ではなく、ループ制御コードの速度が測定されるため、わずかな違いが生じます。最適化を使用すると、計算とループ制御の両方を測定することになり、計算の速度の違いが明確に示されます。

于 2012-08-30T18:02:28.797 に答える
1

2つの違いは、2の累乗による除算が論理命令で簡単に変換できるという事実に要約されます。

a/nここで、nは2の累乗でありa >> log2 n 、モジュロの場合と同等です a mod n。a & (n-1)

しかし、あなたの場合、それはそれよりもさらに進んでいます：あなたの値0x100000000ULLは2^32です。これは、符号なし32ビット変数が自動的にモジュロ2^32値になることを意味します。コンパイラは、32ビット変数に対する不要な操作であるため、操作を削除するのに十分なほど賢いものでした。ULL指定子はその事実を変更しません。

32ビット変数に収まる値0x0F0000000の場合、コンパイラーは操作を削除できません。除算よりも高速に見える変換を使用します。

于 2012-08-30T15:07:06.183 に答える