Improve performance of `parallel.waitForAll` handling many `task_complete` event (if not events in general)

[MineCake147E]

Background and motivation

I recently ran into problems like #1375. When I tried to manage 64 mekanism:chemical_crystallizers with parallel.waitForAll, calling 4 methods for each machine per tick, the whole program halted.

Later, I found out that peripheral methods that run in main thread fires task_complete event when it's complete.

Then I found the code below:

CC-Tweaked/projects/core/src/main/java/dan200/computercraft/core/computer/ComputerExecutor.java

Lines 269 to 282 in bed861f

	void queueEvent(String event, @Nullable Object @Nullable [] args) {
	// Events should be skipped if we're not on.
	if (!isOn) return;
	synchronized (queueLock) {
	// And if we've got some command in the pipeline, then don't queue events - they'll
	// probably be disposed of anyway.
	// We also limit the number of events which can be queued.
	if (closed || command != null || eventQueue.size() >= QUEUE_LIMIT) return;
	eventQueue.offer(new Event(event, args));
	}
	enqueue();
	}

And I found out that, apparently, the event queue has a hard limit QUEUE_LIMIT which is 256.
The code for parallel.waitForAll and ILuaContext.issueMainThreadTask suggests why it was needed.

CC-Tweaked/projects/core/src/main/resources/data/computercraft/lua/rom/apis/parallel.lua

Lines 61 to 92 in 19b8433

	local function runUntilLimit(threads, limit)
	local count = #threads
	if count < 1 then return 0 end
	local living = count
	local event = { n = 0 }
	while true do
	for i = 1, count do
	local thread = threads[i]
	if thread and (thread.filter == nil or thread.filter == event[1] or event[1] == "terminate") then
	local ok, param = coroutine.resume(thread.co, table.unpack(event, 1, event.n))
	if ok then
	thread.filter = param
	elseif type(param) == "string" and exception.can_wrap_errors() then
	error(exception.make_exception(param, thread.co))
	else
	error(param, 0)
	end
	if coroutine.status(thread.co) == "dead" then
	threads[i] = false
	living = living - 1
	if living <= limit then
	return i
	end
	end
	end
	end
	event = table.pack(os.pullEventRaw())
	end
	end

CC-Tweaked/projects/core/src/main/java/dan200/computercraft/core/computer/LuaContext.java

Lines 24 to 53 in 19b8433

	public long issueMainThreadTask(final LuaTask task) throws LuaException {
	// Issue command
	final var taskID = computer.getUniqueTaskId();
	final Runnable iTask = () -> {
	try {
	var results = task.execute();
	if (results != null) {
	var eventArguments = new Object[results.length + 2];
	eventArguments[0] = taskID;
	eventArguments[1] = true;
	System.arraycopy(results, 0, eventArguments, 2, results.length);
	computer.queueEvent("task_complete", eventArguments);
	} else {
	computer.queueEvent("task_complete", new Object[]{ taskID, true });
	}
	} catch (LuaException e) {
	computer.queueEvent("task_complete", new Object[]{ taskID, false, e.getMessage() });
	} catch (Exception t) {
	LOG.error(Logging.JAVA_ERROR, "Error running task", t);
	computer.queueEvent("task_complete", new Object[]{
	taskID, false, "Java Exception Thrown: " + t,
	});
	}
	};
	if (computer.queueMainThread(iTask)) {
	return taskID;
	} else {
	throw new LuaException("Task limit exceeded");
	}
	}

parallel.waitForAll decides what coroutine has to be resumed by the name alone.
The name of the event that ILuaContext.issueMainThreadTask fires aren't unique.
Each coroutine for peripheral function calls decides when to react by checking ID and discarding irrelevant events.
These facts combined, task_complete events has to be handled in $$O(n^2)$$ way per tick.

Proposed changes

Use hash tables in parallel APIs

By using hash table with event name as key (table<string, thread[]>), we can avoid $$O(n)$$ operations for each event (for n different event names).

Make the event name unique

By making the event name unique (something like &{task_id}@{peripheral_name}), we can further utilize the $$O(1)$$ (or something faster than a simple $$O(n)$$ iteration in Lua) lookup time complexity of hash tables given no collision of event names for different main-thread peripheral function calls.

Combining these changes, we can reduce time complexity of waiting $$n$$ peripheral function calls to complete, from $$O(n^2)$$ to something like $$O(n)$$ (assuming table lookup in Lua only takes $$O(1)$$).

Do not discard task-complete events (formally task_complete)

Since parallel.waitForAll is much faster after implementing these two changes, we would no longer have to limit the number of formally task_complete events to accept.

Alternative Designs

Maybe even faster algorithm, if one exists.

Risks

Compatibility issues may come up

[SquidDev]

The fundamental issue here is that you're adding more than 256 events in the queue at once (which I think you know). While it might be possible to reduce some of the overhead of how events are filtered through the system, so that in optimal conditions, the Lua can keep up with events being submitted, the underlying code will still be racey. Any changes in timing (e.g. server under load, another computer wants to run at the same time, etc...) will immediately break things again.