Схема: почему внутреннее определение быстрее, чем внешнее?

Question

Я попытался запустить программу ниже

(define (odd-internal x)
  (define (even x)
    (if (zero? x)
        #t
        (odd-internal (sub1 x))))
  (if (zero? x)
      #f
      (even (sub1 x))))

(define (odd-external x)
  (if (zero? x)
      #f
      (even (sub1 x))))

(define (even x)
  (if (zero? x)
      #t
      (odd-external (sub1 x))))

(begin (display "Using internal definition\n")
       (time (odd-internal 40000000)))

(begin (display "Using external definition\n")
       (time (odd-external 40000000)))

Это результат в Racket

Using internal definition
cpu time: 166 real time: 165 gc time: 0
#f
Using external definition
cpu time: 196 real time: 196 gc time: 0
#f

Там вы можете увидеть, что использование внутреннего определения немного быстрее.Я пробовал работать на Chez Scheme, и результат похож.Почему это так?

Answer 1

Прежде всего, это будет зависеть от вашей реализации, поскольку вложенные определения могут быть реализованы несколькими способами.На моей установке Chez Scheme 9.5 я получаю довольно стабильное время выполнения на 25%, когда я использую odd-internal.

Теперь, почему.Это происходит потому, что вложенные определения (то есть внутренние определения) сильно отличаются от фактических определений.

Когда вы используете define на верхнем уровне, вы добавляете новую запись в таблицу свободных переменных.Всякий раз, когда вы пытаетесь оценить переменную, которая не привязана ни к одной лямбде, она ищется в таблице свободных переменных (хэш).Этот поиск очень эффективен, но он медленнее, чем выбор связанной переменной.Поэтому, когда вы вычисляете (odd-external 40000000), что вы извлекаете even и odd-external из этой таблицы около 40 миллионов раз - даже с кэшированием и другими классными вещами, это все еще работа, которую нужно сделать.

Напротив, вложеннаяопределяет создать связанную переменную.Один из способов их реализации - это вложенные лямбда-выражения / let / letrec.Таким образом функция odd-internal будет преобразована в ^[1] :

(define (odd-internal x)
(let ((even (lambda (x)
              (if (zero? x)
                  #t
                  (odd-internal (sub1 x))))))
  (if (zero? x)
      #f
      (even (sub1 x)))))

(что является упрощением того, что делает схема Chez).
Теперь каждый раз, когда вы применяетеodd-internal это все еще свободная переменная, так что вы хешируете ее и находите ее в таблице свободных переменных.Однако, когда вы применяете even, вы просто извлекаете его из среды (что может стоить всего лишь разыменования памяти даже без хитрых уловок).

Интересным экспериментом будет определение обоих oddи even как связанные переменные, поэтому все выборки с переменными 40 милов выиграют от быстрого времени получения связанных переменных.Я увидел улучшение на 16% по сравнению с исходными 25%.Вот код:

(define (odd-quick x)
    (define (odd x) (if (zero? x) #f (even (sub1 x))))
    (define (even x) (if (zero? x) #t (odd (sub1 x))))
    (odd x))

---

^_[1] let - синтаксический suger для приложения lambda, поэтому вы можете прочитать, чтокод как:

(define (odd-internal x)
    ((lambda (even)
      (if (zero? x)
          #f
          (even (sub1 x))))
     (lambda (x)
       (if (zero? x)
           #t
           (odd-internal (sub1 x))))))

Answer 2

Я был поражен, что это было разницей, поэтому из комментариев Lexis я разделил две версии в каждом их файле internal.rkt и external.rkt, скомпилировал и декомпилировал их следующим образом:

raco make external.rkt
raco decompile compiled/external_rkt.zo

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

(define (odd-external x1)
  (if (zero? x1)
      '#f
      (let ((x2 (sub1 x1)))
        (if (zero? x2)
            '#t
            (let ((x3 (sub1 x2)))
              (if (zero? x3)
                  '#f
                  (let ((x4 (sub1 x3)))
                    (if (zero? x4)
                        '#t
                        (let ((x5 (sub1 x4)))
                          (if (zero? x5) '#f (even (sub1 x5))))))))))))

(define (even x1)
  (if (zero? x1)
       '#t
       (let ((x2 (sub1 x1)))
         (if (zero? x2)
           '#f
           (let ((x3 (sub1 x2)))
             (if (zero? x3)
               '#t
               (let ((x4 (sub1 x3)))
                 (if (zero? x4)
                   '#f
                   (let ((x5 (sub1 x4)))
                     (if (zero? x5)
                       '#t
                       (let ((x6 (sub1 x5)))
                         (if (zero? x6)
                           '#f
                           (let ((x7 (sub1 x6)))
                             (if (zero? x7)
                               '#t
                               (odd-external (sub1 x7))))))))))))))))

Ничего особенного здесь нет.Раскручивает петлю определенное время и постоянные сгибы.Обратите внимание, что у нас все еще есть взаимная рекурсия, и что развертывание происходит 5 и 7 раз.Константа была даже константно свернута, поэтому она заменила мой вызов на (even 399999995), поэтому компилятор также выполнил код на 5 оборотов и сдался.Интересная вещь - это внутренняя версия:

(define (odd-internal x1)
  (if (zero? x1)
      '#f
      (let ((x2 (sub1 x1)))
        (if (zero? x2)
            '#t
            (let ((x3 (sub1 x2)))
              (if (zero? x3)
                  '#f
                  (let ((x4 (sub1 x3)))
                    (if (zero? x4)
                        '#t
                        (let ((x5 (sub1 x4)))
                          (if (zero? x5)
                              '#f
                              (let ((x6 (sub1 x5)))
                                (if (zero? x6)
                                    '#t
                                    (let ((x7 (sub1 x6)))
                                      (if (zero? x7)
                                          '#f
                                          (let ((x8 (sub1 x7)))
                                            (if (zero? x8)
                                                '#t
                                                (odd-internal
                                                 (sub1 x8))))))))))))))))))

Это больше не взаимная рекурсия, поскольку она вызывает себя после 8 раз.Каждый раунд делает 8 ходов, в то время как другая версия делала 7, а затем 5 .. В двух раундах внутренний выполнил 16 раундов, в то время как у другого - 12. Первоначальный вызов внутреннего - (odd-internal '399999992), поэтому компилятор выполнил 8 раундов.прежде чем сдаться.

Я полагаю, что код в стороне функций на уровне декомпилятора имеет открытую кодировку, и код на каждом шаге очень дешев, что делает количество вызовов причиной увеличения скорости на 25%.В конце концов, еще 4 - это на 25% больше за рекурсию, что совпадает с разницей во времени вычислений.Это предположения, основанные на наблюдении, поэтому было бы интересно получить комментарий от Лекси по этому поводу.

Answer 3

Ваши цифры слишком малы, чтобы быть значимыми.Разница между 166 мс и 196 мс в абсолютном выражении крошечная.Кто знает, какие другие факторы могут влиять на это?Время разогрева виртуальной машины, различия в распределении памяти или любые другие факторы могут легко привести к несоответствию этого размера.Чтобы быть уверенным, вы должны сделать цифры намного больше.

На моей машине с Racket v7.0 я увеличил аргументы с 40000000 до 1000000000 и запустил программу.Результаты составили 2,306 с для случая внутреннего определения и 2,212 с для случая внешнего определения.Учитывая перечисленные выше факторы, эта разница слишком мала, чтобы быть значимой.

Сравнительный анализ сложен, а сравнительные тесты языков, которые работают на виртуальных машинах и JIT-компилируются, сложнее.Даже если вы учитываете разминку и сборку мусора, выполняете много итераций и берете средние значения, и, как правило, пытаетесь все сделать правильно, полученные результаты могут быть практически бессмысленными, так как документ OOPSLA 2017 года Виртуальная машина разогревается иCold объясняет:

Виртуальные машины (VM) с компиляторами Just-In-Time (JIT) традиционно считаются выполняющими программы в два этапа: начальный этап прогрева определяет, какие части программыбольше всего выиграет от динамической компиляции до JIT-компиляции этих частей в машинный код;впоследствии говорят, что программа находится в устойчивом состоянии максимальной производительности.Методологии измерений почти всегда отбрасывают данные, собранные на этапе прогрева, так что результаты измерений полностью сосредоточены на максимальной производительности.Мы вводим полностью автоматизированный статистический подход, основанный на анализе точек изменения, который позволяет нам определить, достигла ли программа устойчивого состояния и, если да, то представляет ли это пиковую производительность или нет.Используя это, мы показываем, что даже при работе в наиболее контролируемых обстоятельствах небольшие, детерминированные, широко изученные микробенчмарки часто не достигают устойчивого состояния пиковой производительности на различных распространенных виртуальных машинах .Повторяя наш эксперимент на 3 разных машинах, мы обнаружили, что самое большее 43,5% пар «эталонных», VM, последовательно достигают устойчивого состояния пиковой производительности.

Подчеркните мое.Убедитесь, что вы измеряете то, что, по вашему мнению, измеряете.