Qua*_*Cat 33 c++ algorithm bit-manipulation micro-optimization rust
对于min(ctz(x), ctz(y))，我们可以使用ctz(x | y)来获得更好的性能。但是关于max(ctz(x), ctz(y))？
ctz表示“计数尾随零”。
C++ 版本（编译器资源管理器）
#include <algorithm>
#include <bit>
#include <cstdint>
int32_t test2(uint64_t x, uint64_t y) {
return std::max(std::countr_zero(x), std::countr_zero(y));
}
Rust 版本（编译器资源管理器）
pub fn test2(x: u64, y: u64) -> u32 {
x.trailing_zeros().max(y.trailing_zeros())
}
Sve*_*ach 24
我认为没有什么比天真的最大化最大化方法更好的了。一种尝试是使用身份
x + y = min(x, y) + max(x, y)
因此
max(ctz(x), ctz(y)) = ctz(x) + ctz(y) - min(ctz(x), ctz(y))
这样，我们可以将 max 函数简化为我们已经优化的 min 函数，尽管需要一些额外的操作。
以下是不同方法的一些 Rust 实现：
pub fn naive(x: u64, y: u64) -> u32 {
x.trailing_zeros().max(y.trailing_zeros())
}
pub fn sum_minus_min(x: u64, y: u64) -> u32 {
x.trailing_zeros() + y.trailing_zeros() - (x | y).trailing_zeros()
}
pub fn nielsen(x: u64, y: u64) -> u32 {
let x_lsb = x & x.wrapping_neg();
let y_lsb = y & y.wrapping_neg();
let xy_lsb = x_lsb | y_lsb;
let lsb = xy_lsb & xy_lsb.wrapping_neg();
let xy_max_lsb = if xy_lsb == lsb { lsb } else { xy_lsb ^ lsb };
xy_max_lsb.trailing_zeros()
}
pub fn timmermans(x: u64, y: u64) -> u32 {
let loxs = !x & x.wrapping_sub(1);
let loys = !y & y.wrapping_sub(1);
return (loxs | loys).count_ones();
}
pub fn kealey(x: u64, y: u64) -> u32 {
((x | x.wrapping_neg()) & (y | y.wrapping_neg())).trailing_zeros()
}
我的机器上的结果：
ctz_max/naive time: [279.09 ns 279.55 ns 280.10 ns]
ctz_max/sum_minus_min time: [738.91 ns 742.87 ns 748.61 ns]
ctz_max/nielsen time: [935.35 ns 937.63 ns 940.40 ns]
ctz_max/timmermans time: [803.39 ns 806.98 ns 810.76 ns]
ctz_max/kealey time: [295.03 ns 295.93 ns 297.03 ns]
这个简单的实现击败了所有其他实现。唯一可以与天真的实现竞争的是 Martin Kealey 提出的方法。请注意，由于测试工具的一些开销，实现之间的实际因素可能甚至高于计时所示的值。
很明显，您只有几个 CPU 指令可以用来优化简单的实现，所以我认为您无能为力。作为参考，以下是当这些实现在现代 x86_64 处理器上编译为独立函数时 Rust 编译器发出的程序集：
x + y = min(x, y) + max(x, y)
在我运行的基准测试中，函数被内联，循环部分展开，一些子表达式从内部循环中拉出，因此程序集看起来比上面的干净得多。
为了进行测试，我使用了 Criterion。这是附加代码：
use criterion::{black_box, criterion_group, criterion_main, Criterion};
const NUMBERS: [u64; 32] = [
...
];
fn bench<F>(func: F)
where
F: Fn(u64, u64) -> u32,
{
for x in NUMBERS {
for y in NUMBERS {
black_box(func(x, y));
}
}
}
fn compare(c: &mut Criterion) {
let mut group = c.benchmark_group("ctz_max");
group.bench_function("naive", |b| b.iter(|| bench(naive)));
group.bench_function("sum_minus_min", |b| b.iter(|| bench(sum_minus_min)));
group.bench_function("nielsen", |b| b.iter(|| bench(nielsen)));
group.bench_function("timmermans", |b| b.iter(|| bench(timmermans)));
group.bench_function("kealey", |b| b.iter(|| bench(kealey)));
}
criterion_group!(benches, compare);
criterion_main!(benches);
NUMBERS使用此 Python 代码生成，目的是使函数的分支预测min()尽可能困难：
[
random.randrange(2 ** 32) * 2 ** random.randrange(32)
for dummy in range(32)
]
我正在使用运行基准测试
RUSTFLAGS='-C target-cpu=native -C opt-level=3' cargo bench
在第 8 代 i7 处理器 (Whiskey Lake) 上。
Mar*_*ley 18
这些是等效的：
\nmax(ctz(a),ctz(b))ctz((a|-a)&(b|-b))ctz(a)+ctz(b)-ctz(a|b)数学恒等式ctz(a)+ctz(b)-ctz(a|b)需要 6 个 CPU 指令，在 3 路超标量 CPU 上可并行化为 3 个步骤：
位混合ctz((a|-a)&(b|-b))需要 6 个 CPU 指令，在 2 路超标量 CPU 上可并行化为 4 个步骤：
na\xc3\xafvemax(ctz(a),ctz(b))需要 5 个 CPU 指令，在 2 路超标量 CPU 上可并行化为 4 个步骤：
...但请注意，分支指令可能非常昂贵。
\n如果您的 CPU 有条件加载/移动指令，则这会减少到 4 个 CPU 指令，需要 3 个超标量步骤。
\n如果您的 CPU 有一条max指令（例如 SSE4），则这会减少到 3 个 CPU 指令，需要 2 个超标量步骤。
尽管如此，超标量操作的机会取决于您试图相互对抗的指令。通常，您可以通过并行放置不同的指令来获得最大收益，因为它们使用 CPU 的不同部分（同时）。通常，“加”和“按位或”单元会多于“ctz”单元，因此执行多个 ctz 指令实际上可能是限制因素，特别是对于“数学恒等式”版本。
\n如果“比较和分支”成本太高，您可以在 4 个 CPU 指令中创建一个非分支“max”。假设A和B是正整数：
\nMat*_*ans 11
你可以这样做：
#include <algorithm>
#include <bit>
#include <cstdint>
int32_t maxr_zero(uint64_t x, uint64_t y) {
uint64_t loxs = ~x & (x-1); // low zeros of x
uint64_t loys = ~y & (y-1); // low zeros of y
return std::countr_zero((loxs|loys)+1);
}
| 归档时间： |
|
| 查看次数： |
3184 次 |
| 最近记录： |