Web Worker Strategies in JavaScript

Sunday, June 10th, 2018

Web Workers

Web Worker is an API provided by modern browsers that allows developers to run CPU intensive tasks asynchronously. More preciesly it allows developers to run code seperate from UI thread so it does not slow down the UI. This helps run the websites smoothly and prevents frame drops. For more information about Web Worker API you can visit blog post Multi-Threading with JavaScript Web Workers. In this blog post element-wise 2D-matrix multiplication is used to demonstrate the different Web Worker strategies.

The worker.js file will contain the following code:

onmessage = function(event){
           var arr = event.data.arr;
           var updatedArr = [];
           var startIndex = event.data.startIndex;
           var endIndex = event.data.endIndex;
           var constant = event.data.constant;
           for(var i =startIndex; i<=endIndex; i++){
                updatedArr[i-startIndex] = [];
              for(var j =0; j<2; j++){
                 updatedArr[i-startIndex][j] = arr[i][j]*constant;
              }
           }

           postMessage({updatedArr: updatedArr, prevStartIndex: startIndex, prevEndIndex: endIndex});
}

Basically the Web Worker will multiply given array according to 'startIndex' and 'endIndex' of the first level using the 'constant'.

Linear Execution

<!DOCTYPE html>
	<html>
	<head>
	</head>
	<body>
	    <script type="text/javascript">
	        var increments = 500;
	        var counter = 0;
	        var start = (new Date).getTime();
	        var arrLength = 10000;
	        var arr = createRandom2DArray(arrLength);
	        var totalChunks = arrLength/increments;
	        var startIndex = 0;
	        var endIndex = increments - 1;
	        var updatedArray = [];
	        var multConst = Math.PI;
	        function createRandom2DArray(length){//Generate random array of specified length.
	            var arr = [];
	            for(var i = 0; i<length; i++){
	                arr[i] = [];
	                for(var j = 0; j<2; j++){
	                    arr[i][j] = Math.floor(Math.random()*(500-100)+100);
	                }
	            }
	            return arr;
	        }
	        function createThread() {//Create Web Worker thread.
	            var worker = new Worker('./worker.js');
	            worker.onmessage = function(event) {
	                updatedArray.push(...event.data.updatedArr);//update the array after multiplication.
	                worker.terminate();//terminate worker
	                startIndex = counter*increments;//update start index.
	                endIndex = startIndex + increments -1;//update end index.
	                if (endIndex <= arrLength-1) createThread();
	                else{ //If reached end then display time and updated array.
	                    console.log('\nOriginal Array: ', arr);
	                    console.log('\nUpdated Array: ', updatedArray);
	                    console.log('\nTotal running time in ms: ',(new Date).getTime() - start);
	                }
	            };
	            worker.postMessage({startIndex: startIndex, endIndex: endIndex, constant: multConst, arr: arr}); // start the worker.
	            counter++;//update counter
	        }
	        createThread();
	    </script>
	</body>
	<html>

Basically the array can be split into 'totalChunks' which is the value of the 'arrLength' divided by 'increments'. In this example an array of length 10000 will have 10000/500=20 chunks. So 20 threads will be linearly executed with each thread processing 500 rows of the original array. The 'startIndex' and 'endIndex' are updated so that the thread will only process the sub-arry represented by those indices. After each chunk is processed the previous thread is terminated and a new thread is created with updated 'startIndex' and 'endIndex'. This results in an execution time of 1156 ms.

Pooling

<!DOCTYPE html>
<html>
<head>
</head>
<body>
    <script type="text/javascript">
        var increments = 500;
        var counter = 0;
        var start = (new Date).getTime();
        var arrLength = 10000;
        var arr = createRandom2DArray(arrLength);
        var totalChunks = arrLength/increments;
        var startIndex = 0;
        var endIndex = increments - 1;
        var updatedArray = [];
        var multConst = Math.PI;
        var cpuCores = navigator.hardwareConcurrency || 1;
        var coreCount = cpuCores;
        function createRandom2DArray(length){//Generate random array of specified length.
            var arr = [];
            for(var i = 0; i<length; i++){
                arr[i] = [];
                for(var j = 0; j<2; j++){
                    arr[i][j] = Math.floor(Math.random()*(500-100)+100);
                }
            }
            return arr;
        }
        function createThread(coreNum) {//Create Web Worker thread.
            var worker = new Worker('./worker.js');
            worker.onmessage = function(event) {
                var prevStartIndex = event.data.prevStartIndex;
                var prevEndIndex = event.data.prevEndIndex;
                updatedArray.splice(prevStartIndex, prevEndIndex-prevStartIndex, ...event.data.updatedArr);//update the array for specific indices.
                worker.terminate();//terminate worker
                startIndex = counter*increments;//update start index.
                endIndex = startIndex + increments -1;//update end index.
                if (endIndex <= arrLength-1) createThread(coreNum);
                else{ //If reached end then display time and updated array.
                    coreCount--;
                    console.log('Completed Core: ', coreNum);
                    if(coreCount===0){//All cores done computing
                        console.log('\nOriginal Array: ', arr);
                        console.log('\nUpdated Array: ', updatedArray);
                        console.log('\nCPU Cores: ', cpuCores);
                        console.log('\nTotal running time in ms: ',(new Date).getTime() - start);
                    }
                }
            };
            worker.postMessage({startIndex: startIndex, endIndex: endIndex, constant: multConst, arr: arr}); // start the worker.
            counter++;//update counter
        }
        for(var i = 0; i<cpuCores; i++){
             createThread(i);
        }
    </script>
</body>
<html>

For this example the parent threads are same number as the number of CPU cores. The use of 'cpuCores' variable allows a balanced approach. The 'startIndex' and 'endIndex' do not get updated sequentially as the previous example so '.push()' method of Array will not guarantee orderly update so '.splice()' method is used where the Web Worker returns 'prevStartIndex' and 'prevEndIndex' the same 'startIndex' and 'endIndex' passed to it initially for computation. Finally the 'coreCount' variables helps to determine that all cores have finished computation. It achives the task in 716 ms.

Single Thread Instance

<!DOCTYPE html>
<html>
<head>
</head>
<body>
    <script type="text/javascript">
        var increments = 500;
        var counter = 0;
        var start = (new Date).getTime();
        var arrLength = 10000;
        var arr = createRandom2DArray(arrLength);
        var totalChunks = arrLength/increments;
        var startIndex = 0;
        var endIndex = increments - 1;
        var updatedArray = [];
        var multConst = Math.PI;
        var worker = new Worker('./worker.js');

        function createRandom2DArray(length){//Generate random array of specified length.
            var arr = [];

            for(var i = 0; i<length; i++){
                arr[i] = [];
                for(var j = 0; j<2; j++){
                    arr[i][j] = Math.floor(Math.random()*(500-100)+100);
                }
            }

            return arr;
        }

        function createThread() {//Create Web Worker thread.
            worker.onmessage = function(event) {

                updatedArray.push(...event.data.updatedArr);//update the array after multiplication.

                startIndex = counter*increments;//update start index.
                endIndex = startIndex + increments -1;//update end index.


                if (endIndex <= arrLength-1) createThread();//Rerun for updating indices.
                else{ //If reached end then display time and updated array.
                    worker.terminate();//terminate worker
                    console.log('\nOriginal Array: ', arr);
                    console.log('\nUpdated Array: ', updatedArray);
                    console.log('\nTotal running time in ms: ',(new Date).getTime() - start);
                }
            };
            worker.postMessage({startIndex: startIndex, endIndex: endIndex, constant: multConst, arr: arr}); // start the worker.
            counter++;//update counter
        }

        createThread();
    </script>
</body>
<html>

Unlike the previous two examples the Web Woker is only created once and terminated once. This removes the overhead of creating and terminating the thread for each chunk. So the thread is only terminated once all chunks are updated. This allows for significant speed up and the total execution time is 678 ms.

Pooling with Single Instance Threads

<!DOCTYPE html>
<html>
<head>
</head>
<body>
    <script type="text/javascript">
        var increments = 500;
        var counter = 0;
        var start = (new Date).getTime();
        var arrLength = 10000;
        var arr = createRandom2DArray(arrLength);
        var totalChunks = arrLength/increments;
        var startIndex = 0;
        var endIndex = increments - 1;
        var updatedArray = [];
        var multConst = Math.PI;
        var cpuCores = navigator.hardwareConcurrency || 1;
        var coreCount = cpuCores;
        function createRandom2DArray(length){//Generate random array of specified length.
            var arr = [];
            for(var i = 0; i<length; i++){
                arr[i] = [];
                for(var j = 0; j<2; j++){
                    arr[i][j] = Math.floor(Math.random()*(500-100)+100);
                }
            }
            return arr;
        }
        function createThread(coreNum, worker) {//Create Web Worker thread.
            worker.onmessage = function(event) {
                var prevStartIndex = event.data.prevStartIndex;
                var prevEndIndex = event.data.prevEndIndex;
                updatedArray.splice(prevStartIndex, prevEndIndex-prevStartIndex, ...event.data.updatedArr);//update the array for specific indices.

                startIndex = counter*increments;//update start index.
                endIndex = startIndex + increments -1;//update end index.

                if (endIndex <= arrLength-1) createThread(coreNum, worker);
                else{ //If reached end then display time and updated array.
                    coreCount--;
                    worker.terminate();//terminate worker

                    console.log('Completed Core: ', coreNum);
                    if(coreCount===0){//All cores done computing
                        console.log('\nOriginal Array: ', arr);
                        console.log('\nUpdated Array: ', updatedArray);
                        console.log('\nCPU Cores: ', cpuCores);
                        console.log('\nTotal running time in ms: ',(new Date).getTime() - start);
                    }
                }
            };
            worker.postMessage({startIndex: startIndex, endIndex: endIndex, constant: multConst, arr: arr}); // start the worker.
            counter++;//update counter
        }
        for(var i = 0; i<cpuCores; i++){
             createThread(i,new Worker('./worker.js'));
        }
    </script>
</body>
<html>

This approach further extends the previous example by creating and terminating the thread once and removing associated overhead. It also creates number of threads equal to the number of CPU cores. This enables the code to compute much faster compared to previous methods. So the final execution time comes to 542 ms which is the fastest of all approaches.