Почему `let 'быстрее с лексической областью?

31

Читая исходный код dolistмакроса, я наткнулся на следующий комментарий.

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

Который ссылался на этот фрагмент (который я упростил для ясности).

(if lexical-binding
    (let ((temp list))
      (while temp
        (let ((it (car temp)))
          ;; Body goes here
          (setq temp (cdr temp)))))
  (let ((temp list)
        it)
    (while temp
      (setq it (car temp))
      ;; Body goes here
      (setq temp (cdr temp)))))

Меня удивило то, что letформа используется внутри цикла. Раньше я думал, что это медленно по сравнению с многократным использованием setqодной и той же внешней переменной (как это было сделано во втором случае выше).

Я бы отклонил это как ничто, если бы не комментарий сразу над ним, явно говоря, что это быстрее, чем альтернатива (с лексическим связыванием). Итак ... Почему это?

  1. Почему приведенный выше код отличается по производительности в лексическом и динамическом связывании?
  2. Почему letформа быстрее с лексической?
Malabarba
источник

Ответы:

38

Лексическое связывание и динамическое связывание в целом

Рассмотрим следующий пример:

(let ((lexical-binding nil))
  (disassemble
   (byte-compile (lambda ()
                   (let ((foo 10))
                     (message foo))))))

Он компилирует и сразу разбирает простое lambdaс локальной переменной. При lexical-bindingотключенном, как указано выше, байт-код выглядит следующим образом:

0       constant  10
1       varbind   foo
2       constant  message
3       varref    foo
4       call      1
5       unbind    1
6       return    

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

Если вы привяжете lexical-bindingк tприведенному выше примеру, байт-код выглядит несколько иначе:

0       constant  10
1       constant  message
2       stack-ref 1
3       call      1
4       return    

Обратите внимание, что varbindи varrefполностью ушли. Локальная переменная просто помещается в стек и на нее ссылается постоянное смещение через stack-refинструкцию. По сути, переменная связана и считывается с постоянным временем , считывание и запись в стековую память , которая является полностью локальной и, таким образом, хорошо работает с параллелизмом и кэшированием ЦП , и вообще не включает никаких строк.

Как правило, при поиске лексической привязки локальных переменных (например let, setqи т. Д.) Время выполнения и сложность памяти значительно меньше .

Этот конкретный пример

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

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

С лексической привязкой, letс дешевы. Примечательно, что letвнутри тела цикла не хуже (с точки зрения производительности), чем letснаружи тела цикла. Следовательно, совершенно нормально связывать переменные настолько локально, насколько это возможно, и держать переменную итерации только в теле цикла.

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

0       varref    list            0       varref    list         
1       constant  nil             1:1     dup                    
2       varbind   it              2       goto-if-nil-else-pop 2 
3       dup                       5       dup                    
4       varbind   temp            6       car                    
5       goto-if-nil-else-pop 2    7       stack-ref 1            
8:1     varref    temp            8       cdr                    
9       car                       9       discardN-preserve-tos 2
10      varset    it              11      goto      1            
11      varref    temp            14:2    return                 
12      cdr       
13      dup       
14      varset    temp
15      goto-if-not-nil 1
18      constant  nil
19:2    unbind    2
20      return    

Я понятия не имею, однако, что вызывает разницу.

lunaryorn
источник
7

Короче говоря - динамическое связывание очень медленное. Лексическое связывание очень быстро во время выполнения. Основная причина заключается в том, что лексическое связывание может быть разрешено во время компиляции, в то время как динамическое связывание не может.

Рассмотрим следующий код:

(let ((x 42))
    (foo)
    (message "%d" x))

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

Но подождите - это еще не все. При лексическом связывании компилятор может проверить, что это конкретное связывание xиспользуется только в коде message; так xкак никогда не модифицируется, безопасно встроить xи дать

(progn
  (foo)
  (message "%d" 42))

Я не думаю, что текущий компилятор байт-кода выполняет эту оптимизацию, но я уверен, что это произойдет в будущем.

Итак, вкратце:

  • динамическое связывание - это тяжелая операция, которая дает мало возможностей для оптимизации;
  • лексическое связывание - легкая операция;
  • лексическое связывание значения только для чтения часто может быть оптимизировано.
JCH
источник
3

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

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

GSG
источник
1
Нет varbindв коде, скомпилированном под лексической привязкой. В этом весь смысл и цель.
lunaryorn
Хм. Я создал файл, содержащий вышеупомянутый источник, начиная с ;; -*- lexical-binding: t -*-, загрузил его и вызвал (byte-compile 'sum1), предполагая, что произвел определение, скомпилированное с лексической привязкой. Тем не менее, похоже, что нет.
GSG
Удалены комментарии к байт-коду, так как они основаны на неверном предположении.
GSG
ответ показывает lunaryon, что этот код явно находится быстрее под лексическим связыванием (хотя, конечно , только на микроуровне).
Шости
@gsg Это объявление - просто стандартная файловая переменная, которая не влияет на функции, вызываемые извне соответствующего файлового буфера. IOW, это имеет эффект, только если вы посещаете исходный файл и затем вызываете byte-compileс соответствующим текущим буфером, что, кстати, именно то, что делает байтовый компилятор. Если вы вызываете byte-compileотдельно, вам нужно явно установить lexical-binding, как я сделал в своем ответе.
Лунный Рог