Rustとcount_onesとpopcnt

# 概略

* `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演算をします。

```rust:lib.rs
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

```rust:main.rs
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

```rust:src/main.rs
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`を使うことができます。
性能については[次の記事](https://qiita.com/hakua-doublemoon/items/f8d86eb084aed445b815)で報告します。