按位旋转是否比当前Intel CPU上的转换慢？

Question

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

该基准是很长,肯定不是最好的一段代码,但我不认为这是坏了.或者是吗？根据文档,旋转需要一个周期,就像轮班一样.谁能解释一下结果呢？

rotations:  6860
shift:      5100

---

前两个答案是错误的.gcc和java的JIT都知道旋转指令并使用它们.关于gcc看到上面的链接,关于java看看我的java基准测试及其结果

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

它们的主要区别在于使用salq/sarq SHIFT和rorq,ROTATE所以你想知道为什么时间不同.

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

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

我复制了下面的相关图片和部分.

3.5.1.5按位旋转

按位旋转可以选择旋转CL寄存器中指定的计数,立即数和1位.通常,通过立即旋转和通过寄存器指令旋转比旋转1位慢.rotate by 1指令具有与shift相同的延迟. 汇编/编译器编码规则35.(ML影响,L一般性)避免通过寄存器进行ROTATE或通过立即指令进行ROTATE.如果可能,请使用ROTATE by 1指令替换. 在Intel微体系结构代码名称Sandy Bridge中,ROL/ROR by立即具有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执行单元和发布端口

在每个周期,核心可以将微操作发送到四个发布端口中的一个或多个.在微体系结构级别,存储操作进一步分为两部分:存储数据和存储地址操作.图2-6显示了将μops分派给执行单元以及加载和存储操作的四个端口.一些端口每个时钟可以发送两个μop.这些执行单元标记为Double Speed.

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

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

端口2.此端口支持每个周期分配一个加载操作.

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

每个周期的总发布带宽范围为0到6μs.每个管道包含几个执行单元.μops被分派到与正确操作类型对应的管道.例如,整数算术逻辑单元和浮点执行单元(加法器,乘法器和除法器)可以共享管道.

Answer 2

根据此基准，移位和轮换在CPU上具有相同的延迟，但是轮换具有较低的吞吐量（此处列出的结果为“ T”是互为吞吐量，可以更轻松地与延迟进行比较）。那可能恰好具有您所看到的那种结果-较低的吞吐量有点妨碍，但是您没有完全饱和执行单元，因此没有显示2差的全部因数。测试自己并不容易，特别是在必须与编译器进行斗争以使其发出所需指令的情况下尤其如此。