LoginSignup
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@voidhoge

Brainfuck インタプリタの高速化

Last updated at Posted at 2025-03-31

Brainf*ck は非常に遅い言語です。1 命令では値およびデータポインタを 1 つ動かすことしかできないため、他の命令セットではオペランドの大きさに依らず $O(1)$ でできる基本的な演算に $O(N)$ や $O(N^2)$ かかります。したがって、大規模な Brainf*ck プログラムを開発するためには可能な限り高速な処理系を用意することが望ましいでしょう。本稿では、高速な Brainf*ck インタプリタを実装する上で必要になる工夫について述べ、さらにそれに基づいて実装したインタプリタについて述べます。

今回作成したインタプリタ brust は Erik Bosman 氏のマンデルブロ集合描画プログラムを 約 1.5 秒で実行することができ、私が調査したインタプリタでは世界最高レベルの性能を持っています。

既存のインタプリタ

Brainf*ck の処理系としてはインタプリタを用いるのが一般的です。一時ファイルを生成せず、手軽に実行できて他のプロジェクトにも組み込みやすいため、様々なサービスにおける Brainf*ck 処理系としてもインタプリタが採用されています [1] 。今回は JIT コンパイルや処理系依存の要素 (GCC の拡張機能等) を用いず、純粋な言語仕様のみで実現できるインタプリタを考えます。

Brainf*ck の命令はシンプルすぎるため、より高レベルな命令に畳み込みます。すなわち、与えられた Brainf*ck の命令列は、高レベルな命令列に変換されて実行されます。たとえば、連続する+/-, >/< はまとめて一気に動かしても構わないので、動かす量を即値に持つ命令に変換しすることにより、実行される命令の数を一気に減らすことができます。

ここでは、これまでの高速なインタプリタを 2 つ紹介します。

bf-eval

1 つ目は Go で実装されたインタプリタである bf-eval です [2]。このインタプリタは日本語による解説が提供されています。高速な Brainf*ck インタプリタを実装するための基本的な点が解説されています。

bf-eval の命令は、C に改めると以下のようになっています。

typedef struct {
	Op Op;
	uint8 pad;
	uint16 pad2;
    int32 Data;
} Instruction;

命令の実行に使われるのは種別を保持する Op とその引数を表す Data です。pad と pad2 は命令長を 8 バイトにするために挿入されたパディングです。命令長が 8 バイトになることによりアラインが保たれ、アクセスが高速化されます。これらは単にパディングのためのものであり pad や pad2 は実行中にはアクセスされません。また、[ や ] において、ジャンプテーブルは Data に格納されるわけではなく、別のジャンプテーブルに格納されます。

実装されている命令は以下のものです。

instruction example description
OpShiftRight >>>> ポインタを Data だけ右に動かす
OpShiftLeft <<<< ポインタを Data だけ左に動かす
OpAddMem [->+<] Data 個先の他のセルに今のセルを加算し、今のセルを 0 にする
OpSubMem [->-<] 減算版 OpAddMem
OpLoopStart [ ループ開始
OpLoopEnd ] ループ終了
OpIncr ++++ カレントセルの値に Data 足す
OpDecr ---- カレントセルの値から Data 引く
OpZeroReset [-] カレントセルを 0 にする
OpMultiShift [>] カレントセルが 0 になるまでポインタを Data だけ移動
OpOutput . 標準出力
OpInput , 標準入力 (もとの実装にはなかったので私が追加)

deadbeef

2 つ目は C で実装されたシンプルなインタプリタである deadbeef です [3]。今回の条件を満たすインタプリタとしては最高の性能を誇ります。

deadbeef の命令は以下のようになっています。

struct bfi{
    int mov;
    int cmd;
    int arg;
} *pgm = 0;

命令は 12 バイトで構成されます。mov は各命令の実行前にデータポインタを動かします。例えば、>>>>+++ は +++ の実行前にデータポインタを 4 動かすので、{mov: 4, cmd: '+', arg: 3} という命令に変換されます。これにより、各命令の前の <> がそれぞれの命令に畳み込まれるため、高速化が見込まれます。なお、足し算を行う [->+<] は畳み込まれません。

実装されている命令は以下のとおりです。

instruction example description
0 終端記号
= [-]++++ 今のセルに arg をセット
+ ++++ 今のセルを arg だけ動かす
[ [ ループ開始
] ] ループ終了
? [>] 今のセルが 0 になるまでポインタを arg だけ移動
> >>>> ポインタを arg だけ移動
. . 標準出力
, , 標準入力
! ! ブレークポイント
# # デバッグ出力

Brainf*ck インタプリタの高速化

コンセプト

Brainf*ck インタプリタを高速化するために最も重要な点は実行される命令の設計です。よく用いられる処理の計算量オーダーを落とし、それでカバーできない部分の定数倍を改善することが求められます。今回のインタプリタで実行される命令は以下の特長を持ちます。

  • 複数宛先の定数乗算
    • 値のコピーなどで多用されるイディオムを畳み込む
  • 命令設計の工夫
    • 8 バイトの命令列で可能な限り色々なことをやる

複数宛先の定数乗算

値の移動イディオム [->+<] を応用して宛先を増やしたり、それぞれの宛先に定数を掛けることが可能です。例えば、[->+++>+>--<<<] は以下の C と等価です。

if (data[dp]) {
    data[dp + 1] += data[dp] * 3;
    data[dp + 2] += data[dp] * 1;
    data[dp + 3] += data[dp] * -2;
    data[dp] = 0;
}

以下の条件をすべて満たす命令列を畳み込みます。

  • [] で囲まれた、+, -, <, > のみで構成された命令列であること
  • [ の直後と ] の直前でポインタの移動量が相殺され、同じ場所に戻ってくること
  • 一周で開始番地が 1 減ること
  • [-] でないこと

命令設計の工夫

命令は以下の構造体 (および列挙体) で構成されています。なお、ここでは C に変換していますが、実際には Rust です。 cmd は命令の種別を表す列挙体、arg はシフト量 (>, <) やジャンプ先 ([, ]) を表すための整数、inc は +- によるインクリメントの回数を表す整数、delta はシフト量を表す整数です。全体のサイズは 8 バイトです。

typedef enum {
    ShiftInc,
    Output,
    Input,
    Skip,
    Set,
    Mulzero,
    Mul,
    Open,
    Close
} InstType;

typedef struct {
    InstType cmd;
    int32_t arg;
    uint8_t inc;
    int16_t delta;
} Inst;

Brainf*ck およびそのインタプリタの命令は非常にシンプルで高速に実行されるため、演算器の性能よりも命令の供給速度がボトルネックになります。
そこで、命令に載せることができるビット列をできるだけ有効活用し、1 命令でできるだけ多くの処理を行うほうが有利です。

Brainf*ck で意味のあることを行うために必ずセルのインクリメントやデクリメント、ポインタの移動を行う必要があります。この性質を利用し、各命令の後に +/- や </> が続く場合には inc と delta に埋め込み、可能な限り一命令で行います。

ちなみに、この設計は [4] を参考にしています。

ShiftInc 命令

ShiftInc 命令は >>+++>>>> のように、データポインタのシフト、インクリメント、シフトの 3 つのセクションからなる命令列を 1 命令で実行できるようにしたものです。等価な C は以下のようになります。なお、delta は i16 なので、シフト量が収まらない場合、次の ShiftInc 命令に見送って arg (i32) で処理します。

dp += arg;
data[dp] += inc;
dp += delta;

例えば、>>+++>>>> は以下のように変換されます。

ShiftInc 2, 3, 4

Input, Output, Set 命令

Input, Output は標準入出力を行う ,. をベースとした命令です。これらの命令では delta と inc のみを用います。arg は使いません。(もったいないですが)

例えば、 Input は以下の C と等価です。

data[dp] = getchar();
data[dp] += inc;
dp += delta;

Output や Set 命令もほぼ同様です。

例えば、[-]+++++++>>> は以下のように変換されます。

Set, 0, 8, 3

Mul, Mulzero 命令

Mul と Mulzero は値の移動やコピー、定数での乗算を行う命令です。複数宛先の演算の場合、いくつの宛先があるかがわからず任意の長さに対応できる必要があります。そこで、Mul 命令ではカレントセルをリセットせず、一連の複数宛先乗算の最後に Mulzero 命令を発行してカレントセルを 0 にします。

Mul は以下の C と等価です。

if (data[dp]) {
    data[dp + arg] += data[dp] * inc;
}
// [->+<] からの変換のみを想定しているため delta は常に 0 で no effect
dp += delta;

Mulzero は以下の C と等価です。

if (data[dp]) {
    data[dp + arg] += data[dp] * inc;
    data[dp] = 0;
}
dp += delta;

例えば [->+++>+>--<<<] は以下のように変換されます。

Mul, 1, 3, 0
Mul, 2, 1, 0
Mulzero, 3, -2, 0

Open, Close 命令

Open は [、Close は ] をベースとした命令です。arg にジャンプ先の命令のインデックスを格納します。ただし、[] の中の処理を高速化するために、最初の最大 2 命令を埋め込みます。

Open は以下の C と等価です。

if (data[dp] == 0) {
    ip = arg; // 対応する ] にジャンプ
} else {
    // カッコ内の先頭の命令を実行
    data[dp] += inc;
    dp += delta;
}

Close は以下の C と等価です。

if (data[dp]) {
    ip = arg; // 対応する [ にジャンプ
    // 戻った先の [ の次の命令を実行
    data[dp] += inc;
    dp += delta;
}

例えば、[-<<] は以下のように変換されます。通常のインタプリタであれば 4 命令かかる処理を 2 命令で行えます。

Open, 1, -1, -2
Close, 0, -1, -2

この実装において Close の inc と delta は Open のそれと共通です。これはやや冗長で、] 直後の命令を埋め込むような実装も考えられます。しかし、] 直後の命令よりも、ループ内の命令のほうが多く実行されるためループ内を優先しています。

実験

以上の最適化を施したインタプリタの性能を測定し、既存のインタプリタとの比較を行いました。機材として ThinkPad X13 Gen3 (Ryzen 7 PRO 6850U, Debian GNU/Linux, 32GB RAM) を用いました。各ベンチマークプログラムにつき、まずウォーミングアップとして 100 回実行し、その後 100 回実行してその平均実行時間を取りました。以下のシェルスクリプトを使いました。

benchmark.sh 
#!/bin/bash

if [ $# -lt 2 ]; then
    echo "Usage: $0 <iterations> <interpreter> <source> [input]"
    exit 1
fi

iterations=$1
interpreter=$2
source=$3
input=$4

if [ ! -x "$interpreter" ]; then
    echo "Error: '$interpreter' does not exist or is not executable."
    exit 1
fi

if [ ! -f "$source" ]; then
    echo "Error: Source file '$source' does not exist."
    exit 1
fi

if [ -n "$input" ] && [ ! -f "$input" ]; then
    echo "Error: Input file '$input' does not exist."
    exit 1
fi

echo "=== Benchmark ==="
echo "Iterations:  $iterations"
echo "Interpreter: $interpreter"
echo "Source:      $source"
if [ -n "$input" ]; then
    echo "Input:       $input"
fi

echo "Warming up..."
for (( i=1; i<=$iterations; i++))
do
    echo "$i/$iterations"
    if [ -n "$input" ]; then
        cat "$input" | "./$interpreter" "$source" > /dev/null 2>&1
    else
        "./$interpreter" "$source" > /dev/null 2>&1
    fi
done

total=0

for (( i=1; i<=iterations; i++ ))
do
    begin=$(date +%s.%N)
    if [ -n "$input" ]; then
        "./$interpreter" "$source" < "$input" > /dev/null 2>&1
    else
        "./$interpreter" "$source" > /dev/null 2>&1
    fi
    end=$(date +%s.%N)
    duration=$(echo "$end - $begin" | bc)
    echo "Run $i: $duration seconds"
    total=$(echo "$total + $duration" | bc)
done

average=$(echo "scale=6; $total / $iterations" | bc)
echo "=== Result ==="
echo "Average execution time: $average seconds"

テストスイートとして [5] に含まれるもののうち、パフォーマンステストを目的とした (実行に時間のかかる) ものを選んで使用しました。また、[6] を用いて作成した数独ソルバーも使用しました。

テストに使用したベンチマークプログラムは以下の通りです。

name description input author
awib [7] Cをターゲットとしたセルフホストコンパイラ コンパイラ自身 Mats Linander
Collatz [8] Collatz 列の長さを出力する 2002 桁の数 (47733 回かかるらしい) Daniel B Cristofani
Counter 実行に時間のかかるテストプログラム (最適化はかなり困難) Robert de Bath
EasyOpt 複数宛先の加算が実装されていれば速いプログラム Robert de Bath
Factor [9] 任意長の素因数分解 2147483647 Barin Raiter
Hanoi ハノイの塔のグラフィカルな解 Clifford Wolf
Life [10] ライフゲーム (セル・オートマトン) Figure eight (period-8 oscillator) Linus Akesson
Long 実行に時間のかかるテストプログラム 不明
Mandelbrot マンデルブロ集合描画 (有名なやつ) Erik Bosman
Prime 指定した数までの素数列挙 255 不明
SelfInt [8] セルフホストインタプリタ インタプリタ自身 Daniel B Cristofani
Sudoku [6] 数独ソルバー 20 ヒント問題 Mugi Noda

結果は以下のようになりました。bf-eval が紫、deadbeef が緑、今回作成した brust が水色です。

brust はすべてのテストケースで最も優れた性能を示しました。特に EasyOpt と Life ではオーダーレベルの差が出ています。これは複数宛先加算命令が実装されているかどうかによるものだと考えられます。

平均すると bf-eval に対して 5.62 倍, deadbeef に対して 4.20 倍高速でした。オーダーレベルの差がある EasyOpt と Life を除いても、bf-eval に対して 2.97 倍、deadbeef に対して 2.23 倍高速でした。

bfi_comp.png

まとめ

本稿では高速な Brainf*ck インタプリタを実装しました。既存のオープンソースのインタプリタで行われている最適化に加え、複数宛先定数乗算命令を実装し、さらに命令中にシフトとインクリメント (デクリメント) を埋め込むことにより高速化を行いました。その結果、既存のインタプリタよりも大幅に速いものが得られました。

おまけ (v.s. bffsree)

私が調査した中では最高の性能を誇る bffsree は、brust よりもさらに高速です。brust と bffsree はよく似た命令を使っていますが、括弧の処理などに微妙な差があるようです。しかし bffsree はソースコードが公開されていないため、それが何なのかはよくわかりません。(一部のプログラムについて、結果が合わない気がします。)

bffsree はソースコードが公開されておらず、さらに処理系としての正しさに疑問があるため今回の比較対象とはしませんでした。また、コードサイズと実行時間が標準出力されるので、その点は正しい実装とは言えません。

参考までに比較の結果を掲載します。Long と Prime はオーダーレベルで bffsree が速いです。これはおそらく乗算命令が実装されているからだと思われます (それがどのパターンなのかはよくわかりませんでしたが)。

benchmark brust [s] bffsree [s]
awib 0.02 segmentation fault
Collatz 1.71 1.40
Counter 2.27 2.51
EasyOpt 0.03 0.03
Factor 1.66 1.97
Hanoi 0.011 0.016
Life 0.011 0.011
Long 0.66 0.064
Mandelbrot 1.52 1.47
Prime 1.12 0.11
SelfInt 2.05 1.89
Sudoku 0.72 1.02

また、出力される命令列の長さから、bffsree で一度に可能なシフトは -128 以上 127 以下であることが推察されます (brust は ShiftInc も Mul/Mulzero も-2147483648 以上 2147483647 以下)。そのため多次元配列などを使った大規模なプログラムの性能劣化が予想されます。

参考文献 (すべて 2025 年 3 月閲覧)

6
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?