Принудительное повторное использование таблицы после предыдущего перерыва

Question

Я создал функцию, которая изменяет размер массива и устанавливает новые записи в 0, но также может уменьшить размер массива двумя разными способами: 1. Просто установите n свойство нового размера (по этой причине оператор длины не может быть использован). 2. Установка всех значений после нового размера до нуля до 2 *, чтобы принудительно перефразировать.

local function resize(array, elements, free) 
    local size = array.n 

    if elements < size then  -- Decrease Size 
     array.n = elements 
     if free then 
      size = math.max(size, #array) -- In case of multiple resizes 
      local base = elements + 1 
      for idx = base, 2*size do  -- Force a rehash -> free extra unneeded memory 
       array[idx] = nil 
      end 
     end 
    elseif elements > size then -- Increase Size 
     array.n = elements 
     for idx = size + 1, elements do 
      array[idx] = 0 
     end 
    end 
end 

Как я тестировал:

local mem = {n=0}; 
resize(mem, 50000) 
print(mem.n, #mem)    -- 50000 50000 
print(collectgarbage("count")) -- relatively large number 

resize(mem, 10000, true) 
print(mem.n, #mem)    -- 10000 10000 
print(collectgarbage("count")) -- smaller number 

resize(mem, 20, true) 
print(mem.n, #mem)    -- 20 20 
print(collectgarbage("count")) -- same number as above, but it should be a smaller number 

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

Я что-то упустил? Я ожидаю, что третий будет перефразировать после второго.

Answer 1

Вот более четкое представление о том, как таблица обычно выглядит до и после изменяет размеры:

table: 0x15bd3d0 n: 0  #: 0  narr: 0  nrec: 1 
table: 0x15bd3d0 n: 50000 #: 50000 narr: 65536 nrec: 1 
table: 0x15bd3d0 n: 10000 #: 10000 narr: 16384 nrec: 2 
table: 0x15bd3d0 n: 20  #: 20  narr: 16384 nrec: 2 

А вот что происходит:

• Во время изменения размера до 50000 элементов, таблица перефразируется несколько раз, и в конце он содержит ровно один хэш-фрагмент для поля n и достаточное количество слотов массива для целых ключей.
• Во время сокращения до 10000 элементов вы сначала назначаете nil целым ключам от 10001 до 65536, а затем от 65537 до 100000. Первая группа назначений будет никогда вызывает передел, поскольку вы назначаете существующие поля. Это связано с guarantees for the next function. Вторая группа назначений вызовет повторные попытки, но поскольку вы оцениваете nil, Lua в какой-то момент поймет, что массивная часть таблицы больше половины пустого (см. Комментарий в начале ltable.c). Затем Lua сжимает массив до разумного размера и использует второй хеш-слот для нового ключа. Но поскольку вы назначаете nil s, этот второй хеш-слот никогда не занят, и Lua может повторно использовать его для всех оставшихся присвоений (и это часто, но не всегда). В любом случае вы не заметили бы переигровку, потому что вы всегда будете иметь слоты массива 16384 и 2 хэш-слота (один для n, один для нового элемента, который будет назначен).
• Сокращение до 20 элементов продолжается так же, за исключением того, что уже имеется второй хеш-слот. Таким образом, вы могли бы никогда не получить пересмотр (и размер массива остается большим, чем необходимо), но если вы сделать (Lua по какой-то причине не нравится один свободный хэш-слот), вы увидите количество массивов слоты падают на разумный уровень.

Это то, что он выглядит, когда вы сделать получить перепев во второй усадке:

table: 0x11c43d0 n: 0  #: 0  narr: 0  nrec: 1 
table: 0x11c43d0 n: 50000 #: 50000 narr: 65536 nrec: 1 
table: 0x11c43d0 n: 10000 #: 10000 narr: 16384 nrec: 2 
table: 0x11c43d0 n: 20  #: 20  narr: 32  nrec: 2 

Если вы хотите повторить мои эксперименты, версию мерзавец главы lua-getsize (оригинальная версия here) теперь также возвращает количество слотов в массиве/хэш-частях таблицы.