Когда точно в Lua массив ( таблица только с array-part ) приобретает hash-part ( становится hash )?

Question

[bulatzaripov]

Необходимо передавать таблицы (tables) в Lua коде по сети ( компьютерная мультиплеерная игра).
В связи с чем очень актуален вопрос о размерах передаваемых данных ( о сохранении их как можно меньшими ).

Для сохранения структуры таблицы и "удержания" её в array-like стиле рекомендуют использовать table.insert, table.remove...

Имеется код:

local var = {}

for i = 1, 10000, 1 do
    table.insert ( var, i )
end

var[10000] = { var = 1, some = "string", another = {} }
var[555] = false
var[1] = 1
var[2] = {}

var[1] = {}

Вопросы :
1) Останется ли таблица var массивом ( таблицей только c array part ), или преобразуется в hash ( таблицей с двумя частями array и hash ). ( Сам думаю ответ "останется только с array-part", так как структура таблицы не затронута - затронуты лишь значения элементов, но очень сомневаюсь в этом ответе, а нужно знать наверняка ).
2) Почему? :) Как это проверить?
3) Предельно уточняя: если таблица изначально имеет только array-part, то приведет ли изменение значения элемента таблицы напрямую через синтаксис var[1] = {} var[2] = false var[3] = 1 и т.п. к изменению структуры таблицы и появлению у ней hash-part ? ( При условии что заранее дано: )

local var = {}
for i = 1, 10000, 1 do
    table.insert ( var, i )
end

Подозреваю, что ответ для кода выше "нет", но:

var[10001] = 1

Уже затронет структуру таблицы и создаст "накладные расходы" по памяти.
В связи с чем думаю ответ таков ( для кода выше) : до n <= 10000 код var[n] = {} не затрагивает структуру таблицы, а значит не ведет к созданию hash-part ( таблица остается array-like). Однако код var[n + 1] = {} приведет к накладным расходам памяти (подробнее тут www.lua.org/gems/sample.pdf )

Ответ правильный или нет?

Спасибо!

Answer 1

[Boris Nagaev]

В файле ltable.c сказано следующее:

The actual size of the array is the largest 'n' such that at least half the slots between 0 and n are in use.

Таким образом, массив охватывает ключи от 0 до такого числа n, что используется хотя бы половина. Давайте ещё посмотрим на код функции computesizes, которая решает, каким будет размер массива при изменении размера таблицы. Эта функция перебирает степени двойки (1, 2, 4, 8 ...) и смотрит, какая доля массива была бы занята, если бы он был такого размера. Останавливается, когда эта доля становится меньше половины. Нетрудно доказать, что при таком алгоритме выбора размера массива и при сплошном заполнении всех ключей от 1 до n обязательно будет выбран размер массива, больший или равный n.

Кстати говоря, из этого же следует, что при добавлении в конец массива элементов будут накладные расходы, но не на хеш-часть, а на пустые элементы массива, выделенные "про запас". Но так и должно быть, чтобы не перестраивать массив при каждом новом элементе. (В C++ vector.push_back ведёт себя так же.) Если заранее знаете окончательный размер массива и хотите на этом выгадать, то напишите сишное расширение, которое вызывает lua_createtable(L, размер-массива, 0).

По поводу того, не появится ли хеш-часть при замене значений на различные типы. Не появится. Дело в том, что в паре ключ-значение ключ и значения хранятся в разных полях. Я отследил как используется поле i_val, оказалось только в макросе gval, тип которого нигде не фигурирует (только проверки на nil).

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