Performance: `O(n^2)` time-complexity with `remove_reactions`

[AlbertMarashi]

Describe the bug

I'm building a sort of very custom use-case AI dataset editor which involves rendering approximately ~80k DOM nodes.

Occasionally, a full re-render is required, which leads to remove_reactions getting called for each "cell" in my grid I am rendering.

remove_reactions calls remove_reaction n times, which itself, performs an indexOf on the dependencies, leading to terribly slow re-renders.

Code responsible:

svelte/packages/svelte/src/internal/client/runtime.js

Lines 440 to 493 in f7f87dc

	/**
	* @template V
	* @param {Reaction} signal
	* @param {Value<V>} dependency
	* @returns {void}
	*/
	function remove_reaction(signal, dependency) {
	let reactions = dependency.reactions;
	if (reactions !== null) {
	var index = reactions.indexOf(signal);
	if (index !== -1) {
	var new_length = reactions.length - 1;
	if (new_length === 0) {
	reactions = dependency.reactions = null;
	} else {
	// Swap with last element and then remove.
	reactions[index] = reactions[new_length];
	reactions.pop();
	}
	}
	}
	// If the derived has no reactions, then we can disconnect it from the graph,
	// allowing it to either reconnect in the future, or be GC'd by the VM.
	if (
	reactions === null &&
	(dependency.f & DERIVED) !== 0 &&
	// Destroying a child effect while updating a parent effect can cause a dependency to appear
	// to be unused, when in fact it is used by the currently-updating parent. Checking `new_deps`
	// allows us to skip the expensive work of disconnecting and immediately reconnecting it
	(new_deps === null || !new_deps.includes(dependency))
	) {
	set_signal_status(dependency, MAYBE_DIRTY);
	// If we are working with a derived that is owned by an effect, then mark it as being
	// disconnected.
	if ((dependency.f & (UNOWNED | DISCONNECTED)) === 0) {
	dependency.f ^= DISCONNECTED;
	}
	remove_reactions(/** @type {Derived} **/ (dependency), 0);
	}
	}
	/**
	* @param {Reaction} signal
	* @param {number} start_index
	* @returns {void}
	*/
	export function remove_reactions(signal, start_index) {
	var dependencies = signal.deps;
	if (dependencies === null) return;
	for (var i = start_index; i < dependencies.length; i++) {
	remove_reaction(signal, dependencies[i]);
	}
	}

Reproduction

...

Logs

No response

System Info

System:
    OS: macOS 15.1
    CPU: (8) arm64 Apple M1 Pro
    Memory: 116.11 MB / 16.00 GB
    Shell: 5.9 - /bin/zsh
  Binaries:
    Node: 20.17.0 - ~/.nvm/versions/node/v20.17.0/bin/node
    npm: 10.8.2 - ~/.nvm/versions/node/v20.17.0/bin/npm
    pnpm: 9.7.0 - ~/Library/pnpm/pnpm
    bun: 1.1.39 - ~/.bun/bin/bun
  Browsers:
    Chrome: 131.0.6778.205
    Safari: 18.1
  npmPackages:
    svelte: ^5.16.0 => 5.16.0

Severity

annoyance

[trueadm]

This is fairly complex to optimise – as reactions is an array that can expect duplicates, due to the fact that a reaction might have duplicate dependencies. We originally used a Set here and that actually significantly impacted perf by about 35-40% because Sets are very expensive to operate on compared to simple arrays, and typically an array doesn't typically have more than a few dozen reactions.

I wonder if we can provide a fast-path for remove_reactions when all entries are removed somehow. @AlbertMarashi it would be good to have a repro of this so we can possibly optimise this use-case.

[trueadm]

Actually, it just occurred to me that this could be because you're in DEV and we monkey-patch indexOf. Could you try in prod and seeing if the issue still persists?

[AlbertMarashi]

Give me a couple days to provide a REPL

[AlbertMarashi]

Seems to be a lot more performant 👍🏼 - Sorry for the late reply