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.
}

虽然我还没有想出如何进一步优化这一点，但可能来自操作的内在函数 Bit-Granularity，__shiftleft128或者_rot可能有用？

请注意，我还在 GPU 上对结果数据进行处理，所以重要的是得到resultGPU 可以用来计算正确的数据。

建议？

编辑：

添加了表格查找。

编辑：

            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优化构建生成的代码

操作码（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 = 1 - (bits >> (63 - sign_offset) & 0x2);
int result  = ((x << 18) * sign) | r; // 32 bits

也许处理器会发现移位 32 位值更便宜 -HIDWORD用任何导致直接访问高阶 DWORD 而无需移位的定义替换。另外，为了准备下一步，让我们重新安排第二个作业中的移位：

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

观察到，在二进制补码中，q * (-1)等于~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 回答
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 回答
0

我认为这是最快的解决方案：

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

然后根据是否在 GPU 上设置符号位来纠正 x。

于 2012-08-14T10:46:43.663 回答