- PVSM.RU - https://www.pvsm.ru -
Brainfuck [1] — язык программирования, созданный с одной целью: написать для него интерпретатор. Их было написано так много, что даже не буду давать на них ссылки. В этой статье на пальцах объясняется простой, но эффективный способ его оптимизации.
Для оптимизации нужно выполнить 3 правила:
Обратные инструкции (+ и -, > и <) взаимоуничтожаются, когда идут одна за другой. Код >++>><<- превращается в >+. Это, скорее, защита от дурака, чем оптимизация, т.к. такой код бессмысленен.
Повторяющиеся инструкции заменяются на команды, в аргументах которых сказано сколько раз конкретную инструкцию выполнить. Например, код +++ заменяется на команду ADD с аргументом 3, а код <<< на MOVE:-3.
Каждая команда имеет свой аргумент (далее просто arg). Значение аргумента ограничено только у команды ADD, т.к. размер одной ячейки 256.
Имя команды | Инструкции | Описание |
---|---|---|
ADD | + и - | Изменяет значение текущей ячейки на arg |
MOVE | > и < | Изменяет индекс текущей ячейки на arg |
READ | , | Пропускает из потока ввода arg символов и читает следующий за ними символ |
. | Печатает символ соответствующий значению текущей ячейки arg раз | |
GOTO | [ и ] | Переходит к выполнению arg по счёту команды относительно текущей |
ASSIGN | [+] и [-] | Присваивает текущей ячейке arg |
Интерпретация разделена на 3 этапа. Чтение исходного кода, его преобразование в оптимизированные команды и выполнение этих команд. Это всё происходит в функциях main и parse.
Первый и последний этап происходят сразу в функции main. Её код с комментариями:
int main(int argc, char* argv[]){
/* имя файла с исходниками передаётся первым аргументом */
if(argc == 1){
fprintf(stderr, "%s: Wrong argument countn", argv[0]);
return 1;
};
/* файл открывается для чтения */
FILE* f = fopen(argv[1], "r");
if(f == NULL){
fprintf(stderr, "%s: Can't open %sn", argv[0], argv[1]);
return 2;
};
/* исходный код читается из файла */
int n = fread(str, sizeof(char), SIZE - 1, f);
if(n == 0){
fprintf(stderr, "%s: Can't read data from %sn", argv[0], argv[1]);
return 3;
};
str[n] = '';
/* проверяется правильность расстановки скобок */
fclose(f);
if(brackets()){
fprintf(stderr, "%s: Wrong brackets sequencen", argv[0]);
return 4;
};
/* парсинг исходного кода */
parse();
/* выполнение команд */
ptr = mem;
int (*exe[])(int) = {exe_a, exe_b, exe_c, exe_d, exe_e, exe_f};
struct code* p = src + 1;
for(; p->cmd; ++p){
p += (*exe[p->cmd - 1])(p->arg);
};
return 0;
};
Оптимизация с помощью преобразования инструкций bf в команды для интерпретатора происходит в функции parse. Её код с комментариями:
void parse(){
/* инициализируется массив команд */
struct code *p = src;
p->cmd = 0;
p->arg = 0;
/* указатель на текущую инструкцию */
char* ch = str;
/* указатель на вершину стека необходимый для обработки скобок */
top = stk;
/* массив из указателей на функции обрабатывающих 8 возможных команд и комментарии */
int (*prs[])(struct code*) = {prs_0, prs_1, prs_2, prs_3, prs_4, prs_5, prs_6, prs_7, nothing};
/* парсинг */
for(; *ch != ''; ++ch){
p += (*prs[find(*ch)])(p);
};
/* нуль-терминальная команда в конце массива */
(p + 1)->cmd = 0;
};
Для сравнения взял интерпретатор из официального ubuntu репозитория [2] и несколько тестов из этого [3] репозитория. В таблице записано среднее время работы теста в секундах.
Имя теста | Официальный | Из статьи |
---|---|---|
Long | 34 | 20 |
Mandelbrot | 21 | 26 |
EasyOpt | 24 | 27 |
Counter | 34 | 37 |
На всех тестах, кроме первого, официальный интерпретатор работает примерно на 12 процентов быстрее интерпретатора из статьи. В первом тесте, в отличии от остальных, в большинстве циклов количество инструкций > не совпадает с количеством инструкций <. Это делает циклы несбалансированными и не поддающимися оптимизации (другому виду оптимизации, не описанному в статье). Похоже, официальный интерпретатор оптимизирует сбалансированные циклы и получает от этого 12-процентный прирост к скорости, в то время как интерпретатор из статьи этого не делает и побеждает только на первом тесте. Хотя это неплохой результат для такого простого алгоритма оптимизации.
Исходники на Github [4]
Автор: srbgd
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/242403
Ссылки в тексте:
[1] Brainfuck: https://ru.wikipedia.org/wiki/Brainfuck
[2] репозитория: http://packages.ubuntu.com/ru/trusty/bf
[3] этого: https://github.com/rdebath/Brainfuck/tree/master/testing
[4] Github: https://github.com/srbgd/bf
[5] Источник: https://habrahabr.ru/post/321630/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.