我已经编写了这个非常简单的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中类似的基准测试显示了两者之间的明显差异，这可能是由于在改组情况下分支预测失败所致。
我已经提到过有条件的移动指令，但是如果我对可执行文件进行
otool -tv(我在Mac上运行)，则在iterate方法输出中看不到任何内容。任何人都可以阐明为什么在Rust中有序和无序案例之间没有明显的性能差异吗？
最佳答案
摘要:LLVM能够通过使用cmov指令或SIMD指令的真正巧妙组合来删除/隐藏分支。
我使用Godbolt来view the full assembly(带有-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个不同的“状态”:
LBB0_4)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指令中。如您在this benchmark中所见，执行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为负)。接下来，将此人造
xmm6添加到xmm5中。如果xmm5为正，则xmm6为0，因此添加它不会更改xmm5。但是，如果xmm5为负，则我们添加111...111，它等于减1。最后，我们将xmm5与xmm6异或。同样，如果xmm5在开始时为正，则我们将000...000与没有效果的异或。如果xmm5在开始时为负，则我们对111...111进行异或，这意味着我们将所有位翻转。因此，对于两种情况:add和xor没有任何作用)因此，使用这4条指令，我们计算出
xmm5的绝对值!同样，由于这种摆弄技巧，这里没有分支。请记住，xmm5实际上包含4个整数，因此速度非常快!现在，将这个绝对值添加到累加器中，对其他三个包含切片值的
xmm寄存器进行同样的操作。 (我们不会详细讨论其余的代码。)SIMD与AVX2
如果我们允许LLVM发出AVX2指令(通过
-C target-feature=+avx2)，它甚至可以使用pabsd指令代替四个“hacky”指令:vpabsd ymm2, ymmword ptr [rdx + 4*rdi]
它直接从内存中加载值，计算绝对值，然后在一条指令中将其存储在
ymm2中!请记住，ymm寄存器的大小是xmm寄存器的两倍(可容纳8个32位值)!