Multithreaded code runs worse or roughly as fast as singlethreaded

Question

I am trying to solve the N Queen problem using multiple threads. However, the single threaded version of it runs either faster or roughly the same as the multithreaded one.

In essence, I use a queue which all the threads share. They pop states from the queue and expand them and add then them to the queue. I have tried playing around with the number of threads but to no avail, the more threads I add after around 8 the performance degenerates. The algorithm is correct in that the output is the same in both versions.

Any ideas?

Here's the code:

public class Queens {


    //Thread
    static class Runner implements Runnable {

        private BlockingQueue<Configuration> queue;
        private final AtomicInteger total;

        public Runner(BlockingQueue<Configuration> q, AtomicInteger total) {
            this.queue = q;
            this.total = total;

        }

        public void run()  {

            while(!queue.isEmpty()) {

                Configuration currentConfiguration = null;

                try {
                    currentConfiguration = queue.take();

                }
                catch(InterruptedException e) {

                }

                if(currentConfiguration.done()) {
                    //currentConfiguration.printConfiguration();
                    total.incrementAndGet();
                    System.out.println("Solution");
                    continue;
                }

                for(int i = 0; i < currentConfiguration.getSize(); i++) {


                    if(safe(currentConfiguration, i, currentConfiguration.getColumn())) {


                        Configuration childConfig = new Configuration(currentConfiguration.getColumn() + 1, 
                                currentConfiguration.getBoard());

                        childConfig.place(i, currentConfiguration.getColumn());


                        queue.add(childConfig);
                    }
                }
            }

        }


        //Returns true if we can place a queen on that row and column.
        private  boolean safe(Configuration current, int row, int col)  {


            for (int i = 0; i < col; i++) 
                if (current.getBoard()[row][i] == 1) 
                    return false;


            for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) 
                if (current.getBoard()[i][j] == 1) 
                    return false; 


            for (int i = row, j = col; j >= 0 && i < current.getSize(); i++, j--) 
                if (current.getBoard()[i][j] == 1) 
                    return false; 


            return true; 
        }
    }

    //Board configuration class.
    static class Configuration {

        private int column;
        private int[][] board;
        private int size;

        public  Configuration(int column, int[][] b) {
            this.column = column;
            this.board = new int[b.length][b.length];
            this.size = b.length;
            for(int i = 0; i < size; i++) {
                for(int j = 0; j < size; j++) {
                    board[i][j] = b[i][j];
                }
            }   
        }

        public int getSize() {
            return size;
        }

        public int getColumn() {
            return column;
        }
        public int[][] getBoard() {
            return board;
        }
        public boolean done() {
            if(column == size)
                return true;
            return false;
        }

        public void place(int row, int column) {
            board[row][column] = 1;
        }



        //Method prints the current configuration.
        public synchronized void printConfiguration() {

            synchronized(Configuration.class) {
                System.out.println(Thread.currentThread().getName());
                for(int i = 0; i < size; i++) {
                    for(int j = 0; j < size; j++) {
                        System.out.print(board[i][j] + " ");
                    }
                    System.out.println();
                }
            }


        }
    }
    public static void main(String[] args) throws InterruptedException {


        Configuration x = new Configuration(0, new int[13][13]);

        int threads = 10;

        AtomicInteger totalSolutions = new AtomicInteger(0);
        List<Thread> mythreads = new ArrayList<Thread>();

        BlockingQueue<Configuration> q = new LinkedBlockingDeque<>();

        //Initially the board is empty
        q.put(x);


        long startTime = System.currentTimeMillis();
        //Run 10 threads
        for(int i = 0; i < threads; i++) {
            Thread newthread = new Thread(new Runner(q, totalSolutions));
            newthread.start();
            mythreads.add(newthread);
        }

        for(Thread t : mythreads) {
            try {
                t.join();
            }
            catch(Exception e) {};
        }
        System.out.println(totalSolutions.get());


        long endTime = System.currentTimeMillis();
        System.out.println("Time: " + (endTime - startTime));

    }

}

Answer 1

This was too long for a comment so I have to write it as an answer, apology on that.

In run method I've added the following like:

System.out.println(Thread.currentThread().getName() + " taking " + currentConfiguration.toString() + " out of " + queue.size() + " elem");

When running a single thread program it looks like this:

Thread-0 taking jobs.DeleteMe$Configuration@279b9032 out of 925326 elem
Thread-0 taking jobs.DeleteMe$Configuration@15ced747 out of 925327 elem
Thread-0 taking jobs.DeleteMe$Configuration@42689f59 out of 925328 elem
Thread-0 taking jobs.DeleteMe$Configuration@29aeeda2 out of 925329 elem

When running 10 threads the log looks like:

Thread-6 taking jobs.DeleteMe$Configuration@2775c7e7 out of 39393 elem
Thread-7 taking jobs.DeleteMe$Configuration@4e0ae08b out of 39308 elem
Thread-6 taking jobs.DeleteMe$Configuration@5eb0ba9 out of 39404 elem
Thread-9 taking jobs.DeleteMe$Configuration@12321211 out of 39401 elem
Thread-0 taking jobs.DeleteMe$Configuration@13a07923 out of 39383 elem
Thread-9 taking jobs.DeleteMe$Configuration@442cf86a out of 39415 elem
Thread-0 taking jobs.DeleteMe$Configuration@49366e2a out of 39420 elem
Thread-8 taking jobs.DeleteMe$Configuration@1c4bcfa5 out of 39378 elem

So it seems there is nothing preventing multiple threads to work.

Since your code uses one resource intensively, which is memory.

So I guess the reason is that memory cache is used more efficiently when there is a single thread running instead of multiple threads. It means that single thread access usually Configuration which is already in CPU cache, while when running multithreaded there are more misses.

See: Is multi-thread memory access faster than single threaded memory access?

On the sidenote, it would probably be efficient to take a configuration which was the most recently added, BlockingQueue takes the first configuration, it would probably be more efficient to use LinkedBlockingDeque.

So I tried with LinkedBlockingDeque, with 10 threads, it runs for Time: 3753 with 1 thread: Time: 3352

(it's 3x speedup for me than the version with LinkedBlockingQueue).

Source:

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.atomic.AtomicInteger;

/**
 *
 * @author mladen
 */
public class DeleteMe {

  //Thread
  static class Runner implements Runnable {

    private LinkedBlockingDeque<Configuration> queue;
    private final AtomicInteger total;

    public Runner(LinkedBlockingDeque<Configuration> q, AtomicInteger total) {
      this.queue = q;
      this.total = total;

    }

    public void run() {

      while (!queue.isEmpty()) {

        Configuration currentConfiguration = null;

        //try {
          currentConfiguration = queue.removeLast();
          //System.out.println(Thread.currentThread().getName() + " taking " + currentConfiguration.toString() + " out of " + queue.size() + " elem");
//        } catch (InterruptedException e) {
//
//        }

        if (currentConfiguration.done()) {
          //currentConfiguration.printConfiguration();
          total.incrementAndGet();
          System.out.println("Solution");
          continue;
        }

        for (int i = 0; i < currentConfiguration.getSize(); i++) {

          if (safe(currentConfiguration, i, currentConfiguration.getColumn())) {

            Configuration childConfig = new Configuration(currentConfiguration.getColumn() + 1,
              currentConfiguration.getBoard());

            childConfig.place(i, currentConfiguration.getColumn());

            queue.add(childConfig);
          }
        }
      }

    }

    //Returns true if we can place a queen on that row and column.
    private boolean safe(Configuration current, int row, int col) {

      for (int i = 0; i < col; i++) {
        if (current.getBoard()[row][i] == 1) {
          return false;
        }
      }

      for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (current.getBoard()[i][j] == 1) {
          return false;
        }
      }

      for (int i = row, j = col; j >= 0 && i < current.getSize(); i++, j--) {
        if (current.getBoard()[i][j] == 1) {
          return false;
        }
      }

      return true;
    }
  }

  //Board configuration class.
  static class Configuration {

    private int column;
    private int[][] board;
    private int size;

    public Configuration(int column, int[][] b) {
      this.column = column;
      this.board = new int[b.length][b.length];
      this.size = b.length;
      for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
          board[i][j] = b[i][j];
        }
      }
    }

    public int getSize() {
      return size;
    }

    public int getColumn() {
      return column;
    }

    public int[][] getBoard() {
      return board;
    }

    public boolean done() {
      if (column == size) {
        return true;
      }
      return false;
    }

    public void place(int row, int column) {
      board[row][column] = 1;
    }

    //Method prints the current configuration.
    public synchronized void printConfiguration() {

      synchronized (Configuration.class) {
        System.out.println(Thread.currentThread().getName());
        for (int i = 0; i < size; i++) {
          for (int j = 0; j < size; j++) {
            System.out.print(board[i][j] + " ");
          }
          System.out.println();
        }
      }

    }
  }

  public static void main(String[] args) throws InterruptedException {

    Configuration x = new Configuration(0, new int[13][13]);

    int threads = 1;

    AtomicInteger totalSolutions = new AtomicInteger(0);
    List<Thread> mythreads = new ArrayList<Thread>();

    LinkedBlockingDeque<Configuration> q = new LinkedBlockingDeque<>();

    //Initially the board is empty
    q.put(x);

    long startTime = System.currentTimeMillis();
    //Run 10 threads
    for (int i = 0; i < threads; i++) {
      Thread newthread = new Thread(new Runner(q, totalSolutions));
      newthread.start();
      mythreads.add(newthread);
    }

    for (Thread t : mythreads) {
      try {
        t.join();
      } catch (Exception e) {
      };
    }
    System.out.println(totalSolutions.get());

    long endTime = System.currentTimeMillis();
    System.out.println("Time: " + (endTime - startTime));

  }
}

Answer 2

The synchronization overhead is massive here. Try doing more work without fetching from the queue all the time.

Also, between the isEmpty call and the take call the queue can become empty. Avoid this race condition by using poll and checking for null result.

The memory overhead can be mitigated by going depth-first instead of breadth-first.

Code follows:

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
public class Queens {


    //Thread
    static class Runner implements Runnable {

        private BlockingQueue<Configuration> queue;
        private final AtomicInteger total;
        private boolean local;

        public Runner(BlockingQueue<Configuration> q, AtomicInteger total) {
            this.queue = q;
            this.total = total;
        }

        public void run()  {

            while(true) {
                Configuration currentConfiguration = null;
                try {
                    currentConfiguration = queue.poll(50, TimeUnit.MILLISECONDS);
                }
                catch(InterruptedException e) {

                }

                if(!local && queue.size() > 1000) local = true;


                if(currentConfiguration == null){
                    break;
                }

                recurse(currentConfiguration);

            }
            System.out.println("DONE");

        }


        public void recurse(Configuration c){
            if(c.done()){
                total.incrementAndGet();
                return;
            }
            for(int i = 0; i < c.getSize(); i++) {


                if(safe(c, i, c.getColumn())) {
                    c.place(i, c.getColumn());
                    c.setColumn(c.getColumn() + 1);


                    if(local){
                        recurse(c);
                    }else{
                        queue.add(c.clone());
                    }

                    c.setColumn(c.getColumn() - 1);
                    c.clear(i, c.getColumn());
                }
            }
        }

        //Returns true if we can place a queen on that row and column.
        private  boolean safe(Configuration current, int row, int col)  {


            for (int i = 0; i < col; i++) 
                if (current.getBoard()[row][i] == 1) 
                    return false;


            for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) 
                if (current.getBoard()[i][j] == 1) 
                    return false; 


            for (int i = row, j = col; j >= 0 && i < current.getSize(); i++, j--) 
                if (current.getBoard()[i][j] == 1) 
                    return false; 


            return true; 
        }
    }

    //Board configuration class.
    static class Configuration {

        private int column;
        private int[][] board;
        private int size;

        public  Configuration(int column, int[][] b) {
            this.column = column;
            this.board = new int[b.length][b.length];
            this.size = b.length;
            for(int i = 0; i < size; i++) {
                for(int j = 0; j < size; j++) {
                    board[i][j] = b[i][j];
                }
            }   
        }

        public Configuration clone(){
            return new Configuration(column, board);
        }

        public int getSize() {
            return size;
        }

        public int getColumn() {
            return column;
        }
        public void setColumn( int v) {
            column = v;
        }

        public int[][] getBoard() {
            return board;
        }
        public boolean done() {
            if(column == size)
                return true;
            return false;
        }

        public void place(int row, int column) {
            board[row][column] = 1;
        }

        public void clear(int row, int column){
            board[row][column] = 0;
        }



        //Method prints the current configuration.
        public synchronized void printConfiguration() {

            synchronized(Configuration.class) {
                System.out.println(Thread.currentThread().getName());
                for(int i = 0; i < size; i++) {
                    for(int j = 0; j < size; j++) {
                        System.out.print(board[i][j] + " ");
                    }
                    System.out.println();
                }
            }


        }
    }
    public static void main(String[] args) throws InterruptedException {

        final int size = 14;

        Configuration x = new Configuration(0, new int[size][size]);

        int threads = 8;

        AtomicInteger totalSolutions = new AtomicInteger(0);
        List<Thread> mythreads = new ArrayList<Thread>();

        BlockingQueue<Configuration> q = new LinkedBlockingDeque<>();

        //Initially the board is empty
        q.put(x);


        long startTime = System.currentTimeMillis();
        //Run 10 threads
        for(int i = 0; i < threads; i++) {
            Thread newthread = new Thread(new Runner(q, totalSolutions));
            newthread.start();
            mythreads.add(newthread);
        }

        for(Thread t : mythreads) {
            try {
                t.join();
            }
            catch(Exception e) {};
        }
        System.out.println(totalSolutions.get());


        long endTime = System.currentTimeMillis();
        System.out.println("Time: " + (endTime - startTime));

    }

}