优化位运算逻辑

Question

在我的代码中，以下几行目前是热点部分：

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  

- ronag

---

那么，您可以将预先计算的符号值直接存储在表中与符号偏移量一起吗？符号偏移本身是否需要？另外，检查循环周围是否有任何跨迭代保持不变的内容会让人感到放心。 - Tony Delroy

"在循环中唯一变化的是位(bit)……如果这是真的（在x和r不是从位(bit)计算得出的意义上），那么结果((x << 18) * sign) | r中唯一的变量就是符号(sign)，如果你现在能够将'1'左移，以便可以直接与bits进行&运算，使用它来在循环之前预先计算(x << 18) | r和-(x << 18) | r的值，然后根据bits的值选择这两个值之间的一个。" - Tony Delroy

@TonyDelroy：我有点太快了，x和r是从位计算的。对于我的含糊不清，我很抱歉，我会更新我的示例。 - ronag

我注意到，逻辑右移比算术右移更快。我不知道左移操作是否也是如此，但你可以通过将“x”更改为“unsigned”来尝试一下。 - Christian Ammer

@ronag：我仍然敢打赌，get_函数是减慢速度的罪魁祸首。编译器正在将调用重新排序到热点区域。三个表查找可能比在大表中进行单个查找要糟糕得多。内存访问通常是程序中可以执行的最慢的操作，它可能需要几个周期或数千个周期，具体取决于正在读取哪个内存。 - Skizz

Answer 1

我忽略了符号是+/-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]

Skizz编辑

删除分支的方法：

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]

- Andriy

---

@harold：我也不知道，但这是我目前能获得的最短汇编代码... - Andriy

添加另一个内存查找将使代码比仅计算位位置并使用“bt”指令更慢。内存访问几乎总是比通过CPU运行几个指令慢。 - Skizz

Answer 2

让我们进行一些等价变换：

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

或许处理器会发现移动32位值更便宜 - 用直接访问高位DWORD的方式替换HIDWORD的定义。另外，为了准备下一步，让我们重新排列第二个赋值中的移位操作：

#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

回忆一下与 IT 相关的 - 和 ~ 的身份：

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

再次调整班次：

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

谁最终能解决这个问题？（转换是否正确？）

（请注意，只有在真实CPU上进行分析才能评估性能。像指令计数之类的测量是不够的。我甚至不确定这些转换是否有所帮助。）

- krlmlr

---

很好，实际上我认为可以将“~bits”更改为“bits”，然后让GPU在下一个处理阶段反转该值的符号。我今晚会试试。 - ronag

第一个转换是错误的，我以为是 & 0x1，但实际上应该是 & 0x2。如果 sign 是 -1，那么 result 会发生什么？ - krlmlr

我在想位或运算是否仍然有效，但似乎是的。 - krlmlr

@Andrey：能否解释一下这个小错误？ - krlmlr

@Andrey：没错。一个静态代码分析器可能会因此而崩溃，但编译器和CPU应该能够处理它。 - krlmlr

Answer 3

为了计算符号，我建议这样做：

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

只有两个指令（shl 和 sar）。

如果 sign_offset 比我预期的要大一个：

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

这还不错。应该只有3条指令。

这将给出一个答案为0或-1，你可以这样做：

(*result++) = (((x << 18) ^ sign) - sign) | r;

- harold

---

那样行不通，因为符号位会被移出，应该是 bits << (sign_offset-1)。 - ronag

它会被移出吗？那么get_sign_offset到底返回什么，不是前导零的数量吗？ - harold

sign_bit_index =（63-sign_offset） - ronag

Answer 4

内存访问通常是现代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_函数？

- Skizz

---

我不能直接发布代码，但我可以写一个变体并发布，稍后我会这样做。 - ronag

由于您现在可以看到的分支，因此不会进行重新排序。 - ronag

@ronag：我不会那么确定，编译器可以对代码进行最意想不到的（通常更优化的）操作。条件部分仍然可以重新排序到热点区域，唯一确定的方法是查看汇编输出 - 通常有一个编译器选项将汇编版本写入文件，否则调试器可能能够找到该代码。 - Skizz

我使用了调试器，并使用生成的发布程序集更新了我的帖子。 - ronag

Answer 5

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

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

然后根据GPU上的符号位设置，对x进行修正。

- ronag