Luau Recap: October 2021

Updates Announcements
, ,
#65

But the order is always the same regardless of how the table was created. If there were any other possible orders then the hash table implementation would be broken. They must be sorted for a binary search to be possible when resolving a key’s value, so there is only one possible order unless you mix keys between the array and hash parts.

See for yourself. I got 20000:("A", "H", "C", "B", "E", "D", "G", "F"):

Code 
local keys = {"A", "B", "C", "D", "E", "F", "G", "H"}

local rng = Random.new()
local function shuffle()
	for i = #keys, 2, -1 do
		local j = rng:NextInteger(1, i)
		keys[j], keys[i] = keys[i], keys[j]
	end
end

local function valueToString(v): string
	if type(v) == "string" then
		return string.format("%q", v)
	end
	return tostring(v)
end

local nameStatsList: {string} = {}
local nameStatsLookup: {[string]: number} = {}
local function checkTableOrder(t)
	local order = {}
	for k in pairs(t) do
		table.insert(order, (valueToString(k)))
	end
	local name: string = "(" .. table.concat(order, ", ") .. ")"
	local count: number? = nameStatsLookup[name]
	if count then
		nameStatsLookup[name] = count + 1
	else
		nameStatsLookup[name] = 1
		table.insert(nameStatsList, name)
	end
end

for i = 1, 10000 do
	shuffle()
	do -- Create a table by adding one at a time
		local t = {}
		for i, k in ipairs(keys) do
			t[k] = true
		end
		checkTableOrder(t)
	end
	do -- Create a table by hardcoding it
		assert(#keys == 8)
		checkTableOrder({
			[keys[1] ] = true,
			[keys[2] ] = true,
			[keys[3] ] = true,
			[keys[4] ] = true,
			[keys[5] ] = true,
			[keys[6] ] = true,
			[keys[7] ] = true,
			[keys[8] ] = true,
		})
	end
end

do -- Print out the stats
	local list: {string} = table.create(#nameStatsList)
	for i, name: string in ipairs(nameStatsList) do
		list[i] = string.format("%d:%s", nameStatsLookup[name] :: number, name)
	end
	print(table.concat(list, "\n"))
end

There might be an edge case if you remove the current key while iterating before shrinking the table. Waiting until a GC step might help with that, but I don’t know if that’s feasible.

My project creates constant tables programmatically and I’d like to shrink them down, considering they are kept for a long time.

#66

What does binary search have to do with hash tables?

When I run this example I don’t see all tables having the same order regardless of how they were created:

local t1,t2 = {a = 1,b = 2,c = 3,d = 4},{a = 1,b = 2,c = 3,d = 4}
t1.e = 5
t1.e = nil
local function keys(t,k)
	local n = next(t,k)
	if n == nil then return end
	return n,keys(t,n)
end
print(keys(t1)) --> a c b d
print(keys(t2)) --> a d c b
local T1,T2 = {},{}
local k1,k2 = "a","c"
T1[k1] = k1
T1[k2] = k2
T2[k2] = k2
T2[k1] = k1
print(keys(T1)) --> a c
print(keys(T2)) --> c a

Tables don’t have any order that they are guaranteed to be in, and different tables may have different orders depending upon how they are constructed.

https://www.lua.org/manual/5.1/manual.html#pdf-next
You are allowed to remove a key from the table and use it with next until you insert a new key. There isn’t any reasonable way to determine if you want this or not, so removing keys cannot shrink the table, and the GC can’t later shrink it when it thinks it is no longer needed.

1 Like
#67

Oh that’s really interesting. I failed to come up with an example that did that. Are there any real use cases where one would want to freeze a table one time while keeping a persistent next position like that? table.freeze is still a new method so the shrinking behavior could be documented. I don’t have an understanding of how GC works in Luau, but perhaps shrinking could occur during a GC step if the table still has references and it’s trivial to flag tables for something like that.

I really just want large lookup tables and mixed frozen tables that get compiled into my project’s data system to use less memory once they’re set up.

#68

I can’t think of any case where it’d happen, but often changing a table during iteration is very hard to spot.

A function which shrinks a table would be a better addition, for your use case you can shrink the table and then freeze it, and it can also be used to shrink a table that may be changed in the future.

local function foo(array:{string})
	local t = {}
	for _,v in ipairs(array) do
		t[v] = true
	end
	table.shrink(t) -- shrinks t to reduce memory usage
	table.freeze(t)
	return t
end

This would avoid any imcompatibility and makes the intent clearer.

1 Like
#69

Shrinking the dictionary portion is generally only possible when you’ve removed the items from it (in which case… don’t? :wink: ). This is because dictionaries are restricted to a power of two in size, and need to get completely full to reallocate, so they never waste space in the sense that 129 elements do require a 256-long hash portion but that’s a necessity due to storage mechanics.

2 Likes
#70

Could we ever expect something similar to table.bisect, table.bisectleft, table.bisectright–bisect — Array bisection algorithm — Python 3.11.0 documentation

#71

This topic was automatically closed 120 days after the last reply. New replies are no longer allowed.