Безресурсные (stateless) итераторы в Lua для оптимизации работы циклов

Опубликовано:

Замыкания требуют динамического расхода памяти, и если их много, это создает нагрузку на сборщик мусора, что может приводить к замедлению работы программы. Посмотрим, как эта проблема решается в Lua через создание так называемых итераторов без состояния, и как они связаны с особенностями работы цикла for...in....

Вернемся к нашему самописному примеру фабрики итераторов (генератору):

local function r_ipairs(t)
    local index = #t + 1   -- #t - длина массива и последний индекс
    return function()
        index = index - 1
        if index > 0 then
            return index, t[index]
        else
            return nil
        end
    end
end

local array = {'apple', 'banana', 'pineapple'}

for i, v in r_ipairs(array) do
    print(i, v)
end

3       pineapple
2       banana
1       apple

Как мы выяснили ранее при его вызове в памяти создается объект-замыкание, то есть происходит аллокация памяти — ее выделение, в данном случае под саму анонимную функцию и связанные с ней переменные. Когда цикл for...in... проитерирует свое замыкание, так как ссылок на него больше нет, оно станет мусором в памяти.

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

Безресурсные итераторы по-другому называют бессостоятельными, то есть итераторами без состояния (stateless iterators). В противовес им итераторы на основе замыканий являются состоятельными, то есть итераторами с состоянием (stateful iterators). Хотя безресурсные делают код менее ясным и удобным для программиста, в процессе выполнения программы память динамически на них не выделяется, а значит сборщику мусора не приходится часто работать.

Возможность использования безресурсных итераторов в Lua реализуется через внутренние особенности цикла for...in.... У него есть три скрытые переменные (не имеют отношения к тем, что указываются до in). Одной присваивается ссылка на объект-итератор (итерационную функцию), другой — на таблицу (инвариантные данные), третьей — индекс (меняется).

В тех случаях когда цикл при вызове генератора получает только итератор, двум оставшимся переменным присваивался nil. Их значения игнорируются, ведь итератор с замыканием сам хранит свои состояния и "знает", что возвращать на каждом следующем шаге.

Бессостоятельный итератор ничего в себе не хранит. Это обычная статичная функция в памяти, которая создается в момент запуска программы, а не динамически в процессе выполнения. Генератор, возвращающий такой итератор, на самом деле возвращает не его как объект, а ссылку на него, то есть на функцию. Также генератор возвращает ссылку на таблицу, которую требуется обойти, и стартовый индекс. Если генератор будет вызван множество раз, он столько же раз вернет ссылку на одну и ту же функцию-итератор.

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

Посмотрим, как будет выглядеть наш генератор, если мы его перепишем под безресурсный вариант:

local function r_iter(t, i)
    i = i - 1
    local v = t[i]
    if v ~= nil then
        return i, v
    else
        return nil
    end
end

local function r_ipairs(t)
    return r_iter, t, #t + 1
end

local array = {'apple', 'banana', 'pineapple'}

for i, v in r_ipairs(array) do
    print(i, v)
end

3       pineapple
2       banana
1       apple

Значение, которое возвращается из итератора первым, идет и на присвоение первой явной переменной до in и записывается в скрытую переменную цикла (индексную, или управляющую). На следующей проходе эта же переменная передается вторым аргументом при вызове итератора.

Следует отметить, что встроенные функции ipairs и pairs работают по такому же принципу. Они являются фабриками безресурсных итераторов.

Итак, бессостоятельные итераторы в Lua спроектированы исключительно под внутреннюю механику цикла for...in.... Сами по себе, без этого цикла, они практически теряют смысл и неудобны в использовании. Создатели Lua перенесли возможность хранения состояния внутрь самого цикла, чтобы избежать избыточного выделения памяти (ресурсов).

Из-за таких особенностей итерационного цикла в Lua мы не можем следующий генератор, чей итератор с замыканием возвращает только значение, превратить в безресурсный: 

local function values(t)
    local index = 0 
    return function()
        index = index + 1
        if index <= #t then
            return t[index]
        else
            return nil
        end
    end
end

local array = {'apple', 'banana', 'pineapple'}
for i in values(array) do
    print(i)
end

apple
banana
pineapple

Если мы захотим все же это сделать, stateless-итератор должен будет возвращать индекс. Однако его можно игнорировать. Общепринятым способом является использование нижнего подчеркивания (это полноценная переменная) вместо первой переменной до in:

local function v_iter(t, i)
    i = i + 1
    local v = t[i]
    if v ~= nil then
        return i, v
    else
        return nil
    end
end

local function values(t) 
    return v_iter, t, 0
end

local array = {'apple', 'banana', 'pineapple'}
for _, v in values(array) do
    print(v)
end

Если из итератора надо вернуть больше чем одно значение помимо индекса, то переменные просто перечисляются после return. Второе, третье, четвертое и все последующие значения по порядку разложатся в ваши пользовательские переменные, указанные до слова in.