Как можно использовать байт-код для оптимизации времени выполнения динамических языков?

Question

Меня интересуют некоторые методы оптимизации или общие схемы байт-кода, которые могут ускорить выполнение с использованием VM по сравнению с интерпретацией AST.

Answer 1

Главный выигрыш в интерпретации AST по сравнению с байт-кодом - это операционная рассылка, для сильно оптимизированных интерпретаторов это начинает представлять собой настоящую проблему. «Отправка» - это термин, используемый для описания накладных расходов, необходимых для начала выполнения операции (например, арифметика, доступ к свойствам и т. Д.). переводчик на основе

Довольно нормальное AST будет выглядеть примерно так:

class ASTNode { 
    virtual double execute() = 0; 
} 

class NumberNode { 
    virtual double execute() { return m_value; } 
    double m_value; 
} 

class AddNode { 
    virtual double execute() { return left->execute() + right->execute(); } 
} 

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

В интерпретатором байт-кода у вас есть вам другую модель доставки - а не виртуальных вызовов у вас есть цикл выполнения, сродни:

while (1) { 
    switch (op.type) { 
     case op_add: 
      // Efficient interpreters use "registers" rather than 
      // a stack these days, but the example code would be more 
      // complicated 
      push(pop() + pop()); 
      continue; 
     case op_end: 
      return pop(); 
    } 
} 

Это все еще имеет достаточно дорогую стоимость доставки против нативного кода, но намного быстрее, чем виртуальная отправка. Вы можете еще больше улучшить perf, используя расширение gcc, называемое «вычисленным goto», которое позволяет удалить диспетчерский коммутатор, сократив общую стоимость отправки до одной единственной непрямой ветви.

В дополнение к улучшению затрат на отправку байт-коды на основе байт-кода имеют ряд дополнительных преимуществ перед интерпретаторами AST, в основном из-за способности «байт-кода» «перейти» в другие места, поскольку реальная машина, например, представила фрагмент кода, как это:

while (1) { 
    ...statements... 
    if (a) 
     break; 
    else 
     continue; 
} 

чтобы реализовать это правильно каждый раз заявление выполняется, вам нужно будет указать, означает ли выполнение, чтобы остаться в петле или остановки, так что цикл выполнения становится чем-то вроде:

while (condition->execute() == true) { 
    for (i = 0; i < statements->length(); i++) { 
     result = statements[i]->execute(); 
     if (result.type == BREAK) 
      break; 
     if (result.type == CONTINUE) 
      i = 0; 
    } 
} 

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

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

Наконец интерпретатор AST по определению является рекурсивным, и поэтому должно быть предотвращено от переполнения стека системы, которая ставит очень жесткие ограничения на сколько вы можете рекурсию в своем коде, что-то вроде:

1+(1+(1+(1+(1+(1+(1+(1+1))))))) 

Имеет 8 уровней рекурсии (по крайней мере) в интерпретаторе - это может быть очень значительная стоимость; более старые версии Safari (pre-SquirrelFish) использовали интерпретатор AST, и по этой причине JS разрешалось использовать только несколько сотен уровней рекурсии против 1000 в современных браузерах.

Answer 2

Возможно, вы можете посмотреть на различные методы, которые предоставляет инструмент «opt» . Это оптимизация байт-кода-байт-кода, и сам инструмент будет обеспечивать анализ преимуществ применения конкретной оптимизации.