Is throwing an exception a faster way to break out of recursion in JavaScript?

While the purpose of exceptions is error handling, try / catch blocks might have a performance characteristic that can be useful for a specific optimization. Sure, there might be a significant performance overhead when there is an exception thrown, the stack is unwound and the catch block is executed. But the code wrapped in try block (the code that runs normally) is expected to have a small (if any) performance overhead.

This low to zero additional overhead of try block might be useful when we want to quickly terminate an intensive computation with deep recursion. Without using an exception we have to do some checks of the return values, which, in total, might add more overhead than try / catch blocks for the normal running code. But keep in mind that this might be true only when the time required for handling the thrown exceptions is negligible compared to the total execution time and wrapping in try block produces less overhead than the checks after the function return.

The benchmark

I decided to do a benchmark with Perflink. The benchmarks will be run on Chrome 145, Ubuntu 24.04.4 LTS and AMD Ryzen 5000U.

The core idea of the benchmark

I implemented 2 versions of recursive backtracking algorithms that find and return the first occurred solution for N Queens Problem.

The first one checks return values for recursion termination:

function findNQueensWithReturn(n) {
	if (n <= 0) {
		return null;
	}

	// occupied columns
	var occupiedCols = Array.from({ length: n }, () => false);
	// occupied top left -> bottom right diagonal
	var occupiedDiags1 = Array.from({ length: 2 * n + 1 }, () => false);
	// occupied top right -> bottom left diagonal
	var occupiedDiags2 = Array.from({ length: 2 * n + 1 }, () => false);

	function findRecursively(row) {
		let col = 0, diag1 = row, diag2 = n + row - 1;
		++row;

		// try to place queen in each column
		do {
			// if the current column and diagonals are not occupied
			if (!occupiedCols[col] && !occupiedDiags1[diag1]
				&& !occupiedDiags2[diag2]) {
				// if reached to the last row, it means solved, so 
					// the solution can be returned
				if (row === n) {
					return [col];
				}

				// mark the column and diagonals as occupied
				occupiedCols[col] = occupiedDiags1[diag1] = occupiedDiags2[diag2] = true;
				// recursively repeat the same process for the next rows
				const result = findRecursively(row);
				// if an array is returned, push the column index an return the array
				if (result) {
					result.push(col);
					return result;
				}
				// unmark the column and the diagonals
				occupiedCols[col] = occupiedDiags1[diag1] = occupiedDiags2[diag2] = false;
			}

			// for the next column the first diagonal index increases
			++diag1;
			// for the next column the second diagonal index decreases
			--diag2;
		} while (++col < n)
	}

	return findRecursively(0) ?? null;
}

console.log(findNQueensWithReturn(6));
console.log(findNQueensWithReturn(16));

The second one uses exceptions for recursion termination:

function findNQueensWithException(n) {
	if (n <= 0) {
		return null;
	}

	// occupied columns
	var occupiedCols = Array.from({ length: n }, () => false);
	// occupied top left -> bottom right diagonal
	var occupiedDiags1 = Array.from({ length: 2 * n + 1 }, () => false);
	// occupied top right -> bottom left diagonal
	var occupiedDiags2 = Array.from({ length: 2 * n + 1 }, () => false);

	function findRecursively(row) {
		let col = 0, diag1 = row, diag2 = n + row - 1;
		++row;

		try {
			// try to place queen in each column
			do {
				// if the current column and diagonals are not occupied
				if (!occupiedCols[col] && !occupiedDiags1[diag1]
					&& !occupiedDiags2[diag2]) {
					// if reached to the last row, it means solved, 
						// so the solution can be thrown
					if (row === n) {
						throw [];
					}

					// mark the column and diagonals as occupied
					occupiedCols[col] = occupiedDiags1[diag1] = 
						occupiedDiags2[diag2] = true;
					// recursively repeat the same process for the next rows
					findRecursively(row)
					// unmark the column and the diagonals
					occupiedCols[col] = occupiedDiags1[diag1] = 
						occupiedDiags2[diag2] = false;
				}

				// for the next column the first diagonal index increases
				++diag1;
				// for the next column the second diagonal index decreases
				--diag2;
			} while (++col < n)
		} catch (arr) {
			// handling the thrown solution, pushing the column index to the solution
			arr.push(col);

			// if it's the first row (row was 0 before incrementing in this function) 
				// return instead of rethrow
			if (row === 1) {
				return arr;
			}

			// otherwise rethrow
			throw arr;
		}
	}

	return findRecursively(0) ?? null;
}

console.log(findNQueensWithException(6));
console.log(findNQueensWithException(16));

Both findNQueensWithReturn and findNQueensWithException return array that contains the column indexes of the queens on each row. Keep in mind, that this can be done in O(n) time if we want just one solution, but for the sake of the experiment, we want to have a long running computation.

The setup

Both findNQueensWithReturn and findNQueensWithException will be run with n = 26 and compared.

The results

Here are the results:

As you can see, with exceptions it runs a bit faster.

I did another benchmark with n = 18 and 10 repeats. So, this will create more warmup and more potential for optimization:

Still, slightly faster with exceptions.

What about other browsers?

Although I didn't test much on other browsers, I did a run the second benchmark on Firefox 147. Unlike Chrome, it ran much slower with exceptions (5 ops/s vs 17 ops/s). This is likely because throwing exceptions on Firefox is much more expensive.

Conclusion

So, using exceptions for breaking out of recursions can slightly increase performance on Chromium based browsers. However, this doesn't seem to work reliably for all browsers (such as Firefox, mentioned above). You probably should benchmark on all your targeted browsers to make sure this doesn't do the opposite thing. Also, this might be fragile, even on Chromium based browsers the performance might vary between versions because of changes in optimization heuristics. The performance win here is small (around 5%), and with more extreme warmups, the difference might even out. Also, keep in mind that Perflink runs the tests in isolated workers, it might produce different results than running on the browser main thread. But, in any case, running CPU-heavy tasks on the main thread should be avoided as much as possible.