Recently, I have been trying to expand my knowledge as a backend developer. I want to understand solving problems at scale and also breaking down big tasks into little chunks of tasks. Before I bore you with gibberish, what we will be trying to achieve today is simple > Find all the prime numbers from 1.....n A very classic interview question. To be honest I didn't really settle down to solve it, not because I didn't want to but because I had a different end goal in mind. Get the simplest code you can find and try to achieve at a lesser time using multithreading in NodeJS Before we dive into the code, we need to understand what the problem is. When you run a typical NodeJS program what you get is a single process, single-thread, single event-loop, and single instance app running in the background. (Please correct me if I am wrong.) Now imagine trying to find the prime numbers between 1 and 250 million and that's just a function within your application... Yeah, you guessed right. To achieve multithreading in NodeJS, you need to use the module and you can only get this from Node v10(experimental) and above. It became fully available from Node v12. worker_threads Like I said earlier, our aim is to find the prime numbers between . We could use to solve the problem which is very efficient. But I wanted something that would overwork/overclock my CPU so that I could really appreciate multithreading for what it is. 1....n Sieve of Eratosthenes To start with Create a folder, Name it anything Create 2 files and threaded.js non-threaded.js Now in the file paste this code in it non-threaded.js checkPrime = { ( i = , s = .sqrt(num); i <= s; i++) (num % i === ) ; num > ; }; maxNumber = _000; primeNumbers = []; startTime = .now(); ( index = ; index < maxNumber; index++) { (checkPrime(index)) { primeNumbers.push(index); } } endTime = .now(); .log( , (endTime - startTime) / , ); .log( , primeNumbers); // Function to check if a number is prime number or not const => num for let 2 Math if 0 return false return 1 const 100 // Where the loop should stop let const Date for let 0 if const Date console 'JOB TOOK:: ' 1000 ' to complete' console 'PRIMES:: ' So this is a basic NodeJS program that loops from 0 to ` ` and stores the prime numbers in the Array called ` `. Also, I am calculating the time it takes for the code to run. maxNumber primeNumbers const maxNumber = 100_000; If you are confused about this line of code, please don't be. It's totally allowed in NodeJS. For me I use it to represent very long integers in my code. Before running the benchmark, here are the details of my current laptop OS: Ubuntu 20.04 CPU: Intel® Core™ i7-6500U CPU @ 2.50GHz × 4 RAM: 12gb (I know it's terrible, forgive me, distinguished colleagues) Node Version: 14 BENCHMARK 0-100: ~0s 0-1_000: ~0.001s 0-10_000: ~0.003s 0-100_000: ~0.021s 0-1_000_000: ~0.351s 0-10_000_000: ~8.3s Let's try 100 million... Lol... 0-100_000_000: ~220s Wheeewww... My laptop fan almost blew out running this. Before going deep, what is ? according to : MULTI-THREADING Wikipedia In computer architecture, multithreading is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to provide multiple threads of execution concurrently, supported by the operating system. The keyword here is , how do we breakdown the problem into sub-problems and have them execute concurrently?, NOT sequentially. Remember, we are trying to save time, with as little resources as possible. concurrently So before we go any further, I will post the code and explain everything section by section. Grab this block of code and put it in the `threaded.js` file you created earlier { Worker, isMainThread, parentPort, workerData } = ( ); os = ( ); checkPrime = { ( i = , s = .sqrt(num); i <= s; i++) (num % i === ) ; num > ; }; (isMainThread) { startTime = .now(); coresCount = os.cpus().length; numberOfElements = _000_000; workers = []; sharedBuffer = SharedArrayBuffer( .BYTES_PER_ELEMENT * numberOfElements); arr = (sharedBuffer); .log( ); numElementsPerThread = .ceil(numberOfElements / coresCount); workerIndex = ; completed = ; (workers.length < coresCount) { workerIndex++; start = workers.length * numElementsPerThread; end = start + numElementsPerThread; worker = Worker(__filename, { : { start, end, : workerIndex, arr, }, }); worker.on( , message => { (message.completed) { completed++; } (completed === coresCount) { .log( ); endTime = .now(); .log((endTime - startTime) / , ); .log( , arr); .log( , .from(arr).filter( )); } .log( , message.index); }); workers.push(worker); } } { .log({ : workerData.start, : workerData.end, : workerData.index, }); ( i = workerData.start; i < workerData.end; i++) { check = checkPrime(i); (check) { workerData.arr[i] = i; } } parentPort.postMessage({ : , : workerData.index }); } const require 'worker_threads' const require 'os' const => num for let 2 Math if 0 return false return 1 if const Date const const 100 let const new Int32Array const new Int32Array console 'MAIN THREAD' const Math let 0 let 0 while const const const new workerData index 'message' if if console 'Totally done!' const Date console 1000 'seconds to complete' console 'FINAL ARR:: ' console 'FINAL ARRAY:: ' Array Boolean console 'final time:: ' else console start end index for let let if completed true index Like I said earlier, to perform multi-threaded operations in NodeJS, we need the module. This enables us to write programs that take advantage of multi-threading. worker_threads { Worker, isMainThread, parentPort, workerData } = ( ); os = ( ); const require 'worker_threads' const require 'os' This is a normal standard import of packages we will need to make this program work checkPrime = { ( i = , s = .sqrt(num); i <= s; i++) (num % i === ) ; num > ; }; const => num for let 2 Math if 0 return false return 1 Remember this function from the version of our app?. All it does is take a number and tells us if it's a prime number or not. non-threaded Before we dive into the main code, I want to show you the basic structure of the code, so that you can further understand the main code. { Worker, isMainThread, parentPort, workerData } = ( ); os = ( ); (isMainThread) { .log( ); worker_count = os.cpus().length; .log( , worker_count); workers = ; (workers < worker_count) { Worker(__filename); workers++; } } { .log( ); } const require 'worker_threads' const require 'os' if console 'Main THREAD' let console 'THREADS::: ' let 0 while new else console 'Worker THREAD' Copy the above piece of code save it in a js file and run it. You should see a result like the one below Main THREAD THREADS::: Worker THREAD Worker THREAD Worker THREAD Worker THREAD 4 From the result above, you can see I use a crappy workstation. The from tells us if we are running on the main thread or in one of the worker threads. In the , I spun up more workers based on the number of cores my computer has. That's as basic as a multithreaded program can look like in NodeJS. Now let's get back to the main program. isMainThread worker_threads main thread sharedBuffer = SharedArrayBuffer( .BYTES_PER_ELEMENT * numberOfElements); arr = (sharedBuffer); const new Int32Array const new Int32Array To understand the above code, you need to understand that for multithreading to work, we will need a shared memory where every worker thread will output their result when they are done. Hence, our need for [ ]. Each index in the will be initialized with zero. sharedArrayBuffer READ THIS sharedArrayBuffer So we created a and each element of the array will be of type and the length of the array will be the ceiling to where we want to search for prime numbers. sharedArrayBuffer Int32 numElementsPerThread = .ceil(numberOfElements / coresCount); const Math Remember, multi-threading means sub-processes working concurrently. So basically we are calculating what size of the chunk we will give to each worker to execute. e.g if i want to search for prime numbers from 0-100 and my is 4 then each worker will get 100/4 (=25) elements to perform their operations on. coreCount Now, into the while-loop start = workers.length * numElementsPerThread; end = start + numElementsPerThread; worker = Worker(__filename, { : { start, end, : workerIndex, arr, }, }); const const const new workerData index Even though, we know the size of the chunk each worker will get, how do we set the boundary for each worker. and variable are calculating and holding that value for each worker we are about to spin-up. start end We initialize each worker with these parameters , , (tracking the workers individually) and (this is the shared buffer array each worker will output their result to) start end index arr worker.on( , message => { (message.completed) { completed++; } (completed === coresCount) { .log( ); endTime = .now(); .log((endTime - startTime) / , ); .log( , arr); .log( , .from(arr).filter( )); } .log( , message.index); }); 'message' if if console 'Totally done!' const Date console 1000 'seconds to complete' console 'FINAL ARR:: ' console 'FINAL ARRAY:: ' Array Boolean console 'final time:: ' When each worker finishes its execution, it sends a signal back to the with whatever data it wants to send. So the block of code above is listening for when that event fires. When the last worker sends back its result, we calculate how long the whole process took, we also convert the into the normal Javascript array we are used to. The problem here is, some indexes contain elements that are zero (not prime numbers). So we use the . trick to filter out all values from the Array. mainThread Int32Array filter(Boolean) falsy ( i = workerData.start; i < workerData.end; i++) { check = checkPrime(i); (check) { workerData.arr[i] = i; } } for let let if In each worker, we just loop between its boundaries and check if each index is a prime number or not. If it's a prime number, then change the number at that index in the to . sharedArrayBuffer i e.g If is 7 and 7 is a prime number, then go to and put 7 at index 7 i sharedArrayBuffer parentPort.postMessage({ : , : workerData.index }); completed true index Once the loop terminates, send back completion response to the . mainThread And that my friends, was how I multi-threaded my way through prime numbers. Why don't you run it and tell me the results you got in the comment section. Please don't break your computers while at it, I won't be held liable... lol Please share your results in the comment section. I hope you learned something new. Previously published at https://umaradam.xyz/prime-numbers-and-multi-threading
