Улучшение производительности для симулятора ТМ
Я пытаюсь смоделировать множество машин Тьюринга с двумя состояниями, тремя символами (лента в одном направлении). Каждое моделирование будет иметь разные входные данные и будет выполняться за фиксированное количество шагов. Текущее узкое место в программе — симулятор, занимающий тонну памяти на машинах Тьюринга, которые не останавливаются.
Задача состоит в том, чтобы смоделировать около 650000 ТМ, каждый из которых содержит около 200 непустых входов. Наибольшее количество шагов, которые я пытаюсь сделать, составляет 1 миллиард (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% будет иметь заметное значение.
Решение
Убедитесь, что в течение всего моделирования ТМ не происходит никаких распределений.
Предварительно выделить один глобальный массив при запуске программы, который достаточно велик для любого состояния ленты (например, 10 ^ 8 элементы). Поместите машину в начале этого ленточного массива изначально. Поддерживать сегмент [0; Р] из всех ячеек, которые посетили текущее моделирование машины: это позволяет избежать очистки всего массива ленты при запуске нового моделирования.
Используйте наименьший целочисленный тип для ленточных элементов, которого достаточно (например, используйте unsigned char если алфавит обязательно содержит менее 256 символов). Возможно, вы даже можете переключиться на наборы битов, если алфавит очень маленький. Это уменьшает объем используемой памяти и повышает производительность кэша / оперативной памяти.
Избегайте использования общих целочисленных делений в самом внутреннем цикле (они медленные), используйте только деления по степеням двух (они превращаются в битовые сдвиги). В качестве заключительной оптимизации вы можете попытаться удалить все ветви из самого внутреннего цикла (для этого есть разные хитроумные приемы).
Другие решения
Вот еще один ответ с более алгоритмическими подходами.
Поскольку у вас есть крошечный алфавит и крошечное количество состояний, вы можете ускорить симуляцию, обрабатывая куски ленты сразу. Это связано с общеизвестным теорема ускорения, хотя я предлагаю немного другой метод.
Разделите ленту на блоки по 8 символов каждый. Каждый такой блок может быть представлен 16-битным числом (2 бита на символ). Теперь представьте, что машина находится либо в первом, либо в последнем символе блока. Затем его последующее поведение зависит только от его начального состояния и начального значения в блоке, пока ТМ не выйдет из блока (влево или вправо). Мы можем предварительно вычислить результат для всех комбинаций (значение блока + состояние + конец) или, может быть, лениво вычислить их во время моделирования.
Этот метод может симулировать около 8 шагов одновременно, хотя, если вам не повезло, он может сделать только один шаг за итерацию (движение вперед и назад вокруг границы блока). Вот пример кода:
//R = table[s][e][V] --- outcome for TM which:
// starts in state s
// runs on a tape block with initial contents V
// starts on the (e = 0: leftmost, e = 1: rightmost) char of the block
//The value R is a bitmask encoding:
// 0..15 bits: the new value of the block
// 16..17 bits: the new state
// 18 bit: TM moved to the (0: left, 1: right) of the block
// ??encode number of steps taken??
uint32_t table[2][2][1<<16];
//contents of the tape (grouped in 8-character blocks)
uint16_t tape[...];
int pos = 0; //index of current block
int end = 0; //TM is currently located at (0: start, 1: end) of the block
int state = 0; //current state
while (state != 2) {
//take the outcome of simulation on the current block
uint32_t res = table[state][end][tape[pos]];
//decode it into parts
uint16_t newValue = res & 0xFFFFU;
int newState = (res >> 16) & 3U;
int move = (res >> 18);
//write new contents to the tape
tape[pos] = newValue;
//switch to the new state
state = newState;
//move to the neighboring block
pos += (2*move-1);
end = !move;
//avoid getting out of tape on the left
if (pos < 0)
pos = 0, move = 0;
}
Проблема остановки
Комментарий гласит, что симуляция ТМ, как ожидается, завершится очень рано, или выполнит все шаги до предопределенного огромного предела. Поскольку вы собираетесь моделировать множество машин Тьюринга, возможно, стоит потратить некоторое время на решение проблема остановки.
Первый тип зависания, который можно обнаружить: это когда машина стоит на одном месте, не удаляясь от нее. Давайте поддерживать окружающих TM во время симуляции, которая представляет собой значения сегмента символов на расстоянии < 16 от текущего местоположения ТМ. Если у вас есть 3 символа, вы можете закодировать окружение в 62-битное число.
Поддерживайте хэш-таблицу для каждой позиции ТМ (как мы увидим позже, необходимо только 31 таблица). После каждого шага сохраняйте кортеж (состояние, окружение) в хэш-таблице текущей позиции. Теперь важная часть: после каждого перемещения очищайте все хеш-таблицы на расстоянии> = 16 от ТМ (фактически, должна быть очищена только одна такая хеш-таблица). Перед каждым шагом проверьте, присутствует ли (состояние, окружение) в хеш-таблице. Если это так, то машина находится в бесконечном цикле.
Вы также можете обнаружить другой тип зависания: когда машина движется вправо бесконечно, но никогда не возвращается назад. Для этого вы можете использовать те же хеш-таблицы. Если ТМ находится на последнем символе ленты с индексом п, проверять текущий кортеж (состояние, окружение) не только в п-th, но и в (Р-1)-го, (Р-2)-th, …, (П-15)-хеш таблицы Если вы найдете совпадение, то TM находится в бесконечном цикле, двигаясь вправо.
+ Изменить
int move = data % 2;
к
int move = data & 1;
Один — деление, другой — битовая маска, оба должны давать 0 или 1 основание на младшем бите. Вы можете сделать это в любое время, когда у вас есть% в степени два.
Вы также устанавливаете
cell = tape[head];
data = TM[current_state][cell];
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;
}
^ Этот код не ссылается на «перемещение» или «запись», так что вы можете поместить вычисление для «перемещения» / «запись» после него и вычислять их только если current_state! = Halt_state
Также истинная ветвь оператора if является оптимизированной ветвью. Проверяя для не состояние остановки, и поместив условие остановки в ветвь else, вы можете немного улучшить предсказание ветки CPU.