4
\$\begingroup\$

I'm trying to increase the performance of my N Queens Puzzle solution. I'd find some threads on SO already but they don't appear to help me to increase performance.

My best solution, however, is a strategy with a constant amount of working threads. I also tried to implement a solution with RecursiveTasks. But it appears that the first solution overcomes all my other tries. I think that is because the computer receives too many Tasks and looks for completion of working tasks most of the time.

However, I'd come up with two solutions:

First, the slow one with an implementation of RecursiveTask which needs 2449 ms for the calculation of N = 14:

public class DamenProblemFork extends RecursiveTask<Integer>{
    private static final long serialVersionUID = -6502127276625965624L;
    static int N = 14;

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

        if (args.length == 1) {
            N = Integer.parseInt(args[0]);
        }
        long start = System.currentTimeMillis();
        DamenProblemFork dpf_root = new DamenProblemFork(0L, 0L, 0L, N - 1);
        Integer result = dpf_root.fork().join();

        System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
        System.out.println("Result for " + N + ": " + result);

    }

    private long diagR;
    private long diagL;
    private long mid;
    private int depth;

    public DamenProblemFork(long diagR, long diagL, long mid, int depth) {
        this.diagR = diagR;
        this.diagL = diagL;
        this.mid = mid;
        this.depth = depth;
    }

    @Override
    protected Integer compute() {

        List<DamenProblemFork> ldpf = new ArrayList<>();

        long valid = mid | diagL | diagR;
        int resBuffer = 0;

        for (int i = 0; i < N; i++) {
            int pos = 1 << i;
            if ((valid & pos) > 0) {
                continue;
            }
            if (depth == 0) {
                resBuffer++;
                continue;
            }

            long n_mid = mid | pos;
            long n_diagL = (diagL | pos) >> 1;
            long n_diagR = (diagR | pos) << 1;

            DamenProblemFork dpf = new DamenProblemFork(n_diagR, n_diagL, n_mid, depth - 1);
            ldpf.add(dpf);
        }

        if(depth == 0) {
            return resBuffer;
        }

        return ldpf.stream().parallel().map(d -> d.fork()).mapToInt(x -> x.join()).sum();
    }
}

The next solution I'd come up with is with a dedicated thread pool with thread number equal to processor count. This, however, just needs 124ms for the calculation of 14:

public class DamenProblem {
    static AtomicInteger result = new AtomicInteger(0);
    static int N = 14;

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

        if (args.length == 1) {
            N = Integer.parseInt(args[0]);
        }

        int processors = Runtime.getRuntime().availableProcessors();
        int availableProcessors = processors < N ? processors : N;

        BlockingQueue<Runnable> workQueue = new ArrayBlockingQueue<>(N);
        ThreadPoolExecutor tpe = new ThreadPoolExecutor(availableProcessors, availableProcessors, 100,
                TimeUnit.MILLISECONDS, workQueue);
        Semaphore sem = new Semaphore(0);

        long start = System.currentTimeMillis();


        if(N%2 == 0) {

        for (int i = 0; i < N/2; i++) {
            int pos = 1 << i;
            tpe.execute(() -> {
                int res = run(pos << 1, pos >> 1, pos, N - 2);
                result.getAndAdd(res);
                sem.release();
            });
        }
        sem.acquire(N/2);

        System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
        System.out.println("Result for " + N + ": " + result.get()*2);

        }
        else {
            for (int i = 0; i < N; i++) {
                int pos = 1 << i;
                tpe.execute(() -> {
                    int res = run(pos << 1, pos >> 1, pos, N - 2);
                    result.getAndAdd(res);
                    sem.release();
                });
            }
            sem.acquire(N);

            System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
            System.out.println("Result for " + N + ": " + result.get());
        }
        System.exit(0);
    }

    static int run(long diagR, long diagL, long mid, int depth) {
        long valid = mid | diagL | diagR;
        int resBuffer = 0;

        for (int i = 0; i < N; i++) {
            int pos = 1 << i;
            if ((valid & pos) > 0) {
                continue;
            }
            if (depth == 0) {
                resBuffer++;
                continue;
            }
            long n_mid = mid | pos;
            long n_diagL = (diagL | pos) >> 1;
            long n_diagR = (diagR | pos) << 1;

            resBuffer += run(n_diagR, n_diagL, n_mid, depth - 1);
        }
        return resBuffer;
    }
}

My CPU is an AMD ryzen 5 2600K with 12 cores.

Do you guys have an idea how to improve this code to make it even faster? I thought something of including symmetry. But does this work? I think using symmetry just increases performance if N is greater than the number of processors times two.

What do you think?

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I hope you get some great answers. \$\endgroup\$ – Phrancis Jun 14 '18 at 19:22
  • \$\begingroup\$ Thank you! :) I'm trying to improve my programming skills and my thinking. :) \$\endgroup\$ – Noixes Jun 14 '18 at 19:23
  • 1
    \$\begingroup\$ I agree to you that symmetry could improve performance. Might try for (int i = 0; i < N / 2; i++) { in main and then double result and run again with int i = Math.ceil(N / 2) if N is uneven \$\endgroup\$ – Jonas Wilms Jun 14 '18 at 19:42
  • \$\begingroup\$ @JonasW. nice point, but the Math.ceil is not required :), i update the code in the question \$\endgroup\$ – Noixes Jun 14 '18 at 20:34
  • \$\begingroup\$ @noixes yeah im from Javascript :) and did it effect performance? Im curious... \$\endgroup\$ – Jonas Wilms Jun 14 '18 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.