/ es6

N-Queens: Node Cluster

Just recently I was talking with a student about using node clusters and realized that it would be a great addition to the collection of N-Queens comparisons I have done so far.

If you aren't sure what I'm referring to you can find the previous entires here, here and here.

So, this morning I woke up and did it before work and without further ado, here it is.

The Structure

Node Clusters

Working with node clusters is incredibly straight forward and a lot of fun. As I've come to really enjoy working with concurrent processes this was no surprise. What was surprising was how fast they were! Spoiler: not as fast as Go. But who would expect it to be?! Using a node cluster still allows you to drastically increase the speed of a process and in more practical web applications can greatly improve the rate at which you handle traffic and requests. Let's look at how it works.

So unlike web workers where each worker needs to be in it's own file, the worker processes in a node cluster all start using the same file. The cluster module contains an isMaster property which lets you direct the flow of control through that file based on whether this is the first process or a worker process which has been created.

const cluster = require('cluster');
const countQueensFrom = require('./n-queens');
const numCPUs = require('os').cpus().length;

if (cluster.isMaster) {
  // do master process stuff
} else {
  // do worker process stuff
}

If this is located in index.js then running node index.js will run the program, bring in the cluster module, my n-queens function, and the numCPUs. This third one is very important as we will see shortly. Then the program checks to see if the current execution context isMaster and either does the master process or the worker process accordingly.

Master Process

Here is where that numCPUs variable becomes important. You can see this is just accessed by reading the length of the array-like which contains reference to the current machines actual cpu cores. Why is this important? Well each core can maintain sequential operation of one thread and each node instance is it's own thread so it makes sense to only create as many workers as you have cpu's to maintain them. This works fine when you only want to solve n-queens for n === numCPUs but requires some interesting footwork to get up to n === 16.

This ends up being a chunk of code so I will walk through this bit by adding comments throughout.

if (cluster.isMaster) {
  // set the n to solve for
  const n = 8;

  // setup variables to track solutions
  // processes started and process completed
  let solutions = 0;
  let processes = 0;
  let completed = 0;

  // set limit to # of process to the lower of either cpu's or n
  const limit = numCPUs < n ? numCPUs : n;

  // until there are as many processes as the limit 
  for (let i = 0; processes < limit; i++) {
    // create a worker process
    let worker = cluster.fork();

    // send that worker the 'start' message
    // include the processs # to determine the starting square 0 to (n-1)
    // include n value
    worker.send({ type: 'start', processes, n });
    processes++;

    // when this worker sends a message to the master
    worker.on('message', (msg) => {
      // if it is a 'completed' message
      if (msg.type === 'completed') {
        // add it's solutions to the solutions count
        solutions += msg.solutions;
        // increase completed processes count
        completed++;

        // if # processes less than the total required to run, n
        if (processes < n) {
          // send this worker a new start message with the next starting postion
          worker.send({ type: 'start', processes, n });
          processes++;

        } else if (completed === n) {
          // otherwise if this was the last process that needed to complete
          // shut down the cluster
          cluster.disconnect();

        } else {
          // if there are no more processes to run but not all have completed
          // kill this worker
          worker.kill();
        }
      }
    });
  }
}

Wooo, ok. A bit of stuff there, heres the short version: limit the number of processes by the cpu's. Start as many processes as you can sending them necessary info. Set up a handler for when that worker sends a message back. If the worker says 'complete' and more processes still need to start then give the worker another process. If it was the last needed to finish then shut it all down. If no more need to start but it wasn't the last just kill the worker.

Worker

The worker code by comparison is very simple. I put the n-queens functions in a module and imported it into the index.js. I won't go over that code here since I think the past articles have covered the solution plenty. With the function imported all I have to do in this file is set up an onmessage handler for the worker.

  process.on('message', (msg) => {
    if (msg.type === 'start') {
      countQueensFrom(msg.processes, msg.n);
    }
  });

You see here I refer to the worker as process. This is the reference made available from node to refer to the current worker executing the code. So I give it a handler for a message and simply run the countQueensFrom function passing the starting square and the n length of the board.

This function looks very much like the supervisor in the web workers solution.

function countQueensFrom(i, n){
  const board = buildBoardWithPiece(i, n);
  const cols = buildColsArrayWithPiece(i, n);
  const solutions = search(board, cols, 1, 0);

  process.send({ type: 'completed', solutions });
}

It builds a board, makes its column tracking array and sets off to search for solutions. After it's finished it just calls send on the current process and the master receives the sent message executing the handler that was set up in the maters code.

Benchmarks

All in all I found this much simpler than working with web workers and, again, soooooo much faster. Check it out!

Sequential (s) Web Workers (s) Node Cluster
N = 8 .004 .219 .128
N = 9 .014 .219 .132
N = 10 .056 .264 .135
N = 11 .229 .479 .169
N = 12 1.010 1.425 .354
N = 13 5.495 6.524 1.377
N = 14 32.871 35.310 8.682
N = 15 209.461 272.359 59.970
N = 16 untested untested 399.583