Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Rustとcount_onesとpopcnt

More than 1 year has passed since last update.

概略

  • count_ones()のアセンブラを見る
  • popcnt命令をrustで使う

ある数においてbit列として1になっているbitがいくつあるか数えたくなったのでいろいろやりました。
だいたい既知のこともだらだら書いています。

環境

項目 内容
CPU Intel i7-8550U (Kaby Bridge R)
OS Windows10 (ただしWSL環境でUbuntu)
Rust 1.34.0 (stableでもできます)

方法

1のbit(立っているbit)の数え方

難しいことを考えないとこの問題は下記のように解くでしょう。

  • 変数のbitサイズ分loopして立っているbitを数える

ただこの方法だと変数のサイズ分の計算が発生するので高速なアルゴリズムとは言えません。
そこで次のようなbit演算をします。

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

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

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になってしまいました。

(詳しいことはわからないので結論を言うと)RUSTFLAGtarget-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を使うことができます。
性能については次の記事で報告します。

hakua-doublemoon
横浜の外周部で組み込み装置のファームウェア開発やってます。RTOSのカーネル・ネットワーク関連からはじまりゴリゴリのHW依存のアプリケーション作ったりQtでGUI作ったり、LabVIEWでの画像処理とかもしてます。Ruby/RailsやRustが好きですがそれは本職とはあんまり関係ない。
https://pawoo.net/web/accounts/586636
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away