Exécution de tâches longues en JavaScript

Utilisation d'une thread secondaire avec un WebWorker

Une application JavaScript utilise une seule thread gérant une boucle d'événements. Exécuter un calcul long dans la thread de gestion d'événements est problématique : les événements s'accumulent et ne peuvent plus être traités ; l'application ne répond plus aux sollicitations de l'utilisateur.

On peut utiliser un WebWorker qui créé une nouvelle thread dediée à l'exécution du calcul. Le WebWorker communique avec la thread principale en utilisant des messages bidirectionnels.

Implantation d'un WebWorker

Comment implanter un WebWorker ?

On créé le WebWorker en spécifiant le fichier JavaScript contenant le code à exécuter : let worker = new Worker("worker.js")
On peut envoyer des messages (texte, objet...) depuis la thread principale au worker : worker.postMessage({"a": 1, "b": 2})
Le worker peut réceptionner ces messages en configurant l'événement onmessage : onmessage = msg => { console.log(msg.data); }
Le worker peut envoyer des messages à la thread l'ayant lancé (ici en renvoyant en écho le message reçu) : onmessage = msg => { postMessage(msg.data); }
La thread principale peut réagir aux messages envoyés par le worker : worker.onmessage = msg => { console.log("Message reçu du worker: " + msg.data); }

Quelques remarques :

Un worker peut aussi lancer lui-même d'autres workers. Cela peut être utile pour répartir un calcul sur plusieurs cœurs de CPU.
Un worker peut aussi communiquer par un bus broadcast channel ; cela permet d'échanger des messages globalement entre plusieurs onglets/fenêtres d'un même site

Exemple 2 : script de factorisation d'entiers (test ici)

let numberInput = document.querySelector("input[name='numberToFactorize']");
let startButton = document.querySelector("input[name='startFactorization']");
let stopButton = document.querySelector("input[name='stopFactorization']");
let resultArea = document.querySelector("#factorizationResult");
let remainingArea = document.querySelector("#remainingToFactor");

let worker = new Worker("factorizerWorker.js");
worker.onmessage = msg => {
	console.log(msg);
	let m = msg.data;
	if (m.kind === "factorizationResult") {
		resultText = "";
		for (let [factor, power] of m.result.factors) {
			if (resultText.length > 0) resultText += "\n";
			resultText += factor + "^" + power;
		}
		if (m.result.remainingToFactor !== null) {
			if (resultText.length > 0) resultText += "\n";
			resultText += "Remaining to factor: " + m.result.remainingToFactor;
		}
		resultArea.innerText = resultText;
	} else if (m.kind === "factorizationStopped") {
		startButton.disabled = false;
		stopButton.disabled = true;
	} else if (m.kind === "factorizationProgress") {
		remainingArea.innerText = m.remainingToFactor;
	}
};

startButton.onclick = event => {
	worker.postMessage({"kind": "startFactorization", "number": parseInt(numberInput.value) });
	startButton.disabled = true;
	stopButton.disabled = false;
};

stopButton.onclick = event => {
	worker.postMessage({"kind": "stopFactorization"});
};

let YIELD_DELAY = 100; // in millis
let data = {"started": false, "cancelled": false, "number": NaN, "result": null, "divider": null};

data.addFactor = function(factor) {
	if (this.result.factors.length > 0 && this.result.factors[this.result.factors.length - 1][0] === factor)
		this.result.factors[this.result.factors.length - 1][1]++;
	else
		this.result.factors.push([factor, 1]);
	this.result.remainingToFactor = this.result.remainingToFactor / factor;
	postMessage({"kind": "factorizationProgress", "divider": factor, "remainingToFactor": data.result.remainingToFactor});
};

data.signalEndOfComputation = function(aborted) {
	postMessage({"kind": "factorizationResult", "result": this.result});
	postMessage({"kind": "factorizationStopped", "aborted": aborted});
}

data.doIterations = function() {
	if (this.cancelled) // stop condition in case of cancellation
		this.signalEndOfComputation(true);
	else {
		let startTime = performance.now();
		while (performance.now() - startTime < YIELD_DELAY) {
			if (this.result.remainingToFactor % this.divider == 0) {
				// new factor found
				this.addFactor(this.divider);
			} else if (this.divider === 2) {
				this.divider = 3;
			} else {
				this.divider += 2;
			}
			if (this.divider * this.divider > this.result.remainingToFactor) {
				// remainingToFactor is a prime number
				this.addFactor(this.result.remainingToFactor);
				this.result.remainingToFactor = null;
				this.signalEndOfComputation(false);
				return;
			}
		}
		setTimeout(() => { this.doIterations() }, 0); // recursive call
	}
}
	

onmessage = msg => {
	console.log(msg);
	let m = msg.data;
	if (m.kind === "startFactorization") {
		data.started = true;
		data.cancelled = false;
		data.number = m.number;
		data.divider = 2;
		postMessage({"kind": "factorizationStarted"});
		data.result = {"remainingToFactor": data.number, "factors": []};
		data.doIterations();
	} else if (m.kind === "stopFactorization") {
		data.cancelled = true;
	}
};

Terminaison d'un web worker

On peut tuer un worker avec worker.terminate() : il s'agit d'un arrêt brutal sans préavis.

Il est préférable que le worker s'arrête de lui-même à la réception d'un message. Comment faire en cas de calcul long ?

On découpe le calcul en petites tranches de temps raisonnable (~25ms) exécutées d'un seul tenant en appelant une méthode executeSlice()
A la fin de l'exécution d'une tranche, on planifie l'exécution de la trache suivante avec setTimeout(() => { executeSlice() }, 0) ⟶ cela redonne la main au récepteur d'événements du worker
On modifie un booléen avec onmessage lorsque l'on reçoit un message de terminaison de la thread principale
Au début de la méthode executeSlice(), on vérifie le booléen de terminaison et on arrête le calcul le cas échéant

Mise en œuvre de cette approche pour un compteur incrémenté avec un bouton pour démarrer le processus d'incrémentation et un autre bouton pour le stopper test ici:

<html>
	<body>
		<p>Counter value: <span id="counter">0</span></p>
		<button id="startButton">Start</button>
		<button id="stopButton">Stop</button>
		<script type="module">
			let w = new Worker("worker.js"); // load the worker
			let counterNode = document.getElementById("counter");
			w.onmessage = (msg) => { counterNode.textContent = `${msg.data}`; }
			document.getElementById("startButton").onclick = () => { w.postMessage("start"); };
			document.getElementById("stopButton").onclick = () => { w.postMessage("stop"); };
		</script>
	</body>
</html>

const QUANTUM_TIME = 100; // in millis
let counter = 0;
let interrupted = false;

function executeSlice() {
	let startTime = performance.now();
	while (performance.now() - startTime < QUANTUM_TIME) {
		for (let i = 0; i < 1000; i++)
			counter++;
	}
	postMessage(counter);
	// plan immediately the next slice
	if (! interrupted) setTimeout(executeSlice, 0);
}
 
onmessage = e => {
	console.log(e);
	if (e.data === "start") {
		interrupted = false;
		executeSlice();
	} else if (e.data === "stop")
		interrupted = true;
}

Web worker récursif

Un web worker peut s'appeler lui-même pour résoudre certaines tâches algorithmiques récursives. Nous présentons ici l'exemple d'un web worker (démonstration ici) triant une liste d'éléments par tri fusion. Cet algorithme de tri classique nécessite deux étapes :

Le tri récursif de chaque moitié de liste
La fusion des deux moitiés de liste triées pour reconstituer la liste complète triée

<html>
	<body>
		<h1>Merging with recursive web workers</h1>
		Depth of the recursion tree: <input type="number" id="level" value="3" /> <br>
		Numbers to sort:
		<textarea id="numbersToSort">
		</textarea>
		<br>
		<button id="sortButton">Sort</button>
		<br>
		Result: <br>
		<pre id="result"></pre>
		
		<script type="module">
			document.getElementById("sortButton").onclick = () => {
				let w = new Worker("mergeSort.js");
				w.onmessage = (msg) => {
					let result = msg.data.list;
					document.getElementById("result").textContent = result;
				};
				let numbers = document.getElementById("numbersToSort").value.split(" ").map( x => parseInt(x) );
				let level = parseInt(document.getElementById("level").value);
				w.postMessage({"kind": "job", "id": 0, "list": numbers, "level": level });
			};
		</script>
	</body>
</html>

function merge(l1, l2) {
	let result = [];
	let i = 0;
	let j = 0;
	while (i < l1.length || j < l2.length) {
		if (i < l1.length && j == l2.length)
			return result.concat(l1.slice(i));
		else if (j < l2.length && i == l1.length)
			return result.concat(l2.slice(j));
		else if (l1[i] <= l2[j])
			result.push(l1[i++]);
		else
			result.push(l2[j++]);
	}
	return result;
}

onmessage = msg => {
	let data = msg.data;
	if (data.kind === "job") { // a job request is received to sort a list
		console.log(`job ${data.level}`);
		let list = data.list;
		let level = data.level;
		let id = data.id;
		if (level == 0 || list.length <= 1) {
			// we sort using the sort method of JavaScript API
			list.sort((a,b) => a - b);
			postMessage({"kind": "result", "list": list, "id": id}); // send back the sorted list
		} else {
			// cut the list
			let list1 = list.slice(0, list.length/2);
			let list2 = list.slice(list.length/2, list.length);
			let w = new Worker("mergeSort.js");
			let receivedChunks = [null, null];
			w.onmessage = msg => {
				// a result is received with a sorted list
				receivedChunks[msg.data.id] = msg.data.list;
				if (receivedChunks[0] !== null && receivedChunks[1] !== null) {
					let mergedList = merge(receivedChunks[0], receivedChunks[1]);
					postMessage({"kind": "result", "list": mergedList, "id": id});
				}
			}
			w.postMessage({"kind": "job", "id": 0, "list": list1, "level": level-1});
			w.postMessage({"kind": "job", "id": 1, "list": list2, "level": level-1});
		}
	}
}

Tâche coopérative dans la thread principale avec requestIdleCallback()

L'appel requestIdleCallback() permet de demander l'exécution d'une petite tâche (de temps d'exécution ≤ 50 ms) dans la thread principale. Elle est exécutée à un moment propice lorsque la thread principale est peu occupée.

Utilisation de requestIdleCallback() :

On écrit une fonction taskFunc(info) avec la tâche à exécuter
On demande son exécution avec let handle = window.requestIdleCallback(taskFunc, {"timeout": timeoutInMillis}) ; si la thread principale n'a pas trouvé de créneau libre avant le timeout indiqué, la fonction est quand même exécutée (spécifier timeout est facultatif)
On peut annuler au besoin la demande avec window.cancelIdleCallback(handle)
Le paramètre info de la fonction taskFunc appelée est un objet contenant les attributs suivants :
1. La fonction info.timeRemaining() permet de connaître le temps restant alloué à la tâche ; la fonction doit respecter cette limite pour ne pas engorger la thread principale
2. Le booléan info.didTimeout est true si la fonction a été appelée sur déclenchement du timeout : cela signifie qu'aucun créneau disponible n'a été trouvé ; dans de cas info.TimeRemaining() == 0 et il faut sortir au plus vite de la fonction taskFunc
Si taskFunc souhaite modifier l'arbre DOM, il est conseillé d'appeler window.requestionAnimationFrame(refreshFunc) avec une fonction refreshFunc réalisant les opérations de modification

☞ Il est possible de découper les tâches très longues en une séquence de petites sous-tâches, la sous-tâche i se terminant et planifiant la sous-tâche i+1 dès que info.timeRemaining() atteint 0.

Voici une réécriture de l'exemple du compteur incrémenté en utilisant requestIdleCallback() test ici:

<html>
	<body>
		<p>Counter value: <span id="counter">0</span></p>
		<button id="startButton">Start</button>
		<button id="stopButton">Stop</button>
		<script type="module">
			let counter = 0;
			let interrupted = true;
			let counterNode = document.getElementById("counter");
			let sliceComputation = (info) => {
				if (! info.didTimeout)
					while (info.timeRemaining() > 0) {
						for (let i = 0; i < 1000; i++)
							counter++;
						counterNode.textContent = `${counter}`;
					}
				if (! interrupted) requestIdleCallback(sliceComputation);
			};					
					
			document.getElementById("startButton").onclick = () => { interrupted = false; requestIdleCallback(sliceComputation); };
			document.getElementById("stopButton").onclick = () => { interrupted = true; };
		</script>
	</body>
</html>

On peut ainsi réécrire l'exemple précédent de factorisation d'entier en utilisant requestIdleCallback plutôt qu'un WebWorker (test ici :

(() => {
	let numberInput = document.querySelector("input[name='numberToFactorize']");
	let startButton = document.querySelector("input[name='startFactorization']");
	let stopButton = document.querySelector("input[name='stopFactorization']");
	let resultArea = document.querySelector("#factorizationResult");
	let remainingArea = document.querySelector("#remainingToFactor");

	let d = null; // factorization data

	let addFactor = (data, factor) => {
		if (data.factors.length > 0 && data.factors[data.factors.length - 1][0] === factor)
			data.factors[data.factors.length - 1][1]++;
		else
			data.factors.push([factor, 1]);
		data.remainingToFactor = data.remainingToFactor / factor;
		// update the UI with the remaining number to factorize
		window.requestAnimationFrame( () => {
			remainingArea.innerText = data.remainingToFactor;
		});
	};

	let displayResult = (data) => {
		remainingArea.innerText = data.remainingToFactor;
		let resultText = "";
		for (let [factor, power] of d.factors) {
			if (resultText.length > 0) resultText += "\n";
			resultText += factor + "^" + power;
		}
		resultText += "\n" + data.status;
		resultArea.innerText = resultText;
		startButton.disabled = false;
		stopButton.disabled = true;
	}
		

	startButton.onclick = event => {
		d = {"status": "started", "cancelled": false, "number": BigInt(numberInput.value), "divider": 2n, "factors": [], "handle": null};
		d.remainingToFactor = d.number;
		let taskFunc = function(info) {
			while (d.remainingToFactor > 1n && info.timeRemaining() > 0) {
				if (d.divider * d.divider > d.remainingToFactor)
					addFactor(d, d.remainingToFactor);
				else if (d.remainingToFactor % d.divider == 0n)
					addFactor(d, d.divider); // factor found
				else
					d.divider += (d.divider == 2n)?1n:2n; // increase the divider
			}
			if (d.remainingToFactor > 1n) { // we must schedule a task to finish the work
				d.handle = window.requestIdleCallback(taskFunc, {});
				window.requestAnimationFrame( () => {currentDivider.innerText = d.divider; });
			} else
				window.requestAnimationFrame( () => { d.status = "completed"; displayResult(d) });
		};
		d.handle = window.requestIdleCallback(taskFunc, {});
		resultArea.innerText = "Computing...";
		startButton.disabled = true;
		stopButton.disabled = false;
	};

	stopButton.onclick = event => {
		if (d != null && d.status === "started") {
			d.status = "cancelled";
			window.cancelIdleCallback(d.handle);
			displayResult(d);
		}
	};
})()