Rust の const fn で最速の FizzBuzz

18580 ワード
Rust FizzBuzz FizzBuzz テキストリンク

動機

最速のプログラムは何かと考えたときにその答えは「何もしない」が正解になるのではないでしょうか。ということで実行時 (runtime) ではなくコンパイル時 (compile time) に FizzBuzz をやってしまうということを考えてみました。Rust で。

どうやって

タイトルに書いてあるのでネタバレしていますが、Rust には const fn (C++ で言うところの constexpr) という機能があるのでこれを利用します。つまり const fn を使って"1\n2\nFizz\n4\nBuzz\n6..."のような文字列をバイナリに埋め込んでしまうということです。実行時にはその文字列を標準出力に流し込むだけです。

しかし

const fn の機能は現状 (stable channel) ではかなり制限されており、まともに使えません。制限されている機能は主に下記の通り。

  • if / match 等の条件分岐
  • for / loop 等の繰り返し処理 (#![feature(const_loop)]で使えるとの情報をコメントで頂きました)
  • heap の使用 (Vec 等は使えない)
  • const fn 以外の関数の呼び出し (1.to_string() とかも使えない)

などなど…。つらい。

どうしたか

if / match 等の条件分岐は？

nightly channel なら使えます。その上でfeature flagを設定します。

#![feature(const_if_match)]

const fn foo() {
    match (i % 3, i % 5) {
        // do something
    }
}

for / loop 等の繰り返し処理は？

nightly channel でも使えないようなので、再帰で処理することに。
nightly channel では#![feature(const_loop)]で loop / while が使えます。

// const LIMIT: usize = 20;

// const fn bar() {
//     baz(0);
// }

// const fn baz(mut count: usize) {
//     if count <= LIMIT {
//         // do something
//         count += 1;
//         baz(count);
//     }
// }

#![feature(const_loop)]

const fn bar() {
    loop {
        // do somthing
    }
}

heap の使用は？

コンパイル時にサイズの分かっている型しか使えません。ミュータブルな参照を使うにもfeature flagが必要です。

#![feature(const_mut_refs)]

const fn hoge() -> [u8; 1024] {
    let mut buf = [0; 1024];
    piyo(&mut buf);
    buf
}

const fn piyo(buf: &mut [u8]) {
    // do something
}

const fn 以外の関数の呼び出しは？

1.to_string()で整数を文字に変換したいですが、これはコンパイルエラーです（たぶん heap も使うし）。なのでルックアップテーブルを使って、整数の1を文字の'1'(utf-8 の 0x31) に変換することにしました。

const LUT: [u8; 10] = *b"0123456789";
let fuga = LUT[1]; // 文字の '1' になる。

最速の FizzBuzz がこちら

何をやっているかはコードを読んで察してください。fizzbuzz(n)を大きくすると、どこかでコンパイルエラーになると思います。（編集リクエストありがとうございます！）（みなさまのコメントを反映して書き換えました。）（以下の例は buf サイズを 1024 にしていますが、コンパイル時に計算できます。）

#![feature(const_fn)]
#![feature(const_if_match)]
#![feature(const_mut_refs)]
#![feature(const_loop)]
#![allow(non_upper_case_globals)]

const F: u8 = b'F';
const i: u8 = b'i';
const z: u8 = b'z';
const B: u8 = b'B';
const u: u8 = b'u';
const NEW_LINE: u8 = b'\n';
const LUT: [u8; 10] = *b"0123456789";

#[inline]
const fn insert(buf: &mut [u8], pos: &mut usize, utf8: u8) {
    buf[*pos] = utf8;
    *pos += 1;
}

macro_rules! bulk_insert {
    ($buf:expr, $pos:expr, [$($inner:tt),*]) => (
        $(insert($buf, $pos, $inner);)*
    );
}

const fn fizzbuzz(limit: usize) -> [u8; 1024] {
    let mut buf = [0; 1024];
    let mut num = 1;
    let mut pos = 0;
    loop {
        if num > limit {
            break;
        }
        match (num % 3, num % 5) {
            (0, 0) => {
                bulk_insert!(&mut buf, &mut pos, [F, i, z, z, B, u, z, z]);
            }
            (0, _) => {
                bulk_insert!(&mut buf, &mut pos, [F, i, z, z]);
            }
            (_, 0) => {
                bulk_insert!(&mut buf, &mut pos, [B, u, z, z]);
            }
            (_, _) => {
                let third = if num / 100 > 0 {
                    insert(&mut buf, &mut pos, LUT[(num / 100)]);
                    (num / 100) * 100
                } else {
                    0
                };
                let second = if (num - third) / 10 > 0 {
                    insert(&mut buf, &mut pos, LUT[(num - third) / 10]);
                    ((num - third) / 10) * 10
                } else {
                    0
                };
                insert(&mut buf, &mut pos, LUT[(num - third - second)]);
            }
        }
        insert(&mut buf, &mut pos, NEW_LINE);
        num += 1;
    }
    buf
}

// 1..=20
const FIZZBUZZ_20: [u8; 1024] = fizzbuzz(20);

fn main() {
    println!("{}", unsafe { std::str::from_utf8_unchecked(&FIZZBUZZ_20) });
}

できあがったバイナリを覗いてみると、確かに"1\n2\nFizz\n4\nBuzz\n6..."な文字列が埋め込まれていますね。

まとめ

const fn つらい いいぞ。