java - 按位旋转是否比当前Intel CPU的移位慢？

Question

我很好奇java.lang.Integer.rotateLeft是否通过使用旋转指令进行了优化并为此编写了基准。结果尚无定论：它比两班制快得多，但比单班制慢一点。所以我用C ++重写了它，并得到了差不多的结果。通过g++ -S -Wall -O3编译时，可以在generated assembler中看到说明。我的CPU是Intel Core i5。

benchmark很长，肯定不是最好的代码，但是我认为它没有坏。还是？根据文档，旋转需要一个周期，就像换档一样。有人可以解释结果吗？

rotations:  6860
shift:      5100

前两个答案是错误的。 gcc和java的JIT都知道旋转指令并使用它们。关于gcc，请参见上面的链接，关于java，请参见我的 java benchmark及其结果

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

Answer 1

我不知道gcc和java jit是否能够识别SHIFT和OR运算符序列可以简化为ROTATE指令，这很有趣。

g ++编译器展开循环，并使用SHIFT immediate和ROTATE 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

它们的主要区别在于 SHIFT的salq / sarq和 ROTATE的rorq的用法，因此您想知道为什么时间不同是正确的。

答案深藏于Sandy Bridge（您的Core i5处理器）的微体系结构中，可在 INTEL® 64 and IA-32 Processor Architectures Optimization Reference Manual中找到
最新的是 Order Number: 248966-026 April 2012

无论使用 SHIFT操作码还是 by 1， by immediate指令都有1个周期延迟。它可以从 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
通过注册或立即指示进行轮换。如果可能，替换为
通过1条指令旋转。
在英特尔微体系结构代码名称Sandy Bridge中，ROL / ROR按立即数为1
循环吞吐量，SHLD / SHRD使用与源和目标相同的寄存器，
立即数具有1个周期的延迟和0.5个周期的吞吐量。 “ ROL / ROR
reg，imm8”指令具有两个微操作，旋转的延迟为1个周期
如果使用标志，则将结果注册并为标志分配2个周期。
在英特尔微体系结构代码名称Ivy Bridge中，立即大于1的“ ROL / ROR reg，imm8”指令是一个微操作，具有一个周期的延迟，当
使用溢出标志结果。当立即数为1时，依赖于溢出
后续指令对ROL / ROR的标志结果将看到ROL / ROR指令
具有两个周期的延迟。

2.4.4.2执行单元和发布端口

在每个周期，核心可以将µops调度到四个发布端口中的一个或多个。在
在微体系结构级别，存储操作进一步分为两部分：存储
数据和存储地址操作。派发μop的四个端口
执行单元以及加载和存储操作的关系如图2-6所示。一些
端口每个时钟可以调度两个µop。这些执行单元标记为Double
速度。

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

端口1。在周期的前半部分，端口1可以调度一个浮点数
执行（除移动之外的所有浮点操作，所有SIMD操作）µop或
一个标准速度整数（乘，移位和旋转）μop或一个ALU（算术）
op在周期的后半部分，它可以调度一个类似的ALU µop。

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

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

每个周期的总发行带宽范围为零到六微欧。每条管道
包含几个执行单元。 µop将被分派到与正确操作类型相对应的管道。例如，整数算术逻辑单元
并且浮点执行单元（加法器，乘法器和除法器）可以共享一个
管道。