Что заставляет эту функцию работать намного медленнее?

Question

Я пытался провести эксперимент, чтобы проверить, хранятся ли локальные переменные в функциях в стеке.

Так что я написал небольшой тест производительности

function test(fn, times){ 
    var i = times; 
    var t = Date.now() 
    while(i--){ 
     fn() 
    } 
    return Date.now() - t; 
} 
ene 
function straight(){ 
    var a = 1 
    var b = 2 
    var c = 3 
    var d = 4 
    var e = 5 
    a = a * 5 
    b = Math.pow(b, 10) 
    c = Math.pow(c, 11) 
    d = Math.pow(d, 12) 
    e = Math.pow(e, 25) 
} 
function inversed(){ 
    var a = 1 
    var b = 2 
    var c = 3 
    var d = 4 
    var e = 5 
    e = Math.pow(e, 25) 
    d = Math.pow(d, 12) 
    c = Math.pow(c, 11) 
    b = Math.pow(b, 10) 
    a = a * 5 
} 

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

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

Пример:

> test(straight, 10000000) 
30 
> test(straight, 10000000) 
32 
> test(inversed, 10000000) 
390 
> test(straight, 10000000) 
392 
> test(inversed, 10000000) 
390 

такое же поведение при испытании в альтернативном порядке.

> test(inversed, 10000000) 
25 
> test(straight, 10000000) 
392 
> test(inversed, 10000000) 
394 

Я проверил его как в браузере Chrome и в Node.js и у меня нет абсолютно никакого понятия, почему бы это случилось. Эффект длится до тех пор, пока я не обновляю текущую страницу или не перезапустите Node REPL.

Что может быть источником таких значительных (в 12 раз хуже) характеристик?

PS. Так как это работает только в некоторых условиях, напишите среду, которую вы используете для ее проверки.

Mine были:

ОС: Ubuntu 14,04
Узел v0.10.37
Chrome 43.0.2357.134 (Official Build) (64-разрядная версия)

/Edit
На Firefox 39 она занимает ~ 5500 мс для каждого теста независимо от порядка. Кажется, это происходит только на определенных двигателях.

/Edit2
Включение функции в тестовую функцию заставляет ее работать всегда в одно и то же время.
Возможно ли, что существует оптимизация, которая включает параметр функции, если она всегда является одной и той же функцией?

Answer 1

После того, как вы называете test с двумя различными функциями fn() callsite внутри становится megamorphic и V8 не может встраивать в него.

вызов функций (в отличие от вызовов метода o.m(...)) в V8 сопровождаются один элемент инлайн кэша вместо истинного полиморфного кэша инлайн.

Поскольку V8 не может подключаться к контактному сайту fn(), он не может применить различные варианты оптимизации к вашему коду.Если вы посмотрите на свой код в IRHydra (я загрузил артефакты компиляции в суть для вашего удобства), вы заметите, что первая оптимизированная версия test (когда она была специализирована для fn = straight) имеет полностью пустой основной цикл.

V8 просто встраиваемый straight и удалены всего кода ваш надеялся бенчмарка с оптимизацией Dead Code Elimination. В более старой версии V8 вместо DCE V8 будет просто вытаскивать код из цикла через LICM - потому что код полностью петлевый инвариант.

Когда straight не является накладным, V8 не может применять эти оптимизации - отсюда разница в производительности. Новые версии V8 будет по-прежнему применяться к ДХЭ straight и inversed сами превращая их в пустые функции

так разница в производительности не так велика (около 2-3х). Старые V8 не были достаточно агрессивны с DCE, и это проявилось бы в большей разнице между inlined и not-inlined случаями, потому что максимальная производительность вложенного случая была исключительно результатом агрессивного цикла-инвариантного движения кода (LICM).

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

Если вас интересует полиморфизм и его последствия в V8, ознакомьтесь со своим сообщением "What's up with monomorphism" (раздел «Не все кэши - это одни и те же» разговоры о тайниках, связанных с вызовами функций). Я также рекомендую прочитать один из моих разговоров об опасностях микромаркетинга, например. последнее сообщение "Benchmarking JS" talk from GOTO Chicago 2015 (video) - это может помочь вам избежать распространенных ошибок.

Answer 2

Вы недопонимаете стек.

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

var x = 1; 
var y = 2; 

x = x + 1; 
y = y + 1; 

переводит на что-то вроде

push 1 ; x 
push 2 ; y 

; get y and save it 
pop tmp 
; get x and put it in the accumulator 
pop a 
; add 1 to the accumulator 
add a, 1 
; store the accumulator back in x 
push a 
; restore y 
push tmp 
; ... and add 1 to y 

В самом деле, реальный код больше, как это:

push 1 ; x 
push 2 ; y 

add [bp], 1 
add [bp+4], 1 

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

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

Answer 3

Включение функции в тестовую функцию заставляет ее работать всегда в одно и то же время.
Возможно ли, что существует оптимизация, которая включает параметр функции, если она всегда является одной и той же функцией?

Да, это похоже на то, что вы наблюдаете. Как уже упоминалось @Luaan, компилятор, вероятно, в любом случае сбрасывает тела ваших straight и inverse функций, потому что они не имеют никаких побочных эффектов, но только манипулируют некоторыми локальными переменными.

Когда вы вызываете test(…, 100000) в первый раз, оптимизирующий компилятор реализует после некоторых итераций, вызываемых fn(), всегда является одним и тем же, и делает его встроенным, избегая дорогостоящего вызова функции. Все, что он делает сейчас, составляет 10 миллионов раз, декрементируя переменную и тестируя ее против 0.

Но когда вы звоните test с другим fn, тогда он должен де-оптимизировать. Позднее он может сделать некоторые другие оптимизации, но теперь, зная, что есть две различные функции, которые можно назвать, они больше не могут их встроить.

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

эксперимент, чтобы увидеть, если локальные переменные в функции хранятся в стеке

Что касается вашего фактического вопроса, нет, одиночные переменные не хранятся в стеке (stack machine), но в регистрах (register machine). Не имеет значения, в каком порядке они объявлены или используются в вашей функции.

Тем не менее, они хранятся на the stack, как часть так называемых «стоп-кадров». У вас будет один кадр на вызов функции, сохраняя переменные контекста его выполнения. В вашем случае, стек может выглядеть следующим образом:

[straight: a, b, c, d, e] 
[test: fn, times, i, t] 
…