こんにちは
半年ぶりに記事を書く六角レンチです
実は高校卒業しました
大学でC言語を学ぶ必要がありそうなのでC++を勉強し始めました
なので練習としてBrainf*ckインタプリンタ作ってどれくらい速いか調べたいと思います。
(C言語じゃなくてC++言語だけどまぁ大丈夫でしょ)

作成するBrainf*ckインタプリンタの仕様

メモリは1<<20個(1048576)まで拡張可能(それ以上は例外を送出)
メモリのポインターはマイナスの場所に行けない(例外を送出)
メモリの値は0~255
メモリのオーバーフローは0に戻る
アンダーフローは255になる
パイプからの入力時は何も表示しないけどターミナルからの入力の時は>>> を表示する

C++のコード

長いよ(190行くらい)

brainfuck.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <stdexcept>
#include <unistd.h>

class BracketNotMatch : public std::exception {
public:
    const char* what() const noexcept override {
        return "The number of matches brackets is incorrect.";
    }
};

class MemoryPosFlow : public std::exception {
public:
    const char* what() const noexcept override {
        return "Memory space has increased too much.";
    }
};

class MemoryPosUnderFlow : public std::exception {
public:
    const char* what() const noexcept override {
        return "Memory location cannot be backward.";
    }
};

class InputisNothing : public std::exception {
public:
    const char* what() const noexcept override {
        return "No inputs.";
    }
};

class BrainFuck
{
private:
    const unsigned int memory_limit = 1 << 20;  // 1MBくらい
    const unsigned int memory_num_limit = 255;
    std::string program;
    std::string inputs;
    int program_pos = 0;
    int cursor_pos = 0;
    std::vector<unsigned char> memory{0, 0, 0};
    std::unordered_map<int, int> bracket_open_map{};
    std::unordered_map<int, int> bracket_close_map{};

    void cursor_pos_increment () {
        if (cursor_pos == memory_limit) {
            throw MemoryPosFlow();
        } else {
            cursor_pos += 1;
            if ((memory.size()-1) < cursor_pos) {
                memory.push_back(0);
            }
        }
    }

    void cursor_pos_decrement () {
        if (cursor_pos == 0) {
            throw MemoryPosUnderFlow();
        } else {
            cursor_pos -= 1;
        }
    }

    void memory_increment () {
        if (memory[cursor_pos] == memory_num_limit) {
            memory[cursor_pos] = 0;
        } else {
            memory[cursor_pos] += 1;
        }
    }

    void memory_decrement () {
        if (memory[cursor_pos] == 0) {
            memory[cursor_pos] = memory_num_limit;
        } else {
            memory[cursor_pos] -= 1;
        }
    }

    void bracket_open () {
        if (memory[cursor_pos] == 0) {
            program_pos = bracket_open_map[program_pos];
        }
    }

    void bracket_close () {
        if (memory[cursor_pos] != 0) {
            program_pos = bracket_close_map[program_pos];
        }
    }

    void memory_out_char () {
        char a = static_cast<char>(memory[cursor_pos]);
        std::cout << a;
    }

    void memory_input_char () {
        // 入力文字がないとき
        if (inputs.empty()) {
            std::getline(std::cin, inputs);
            // 入力文字の中身がなく、EOFの時
            if (inputs.empty() && std::cin.eof()) {
                throw InputisNothing();
            }

        memory[cursor_pos] = static_cast<int>(inputs.front());
        inputs.erase(0);
        }
    }

public:
    explicit BrainFuck(const std::string& n) : program(n) {
        // [と]の数があっているか確認
        int bracket_match = 0;
        std::vector<int> bracket_stash{};

        for (int i=0; i < program.length(); i++) {
            switch (program[i]) {
            case '[':
                bracket_match += 1;
                bracket_stash.push_back(i);
                break;
            case ']':
                bracket_match -= 1;
                if (bracket_match < 0) {
                    throw BracketNotMatch();  // 例えば']['みたいな時
                }
                bracket_open_map.emplace(bracket_stash.back(), i);
                bracket_close_map.emplace(i, bracket_stash.back());
                bracket_stash.pop_back();
                break;
            default:
                break;
            }
        }

        if (bracket_match != 0) {
            throw BracketNotMatch();  // 例えば[][みたいな時
        }
    }

    void execute() {
        while (program_pos < program.length()) {
            switch (program[program_pos]) {
                case '>':
                    cursor_pos_increment();
                    break;
                case '<':
                    cursor_pos_decrement();
                    break;
                case '+':
                    memory_increment();
                    break;
                case '-':
                    memory_decrement();
                    break;
                case '[':
                    bracket_open();
                    break;
                case ']':
                    bracket_close();
                    break;
                case ',':
                    memory_input_char();
                    break;
                case '.':
                    memory_out_char();
                    break;
                default:
                    break;
            }
            program_pos++;
        }
    }
};

int main() {
    std::string input;

    if (isatty(STDIN_FILENO)) {
        // 端末(キーボード)からの実行時
        std::cout << ">>> ";
    }
    std::getline(std::cin, input);

    BrainFuck brain = BrainFuck(input);
    brain.execute();
}

コンパイラの設定はC++17らしい(よくわからん)
作って感じたのはデバッグ大変ということ
配列の確認がPythonならprintに渡すだけでできるけどこっちはfor文で回したりしないと見えない
他に方法あるのかな

Pythonのコード

長いよ(140行くらい)

brainfuck.py

from sys import stdin
from typing import Final


class BracketNotMatch(Exception):
    def __str__(self):
        return "The number of matches brackets is incorrect."


class MemoryPosFlow(Exception):
    def __str__(self):
        return "Memory space has increased too much."


class MemoryPosUnderFlow(Exception):
    def __str__(self):
        return "Memory location cannot be backward."


class InputisNothing(Exception):
    def __str__(self):
        return "No inputs."


class BrainFuck:
    def __init__(self, program: str):
        # 内部で使う変数の初期化
        self.__MEMORY_LIMIT: Final[int] = (1 << 20)
        self.__MEMORY_NUM_LIMIT: Final[int] = 255
        self.__program: str = program
        self.__inputs: str = ""
        self.__program_pos: int = 0
        self.__cursor_pos: int = 0
        self.__memory: list[int] = [0, 0, 0]
        self.__bracket_open_map = dict()
        self.__bracket_close_map = dict()

        # 一々len関数実行してると実行時間とんでもないことになるので変数で管理する
        self.__memory_length: int = len(self.__memory)

        # ブラケットの確認
        bracket_match: int = 0
        bracket_stash: list[int] = []
        for i in range(len(program)):
            match program[i]:
                case "[":
                    bracket_match += 1
                    bracket_stash.append(i)
                case "]":
                    bracket_match -= 1
                    if bracket_match < 0:
                        raise BracketNotMatch()
                    self.__bracket_open_map[bracket_stash[-1]] = i
                    self.__bracket_close_map[i] = bracket_stash[-1]
                    bracket_stash.pop()

        if bracket_match != 0:
            raise BracketNotMatch()

    def __cursor_pos_increment(self):
        if self.__cursor_pos == self.__MEMORY_LIMIT:
            raise MemoryPosFlow()
        else:
            self.__cursor_pos += 1
            if self.__memory_length-1 < self.__cursor_pos:
                self.__memory.append(0)
                self.__memory_length += 1

    def __cursor_pos_decrement(self):
        if self.__cursor_pos == 0:
            raise MemoryPosUnderFlow()
        else:
            self.__cursor_pos -= 1

    def __memory_increment(self):
        if self.__memory[self.__cursor_pos] == self.__MEMORY_NUM_LIMIT:
            self.__memory[self.__cursor_pos] = 0
        else:
            self.__memory[self.__cursor_pos] += 1

    def __memory_decrement(self):
        if self.__memory[self.__cursor_pos] == 0:
            self.__memory[self.__cursor_pos] = self.__MEMORY_NUM_LIMIT
        else:
            self.__memory[self.__cursor_pos] -= 1

    def __bracket_open(self):
        if self.__memory[self.__cursor_pos] == 0:
            self.__program_pos = self.__bracket_open_map[self.__program_pos]

    def __bracket_close(self):
        if self.__memory[self.__cursor_pos] != 0:
            self.__program_pos = self.__bracket_close_map[self.__program_pos]

    def __memory_out_char(self):
        print(chr(self.__memory[self.__cursor_pos]), end="")

    def __memory_input_char(self):
        if self.__inputs == []:
            try:
                self.__inputs = input()
            except EOFError:
                raise InputisNothing()

        self.__memory[self.__cursor_pos] = ord(self.__inputs[-1])
        self.__inputs[:-1]

    def execute(self):
        program_length = len(self.__program)  # そのままwhile文に入れると毎回len関数呼んで遅くなる
        while self.__program_pos < program_length:
            match self.__program[self.__program_pos]:
                case ">":
                    self.__cursor_pos_increment()
                case "<":
                    self.__cursor_pos_decrement()
                case "+":
                    self.__memory_increment()
                case "-":
                    self.__memory_decrement()
                case "[":
                    self.__bracket_open()
                case "]":
                    self.__bracket_close()
                case ",":
                    self.__memory_input_char()
                case ".":
                    self.__memory_out_char()

            self.__program_pos += 1


if __name__ == "__main__":
    if stdin.isatty():
        print(">>> ", end="")
    inputs = input()
    brainfuck = BrainFuck(inputs)
    brainfuck.execute()

Pythonのバージョンは3.11.9（match-case文使いたかった）
C++のコードを先に作ったのでできるだけ実装を似せて作った
違いはlistのメソッドにsizeみたいな長さを確認するやつがなくて一々len関数使ってたら絶対遅くなるのでメモリの長さの変数を置いてることくらい

計測

powershellのMeasure-Commandを使って計測する
linuxでいうtimeコマンドみたいな？

環境

OS
Windows10 Pro 22H2
もうすぐでサポート切れるらしい
CPU
Core i7 4770
C++のコンパイラ
よくわからんけどMSYS2経由で入れたmingwのg++(versionは14.2.0)
C++のバージョンはC++17らしい(よくわからん)
Pythonのバージョン
CPython 3.11.9(確かWindows Store経由でインストール)

Hello World!

wikimediaより以下のbrainfuckコードを拝借

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

echoコマンドとパイプで流す感じ

やってみる

何回かやってみてC++が13ミリ秒前後、Pythonが130ミリ秒後半という感じ
C++はPythonと違ってコンパイル言語なのですごいはやい

Pythonは処理よりも立ち上げに時間がかかっている可能性がある

いっぱいループさせる

以下のbrainfuckプログラムを実行する

+++++++++[>-[>-[>+<-]<-]<-]

メモリのアンダーフローは上限値(255)になるので9x255x255=585,225回ループすることになる

やってみる

C++が80ミリ秒前後といった感じでPythonは1秒と350~400ミリ秒といったところ
1秒が1000ミリ秒だからPythonを1375としてC++を80とすると大体17倍くらい速いかな？

コンパイル言語がどれだけ早いのか実感する

いっぱいメモリ拡張してみる

以下のbrainfuckプログラムを実行する

++++++++[>++++++++<-]>[>+>-[[>+<-]>-]>+<-[+<-]<[>>-[>-]+>+<<[+<]<-]-[>-]>-]

適当に作ったbrainfuckのコード
よくわからん人向けに適当に解説すると

++++++++[>++++++++<-]  # 8x8で64を生成
>  # 64に移動
[
    >+  # フラグを作って（フラグ1とする）
    >-  # 横に255を作って
    [[>+<-]>-]  # 255回横に移動する
    >+  # フラグをもう一個作って（フラグ2とする）
    <-[+<-]  # フラグ1に移動
    <  # 64に移動して
    [>>-[>-]+>+<<[+<]<-]　　# 64をフラグ2の横に移動する
    -[>-]  # 今自分は64が前あったにいるのでフラグ2に移動して
    >-  #　64から1個減らす
]  # 64が0になるまで繰り返す

こんな感じ

一回のループで259回メモリが拡張されるので259x64で16,576回拡張される
なんかループ処理が多すぎてそっちの処理に時間がかかりそうな気がするけど気にしないことにする。

実行してみる

C++が320~350ミリ秒後半、Pythonが6秒半くらいといった感じ
やっぱりメモリ拡張というよりループ処理が多すぎる可能性あるけど...

Pythonが6500としてC++が335とすると大体19倍速い

Pythonが遅すぎるのかC++が速すぎるのか...

限界までメモリ拡張させる

以下のbrainfuckプログラムを実行する

+[>+]

無限に右に移動し続けるプログラムです
メモリの大きさの上限に達して例外を吐くまでループし続ける
メモリの大きさの上限は1<<20 = 1048576個なので、1048576回くらいメモリを拡張することになる

実行してみる

C++の方が遅く見えるけど実はC++の方が速く例外の文字を出している
ただそのあとに謎の硬直が生じてその時間分遅れてる感じ
Pythonは例外の文字の後に硬直はないので処理時間が実時間そのものという感じ

なぜこの硬直が発生するのか謎
知ってる人いたら教えてほしい

C++の例外文字は体感一瞬で出力されている
Enter押したらすぐ出るみたいな感じ

あとC++の例外の情報量少なすぎて困る
普通にプログラミングしてたらこの例外すら出さずに止まったりするのでさらに困る
速さのためにはしょうがないのかな

感想

C++すごいはやい
意外と書きやすい
でもデバッグがめんどくさい
特に未定義動作とかいうやつのせいで時間が溶ける
Python遅い
だけど書きやすさとデバッグのやりやすさは段違い
ChatGPT君にすごい助けられた

こんな感じかな

C++のデバッグが本当に難しいのでどうにかしたい
未定義動作って本当に何

あとprintデバッグも配列とか辞書型とかの内容を出力するみたいなのが難しいのでどうにかする方法を見つけたい

まだC++始めて1週間も経ってないので頑張りたいところ
Pythonは大体1年半かな？

C++の構文はPythonとだいぶ違うので戸惑う物かと思ったけど思ったより難しくなかった
Pythonもそうだけどlinterが強力なので基本的な構文エラー(ブラケットがあってない、型が違う、;を付け忘れてる)等を教えてくれるのでコンパイルエラーには会わなかった

おまけ

Pythonがあまりにも遅すぎるのでできるだけ速くしたい

でも改善できそうなところは特にない...
(関数を書かずにmatch-case文のところに直に書いてみたけど逆に遅くなった)

...あれを使えばいいのでは？

PyPyを使おう

ということでPyPyを使います

なんかPyPyって3.9までしか対応してないと思ってたけど今見てみたら3.11対応してた
(逆に考えれば今3.9を使っている自分がおかしいのでは...?)

PyPyのバージョンはPython 3.11.11(PyPy 7.3.18)です

立ち上がりの速度

大体50ミリ秒後半といった所

Hello World!

大幅には変わってないけど速くはなっている
さらに多くの処理をさせるとどうなるのか気になる

いっぱいループさせる

普通のCPythonが大体1350~1400ミリ秒だったのを考えると8倍くらい速い
流石にC++の方が速いがインタプリンタを変えるだけでここまで速くなるとは驚き
もっと行こう

いっぱいメモリ拡張してみる

なんかありえないくらい速い
C++と同じ速度ってマジ？

でもプログラムは一緒だし...
デバッグして確かめてみたけど特にバグがあるようではない...
これがJITコンパイラの力なのか...?

限界までメモリ拡張させる

やはりこちらも速い
C++は謎の硬直があるのでしょうがないけどCPythonと比べるととんでもなく速い

前（いっぱいメモリ拡張してみる）と比べると同じ処理を何度もしているという共通点がある
JITコンパイラの強みなのかもしれない

PyPyの感想

ありえないくらい速くなった
CPythonとPyPyの違いといえばJITコンパイラだけど繰り返し処理に強いのかもしれない

でもそれだけで片づけるには速すぎる気がする
同じプログラム使ってるんだけどな...

CPythonが遅すぎる可能性もある