为什么我不使用get_unchecked()来提高性能？
ant*_*oyo 9 optimization performance assembly rust
我尝试使用get_unchecked()而不是[]索引运算符来获得s()我的des箱子功能的性能提升.
但是,即使在我的基准测试中将[](或get_unchecked())函数调用了48亿次,它也不会导致可见的性能提升.我原本认为,调用get_unchecked()48亿次而不是[]将使我的英特尔酷睿2双核2.4 GHz处理器的时间缩短2秒.
我做了这个小基准测试,有一个小代码向您展示:
#![feature(test)]
extern crate test;
fn main() {
}
pub fn s(box_id: usize, block: u64) -> u64 {
const TABLES: [[[u64; 16]; 4]; 8] =
[[[ 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7]
, [ 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8]
, [ 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0]
, [ 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]
],
[ [ 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10]
, [ 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5]
, [ 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15]
, [ 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]
],
[ [ 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8]
, [ 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1]
, [ 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7]
, [ 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]
],
[ [ 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15]
, [ 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9]
, [ 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4]
, [ 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]
],
[ [ 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9]
, [ 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6]
, [ 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14]
, [ 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]
],
[ [ 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11]
, [ 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8]
, [ 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6]
, [ 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]
],
[ [ 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1]
, [ 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6]
, [ 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2]
, [ 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]
],
[ [ 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7]
, [ 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2]
, [ 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8]
, [ 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]
]];
let i = ((block & 0x20) >> 4 | (block & 1)) as usize;
let j = ((block & 0x1E) >> 1) as usize;
unsafe { *TABLES.get_unchecked(box_id).get_unchecked(i).get_unchecked(j) }
//TABLES[box_id][i][j]
}
#[cfg(test)]
mod bench {
use test::{Bencher, black_box};
use super::s;
#[bench]
fn bench_s(bencher: &mut Bencher) {
bencher.iter(|| {
let box_id = black_box(7);
(0 .. 40_000_000).fold(0, |acc, block| acc + s(box_id, block))
});
}
}
我第一次运行这个基准测试时[],花费的时间比版本少get_unchecked()(尽管get_unchecked()版本看起来平均速度稍微快一点).我不确定它是否真的反映了我的真实基准(包括加密大文件),但它提供了一个想法.
我检查了程序集,以确保编译器没有优化掉绑定检查.
这是以下版本get_unchecked():
0000000000009360 <_ZN3des7s_table17hbabdd9dee72331a5E>:
9360: 48 89 f0 mov %rsi,%rax
9363: 48 c1 e8 04 shr $0x4,%rax
9367: 83 e0 02 and $0x2,%eax
936a: 89 f1 mov %esi,%ecx
936c: 83 e1 01 and $0x1,%ecx
936f: 48 09 c1 or %rax,%rcx
9372: 48 c1 e7 09 shl $0x9,%rdi
9376: 48 8d 05 93 57 04 00 lea 0x45793(%rip),%rax # 4eb10 <ref10404>
937d: 48 01 f8 add %rdi,%rax
9380: 48 c1 e1 07 shl $0x7,%rcx
9384: 48 01 c1 add %rax,%rcx
9387: 83 e6 1e and $0x1e,%esi
938a: 48 8b 04 b1 mov (%rcx,%rsi,4),%rax
938e: c3 retq
938f: 90 nop
以下是版本[]:
0000000000009390 <_ZN3des7s_table17hbabdd9dee72331a5E>:
9390: 50 push %rax
9391: 48 89 f8 mov %rdi,%rax
9394: 48 83 f8 07 cmp $0x7,%rax
9398: 77 30 ja 93ca <_ZN3des7s_table17hbabdd9dee72331a5E+0x3a>
939a: 48 89 f1 mov %rsi,%rcx
939d: 48 c1 e9 04 shr $0x4,%rcx
93a1: 83 e1 02 and $0x2,%ecx
93a4: 89 f2 mov %esi,%edx
93a6: 83 e2 01 and $0x1,%edx
93a9: 48 09 ca or %rcx,%rdx
93ac: 48 c1 e0 09 shl $0x9,%rax
93b0: 48 8d 0d 99 57 04 00 lea 0x45799(%rip),%rcx # 4eb50 <const10401>
93b7: 48 01 c1 add %rax,%rcx
93ba: 48 c1 e2 07 shl $0x7,%rdx
93be: 48 01 ca add %rcx,%rdx
93c1: 83 e6 1e and $0x1e,%esi
93c4: 48 8b 04 b2 mov (%rdx,%rsi,4),%rax
93c8: 59 pop %rcx
93c9: c3 retq
93ca: 48 8d 3d b7 a3 25 00 lea 0x25a3b7(%rip),%rdi # 263788 <panic_bounds_check_loc10404>
93d1: ba 08 00 00 00 mov $0x8,%edx
93d6: 48 89 c6 mov %rax,%rsi
93d9: e8 82 25 04 00 callq 4b960 <_ZN4core9panicking18panic_bounds_check17hb2d969c3cc11ed08E>
93de: 66 90 xchg %ax,%ax
我们可以看到get_unchecked()版本较小,带有[]检查边界的版本.
两个版本都在发布模式下编译.
为什么get_unchecked()版本不比这快？我认为这应该是至少几秒钟比更快[]的版本时,get_unchecked()/ []被称为4.8十亿倍.
编辑:我使用了配置代码valgrind.
[]对于具有数组索引的行,版本显示成本为10,而版本get_unchecked()显示成本小于1(参见下图).但是,该功能的成本(见图像左侧)保持不变.这很奇怪.有人有解释吗？
版本用get_unchecked().
版本用 []
我还没有学到太多 Rust，但我想我仍然可以回答其中的性能部分。
首先，您确定您的基准测试实际上正在运行该函数的独立版本吗？它可能会将函数内联到调用站点中，其中box_id是编译时常量。除了消除次要的 call/ret 开销之外，表索引计算 asm 也将得到显着简化。此外，如果在编译时知道没有超出边界检查，则可以省略边界检查。
如果有人展示如何修改 OP 的示例以在 Godbolt 编译器资源管理器上编译为实际的 asm ，我就可以看一下并说更多。将其按原样放在 godbolt 上会得到编译为空 asm 输出的内容。我可能会决定学习足够的 Rust 来自己完成这项工作，但可能不会很快。
看一下该函数的独立版本：
检查版本中的额外指令只是前 4 条：
9390: 50 push %rax # align the stack in case we make a function call (wasted work for the common case)
9391: 48 89 f8 mov %rdi,%rax # compiler is dumb, could have checked the value in %rdi
9394: 48 83 f8 07 cmp $0x7,%rax
9398: 77 30 ja 93ca <_ZN3des7s_table17hbabdd9dee72331a5E+0x3a>
最后pop %rcx将 8 添加到 %rsp。
所以函数开始时有 4 个 uop。（Core2Duo 无法在 64 位模式下进行宏融合。不过，Core2Duo 可以在 32 位代码中进行宏融合 cmp/ja。（请参阅Agner Fog 的 microarch pdf）。如果编译器更聪明，则只需额外 2 个通过函数 (cmp/ja) 的快速路径上的指令 / uops 总数，另一个函数调用的堆栈对齐仅在实际进行调用的分支中完成。
您可能认为将这 4 个微指令作为函数的第一组发出会是一个问题，因为它会延迟 CPU 获取关键路径上的指令。但事实并非如此，因为显然您的代码在前端并没有遇到瓶颈。（您没有显示循环调用此代码的汇编语言）。因此，指令先于实际执行的指令发送到无序核心。
也许当函数输入在 %rdi 中准备好时，调度程序已经有关键路径指令在等待。如果基准测试实际上运行的是独立版本，则函数开头的 4 条额外指令实际上不会延迟关键路径。因此，推测关键路径的瓶颈在于延迟，而不是吞吐量。（一次调用的输出是否构成下一次查找的索引？如果是这样，这将阻止针对不同输入同时执行该函数的多个调用。L1 加载使用延迟在 Core 2 上为 3 个周期（根据阿格纳·福格 (Agner Fog) 的微架构 pdf )。
不过，根据输入计算表索引的指令中有相当多的指令级并行性。有几个mov指令可以制作副本，然后指令对副本和原始文件执行不同的操作。并且这两个参数已经是分开的。我认为在输入准备好和表索引准备好之间，很多时候可能有足够的并行性来并行运行 3 个指令。因此，如果在有另一个输入之前执行必须等待 3 个周期进行表查找，那么就需要运行额外的微指令了。（不过，调度程序在先就绪的基础上运行 uops，而不是关键路径优先，因此您可能会期望它们有时会因资源冲突而延长关键路径（从关键路径窃取执行端口）。
TL:DR 如果一个调用的输出是下一个调用的输入，那么 L1 加载使用延迟仍然很容易成为瓶颈，而不是 uop 吞吐量。否则，一定存在其他瓶颈，可以为 5 个额外的 uops 提供运行时间，而不会延迟“实际工作”。否则，该检查将在实际运行的代码中被优化掉。