Компиляция "на лету"
В предыдущем разделе мы говорили о программах, которые пишут программы. В каждом примере программы генерировались в виде исходного кода и, стало быть, для запуска должны были быть скомпилированы или нтерпретированы. Однако возможно сгенерировать код, который можно запускать сразу, создавая машинные инструкции, а не исходный текст, такой процесс известен как компиляция "налету" (on the fly) или "как раз вовремя" (just in time); первый термин появился раньше, однако последний – включая его акроним JIT – более популярен.
Очевидно, что скомпилированный код по определению получается непереносимым – его можно запустить только на конкретном типе процессора, зато он может получиться весьма скоростным. Рассмотрим такое выражение:
max (b, c/2)
Здесь нужно вычислить с, поделить его на 2, сравнить результат с b и выбрать большее из значений. Если мы будем вычислять это выражение, используя виртуальную машину, которую мы в общих чертах описали в начале этой главы, то хотелось бы избежать проверки деления на ноль в divop: поскольку 2 никогда не. будет нулем, такая проверка попросту бессмысленна. Однако ни в одном из проектов, придуманных нами для реализации этой виртуальной машины, нет возможности избежать этой проверки – во всех реализациях операции деления проверка делителя на ноль осуществляется в обязательном порядке.
Вот здесь-то нам и может помочь динамическая генерация кода. Если мы будем создавать непосредственно код для выражения, а не использовать предопределенные операции, мы сможем исключить проверку деления на ноль для делителей, которые заведомо отличны от нуля. На самом деле мы можем пойти еще дальше: если все выражение является константой, как, например, max(3*3, 2/2), мы можем вычислить его единожды, при генерации кода, и заменять константой-значением, в данном случае числом 9. Если такое выражение используется в цикле, то мы экономим время на его вычисление при каждом проходе цикла. При достаточно большом числе повторений цикла мы с лихвой окупим время, потраченное на дополнительный разбор выражения при генерации кода.
Основная идея состоит в том. что способ записи позволяет нам вообще выразить суть проблемы, а компилятор для выбранного способа записи может специально оптимизировать код конкретного вычисления, Например, в виртуальной машине для регулярных выражений у нас, скорее всего, будет оператор для сравнения с символом:
Однако, когда мы генерируем код для конкретного шаблона, значение этого literal фиксировано, например 'х', так что мы можем вместо показанного выше сравнения использовать оператор вроде следующего:
И затем, вместо того чтобы предварительно определять специальный оператор для значения каждого символа-литеры, мы можем поступить проще: генерировать код для операторов, которые нам будут действительно нужны для данного выражения. Применив эту идею для полного набора операторов, мы можем написать JlT-компилятор, который будет транслировать заданное регулярное выражение в специальный код, оптимизированный именно под это выражение.
Кен Томпсон (Ken Thompson) именно это и сделал в 1967 году для реализации регулярных выражений на машине IBM 7094. Его версия генерировала в двоичном коде небольшие блоки команд этой машины для разных операторов выражения, сшивала их вместе и затем запускала получившуюся программу, просто вызвав ее, совсем как обычную функцию. Схожие технологии можно применить для создания специфических последовательностей команд для обновлений экрана в графических системах, где может быть так много различных случаев, что гораздо более эффективно создавать динамический код для каждого из них, чем расписать с все заранее или включить сложные проверки в более общем коде.
Демонстрация того, что же включает в себя создание полноценного Т-компилятора, неизбежно вынудит нас обратиться к деталям конкретных наборов команд, однако все же стоит потратить некоторое время, чтобы на деле понять, как работает такая система. В оставшейся части этого параграфа для нас важно будет понимание сути, идеи происходящего, а не деталей конкретных реализаций.