Tips when using list

[zyxkad]

TL; DR

Please note, these suggestions only apply when you are operating large list continuously.
The performance issue will not be significant for most cases.

avoid use list[#list + 1] or table.insert when appending item.
avoid use ipairs, pairs to iterate over a list.

---

I was operating sets of peripherals on serval computers (about 100 peripherals for each computer). After the computer failed multiple times by Too long without yielding. ComputerCraft may be installed incorrectly. error, I did this simple benchmark about list performance.

list_append_test.lua

_ = true

local testRound, listSize = tonumber(arg[1]), tonumber(arg[2])

if not testRound or not listSize then
	printError('usage: test <testRound> <listSize>')
	return
end

local function recordTime(fn, name, ops)
	print(name)
	local start = os.epoch('utc')
	fn()
	local used = os.epoch('utc') - start
	print('used time', used, 'ms')
	print(used * 1e6 / ops, 'ns/op')
end

local function testAppendUsingCounter()
	for n = 1, testRound do
		local arr = {}
		local j = 1
		for i = 1, listSize do
			arr[j] = i
			j = j + 1
		end
		_ = arr
	end
end

local function testAppendUsingArrayLength()
	for n = 1, testRound do
		local arr = {}
		for i = 1, listSize do
			arr[#arr + 1] = i
		end
		_ = arr
	end
end

local function testAppendUsingTableInsert()
	for n = 1, testRound do
		local arr = {}
		for i = 1, listSize do
			table.insert(arr, i)
		end
		_ = arr
	end
end

for round = 1, 3 do
	print('Round', round)
	sleep(1)
	recordTime(testAppendUsingCounter, 'testAppendUsingCounter', testRound * listSize)
	sleep(0.05)
	recordTime(testAppendUsingArrayLength, 'testAppendUsingArrayLength', testRound * listSize)
	sleep(0.05)
	recordTime(testAppendUsingTableInsert, 'testAppendUsingTableInsert', testRound * listSize)
	sleep(3)
end

print(_)

results of list append

As we can see in the result, when appending to a array that have size at 100 and above, self maintain a counter when appending a list is almost twice faster than using #(list length operator), and is 3~4 times faster than using table.insert.
After looking into Cobalt's code, I found that internally the # operator is using binary search (and linear search in some case?), which is why its that slow. (I don't know if we can cache the length then the operator may be faster.)

---

The next benchmark is about list iterator. Cobalt provides a built-in generator ipairs, it can be used in for in to produce nicer code. But does it also give a nice performance?

list_iterator_test.lua

_ = true

local testRound, listSize = tonumber(arg[1]), tonumber(arg[2])

if not testRound or not listSize then
	printError('usage: test <testRound> <listSize>')
	return
end

local function makeList(size)
	local list = {}
	for i = 1, size do
		list[i] = {}
	end
	return list
end

local function recordTime(fn, name, ops)
	print(name)
	local start = os.epoch('utc')
	fn()
	local used = os.epoch('utc') - start
	print('used time', used, 'ms')
	print(used * 1e6 / ops, 'ns/op')
end

local globalList = makeList(listSize)

local function iterUsingConstIndex()
	for n = 1, testRound do
		local size = listSize
		for i = 1, size do
			_ = globalList[i]
		end
	end
end

local function iterUsingTableIndex()
	for n = 1, testRound do
		local size = #globalList
		for i = 1, size do
			_ = globalList[i]
		end
	end
end

local function iterUsingIpairs()
	for n = 1, testRound do
		for i, v in ipairs(globalList) do
			_ = v
		end
	end
end

local function iterUsingPairs()
	for n = 1, testRound do
		for i, v in pairs(globalList) do
			_ = v
		end
	end
end

for round = 1, 3 do
	print('Round', round)
	sleep(1)
	recordTime(iterUsingConstIndex, 'iterUsingConstIndex', testRound * listSize)
	sleep(0.05)
	recordTime(iterUsingTableIndex, 'iterUsingTableIndex', testRound * listSize)
	sleep(0.05)
	recordTime(iterUsingIpairs, 'iterUsingIpairs', testRound * listSize)
	sleep(0.05)
	recordTime(iterUsingPairs, 'iterUsingPairs', testRound * listSize)
	sleep(3)
end

print(_)

results of list iterator

The result tells us the answer, No! Iterator over using for i = is also twice faster than for in ipairs.

I do not have a good understanding of how Cobalt internally works. But my guess is # operation and ipairs both is implemented in Java, when you invoking them it might increase stack change & usage, and eventually slows your program down.

[SquidDev]

I don't know if we can cache the length then the operator may be faster.

It's something I keep meaning to look at. It's not something PUC Lua does (hence why Cobalt doesn't either), but other implementations like Luau do.

The result tells us the answer, No! Iterator over using for i = is also twice faster than for in ipairs.

When you use a for loop, it gets converted into the (rough) equivalent of:

local tbl, iter = ipairs(list)
local i, v = iter(tbl)
while i ~= nil do 
  -- Loop body 
  i, v = iter(tbl, i)
end 

Despite the fact that ipairs and iter are implemented in Java, they still are function calls, and so have considerably more overhead than a single bytecode instruction like table indexing (due to setting up the stack frame, debug hooks, etc...).

With a smarter interpreter, it is possible to handle this better. I believe LuaJIT has a specialisation for this case, and will desugar ipairs into a for i = 1, #list loop. This would be possible in Cobalt, but would require specialisation/quickening in the interpreter, and that is not something I'm going to work on. Lost too much time trying to make the interpreter faster already :).