c++ - 提高 TM 模拟器的性能

Question

我正在尝试模拟很多 2 状态、3 符号(单向磁带)图​​灵机。每个模拟将有不同的输入，并将运行固定数量的步骤。该程序当前的瓶颈似乎是模拟器，在不停止的图灵机上占用大量内存。

任务是模拟大约 650000 个 TM，每个有大约 200 个非空白输入。我正在尝试的最大步数是 10 亿 (10**9)。

下面是我正在运行的代码。 vector<vector<int> > TM是一个转换表。

vector<int> fast_simulate(vector<vector<int> > TM, string TM_input, int steps) {
    /* Return the state reached after supplied steps */

    vector<int> tape = itotape(TM_input);

    int head = 0;
    int current_state = 0;
    int halt_state = 2;

    for(int i = 0; i < steps; i++){

        // Read from tape
        if(head >= tape.size()) {
            tape.push_back(2);
        }
        int cell = tape[head];
        int data = TM[current_state][cell];  // get transition for this state/input

        int move = data % 2;
        int write = (data % 10) % 3;
        current_state = data / 10;

        if(current_state == halt_state) {
            // This highlights the last place that is written to in the tape
            tape[head] = 4;
            vector<int> res = shorten_tape(tape);
            res.push_back(i+1);
            return res;
        }

        // Write to tape
        tape[head] = write;

        // move head
        if(move == 0) {
            if(head != 0) {
                head--;
            }
        } else {
            head++;
        }
    }

    vector<int> res {-1};
    return res;
}

vector<int> itotape(string TM_input) {
    vector<int> tape;
    for(char &c : TM_input) {
        tape.push_back(c - '0');
    }
    return tape;
}

vector<int> shorten_tape(vector<int> tape) {
    /*  Shorten the tape by removing unnecessary 2's (blanks) from the end of it.
    */
    int i = tape.size()-1;
    for(; i >= 0; --i) {
        if(tape[i] != 2) {
            tape.resize(i+1);
            return tape;
        }
    }
    return tape;
}

在性能或内存使用方面有什么地方可以改进吗？即使减少 2% 也会产生显着差异。

Answer 1

确保在整个 TM 模拟期间没有分配发生。

在程序启动时预分配一个全局数组，它对于磁带的任何状态都足够大(例如 10^8 元素)。最初将机器放在该磁带阵列的开头。维护段 [0;当前机器模拟访问过的所有单元格的 R]:这使您可以避免在开始新模拟时清除整个磁带阵列。

对磁带元素使用足够的最小整数类型(例如，如果字母肯定少于 256 个字符，则使用 unsigned char)。如果字母表非常小，您甚至可以切换到位集。这减少了内存占用并提高了缓存/RAM 性能。

避免在最内层循环中使用通用整数除法(它们很慢)，仅使用二的幂除法(它们会变成移位)。作为最终的优化，您可以尝试从最内层循环中删除所有分支(对此有多种巧妙的技术)。