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)); } }

You seem to be absolutely hammering that queue from multiple threads. You'd probably betterof using something like fork-join. — Tom Hawtin - tackline
– Tom Hawtin - tackline, Commented Mar 7, 2020 at 14:01
How many cpu cores does the machine have where you run the tests? — rsp
– rsp, Commented Mar 7, 2020 at 15:25

Mladen Adamovic · Accepted Answer · 2020-03-07 14:37:59Z

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)); } }

maniek · Accepted Answer · 2020-03-07 15:54:27Z

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)); } }

Why does going depth first work but not breadth-first? Is this because of caching? Also what I get from if(.. queue.size() > 1000) is that this limits depth. Why?
@MetaXenology : depth-first is faster because it avoids creating and deleting all these Configuration instances. The mentioned line is just to add some configurations to the queue, then workers will pick up the elements, and go depth-first from these. More elegantly, you could add some (like a few thousand) starter configurations in a single thread, then start the workers, which would all go depth-first. This was something I could not be bothered to do.
@MetaXenology the main problem, which causes multithreading to not work at all, is that in your code the queue is being hammered all the time, the threads are waiting for access to the queue. You are doing too little work in-between queue accesses.

Collectives™ on Stack Overflow

Multithreaded code runs worse or roughly as fast as singlethreaded

2 Answers 2

Comments

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Linked

Related