微优化指针+无符号+ 1

Question

很难以相信构造p[u+1]发生在代码的最内层循环中的几个地方,我保持这样,在正确运行数天的操作中,对其进行微观优化会产生数小时的差异.

通常*((p+u)+1)是最有效的.有时候*(p+(u+1))效率最高.很少*((p+1)+u)是最好的.(但通常优化器可以转换*((p+1)+u)为*((p+u)+1)后者更好,并且不能*(p+(u+1))与其他任何一个转换).

p是一个指针,u是一个无符号的.在实际代码中,它们中的至少一个(更可能两者)在表达式被评估的点处已经在寄存器中.这些事实对我的问题至关重要.

在32位(在我的项目放弃支持之前)中,所有三个都具有完全相同的语义,并且任何一半不错的编译器只选择三者中最好的并且程序员永远不需要关心.

在这些64位用法中,程序员知道这三者具有相同的语义,但编译器不知道.就编译器所知,何时u从32位扩展到64位的决定会影响结果.

什么是最简洁的方法告诉编译器这三个语义是相同的,编译器应该选择最快的？

在一个Linux 64位编译器中,我几乎在那里p[u+1L]使编译器在通常最好*((p+u)+1)和有时更好之间智能地选择*(p+( (long)(u) + 1) ).在极少数情况下*(p+(u+1))仍然比第二种更好,有点丢失.

显然,这在64位Windows中没有用.既然我们已经放弃了32位支持,那么可能p[u+1LL]足够便携且足够好.但我能做得更好吗？

请注意,使用std::size_t而不是unsignedfor u将消除整个问题,但会在附近产生更大的性能问题.铸造u到std::size_t那里几乎是足够好,也许我能做到的最好.但对于一个不完美的解决方案来说,这是非常冗长的.

简单编码(p+1)[u]使选择更可能是最佳选择p[u+1].如果代码的模板化程度较低且更稳定,我可以将它们全部设置为(p+1)[u]然后进行配置文件,然后再将其切换回p[u+1].但是模板化往往会破坏这种方法(在配置文件的许多地方出现单一的源代码行,导致严重的时间,但不是单独的严重时间).

对此应该有效的编译器是GCC,ICC和MSVC.

Answer 1

答案不可避免地是特定于编译器和目标的，但即使1ULL比任何目标体系结构上的指针更宽，一个好的编译器也应该优化它。 如果只需要结果的低位部分，可以使用哪种 2 的补码整数运算而无需将输入中的高位清零？解释了为什么截断为指针宽度的更宽计算会给出与首先使用指针宽度进行计算相同的结果。这就是为什么编译器甚至可以在 32 位机器（或具有 x32 ABI 的 x86-64）上对其进行优化，从而将操作数1ULL提升+为 64 位类型。（或者在某些 64 位 ABI 上，某些架构的long long128b 是）。

1ULL 看起来对于 64 位是最佳的，对于 32 位和 clang 来说是最佳的。无论如何，你并不关心 32 位，但 gcc 浪费了return p[u + 1ULL];. 所有其他情况均编译为具有缩放索引+4+p 寻址模式的单个负载。因此，除了一个编译器的优化失败之外，1ULL32 位看起来也很好。（我认为这不太可能是一个 clang bug 并且优化是非法的）。

int v1ULL(std::uint32_t u) { return p[u + 1ULL]; }
//   ...  load u from the stack
//    add     eax, 1
//    mov     eax, DWORD PTR p[0+eax*4]

代替

    mov     eax, DWORD PTR p[4+eax*4]

有趣的是， gcc 5.3 在针对 x32 ABI （具有 32 位指针的长模式和类似于 SySV AMD64 的寄存器调用 ABI）时不会犯此错误。它使用 32 位地址大小前缀来避免使用 的高 32b edi。

令人烦恼的是，当它可以通过使用 64 位有效地址来保存一个字节的机器代码时（当没有机会溢出/进位到 upper32 中生成低 4GiB 之外的地址时），它仍然使用地址大小前缀。通过引用传递指针是一个很好的例子：

int x2   (char *&c) { return *c; }
//    mov     eax, DWORD PTR [edi]  ; upper32 of rax is zero
//    movsx   eax, BYTE PTR [eax]   ; could be byte [rax], saving one byte of machine code

呃，其实我忘了。32 位地址可以符号扩展为 64b，而不是零扩展。如果是这种情况，它也可以用于movsx第一条指令，但这会花费一个字节，因为movsx它的操作码比mov.

不管怎样，对于需要更多寄存器和更好的 ABI 的指针密集型代码来说，x32 仍然是一个有趣的选择，而没有 8B 指针的缓存未命中命中。

64 位 asm 必须将保存参数的寄存器的 upper32 位清零（使用mov edi,edi），但在内联时这种情况会消失。查看微小函数的 godbolt 输出是测试这一点的有效方法。

如果我们想双重确保编译器不会搬起石头砸自己的脚，并在知道 upper32 已经为零时将其归零，我们可以使用通过引用传递的 arg 来创建测试函数。

int v1ULL(const std::uint32_t &u) { return p[u + 1ULL]; }
//  mov     eax, DWORD PTR [rdi]
//  mov     eax, DWORD PTR p[4+rax*4]