Почему компилированный Бейсик выполняется быстро?

[vlad-kras]

Берем программу на бейсике, компилируем и она ускоряется ... в несколько раз. А почему так сильно ускорается, в несколько раз? Часто пишут, что интерпретатору сначала надо проанализировать программу. Но он (наверное) программу, выполняет по строчкам, как разные источники пишут. То есть берет из строки по одной команде, анализирует что за команда и переводит в машинный код. И вот вопрос - неужели интерпретатор самую большую часть времени тратит просто на анализ текста, может еще какие технические причины есть для ускорения?

Например по операторам, в спектруме ключевые слова это же токены, а не строки букв. Значит надо проанализировать не всю строку до пробела, а всего 1 байт и понятно будет что за оператор - для ABS и CLS 1 байт вместо 3 букв, а для PAUSE 5 и RANDOMIZE 9 букв. И кроме того сразу можно сделать таблицу соответствия токен -- адрес его обработки, тогда переход к подпрограмме обработки оператора должен будет выполняться за время о(1), т.е. независимо от числа возможных токенов. Ну ладно, я не знаю как внутри обработка в ROM устроено, может даже не сделали таблицу и выполняют сравнение токенов по цепочке if 200 else if 201 else if 202 итд. Ну все равно, проверка менее 128 вариантов должна выполняться не очень долго.

Потом подумал, что еще другие моменты есть. Например, интерпретатор все время опрашивает клавиатуру на предмет нажатия BREAK, а компилированный код не опрашивает - или тоже опрашивает?
И при выполнении операторов GOTO адрес для строки перехода скорее всего неизвестен интерпретатору, поэтому он начинает анализировать каждую строку программы, выискивая нужную.

Какие еще мысли есть по поводу того, где интерпретатор тормозит, а компилированный бейсик ускоряется?

P.S.

Есть похожая тема
Почему Спектрум-бейсик такой медленный?
https://zx-pk.ru/threads/27831-poche...medlennyj.html

наиболее понятные объяснения в ответах 3,12,25,35,45,53

[Advertiser]

[goodboy]

берет из строки по одной команде, анализирует что за команда и переводит в машинный код.

скорее вызывает свои подпрограммы с полученными параметрами

[Bedazzle]

Какие еще мысли есть по поводу того, где интерпретатор тормозит, а компилированный бейсик ускоряется?

Ну, к примеру, простая команда в ассемблере - jp на нужный адрес выполняется мгновенно.

В бейсике пускай, будет goto 1000. Но... чтобы узнать, где находится строка, на которую требуется переход - нужно взять адрес начала программы из системных переменных, и в цикле пробежаться по тексту программы, разбирая номера строк, и адреса следующей строки.
Для не сильно большой программы чтобы найти номер 1000, может потребоваться перелопатить сотню строк.

[andrews]

И при выполнении операторов GOTO

если есть исходник интерпретатора, то все станет очевидным. Если нет - придется лопатить с дизассемблером и эмулятором. Компиляторы Бейсика аналогично. Оптимизаторы могуn быть разными.

[null_device]

vlad-kras, приколов много. Начиная от того, что в процессе выполнении программы работает куча подпрограмм интерпретатора. Анализатор операторов в строке, калькулятор работы с цифровыми значениями, обработчик поиска значения переменных (числовых, символьных, внутри массивов, циклов, ПП go sub и т.п.), подпрограмма печати на экране символов, обработчик ошибок в конце - концов.
Числовое значение, для оператора PAUSE может содержать, алгебраические выражения (сложение, вычитание и т.п.), так и логические операторы (and, or), которые должен "перемолоть" интерпретатор. Также числовой аргумент команды может быть вызов кода через USR.
А та же RANDOMIZE с числовым параметром, без, и USR - выполняется вполне по разному. Вот за эту гибкость и приходится платить не слишком большим быстродействием.

При компиляции, эта гибкость теряется т.к. операторы бейсика, заменяются вполне определенным набором ассемблерных "кубиков". Плюс, ограничения самих компиляторов - типа целочисленности, ограничения описателей переменных, массивов и фенкционала команд (иногда, до полной невозможности их использования).

[Andrew771]

Полностью поддерживаю null_device, универсализм убивает всё. Я с этим столкнулся, когда писал свой ZX Like Pascal. Компиляторы убивают универсализм по возможности, поэтому намного быстрее

[vlad-kras]

операторы бейсика, заменяются вполне определенным набором ассемблерных "кубиков". Плюс, ограничения самих компиляторов - типа целочисленности, ограничения описателей переменных, массивов и фенкционала команд (иногда, до полной невозможности их использования).

Да, целочисленность в компиляторе хитрая штука, вроде есть числовые операции, но диапазон очень ограничен. Получается совсем другой алогоритм в отличие от бейсика - там числа с плавающей точкой, значит для сложения пары чисел сначала нужно привести их к единой степени, потом одно из них дополнительно округлить и только потом сложение.

А невозможность использования команд на скорость влиять не должна - компилятор скажет, что синус нельзя использовать и на этом остановится. Но если программа есть в бейсике и компилируется нормально, значит она состоит из нормальных допустимых команд.

[null_device]

А невозможность использования команд на скорость влиять не должна - компилятор скажет, что синус нельзя использовать и на этом остановится. Но если программа есть в бейсике и компилируется нормально, значит она состоит из нормальных допустимых команд.

Это, как посмотреть. Дополнительный функционал, любой команды в компилляторе, это как минимум: трата памяти на хранение библиотеки с куском кода, ей соответствующий. И время на поиск нужной библиотеки. А уж вычисление, тех же алгебраических функций, далеко не самое быстрое занятие. Из-за чего, некоторыми даже используется не встроенный в Бейсик калькулятор и процедура печати на экран.

[Barmaley_m]

Берем программу на бейсике, компилируем и она ускоряется ... в несколько раз.

Да, это опьяняет - поначалу. Но всё равно, это ускорение - ничто по сравнению с тем, что можно получить, программируя на ассемблере.

А почему так сильно ускорается, в несколько раз? Часто пишут, что интерпретатору сначала надо проанализировать программу.

Да, надо проанализировать. Синтаксический анализ - очень непростая тема. Особенно, когда начинаешь думать, какие сложные варианты конструкций языка программирования могут встретиться, и их все интерпретатор должен правильно понять и обработать.

Но он (наверное) программу, выполняет по строчкам, как разные источники пишут. То есть берет из строки по одной команде, анализирует что за команда и переводит в машинный код.

По командам, если точнее. В одной строке могут встретиться несколько команд, разделенных двоеточием. Как только интерпретатор доходит до конца команды (последней в строке, или отделенной двоеточием от следующих команд) - то он ее выполняет. Потом переходит к следующей. Принципиальных отличий строк от команд два:
1) На строку можно перейти командой GOTO или GOSUB (исполнение продолжится с первой команды в строке, на которую переходит GOTO/GOSUB). На отдельную (не первую) команду в строке прямо перейти нельзя - нет таких команд. Хотя можно вернуться на вторую и последующие команды в строке с помощью RETURN.
2) Команда REM делает всё, что стоит в строке после нее, недостижимым для исполнения интерпретатором, и потому является последней в строке, где она встретилась.

Интерпретатор не переводит программу в машинный код. Он ее анализирует и, по мере анализа, исполняет действия, которые требуется. Например, встретилась команда BEEP - интерпретатор анализирует её параметры и вызывает подпрограмму в машинных кодах, которая издаёт звук. Встретилась команда DRAW - интерпретатор анализирует параметры и вызывает подпрограмму рисования линии в машинных кодах.

И вот вопрос - неужели интерпретатор самую большую часть времени тратит просто на анализ текста,

Да, это занимает львиную долю процессорного времени. Анализ текста программы - трудная задача. Большинство профессиональных программистов нашего времени не умеют ее решать эффективно и без ошибок. Учили когда-то в университете основы теории, но благополучно забыли и на практике не используют. Попробуй, ради интереса, написать на любом языке программирования, программу вычисления выражений, заданных формулами в текстовом виде. Сразу прочувствуешь всю глубину транса.

может еще какие технические причины есть для ускорения?

Да, есть и еще причины.

Во-первых, как уже говорили выше, для исполнения команд GOTO или GOSUB интерпретатору приходится сканировать весь текст программы, от ее начала, пока он не найдет нужную строку. В компилированной программе можно заранее (на этапе компиляции) рассчитать в памяти место программы, откуда надо продолжить исполнение. Кроме случая "косвенного перехода", когда параметром GOTO или GOSUB является не константа, а переменная или математическое выражение с переменными. Но последний случай не поддерживается большинством компиляторов бейсика. Его поддержка обошлась бы сложно и дорого (по времени исполнения).

Во-вторых, подпрограммы, с помощью которых выполняются конкретные действия (рисование линий, печать символов, выдача звука и т.д.) являются универсальными и потому неэффективными для отдельных частных случаев, где программирование на ассемблере могло бы в десятки и сотни раз увеличить быстродействие.

Наконец, не все подпрограммы действия в машинных кодах эффективны. В свое время я занимался переделкой Спектрум-бейсика, и удалось ускорить исполнение команды CIRCLE в разы, применив более эффективный алгоритм.

Например по операторам, в спектруме ключевые слова это же токены, а не строки букв. Значит надо проанализировать не всю строку до пробела, а всего 1 байт и понятно будет что за оператор - для ABS и CLS 1 байт вместо 3 букв, а для PAUSE 5 и RANDOMIZE 9 букв. И кроме того сразу можно сделать таблицу соответствия токен -- адрес его обработки, тогда переход к подпрограмме обработки оператора должен будет выполняться за время о(1), т.е. независимо от числа возможных токенов.

Токенизация строк - это очень важный момент, и если бы ее не было - то бейсик работал бы в разы медленнее. Большинство интерпретаторов бейсика используют токенизацию для внутреннего представления программы, даже те, где надо набивать операторы по буквам, и токенизации как бы не видно.

Но не токенизацией единой. Кроме самих команд, надо еще обрабатывать параметры, переводить в двоичную форму числа и вычислять выражения. Даже с числами в Спектрум-бейсике применяется трюк: внутреннее представление программы содержит числовые константы в предварительно интерпретированном, двоичном виде. Это внутреннее представление может отличаться от текстового. С этим связан хакерский трюк: реальные числа, с которыми работает программа, могут отличаться от отображаемых, если над внутренним представлением программы провести манипуляции. В программе может стоять команда RANDOMIZE USR 0, но при ее выполнении не произойдет сброс, как ожидается, а будет вызван машинный код совсем с другого адреса.

Но даже и предварительное преобразование числовых констант не решает все проблемы быстродействия. Для вычисления выражений все равно приходится использовать сложные процедуры, которые долго исполняются. А компилятор может один раз проверить синтаксис и преобразовать любое выражение в обратную польскую запись. Даже при сохранении затрат на собственно математические операции, это может в разы повысить быстродействие.

Ну ладно, я не знаю как внутри обработка в ROM устроено, может даже не сделали таблицу и выполняют сравнение токенов по цепочке if 200 else if 201 else if 202 итд.

Конечно, там сделали таблицу. Авторы бейсика, хоть и не боги, но вполне хорошие и опытные программисты уровня гораздо выше среднего (особенно в сравнении с нашим временем). У них можно многому поучиться. Для меня в свое время анализ интерпретатора Спектрум-бейсика был хорошей школой. Два добрых человека Ian Logan & Frank O'Hara провели полное дизассемблирование, анализ и комментирование Спектрум-бейсика, и издали результаты в виде книги. Там каждая команда разжевана, все идеи и алгоритмы расписаны. Очень рекомендую. Гугл в помощь. Был и русский перевод. "Ян логан, Френк о хара"

Потом подумал, что еще другие моменты есть. Например, интерпретатор все время опрашивает клавиатуру на предмет нажатия BREAK, а компилированный код не опрашивает - или тоже опрашивает?

Это от компилятора зависит. Большинство не опрашивают. Но такой опрос не занимает много процессорного времени, даже, если он есть.

[vlad-kras]

Для вычисления выражений все равно приходится использовать сложные процедуры, которые долго исполняются. А компилятор может один раз проверить синтаксис и преобразовать любое выражение в обратную польскую запись. Даже при сохранении затрат на собственно математические операции, это может в разы повысить быстродействие.

Спасибо за подробные ответы