一番上位に立っているbitの桁を速めに得る方法 @ Rust

概要

• 一番上位の立っているbitの桁を速く得る方法を模索……というより、それをRustで実践します

前回、popcntを使うことについて書きましたが、もともとは掲題の問題を速く解くことが目的でした。
よって簡単な実装と手順でどの程度速いものが得られるか実験します。

今回取り扱うこと

• 「一番上位の立っているbit」をRustで求める
• bench mark計測する

ところで一番上位の立っているbitとは

一応定義します。
たとえば0b0010_1010みたいな数があったら「右を0番として5番目のbitが立っている」と答えたいということです。なおこれに類する話としてJavaにはhighestOneBit()という関数があるようなので、本稿でも「一番上位の立っているbit」のことをhighestOneBitと呼称します。

実施環境

項目	内容
CPU	Intel i7-8550U (Kaby Bridge R)
OS	Windows10 (ただしWSL環境でUbuntu)
Rust	1.37.0 (今回はnightlyです)

実装

戦略

highestOneBitを速く得る方法（あるいは他のbit演算を速くする方法）は多くの取り組みがあり、ここではその神髄を実践することは目的としません。下記のような簡単な戦略に基づいた実装のみ行います。

1. 1になっている（立っている）最上位のbit以下すべてのbitを立てる
2. 立っているbitを数える

こうすると２で得られる数がhighestOneBitの桁に一致します。
そして結論を先取りしますが、ここで２をやるのにpopcnt命令が使えるとだいぶ速くなります。

比較実装

次のような２つの関数を用意して比較します。

• loopで0から64までbitを探索してhighestOneBitの桁を見つける（fn1）
• bitシフトしながらhighestOneBit以下をすべて立てたのち、立っているbitを数えてhighestOneBitの桁を求める(fn2)

また前回書いたようにコンパイルオプションでpopcntが使えたり使えなかったりするので、popcntを使わないfn2をfn2-1、つかうそれをfn2-2として比較します。

ソースコード

以下のGistに示します。（ソースコード上のMSBはhighestOneBitのことです……）
https://gist.github.com/hakua-doublemoon/f836ee26e77526900954a1d6677697bf

benchの使用について

本筋の実装に関しては言った通りのシンプルなものですが、ベンチマーク計測のためのbenchの利用について少し書かせてください。
benchに関しては次に説明はあります。
https://doc.rust-jp.rs/the-rust-programming-language-ja/1.6/book/benchmark-tests.html
基本的な使い方は下記のようになります。

• test feature gate を使う（unstableだからだそうです）
• test crateをインポートする（デフォルトだとモジュール名がtestsなのでややこしい）
• nightlyでbuildする

nightlyを使ったことがないのなら、これの導入に関しては下記を参考にしやすいです。
https://qiita.com/chikoski/items/b6461367e8c3875bb235
例えば下記のようにbuildします

rustup run nightly cargo bench

なお#[cfg(test)]は無くても動くみたいです。サンプルに書いてあるのでそのままつけてますが……。

先に示したRustのベンチマークテストのページにも書いてありますが、Rustのベンチマークテストでは最適化に気を付ける必要があります。処理時間の短い関数ではnano secondで１桁とかわけのわからない結果になるので、次のように1000回とか実行したくなりますが……

(s..e).fold(0, |_, _| bit_test::msb_digit_get(0x8000) )

最適化により関数が同じ答えしか返さないことが見破られるのか、異常に処理時間が短くなったりします。
これへの対策としては、ドキュメントに書いてあるようにまずセミコロン;をつけないことですが、もうひとつ、foldのaccumulatorとelementを両方使わなければならなかった、というのが私の結論です。

b.iter(|| { (s..e).fold(0, |a,x| bit_test::msb_digit_get(x|a) ) })

black_boxをうまく使えば違う展開になるかもですが、ひとまずはこんな感じでした。
なおこのor演算により最速パターンの4%ほどのオーバーヘッドが発生するようです。

測定

highestOneBitが9:0の範囲、31、63の３つのパターンで計測します。すなわち計算範囲を1～1001、0xF0000000-1000～0xF0000000、0xF000000000000000-1000～0xF000000000000000にとって計算してみます。
比較対象はすでに述べたfn1, fn2-1, fn2-2とします。それぞれ1000回ずつ計算しているので、１回あたりは1000分の1になります。下表における単位はnsです。

highedtOneBit	9:0	31	63
fn1	7,296	18,246	35,514
fn2-1	16,645	17,287	17,436
fn2-2	10,201	10,443	9,855

結果をまとめると下記のように言えるでしょう。

• 0から64までloopするfn1はhighestOneBitが上に行くほど時間がかかる
  • loopしないfn2-1/2はhighestOneBitの位置にかかわらず計算時間が一定
    （値が変動していますが単にCPUの調子の問題だと思います）
• popcnt命令が使えるfn2-2はやっぱり速い。highestOneBitが下でもfn1より少し遅いぐらいで済む
  • popcntを使わないfn2-1はそうでもないので、例えばhighestOneBitが32より大きいことが少ないと想定される状況では採用されないかもしれない。
    • まあ二分探索とか他のアルゴリズムならCPUに依存しなくてもなんとかなるかもしれませんが

まとめ

popcnt命令を組み込ませることで、単純な実装でもそこそこの速度が得られることがわかりました。またRustのbenchやnightlyの使い方もなんとなくわかりました。

CPUに依存する実装は移植性が低いわけですが、CPUに依存しない実装でも余人に理解されないアルゴリズムによる実装なら、やはり再利用性が低いのではと私は思います。なので私はこのようなCPUに頼るやりかたも選択肢の１つに入れられると思っています。