我写了一个非常简单的Rust函数：
fn iterate(nums: &Box<[i32]>) -> i32 {
let mut total = 0;
let len = nums.len();
for i in 0..len {
if nums[i] > 0 {
total += nums[i];
} else {
total -= nums[i];
}
}
total
}
我已经编写了一个基本的基准测试，它调用了一个有序数组和一个搅乱数组的方法：
fn criterion_benchmark(c: &mut Criterion) {
const SIZE: i32 = 1024 * 1024;
let mut group = c.benchmark_group("Branch Prediction");
// setup benchmarking for an ordered array
let mut ordered_nums: Vec<i32> = vec![];
for i in 0..SIZE {
ordered_nums.push(i - SIZE/2);
}
let ordered_nums = ordered_nums.into_boxed_slice();
group.bench_function("ordered", |b| b.iter(|| iterate(&ordered_nums)));
// setup benchmarking for a shuffled array
let mut shuffled_nums: Vec<i32> = vec![];
for i in 0..SIZE {
shuffled_nums.push(i - SIZE/2);
}
let mut rng = thread_rng();
let mut shuffled_nums = shuffled_nums.into_boxed_slice();
shuffled_nums.shuffle(&mut rng);
group.bench_function("shuffled", |b| b.iter(|| iterate(&shuffled_nums)));
group.finish();
}
criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);
令我惊讶的是，这两个基准测试的运行时几乎完全相同，而Java中类似的基准测试显示出两者之间的明显差异，这可能是由于shuffled情况下的分支预测失败。
我看到有条件移动指令，但如果我otool -tv是可执行文件(我在Mac上运行)，我在iterate方法输出中看不到任何指令。
有人能解释为什么Rust中的有序和无序情况之间没有明显的性能差异吗？
摘要:LLVM能够通过使用cmov指令或SIMD指令的巧妙组合来删除/隐藏分支。
我使用Godbolt查看完整的组件(使用-C opt-level=3)。我将在下面解释大会的重要部分。
它是这样开始的：
mov r9, qword ptr [rdi + 8] ; r9 = nums.len()
test r9, r9 ; if len == 0
je .LBB0_1 ; goto LBB0_1
mov rdx, qword ptr [rdi] ; rdx = base pointer (first element)
cmp r9, 7 ; if len > 7
ja .LBB0_5 ; goto LBB0_5
xor eax, eax ; eax = 0
xor esi, esi ; esi = 0
jmp .LBB0_4 ; goto LBB0_4
.LBB0_1:
xor eax, eax ; return 0
ret
这里，函数区分3种不同的"状态"：
- 切片为空→立即返回0
- 切片长度≤7→使用标准顺序算法(
LBB0_4) - 切片长度>7→使用SIMD算法(
LBB0_5)
所以让我们来看看这两种不同的算法！
标准序列算法
请记住，rsi(esi)和rax(eax)设置为0，并且rdx是指向数据的基指针。
.LBB0_4:
mov ecx, dword ptr [rdx + 4*rsi] ; ecx = nums[rsi]
add rsi, 1 ; rsi += 1
mov edi, ecx ; edi = ecx
neg edi ; edi = -edi
cmovl edi, ecx ; if ecx >= 0 { edi = ecx }
add eax, edi ; eax += edi
cmp r9, rsi ; if rsi != len
jne .LBB0_4 ; goto LBB0_4
ret ; return eax
这是一个在num的所有元素上迭代的简单循环。不过，在循环的主体中有一个小技巧：从原始元素ecx，一个取反的值存储在edi中。通过使用cmovl，如果原始值为正，则edi将被原始值覆盖。这意味着edi将始终变为正(即包含原始元素的绝对值)。然后将其添加到eax(最后返回)。
所以您的if分支被隐藏在cmov指令中。正如您在这个基准测试中看到的，执行cmov指令所需的时间与条件的概率无关。这是一个非常神奇的指令！
SIMD算法
SIMD版本包含相当多的指令，我不会完全粘贴到这里。主循环一次处理16个整数！
movdqu xmm5, xmmword ptr [rdx + 4*rdi]
movdqu xmm3, xmmword ptr [rdx + 4*rdi + 16]
movdqu xmm0, xmmword ptr [rdx + 4*rdi + 32]
movdqu xmm1, xmmword ptr [rdx + 4*rdi + 48]
它们从存储器加载到寄存器xmm0、xmm1、xmm3和xmm5中。这些寄存器中的每一个都包含四个32位值，但为了更容易理解，假设每个寄存器只包含一个值。下面的所有指令都分别对这些SIMD寄存器的每个值进行操作，这样心理模型就可以了！我在下面的解释听起来好像xmm寄存器只包含一个值。
现在主要的技巧是以下指令(处理xmm5)：
movdqa xmm6, xmm5 ; xmm6 = xmm5 (make a copy)
psrad xmm6, 31 ; logical right shift 31 bits (see below)
paddd xmm5, xmm6 ; xmm5 += xmm6
pxor xmm5, xmm6 ; xmm5 ^= xmm6
逻辑右移用符号位的值填充"空高位"(左侧"移入"的高位)。通过移动31，我们最终得到，每个位置只有符号位！所以任何正数都会变成32个零，任何负数都会变为32个一。所以xmm6现在是000...000(如果xmm5是正的)或111...111(如果xmm5是负的)。
接下来，该人工CCD_ 33被添加到CCD_ 34。如果xmm5为正，则xmm6为0，因此添加它不会改变xmm5。然而，如果xmm5是负的，我们将111...111相加，这相当于减去1。最后，我们将xmm5与xmm6进行异或。同样，如果xmm5在一开始是阳性的，我们用000...000异或，这没有效果。如果xmm5一开始是负的，我们用111...111异或，这意味着我们翻转所有的位。因此，对于这两种情况：
- 如果元素是正的，我们什么都不改变(
add和xor没有任何影响) - 如果元素为负数，我们减去1并翻转所有位这是二的补码否定
因此，使用这4条指令，我们计算了xmm5的绝对值！再说一遍，这里没有分支，因为这个小把戏。请记住，xmm5实际上包含4个整数，所以它的速度相当快！
这个绝对值现在被添加到一个累加器中，另外三个包含片中值的xmm寄存器也是如此。(我们不会详细讨论剩下的代码。)
带AVX2的SIMD
如果我们允许LLVM发出AVX2指令(通过-C target-feature=+avx2)，它甚至可以使用pabsd指令，而不是四个"黑客"指令：
vpabsd ymm2, ymmword ptr [rdx + 4*rdi]
它直接从内存加载值，计算绝对值并将其存储在一条指令中的ymm2中！请记住，ymm寄存器是xmm寄存器的两倍大(适合八个32位值)！