Erzwingen einer Tabelle rehash funktioniert nicht nach einer vorherigen rehash

Question

Ich habe eine Funktion erstellt, die Größe eines Arrays und setzt neue Einträge auf 0, kann aber auch die Größe des Arrays auf 2 verschiedene Arten verringern: 1. Einfach einstellen n Eigenschaft auf die neue Größe (der Längenoperator kann aus diesem Grund nicht verwendet werden). 2. Setzen Sie alle Werte nach der neuen Größe auf nil bis zu 2 *, um eine erneute Bereinigung zu erzwingen.

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 

Wie ich es getestet:

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 

Jedoch, wenn ich nicht true als drittes Argument auf den zweiten Aufruf von Resize passieren kann (so ist es kein Aufguss erzwingt auf dem zweiten Aufruf), der dritte Aufruf endet damit, es erneut zu tun.

Fehle ich etwas? Ich erwarte, dass der dritte nach dem zweiten auch rehasht.

Answer 1

Hier ist ein klareres Bild davon, wie die Tabelle sieht in der Regel wie vor und nach den Größenänderungen:

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 

Und hier ist, was passiert:

• Während die Größe ändert auf 50000 Elemente, die Tabelle wird mehrmals aufgeräumt, und am Ende enthält es genau einen Hash-Teil-Slot für das n-Feld und genug Array-Teil-Slots für die Integer-Schlüssel.
• Während die Schrumpfung auf 10000 Elemente, müssen Sie zuerst nil zu dem ganzzahligen Schlüssel 10.001-65.536, zuweisen und von 65537 dann Die ersten Gruppe von Zuweisungen 100000. nie einen Aufguss verursachen, da Sie vorhandene Felder zuordnen. Dies hat mit der guarantees for the next function zu tun. Die zweite Gruppe von Zuweisungen wird Wiederaufreinigungen verursachen, aber da Sie nil s anfordern, wird Lua irgendwann feststellen, dass der Array-Teil der Tabelle mehr als halb leer ist (siehe Kommentar zu Beginn von ltable.c). Lua wird dann den Array-Teil auf eine vernünftige Größe verkleinern und einen zweiten Hash-Slot für den neuen Schlüssel verwenden. Aber da Sie nil s zuweisen, ist dieser zweite Hash-Slot nie besetzt, und Lua ist frei, ihn für alle die verbleibenden Zuweisungen wieder zu verwenden (und es oft, aber nicht immer). An diesem Punkt würden Sie ohnehin keine Aufrhung bemerken, da Sie immer die 16384-Array-Slots und 2 Hash-Slots (einen für n, einen für das neue zuzuweisende Element) haben werden.
• Die Schrumpfung auf 20 Elemente geht einfach so weiter, mit der Ausnahme, dass bereits ein zweiter Hash-Slot verfügbar ist. So könnten Sie nie erhalten eine Wiederaufbereitung (und die Array-Größe bleibt größer als nötig), aber wenn Sie tun (Lua aus irgendeinem Grund nicht die eine freie Hash-Slot mag), werden Sie die Anzahl der Array sehen Slots fallen auf ein vernünftiges Niveau.

Dies ist, wie es aussieht, wenn Sie tun, um eine Aufguss während der zweiten Schrumpf erhalten :

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 

Wenn Sie meine Experimente zu wiederholen, die git HEAD-Version lua-getsize (original version here) gibt nun auch die Anzahl der Slots in den Array/Hash-Teilen einer Tabelle zurück.