2

我很好奇是否java.lang.Integer.rotateLeft通过使用旋转指令进行优化并为其编写基准。结果尚无定论:它比两班倒快得多,但比单班倒慢一点。所以我用 C++ 重写了它并得到了大致相同的结果。通过编译时,g++ -S -Wall -O3我可以看到生成的汇编器中的指令。我的 CPU 是 Intel Core i5。

基准很长,肯定不是最好的代码,但我不认为它被破坏了。或者是吗?根据文档,轮换需要一个周期,就像轮班一样。任何人都可以解释结果吗?

rotations:  6860
shift:      5100

前两个答案是错误的。gcc 和 java 的 JIT 都知道旋转指令并使用它们。关于 gcc 参见上面的链接,关于 java 参见我的java benchmark and its results

benchmark   ns linear runtime
   Rotate 3.48 ====================
NonRotate 5.05 ==============================
    Shift 2.16 ============
4

3 回答 3

7

我不知道 gcc 和 java jit 能够识别一系列 SHIFT 和 OR 运算符可以简化为 ROTATE 指令,非常有趣。

g++ 编译器展开您的循环、使用SHIFT immediateROTATE immediate指令(因为您按常量值移位和旋转)。

这是在 TimeShift 循环展开案例中重复的六个指令序列:

movq    %rax, %rbx
salq    $13, %rbx
leaq    (%rbp,%rbx), %rbx
movq    %rdi, %rbp
sarq    $27, %rbp
xorq    %rbx, %rdx

这是在 TimeRotate 循环展开案例中重复的六个指令序列:

movq    %rdx, %rbx
rorq    $45, %rbx
leaq    (%rbp,%rbx), %rbx
movq    %r8, %rbp
rorq    $49, %rbp
xorq    %rbx, %r9

它们的区别主要在于salq/sarq forSHIFT和rorq for的使用,ROTATE所以你想知道为什么时间不同是正确的。

答案深藏在 Sandy Bridge(您的 Core i5 处理器)的微架构中,可在INTEL® 64 和 IA-32 处理器架构优化参考手册 中找到最新的是Order Number: 248966-026 April 2012

SHIFT无论您使用操作by 1码还是by immediate. 它可以从Port 0或分派,Port 1因此具有 0.5 个周期的吞吐量 - 处理器SHIFT immediate每个周期可以分派和退出两条指令。如果需要条件标志的结果(它们不在 gcc 生成的代码中),则该ROTATE指令需要三个微操作,如果不需要,则需要两个微操作(因此在您的情况下需要两个微操作)。然而,该ROTATE指令只能被分派Port 1,因此具有 1 个周期的吞吐量——处理器每个周期只能分派和退出一个ROTATE immediate

我已经复制了下面的相关图片和部分。

3.5.1.5 按位旋转

按位旋转可以在 CL 寄存器中指定的计数、立即数和 1 位之间进行选择。通常,立即循环和寄存器循环指令比循环旋转 1 位要慢。循环 1 指令具有与移位相同的延迟。 汇编/编译器编码规则 35。(ML 影响,L 通用性)避免通过寄存器旋转或通过立即指令旋转。如果可能,请用 ROTATE by 1 指令替换。 在英特尔微架构代号 Sandy Bridge 中,立即数的 ROL/ROR 具有 1 个周期的吞吐量,使用相同寄存器作为源和目标的立即数常量的 SHLD/SHRD 具有 1 个周期的延迟和 0.5 个周期的吞吐量。“ROL/ROR reg, imm8”指令有两个微操作,循环寄存器结果的延迟为 1 个周期,标志的延迟为 2 个周期(如果使用)。在 Intel 微架构代号 Ivy Bridge 中,立即数大于 1 的“ROL/ROR reg, imm8”指令是一个在使用溢出标志结果时具有一个周期延迟的微操作。当立即数为 1 时,后续指令对 ROL/ROR 溢出标志结果的依赖会看到 ROL/ROR 指令有两个周期的延迟。

2.4.4.2 执行单元和发布端口

在每个周期,内核可以将微操作发送到四个发布端口中的一个或多个。在微架构层面,存储操作进一步分为两部分:存储数据和存储地址操作。图 2-6 显示了将 μop 分派到执行单元以及加载和存储操作的四个端口。一些端口每个时钟可以调度两个微操作。这些执行单元被标记为双速。

端口 0。在周期的前半部分,端口 0 可以调度一个浮点移动 µop(浮点堆栈移动、浮点交换或浮点存储数据)或一个算术逻辑单元 (ALU) µop (算术、逻辑、分支或存储数据)。在周期的后半部分,它可以调度一个类似的 ALU µop。

端口 1。在周期的前半部分,端口 1 可以调度一个浮点执行(除移动之外的所有浮点运算、所有 SIMD 运算)μop 或一个正常速度整数(乘法、移位和旋转)μop 或一个 ALU(算术)微操作。在周期的后半部分,它可以调度一个类似的 ALU µop。

端口 2。此端口支持每个周期调度一个加载操作。

端口 3。此端口支持每个周期调度一个存储地址操作。

每个周期的总问题带宽范围为 0 到 6 µops。每个管道包含几个执行单元。µops 被分派到对应于正确操作类型的管道。例如,整数算术逻辑单元和浮点执行单元(加法器、乘法器和除法器)可以共享一个流水线。

图 2-11。 乱序核心中的执行单元和端口

于 2012-10-07T16:50:48.967 回答
5

根据这个基准,移位和轮换在您的 CPU 上具有相同的延迟,但轮换的吞吐量较低(列为“T”的结果是倒数吞吐量,这更容易与延迟进行比较)。这可能正是您所看到的那种结果 - 较低的吞吐量有点妨碍,但您并没有完全使执行单元饱和,因此它没有显示出 2 差异的全部因素。对自己进行测试并不容易,尤其是当您必须与编译器对抗以使其发出您想要的指令时。

于 2012-10-07T19:32:31.163 回答
1

When you are looking at micro-benchmarks, you have to consider that the JIT will optimise common patterns e.g. shift, it recognises more efficiently than uncommon patterns e.g. rotate (or ones it does not recognise) This can means that two operations which should take the same amount of time can perform quite differently because one is more heavily optimised than the other. e.g. with more loop unrolling or dead code removal.

Even simple instructions can interact to produce different and unexpected results. In other words you cannot look at a single instruction and assume it tell you very much about how it will perform when more instructions are used. Context is important at such a low level.

I suggest you try comparing these operations in a realistic program and I suspect you will have great difficulty finding a measurable difference.

于 2012-10-07T19:20:18.900 回答