PythonとC++の速さをBrainf*ckのインタプリンタ作って比較してみた

Posted at 2025-02-25

こんにちは
半年ぶりに記事を書く六角レンチです
実は高校卒業しました
大学で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になるまで繰り返す