Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

this is my first question in SOF.

I have a question about this problem.

I coded a linear (without threads) app, it looks ok, solving speed - normal. Also I coded a multi-thread app, and it is ok, when I use 2 processors and 2 threads, also it is fine when I use 4 processors and 4 threads, but when I try to solve with 6 processors and 6 threads I am not satisfied with solving speed. I attached a source code and my results table. Maybe do you have any ideas how to make it faster?

P.S. algorithm works perfect, it founds the correct answer.

Thank you for time, xsiraul.

Main.java file:

import java.util.Scanner;

public class Main {

     public static void main(String[] args) throws InterruptedException {
        // TODO Auto-generated method stub
        //Scanner scanner = new Scanner(System.in);
        //System.out.println("Iveskite N:");
        //int n = Integer.parseInt(scanner.nextLine());
         int n = Integer.parseInt(args[0]);
         int maxThreads = Integer.parseInt(args[1]);
         Karalienes.setMaxGSK(maxThreads);
        Karalienes queens = new Karalienes(n, 1, new int[n+1]);
        long startedTime = System.currentTimeMillis();
        queens.start();
        queens.join();
        System.out.println("Solutions: "+Karalienes.getVariantuSkaiciu());
        //queens.print();
        System.out.println("Working time: "+(float)(System.currentTimeMillis()-startedTime)/1000
                + " s.");
    }
}

Karalienes.java file:

import java.util.Stack;


public class Karalienes extends Thread {
    private int n;
    private int places[];
    private int column;
    private static Integer solutions = new Integer(0);
    private static Integer startedThreads = 0;
    private static int maxThreads;
    private Stack<Karalienes> stack;

    public Karalienes(int n,int column, int places[]) {
        this.n = n;
        this.column = column;
        this.places = places;
        stack = new Stack<Karalienes>();
    }

    public static void setMaxGSK(int sk) {
        this.maxThreads = sk;
    }

    private boolean arOk(int row, int column) {
        boolean ok = true;
        int tmpColumn = column-1;
        for(; tmpColumn>=1; tmpColumn--) {
            if ((places[tmpColumn]-row)==0) {
                ok = false;
                break;
            }

            int rowDiff = places[column] - places[tmpColumn];

            if (rowDiff < 0)
                rowDiff = 0 - rowDiff;

            if (rowDiff == column-tmpColumn) {
                ok = false;
                break;
            }       
        }
        return ok;
    }
    public void deliojam() {
        for(int i=1; i<=n ; i++ ) { //dirbam su row
            places[column] = i;
            if (arOk(i, column)) {
                if (column<n) {
                    int gSk;
                    synchronized (startedThreads) {
                        gSk = startedThreads;
                    }
                    if (gSk < maxThreads) {
                        Karalienes kar = new Karalienes(n, column+1, places.clone());
                        kar.start();
                        stack.add(kar);
                    }
                    else {
                        column++;
                        deliojam();
                        column--;
                    }
                }
                if (column==n) {
                    Karalienes.incVariantuSkaiciu();
                }
            }   
        }

        while (stack.size()!=0) {
            try {
                stack.pop().join();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }

    }

    @Override
    public void run() {
        // TODO Auto-generated method stub
        Karalienes.incGijuSk();
        deliojam();
        Karalienes.decGijuSk();
    }

    private static synchronized void incVariantuSkaiciu() {
        solutions++;
    }

    private static synchronized void incGijuSk() {
        startedThreads++;
    }

    private static synchronized void decGijuSk() {
        startedThreads--;
    }
    public static int getVariantuSkaiciu() {
        return solutions;
    }
}

List of times:

Computer (code with threads)            
Proc    Threads N   Working time (in seconds)
2   2   9   0,022
2   2   10  0,052
2   2   11  0,106
2   2   12  0,299
2   2   13  1,342
2   2   14  7,303
2   2   15  47,486
2   2   16  345,369
2   2   17  2702,898
4   4   9   0,043
4   4   10  0,067
4   4   11  0,135
4   4   12  0,438
4   4   13  1,609
4   4   14  7,146
4   4   15  42,196
4   4   16  293,293
4   4   17  2038,762
6   6   9   0,053
6   6   10  0,09
6   6   11  0,194
6   6   12  0,483
6   6   13  1,99
6   6   14  10,347
6   6   15  62,086
6   6   16  420,496
6   6   17  2915,52
share|improve this question
2  
Please see FAQ: If you want a code review, you must post the relevant snippets of code in your question. People here don't want to download files that may contain who knows what. –  Joonas Pulakka Apr 5 '12 at 12:53

1 Answer 1

up vote 2 down vote accepted

You're probably encountering locking between threads, where the synchronized between threads is costing you more than you gain. Here's what I'd do:

  • Instead of using synchronized to protect your counters I'd use AtomicInteger to reduce the amount of locking between threads.
  • Instead of creating and lots of short-lived threads yourself, I'd use a a thread pool (e.g. ThreadPoolExecutor. You can use setMaximumPoolSize to restrict the number of threads being used. The executor service will provide a queue of jobs.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.