[Bug] Diff algorithm performance decrease

Reproducible in vscode.dev or in VS Code Desktop?

• Not reproducible in vscode.dev or VS Code Desktop

Reproducible in the monaco editor playground?

• Not reproducible in the monaco editor playground

Monaco Editor Playground Link

No response

Monaco Editor Playground Code

// Hover on each property to see its docs!
const editor = monaco.editor.createDiffEditor(document.getElementById("container"), {
	language: 'javascript',
	defaultEndOfLine: '\n',
	maxComputationTime: 1000000,
	maxFileSize: 10000000
});

let d0;
function start() {
	d0 = Date.now();
	return '';
}
function stop() {
	const elapsed_ms = Date.now() - d0;
	return elapsed_ms + 'ms'
}

async function setModel() {
	console.info('Fetching text...', start());
	const response = await fetch('https://raw.githubusercontent.com/dscape/spell/refs/heads/master/test/resources/big.txt');
	let value = await response.text();
	value = value.substring(0, 1000000);
	console.info('Fetching text...DONE', stop());

	console.info('Initializing...')
	const original = monaco.editor.createModel(value, 'text');
	const modified = monaco.editor.createModel(value.replace(/i/g, 'I'), 'text');
	console.info('Initializing...DONE', stop());

	console.info('Requesting diff...')	
	editor.setModel({original, modified});
	editor.onDidUpdateDiff(() => {
		console.info('Requesting diff...DONE', stop())
	});
}




setModel();

Reproduction Steps

No response

Actual (Problematic) Behavior

Good morning, I've noticed a significant decrease of the diff algorithm performance.
Using exactly the same input v0.52.2 (7.2s) is more than twice slower than v0.37.1 (2.6s)
Moreover depending the size of the input the duration is not linear.
Using 5M characters instead of 1M (ajusting the 2 parameter of the substring value) v0.37.1 gives a diff within 122s and the v0.52.2 260s

Expected Behavior

No response

Additional Context

No response

Start with the Monaco Editor Playground code using createDiffEditor and onDidUpdateDiff, then benchmark the supplied 1M- and 5M-character inputs against versions 0.37.1 and 0.52.2. Compare the diff algorithm behavior and identify the source of the regression; done means the benchmark is reproducibly improved without breaking diff results.