概略
-
count_ones()のアセンブラを見る -
popcnt命令をrustで使う
ある数においてbit列として1になっているbitがいくつあるか数えたくなったのでいろいろやりました。
だいたい既知のこともだらだら書いています。
環境
| 項目 | 内容 |
|---|---|
| CPU | Intel i7-8550U (Kaby Bridge R) |
| OS | Windows10 (ただしWSL環境でUbuntu) |
| Rust | 1.34.0 (stableでもできます) |
方法
１のbit（立っているbit）の数え方
難しいことを考えないとこの問題は下記のように解くでしょう。
- 変数のbitサイズ分loopして立っているbitを数える
ただこの方法だと変数のサイズ分の計算が発生するので高速なアルゴリズムとは言えません。
そこで次のようなbit演算をします。
pub fn pop_count(v :u64) -> u64
{
let mut count = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
count = (count & 0x3333333333333333) + ((count >> 2) & 0x3333333333333333);
count = (count & 0x0f0f0f0f0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f0f0f0f0f);
count = (count & 0x00ff00ff00ff00ff) + ((count >> 8) & 0x00ff00ff00ff00ff);
count = (count & 0x0000ffff0000ffff) + ((count >> 16) & 0x0000ffff0000ffff);
/*count=*/ (count & 0x00000000ffffffff) + ((count >> 32) & 0x00000000ffffffff)
}
参考: http://www.nminoru.jp/~nminoru/programming/bitcount.html
こうすると例えば64bitの数に対して64回loopするよりは早く立っているbitの数がわかるわけです。
しかしCPUの素質を活かすなら、Intel CPUにはpopcnt命令があります。
一方で上の関数みたいのをいちいち書かなくても、よく知られたアルゴリズムだからなんとかならないのか思えば、実はrustにはcount_ones()という関数もあります。
count_ones()
というわけでまずcount_ones()を使って、中身も見てみます。
coune_ones()の説明は下記にあります。
https://doc.rust-lang.org/std/primitive.u32.html#method.count_ones
fn main() {
let v = (10 as u64).count_ones();
println!("{}", v);
}
アセンブラを見るにはcargoで何とかできるみたいですが、うまく出てこないのでobjdumpで見ます。
objdump -dr target/debug/<パッケージ名> の抜粋
0000000000003ed0 <_ZN11test_popcnt4main17h3c22cc7fb67e6cdaE>:
3ed0: 48 83 ec 78 sub $0x78,%rsp
3ed4: bf 0a 00 00 00 mov $0xa,%edi
3ed9: e8 62 ff ff ff callq 3e40 <_ZN4core3num21_$LT$impl$u20$u64$GT$10count_ones17h6852c92f475118a2E>
0000000000003e40 <_ZN4core3num21_$LT$impl$u20$u64$GT$10count_ones17h6852c92f475118a2E>:
3e40: 48 83 ec 18 sub $0x18,%rsp
3e44: 48 89 7c 24 08 mov %rdi,0x8(%rsp)
3e49: 48 8b 7c 24 08 mov 0x8(%rsp),%rdi
3e4e: 48 89 f8 mov %rdi,%rax
3e51: 48 d1 e8 shr %rax
3e54: 48 b9 55 55 55 55 55 movabs $0x5555555555555555,%rcx
3e5b: 55 55 55
3e5e: 48 21 c8 and %rcx,%rax
3e61: 48 29 c7 sub %rax,%rdi
3e64: 48 b8 33 33 33 33 33 movabs $0x3333333333333333,%rax
:
:
という感じで、10（0xa）をdiレジスタに突っ込んでcxレジスタにどこかで見たことのあるビット列を入れながらどこかで見たことのある計算を繰り返していることがわかりました。
popcntを使う
「rust popcnt」と検索してもいまいちな結果しかでてきませんが、実は公式サイトでpopcntを検索すると一発で出てきます。
https://doc.rust-lang.org/1.27.2/core/arch/x86_64/fn._popcnt64.html
fn main() {
let v :i32;
unsafe {
v = core::arch::x86_64::_popcnt64(10 as i64) as i32;
}
println!("{}", v);
}
これでbuildします。
0000000000003f10 <_ZN11test_popcnt4main17h3c22cc7fb67e6cdaE>:
3f10: 48 83 ec 78 sub $0x78,%rsp
3f14: bf 0a 00 00 00 mov $0xa,%edi
3f19: e8 d2 fe ff ff callq 3df0 <_ZN4core9core_arch6x86_643abm9_popcnt6417h58c2a7e718c29531E>
0000000000003df0 <_ZN4core9core_arch6x86_643abm9_popcnt6417h58c2a7e718c29531E>:
3df0: 48 83 ec 18 sub $0x18,%rsp
3df4: 48 89 7c 24 10 mov %rdi,0x10(%rsp)
3df9: 48 8b 7c 24 10 mov 0x10(%rsp),%rdi
3dfe: e8 5d 00 00 00 callq 3e60 <_ZN4core3num21_$LT$impl$u20$i64$GT$10count_ones17h0b28e2d260d21fcaE>
0000000000003e60 <_ZN4core3num21_$LT$impl$u20$i64$GT$10count_ones17h0b28e2d260d21fcaE>:
3e60: 48 83 ec 18 sub $0x18,%rsp
3e64: 48 89 7c 24 10 mov %rdi,0x10(%rsp)
3e69: 48 8b 7c 24 10 mov 0x10(%rsp),%rdi
3e6e: e8 0d 00 00 00 callq 3e80 <_ZN4core3num21_$LT$impl$u20$u64$GT$10count_ones17h6852c92f475118a2E>
0000000000003e80 <_ZN4core3num21_$LT$impl$u20$u64$GT$10count_ones17h6852c92f475118a2E>:
3e80: 48 83 ec 18 sub $0x18,%rsp
3e84: 48 89 7c 24 08 mov %rdi,0x8(%rsp)
3e89: 48 8b 7c 24 08 mov 0x8(%rsp),%rdi
3e8e: 48 89 f8 mov %rdi,%rax
3e91: 48 d1 e8 shr %rax
3e94: 48 b9 55 55 55 55 55 movabs $0x5555555555555555,%rcx
:
あれ？ count_onesになってしまいました。
（詳しいことはわからないので結論を言うと）RUSTFLAGでtarget-featureを使う必要があります。おそらくpopcntはSSEの命令であり、RustはnightlyでもデフォルトではCPUに依存する命令を使わないようです。
まあEqualL2さんのおっしゃる通り、count_onesの中身がstd::intrinsicsのpopcntを使っていて、LLVMが次に述べるCPUへの最適化を行うときにpopcntなどSIMDの命令を引っ張り出すのかなと、調べて思いました。
target-feature × count_ones
target-featureは下記に説明があります。
https://rust-lang-nursery.github.io/packed_simd/perf-guide/target-feature/rustflags.html#target-feature
というわけでコードをはじめの状態に戻して、次のようにbuildします。
RUSTFLAGS='-C target-feature+=popcnt' cargo build
なお下記のようにtarget-cpuを使ってもできます。（御指摘ありがとうございます）
RUSTFLAGS='-C target-cpu=native' cargo build
すると次のようなアセンブラを得ます。
0000000000003ed0 <_ZN11test_popcnt4main17h589d6e7e9c1fe881E>:
3ed0: 48 83 ec 78 sub $0x78,%rsp
3ed4: bf 0a 00 00 00 mov $0xa,%edi
3ed9: e8 62 fe ff ff callq 3d40 <_ZN4core3num21_$LT$impl$u20$u64$GT$10count_ones17hd9b4bf1f8b599306E>
0000000000003d40 <_ZN4core3num21_$LT$impl$u20$u64$GT$10count_ones17hd9b4bf1f8b599306E>:
3d40: 48 83 ec 18 sub $0x18,%rsp
3d44: 48 89 7c 24 08 mov %rdi,0x8(%rsp)
3d49: 48 8b 7c 24 08 mov 0x8(%rsp),%rdi
3d4e: f3 48 0f b8 ff popcnt %rdi,%rdi
3d53: 48 89 7c 24 10 mov %rdi,0x10(%rsp)
3d58: 48 8b 7c 24 10 mov 0x10(%rsp),%rdi
3d5d: 48 89 3c 24 mov %rdi,(%rsp)
3d61: 48 8b 04 24 mov (%rsp),%rax
3d65: 89 c1 mov %eax,%ecx
3d67: 89 c8 mov %ecx,%eax
3d69: 48 83 c4 18 add $0x18,%rsp
3d6d: c3 retq
ついにpopcntがお出ましになりました！
まとめ
Rustの標準で使えるcount_ones()関数でもRUSTFLAGS='-C target-cpu=nativeでコンパイルすることでpopcntを使うことができます。
性能については次の記事で報告します。