Почему этот оптимизационный оптимизатор Lua улучшает производительность?

Question

Я просматриваю код сценария document that describes various techniques to improve performance of Lua, и я шокирован тем, что такие трюки потребуются. (Хотя я цитирую Lua, я видел похожие хаки в Javascript).

Почему это оптимизация требуется:

Например, код

for i = 1, 1000000 do 
    local x = math.sin(i) 
end 

работает 30% медленнее, чем это:

local sin = math.sin 
for i = 1, 1000000 do 
    local x = sin(i) 
end 

Они повторно -declaring sin функция локально.

Зачем это было бы полезно? Это все-таки задача компилятора. Почему программист должен выполнять работу компилятора?

Я видел подобные вещи в Javascript; и поэтому, очевидно, должен быть очень Хорошая причина, почему интерпретатор не выполняет свою работу. Что это?

---

Я вижу его неоднократно в среде Lua, в которой я возился; переменные для переопределения переменных как локальные:

local strfind = strfind 
local strlen = strlen 
local gsub = gsub 
local pairs = pairs 
local ipairs = ipairs 
local type = type 
local tinsert = tinsert 
local tremove = tremove 
local unpack = unpack 
local max = max 
local min = min 
local floor = floor 
local ceil = ceil 
local loadstring = loadstring 
local tostring = tostring 
local setmetatable = setmetatable 
local getmetatable = getmetatable 
local format = format 
local sin = math.sin 

Что здесь происходит, что люди должны выполнять работу компилятора? Является ли компилятор запутанным, как найти format? Почему это проблема, с которой программист должен иметь дело? Почему в 1993 году этого не позаботились?

---

Я также, кажется, попал логический парадокс:

1. Оптимизация не должна быть сделана без профилирования
2. Lua не имеет возможностей быть профилированным
3. Lua не должно быть оптимизирован

Answer 1

Почему это полезно? Это все-таки задача компилятора. Почему программист должен выполнять работу компилятора?

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

Основная структура Lua (а также только) - это таблица. math - это просто таблица, хотя она используется как пространство имен. Никто не может помешать вам изменить функцию math.sin где-нибудь в цикле (даже подумал, что это будет неразумно), и компилятор не может знать, что при компиляции кода. Поэтому компилятор делает именно то, что вы ему поручите: на каждой итерации цикла найдите функцию sin в таблице math и вызовите ее.

Теперь, если ВЫ знаете, что вы не собираетесь изменять math.sin (т. Е. Вы собираетесь называть ту же функцию), вы можете сохранить его в локальной переменной вне цикла. Поскольку нет поиска в таблице, полученный код выполняется быстрее.

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

Что касается переменных «redeclaring variables as local» - много раз при определении модуля вы хотите работать с исходной функцией. При доступе к pairs, max или чему-либо, используя их глобальные переменные, никто не может заверить вас, что это будет одна и та же функция для каждого вызова. Например, stdlib переопределяет множество глобальных функций.

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

Update: Я только что прочитал Lua Performance Tips Роберто Ierusalimschy, один из авторов Lua, и это в значительной степени объясняет все, что вам нужно знать о Lua, производительности и оптимизации. ИМО наиболее важные правила:

Правило № 1: Не делайте этого.

Правило № 2: Не делайте этого еще. (Только для экспертов)

Answer 2

Мое предположение заключается в том, что в оптимизированной версии, поскольку ссылка на функцию хранится в локальной переменной, обход дерева не обязательно должен выполняться на каждой итерации цикла for (для поиска по math.sin).

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

Затем снова, я мог бы WAY покинуть базу;)

Edit: Я также предполагаю, что компилятор Lua туп (который является общим предположением для меня о компиляторов так или иначе;))

Answer 3

Сохранение функции в локальных переменных удаляет индексирование таблицы для поиска функциональной клавиши каждой итерации цикла, математические очевидны, так как нужно искать хэш в таблице Math, а другие нет, они индексируются в _G (глобальная таблица), которая теперь составляет _ENV (таблица окружения) по 5.2.

Кроме того, вы должны иметь возможность профилировать lua с помощью API-интерфейсов отладки или использовать отладчики lua, лежащие вокруг.

Answer 4

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

Что касается видимости (например, с функцией формата): локальный скрывает глобальный. Поэтому, если вы объявляете локальную функцию с тем же именем, что и глобальная, локальная будет использоваться вместо этого, пока она находится в области видимости. Если вы хотите использовать глобальную функцию, используйте _G.function.

Если вы действительно хотите быстрый Lua, вы можете попробовать LuaJIT

Answer 5

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

Выполнение этого по умолчанию является неправильным.

Это, возможно, полезно использовать локальные ссылки вместо таблицы обращается, когда функция используется снова и снова, как в вашем примере цикла:

local sin = math.sin 
for i = 1, 1000000 do 
    local x = sin(i) 
end 

Однако, вне петли, накладные расходы добавления таблицы доступ совершенно ничтожен.

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

Поскольку два образца кода, которые вы сделали выше, не означают абсолютно то же самое.

Это не так, как функция может меняться во время моей работы.

Lua очень динамичный язык, и вы не можете сделать то же предположение, чем в других более ограничительных языках, как C. Функция может изменения в то время как ваш цикл работает. Учитывая динамический характер языка, компилятор не может предположить, что функция не изменится. Или, по крайней мере, не без сложного анализа вашего кода и его последствий.

Фокус в том, что даже если ваши две части кода выглядят эквивалентными, в Lua они не являются. На первом вы явно говорите ему, чтобы «получить функцию sin внутри математического стола на каждой итерации». На втором вы снова и снова используете одну ссылку на одну и ту же функцию.

Рассмотрим это:

-- The first 500000 will be sines, the rest will be cosines 
for i = 1, 1000000 do 
    local x = math.sin(i) 
    if i==500000 then math.sin = math.cos end 
end 

-- All will be sines, even if math.sin is changed 
local sin = math.sin 
for i = 1, 1000000 do 
    local x = sin(i) 
    if i==500000 then math.sin = math.cos end 
end 

Answer 6

Это не просто ошибка/особенность Lua многие языки, включая Java и C будет работать быстрее, если доступ локальных значений вместо значений из области видимости, например, от класс или массив.

Например, в C++ доступ к локальному члену быстрее, чем к доступу к членам переменной класса.

Это сосчитать до 10000 быстрее:

for(int i = 0; i < 10000, i++) 
{ 
} 

чем:

for(myClass.i = 0; myClass.i < 10000; myClass.i++) 
{ 
} 

Причина Lua имеет глобальное значение внутри таблицы, потому что это позволяет программисту быстро сохранить и изменить глобальную окружающую среду просто изменив таблицу, ссылающуюся на _G. Я согласен с тем, что было бы неплохо иметь некоторый «синтаксический сахар», который рассматривал глобальную таблицу _G как особый случай; переписывая их как локальные переменные в области файлов (или что-то подобное), конечно, нет ничего, что мешает нам сделать это сами; возможно, функция optGlobalEnv (...), которая «локализует» таблицу _G и ее членов/значений в «области файлов», используя unpack() или что-то в этом роде.