12

私のコードでは、次の行が現在ホットスポットです。

int table1[256] = /*...*/;
int table2[512] = /*...*/;
int table3[512] = /*...*/;

int* result = /*...*/;
for(int r = 0; r < r_end; ++r)
{
    std::uint64_t bits = bit_reader.value(); // 64 bits, no assumption regarding bits.

    // The get_ functions are table lookups from the highest word of the bits variable.

    struct entry
    {
        int sign_offset : 5;
        int r_offset    : 4;        
        int x           : 7;        
    };

    // NOTE: We are only interested in the highest word in the bits variable.

    entry e;
    if(is_in_table1(bits)) // branch prediction should work well here since table1 will be hit more often than 2 or 3, and 2 more often than 3.
        e = reinterpret_cast<const entry&>(table1[get_table1_index(bits)]);
    else if(is_in_table2(bits))
        e = reinterpret_cast<const entry&>(table2[get_table2_index(bits)]);
    else
        e = reinterpret_cast<const entry&>(table3[get_table3_index(bits)]);

    r                 += e.r_offset; // r is 18 bits, top 14 bits are always 0.
    int x              = e.x; // x is 14 bits, top 18 bits are always 0.        
    int sign_offset    = e.sign_offset;

    assert(sign_offset <= 16 && sign_offset > 0);

    // The following is the hotspot.

    int sign    = 1 - (bits >> (63 - sign_offset) & 0x2);
    (*result++) = ((x << 18) * sign) | r; // 32 bits

    // End of hotspot

    bit_reader.skip(sign_offset); // sign_offset is the last bit used.
}

これをさらに最適化する方法はわかりませんが、ビット粒度での操作の組み込み関数から何かが役立つ可能性がありますか__shiftleft128？_rot

結果のデータもGPUで処理していることに注意してください。重要なことはresult、GPUが正しい計算に使用できるものを取得することです。

提案？

編集：

テーブルルックアップを追加しました。

編集：

            int sign = 1 - (bits >> (63 - e.sign_offset) & 0x2);
000000013FD6B893  and         ecx,1Fh  
000000013FD6B896  mov         eax,3Fh  
000000013FD6B89B  sub         eax,ecx  
000000013FD6B89D  movzx       ecx,al  
000000013FD6B8A0  shr         r8,cl  
000000013FD6B8A3  and         r8d,2  
000000013FD6B8A7  mov         r14d,1  
000000013FD6B8AD  sub         r14d,r8d
4

5 に答える 5

2

符号が +/-1 であることを見落としていたので、回答を修正します。

maskのすべての可能な値に対して適切に定義されたビットマスクを持つ配列であると仮定するとsign_offset、このアプローチはより高速になる可能性があります

  bool sign = (bits & mask[sign_offset]) != 0;
  __int64 result = r;
  if (sign)
    result |= -(x << 18);
  else
    result |= x << 18;

VC2010 最適化ビルドによって生成されたコード

OPコード（11命令）

; 23   :   __int64 sign = 1 - (bits >> (63 - sign_offset) & 0x2);

    mov rax, QWORD PTR bits$[rsp]
    mov ecx, 63                 ; 0000003fH
    sub cl, BYTE PTR sign_offset$[rsp]
    mov edx, 1
    sar rax, cl

; 24   :   __int64 result  = ((x << 18) * sign) | r; // 32 bits
; 25   :   std::cout << result;

    and eax, 2
    sub rdx, rax
    mov rax, QWORD PTR x$[rsp]
    shl rax, 18
    imul    rdx, rax
    or  rdx, QWORD PTR r$[rsp]

私のコード (8 命令)

; 34   :   bool sign = (bits & mask[sign_offset]) != 0;

    mov r11, QWORD PTR sign_offset$[rsp]

; 35   :   __int64 result = r;
; 36   :   if (sign)
; 37   :     result |= -(x << 18);

    mov rdx, QWORD PTR x$[rsp]
    mov rax, QWORD PTR mask$[rsp+r11*8]
    shl rdx, 18
    test    rax, QWORD PTR bits$[rsp]
    je  SHORT $LN2@Test1
    neg rdx
$LN2@Test1:

; 38   :   else
; 39   :     result |= x << 18;

    or  rdx, QWORD PTR r$[rsp]

スキズによる編集

ブランチを削除するには:

shl rdx, 18
lea rbx,[rdx*2]
test rax, QWORD PTR bits$[rsp]
cmove rbx,0
sub rdx,rbx
or rdx, QWORD PTR r$[rsp]
于 2012-08-14T07:27:19.227 に答える
1

符号を計算するには、次のことをお勧めします。

int sign = (int)(((int64_t)(bits << sign_offset)) >> 63);

これは 2 つの命令 (shlおよびsar) のみです。

sign_offset予想よりも大きい場合:

int sign = (int)(((int64_t)(bits << (sign_offset - 1))) >> 63);

これはまだ悪くありません。3 つの命令のみである必要があります。

それはあなたがこれを行うことができる0または-1として答えを与えます：

(*result++) = (((x << 18) ^ sign) - sign) | r;
于 2012-08-14T08:52:36.327 に答える
1

メモリ アクセスは通常、最新の CPU におけるすべての最適化問題の根源です。速度低下がどこで発生しているかについて、パフォーマンス ツールによって誤解されています。コンパイラはおそらくコードを次のように並べ替えています:-

int sign    = 1 - (bits >> (63 - get_sign_offset(bits)) & 0x2);
(*result++) = ((get_x(bits) << 18) * sign) | (r += get_r_offset(bits));

あるいは：-

(*result++) = ((get_x(bits) << 18) * (1 - (bits >> (63 - get_sign_offset(bits)) & 0x2))) | (r += get_r_offset(bits));

これにより、ホットスポットとして特定した行が強調表示されます。

メモリを整理する方法と、さまざまな get_ 関数の機能を調べます。get_ 関数を投稿できますか?

于 2012-08-14T09:03:06.990 に答える
1

同等の変換をいくつか行いましょう。

int sign = 1 - (bits >> (63 - sign_offset) & 0x2);
int result  = ((x << 18) * sign) | r; // 32 bits

おそらく、プロセッサは 32 ビット値をシフトする方が安価であることに気付くでしょう。 の定義をHIDWORD、シフトせずに上位の DWORD に直接アクセスできるものに置き換えます。また、次のステップの準備として、2 番目の割り当てのシフトを再配置しましょう。

#define HIDWORD(q) ((uint32_t)((q) >> 32))
int sign = 1 - (HIDWORD(bits) >> (31 - sign_offset) & 0x2);
int result  = ((x * sign) << 18) | r; // 32 bits

2 の補数では、 が、または、 がとq * (-1)等しいことに注意してください。これは、厄介な乗算を取り除く 2 番目の変換を正当化します。~q + 1(q ^ -1) - (-1)q * 1(q ^ 0) - 0

int mask = -(HIDWORD(bits) >> (32 - sign_offset) & 0x1);
int result  = (((x ^ mask) - mask) << 18) | r; // 32 bits

次に、シフトを再配置しましょう。

int mask = (-(HIDWORD(bits) >> (32 - sign_offset) & 0x1)) << 18;
int result  = (((x << 18) ^ mask) - mask) | r; // 32 bits

-およびに関するアイデンティティを思い出してください~。

int mask = (~(HIDWORD(bits) >> (32 - sign_offset) & 0x1) + 1) << 18;

再配置を再度シフトします。

int mask = (~(HIDWORD(bits) >> (32 - sign_offset) & 0x1)) << 18 + (1 << 18);

誰が最終的にこれを解き放つことができますか? （とにかく変換​​は正しいですか？）

(実際の CPU でのプロファイリングのみがパフォーマンスを評価できることに注意してください。命令数などの測定は行いません。変換がまったく役に立ったかどうかさえ確信が持てません。)

于 2012-08-14T07:44:41.800 に答える
0

これが最速の解決策だと思います：

*result++ = (_rotl64(bits, sign_offset) << 31) | (x << 18) | (r << 0); // 32 bits

次に、GPU で符号ビットが設定されているかどうかに応じて x を修正します。

于 2012-08-14T10:46:43.663 に答える