はじめに

この記事は，Rust で整数 n が整数 m で割り切れるかどうかを判定する方法について調べたものです。
「割り切れるかどうかの判定」をこの記事では「整除判定」と呼ぶことにします。

二つの方法を提示し，どちらが高速かをベンチマークテストで確かめます。

筆者は Rust のド素人です。私くらいの初心者でも理解し追体験できるように書きたいと思います。

Rust 1.32.0 で確認しています。もちろんエディション 2018 です。

動機

競プロ参戦記 #33 Match Matching | ABC 118 - Qiita
という記事を見ていたら，整除判定課題が出てきて，

n % m == 0

的なコードが書かれていました。まあ，そう書きますよね，ふつう。

でも「もしかしたら整除判定のための専用関数が用意されているのでは？」と思いました。
もし専用の関数が存在するのなら，そちらのほうが速いと予想しました。
だって，割り切るかどうかだけ知りたいのに，剰余を求めて 0 と比較する必要ないですもんね。
とはいえ，多倍長整数でもない，例えば i32 の範囲で差がつくものか？という疑問もありました。
ベンチマークテストで確認しましょう！

整除判定メソッド

適当にウェブ検索すると，num-integer というクレートに is_multiple_of という，そのものズバリのメソッドが見つかりました。

まず

Cargo.toml（抜粋）

[dependencies]
num-integer = "0.1"

して，

main.rs

use num_integer::Integer;

fn main() {
    assert_eq!(12.is_multiple_of(&4), true);
    assert_eq!(10.is_multiple_of(&3), false);
}

みたいにして使えました。

「num-integer」のようにクレート名にハイフンが入っている場合，そのままでは識別名として不適なので，ハイフンをアンダースコアに変えて記述するみたいです。

引数は整数への参照の形で渡すのですね。これは多倍長整数など，コピーにコストがかかる整数に配慮した仕様なのでしょうか？

ベンチマーク

方針

変数 i, j の値をそれぞれ 1 から 1000 まで変えて，i が j で割り切れるかどうかを，

// (1)
i % j == 0

// (2)
i.is_multiple_of(&j)

でそれぞれ判定するコードを書いてみたいと思います。

ベンチマークのための main.rs

main.rs を以下のように変えます。

main.rs

#![feature(test)]
extern crate test;

fn main() {
}

#[cfg(test)]
mod tests {
    use num_integer::Integer;
    use test::Bencher;

    #[bench]
    fn bench_remainder_is_zero(b: &mut Bencher) {
        b.iter(||
            for i in 1..10000 {
                let i = test::black_box(i);
                for j in 1..10000 {
                    i % j == 0;
                }
            }
        );
    }

    #[bench]
    fn bench_is_multiple_of(b: &mut Bencher) {
        b.iter(||
            for i in 1..1000 {
                let i = test::black_box(i);
                for j in 1..1000 {
                    i.is_multiple_of(&j);
                }
            }
        );
    }
}

訂正

コメントでご指摘いただいたように，このコードにはとんでもない間違いがありました。
比較した二つの処理で，for の繰り返し範囲が 1 桁違っています！
この件は後述します。

コードの説明

冒頭の

#![feature(test)]

は「test フィーチャゲート」とかいうものに関係あるらしいですが，何のことかさっぱり分かりません。
ウォーターゲート事件やそれに倣って名付けられたロシアゲート事件なら知っていますが。

次の行の

extern crate test;

はベンチマークテストをやるために test というクレートを使う宣言ですよね。
このクレートは Cargo.toml の [dependencies] に書く必要は無いようです。
エディション 2018 なので extern crate ... は不要かと思ったのですが，削除すると

error[E0432]: unresolved import `test`

とエラーが出たので，省けませんでした。

また，

#[cfg(test)]

も何のことかさっぱり分かりませんが，テスト用モジュールの前にこう書くみたいです。たぶん，こうしておくと，そのモジュールはテストのときしかコンパイルされないのでしょう。

さてテスト用モジュール

#[cfg(test)]
mod tests {

}

の中身を見ます。

まず，is_multiple_of が使いたいので，

use num_integer::Integer;

を書きますね。モジュールの外ではダメで，中に書く必要があるようです。

いよいよベンチマークのコードを書きます。以下のような形式で関数を定義すればよいようです。

#[bench]
fn bench_XXXX(b: &mut Bencher) {
    b.iter( クロージャー );
}

関数名は慣習的に bench_ で始めるのでしょうかね。

「クロージャー」のところに，やらせたい処理をクロージャーの形式で記述します。

ベンチマークは一般に，やらせたい処理を多数回実行して，その実行時間を計測し，実行回数で割り算します。
しかし，多数回の実行は自動的にやってくれるので，クロージャーには 1 回ぶんの処理だけを書きます。

クロージャーに引数は要らないので，引数のところは単に || と書きます。

剰余を 0 と比較するやり方のほうを例にとると，クロージャーは

||
for i in 1..10000 {
    let i = test::black_box(i);
    for j in 1..10000 {
        i % j == 0;
    }
}

となっています。
ここで，非常に気になるのが

let i = test::black_box(i);

の行です。変数 i をシャドーイングしていますが，test::black_box( ) は何をやっているのでしょうか？

この行をまるまる削除すると，すごく素直なコードになりますが，ベンチマークを実行すると，実行時間がゼロになってしまいます。
どうやら，コンパイラーによる最適化が働いて，「何もしない」コードが生成されてしまうようです（たぶん）。

test::black_box( ) はコンパイラーの目をくらまして最適化の邪魔をするもののようです。

追記

あとで分かりましたが，test::black_box( ) は i だけでなく j についてもやるべきのようです。
一方だけやってればベンチマークテストを無意味化する最適化が一切起こらないのかと勝手に勘違いしてました。

ベンチマーク実行

いよいよ実行します。

ベンチマークを実行するには，まだナイトリーのコンパイラーが必要なようです。

もしまだインストールしていないようなら

rustup install nightly

でインストールしてください。

インストールされていれば，

cargo +nightly bench

でベンチマークが実行されます。
cargo コマンドは，ベンチマークに限らず，build や run などでも，+nightly を付ければナイトリー版で，+beta を付ければベータ版で実行してくれます。

実行するとき，i % j == 0 に関して，

unused comparison that must be used

と警告が出ましたが，計測自体は正常にできているぽいので，無視することにしました。

結果

こんなふうに結果が出ました。

test tests::bench_is_multiple_of    ... bench:         391 ns/iter (+/- 71)
test tests::bench_remainder_is_zero ... bench:       3,742 ns/iter (+/- 189)

~~思った以上に違いが出ました。専用メソッドを使ったほうが 10 倍ちかく速いですね。~~

きちんとした比較のためには，数の範囲を変えてみたり，割り切れる場合／割り切れない場合をそれぞれ独立に計測したり，といったことが必要だと思います。
~~しかし，大雑把な話としては，「整除判定は is_multiple_of を使うのが速い」と言えるのだろうと思います。~~

訂正

「コード」のところで書いたように，正しい比較になっていませんでした。

for の繰り返し範囲を同じにしたところ，有意な差は無くなりました。つまり，どっちで書いても同じというのが正しい結論です。

苦労話

初心者ゆえに苦労した点を記録しておきます。

どうやって is_multiple_of が使えるように？

is_multiple_of メソッド自体は，ウェブ検索ですぐに下記のページが引っかかったので見つけることができました。

しかし，これを見ても「num-integer クレートをインポートしなければならない」ことや「何を use すればよいのか」が分からず，難渋しました。

ベンチマークテストのやり方

初心者が Rust の基本的なことをウェブで学ぶのに，『The Rust Programming Language』が必須ですよね。

有志による和訳は

の二つが出ているようです。（文書の正式なバージョン表記は知りません。括弧内はテキトー）

1.6 のほうはかなり古い Rust に基づいて書かれているので，今なら 2 のほうを読むべきです。

しかし，1.6 にあった，「ベンチマークテスト」の節を含む「Nightly Rust」の章が，2 ではまるまる削除されてしまいました。

そのため，日本語で読むには 1.6 のほうを見なければなりません。
幸い，仕様が当時とさほど違っていないのか，とくに惑うところはありませんでしたが。

Qiita にも Rust のベンチマークテストのやり方についての記事は見当たらないようです。
そのことも，この記事を書いた動機でした。

最適化対策

コンパイラーによる最適化のためにベンチマークが意味をなさなくなる場合があることは本文に書きました。
このことは「プログラミング言語Rust」にも書かれています。

しかし，その対策について「スッキリと分かった」とは言いかねます。

さいごに

~~多言語のベンチマーク対決で，n % m == 0 を使った Rust コードを見ます。is_multiple_of で書き換えたらどのくらい結果が変わるでしょう。~~ （追記：差はありません）
is_multiple_of のコードを見たのですが，中身がありません。へ？　（追記：見るところが間違っていました）
新しく言語を学ぶのは楽しい。
Rust は学び甲斐があります。
stable に bench はよ。

追記

コメントでご指摘いただいたように，is_multiple_of の実装は当該のファイル中にちゃんとありました（私の目は節穴か）。

なんかよく分からないのですが，isize 用と usize 用に分かれてる？　こことここですね。
macro_rules! とか使ってて理解できませんが。

どちらの実装も同じで，

#[inline]
fn is_multiple_of(&self, other: &Self) -> bool {
    *self % *other == 0
}

でした。
ベンチマークで差がつかないはずですよ！

こいつは関数の形をしていますが，#[inline] が付いているので，この関数を呼び出すコードは，たぶんコンパイル後は関数呼び出しじゃなくて

*self % *other == 0

をコンパイルしたのと同じになるんですよね，きっと。
で，参照外しもコンパイル時に解決されちゃうから，おそらく本記事のテーマだった二つの処理はコンパイルすると全く同じになるのでしょうね。