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

Question

Я просматриваю документ , в котором описываются различные методы повышения производительности кода сценария 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

Они повторно декларируют 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. У Луа нет возможности быть профилированным
3. Lua не должен быть оптимизирован

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

я вижу это неоднократно в среде 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 4

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

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

Answer 5

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

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

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

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

than:

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

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

Answer 6

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

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

Опять же, я мог бы уйти с базы;)

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