Как встраивание более эффективно, чем рекурсивное определение?

Question

Учебник "Мои парадигмы программирования", Основы языков программирования (3-е изд.) , глава 1 содержит упражнение:

Упражнение 1.12

Устранить один вызов subst-in-s-exp в subst: заменив его определением и упростив получившийся процедура. Результатом будет версия subst, которая не нужна субст-в-е-ехр. Эта техника называется встраиванием и используется оптимизирующие компиляторы.

Исходный код будет иметь две функции: subst и subst-in-sexp, которые в основном заменяют все вхождения старого символа новым символом в списке ввода.

(define subst
  (lambda (new old slist)
    (if (null? slist) '()
        (cons
         (subst-in-s-exp new old (car slist))
         (subst new old (cdr slist))))))

(define subst-in-s-exp
  (lambda (new old sexp)
    (if (symbol? sexp)
        (if (eqv? sexp old) new sexp)
        (subst new old sexp))))

Ответ на этот вопрос заключается в устранении subst-in-sexp, который становится таким

(define subst
  (lambda (slist old new)
    (cond
      [ (null? slist) '()]
      [ (eqv? (car slist) old) (cons new (subst (cdr slist) old new))]
      [ else (cons (car slist) (subst (cdr slist) old new))])))

Почему встраивание лучше, кроме того, что оно может быть намного короче (меньше места)? Меняется ли размер рекурсии? Другими словами, создает ли это встраивание меньше элементов стека?

Кроме того, как я могу использовать эту идею, чтобы ускорить мой код на C ++, Python и Java? Могу ли я легко расширить эту идею? Спасибо.

Я отметил это на Схеме (на самом деле, в Ракете), потому что это выбор языка в книге.

Answer 1

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

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

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

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

Answer 2

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

Например: предположим, у меня есть функция с именем f:

(define (f x) (+ (* x x) 3.0))

... и я называю ее встроенной:

(+ (f 3.2) (g 3.9))

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

Answer 3

В ответ на вопрос: «Как я могу использовать эту идею, чтобы ускорить мой код на C ++, Python и Java?»

Я не думаю, что среда исполнения Python выполняет такие функции, как автоматическое встраивание небольших методов. (Если это не так, кто-то, пожалуйста, поправьте меня!) Так что в Python, если у вас есть фрагмент кода, который очень чувствителен к производительности, возможно, выполняется десятки тысяч или миллионы раз во внутреннем цикле, Вы можете попробовать встроить вручную. Только делайте это, если код действительно является узким местом, и он действительно должен быть настолько быстрым, насколько это возможно, и всегда проверять, действительно ли такая оптимизация помогает. (Если вы попытаетесь вставить что-то, а это не поможет, лучше отменить оптимизацию, потому что встраивание, как правило, затруднит чтение вашего кода.)

В Java и C ++ любой хороший компилятор встроит небольшие методы для вас. То, что может (иногда) делать, - это помочь компилятору увидеть, что метод может быть встроенным. Если точный вызываемый метод зависит от типа объекта во время выполнения (как при использовании методов virtual в C ++), компилятор не сможет встроить вызов. Методы static в Java могут быть легко встроены, и объявление методов как final (когда это имеет смысл) также может позволить компилятору встроить.

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