test/loops/AsyncNQueensCS.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public final class AsyncNQueensCS extends LinkedAsyncAction {

    static long lastStealCount;
    static int boardSize;

    static final int[] expectedSolutions = new int[] {
        0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200,
        73712, 365596, 2279184, 14772512, 95815104, 666090624
    }; // see http://www.durangobill.com/N_Queens.html

    static final int FIRST_SIZE = 8; // smaller ones too short to measure well
    static final int LAST_SIZE = 15; // bigger ones too long to wait for

    /** for time conversion */
    static final long NPS = (1000L * 1000 * 1000);

    public static void main(String[] args) throws Exception {
        int procs = 0;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
        }
        catch (Exception e) {
            System.out.println("Usage: java AsyncNQueensCS <threads> ");
            return;
        }
        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
                new ForkJoinPool(procs);
            System.out.println("Number of procs=" + g.getParallelism());
            lastStealCount = g.getStealCount();
            for (int i = FIRST_SIZE; i <= LAST_SIZE; i++)
                test(g, i);
            g.shutdown();
        }
    }

    static void test(ForkJoinPool g, int i) throws Exception {
        boardSize = i;
        int ps = g.getParallelism();
        long start = System.nanoTime();
        AsyncNQueensCS task = new AsyncNQueensCS(null, new int[0]);
        g.invoke(task);
        int solutions = task.solutions;
        long time = System.nanoTime() - start;
        double secs = ((double)time) / NPS;
        if (solutions != expectedSolutions[i])
            throw new Error();
        System.out.printf("AsyncNQueensCS %3d", i);
        System.out.printf(" Time: %7.3f", secs);
        long sc = g.getStealCount();
        long ns = sc - lastStealCount;
        lastStealCount = sc;
        System.out.printf(" Steals/t: %5d", ns/ps);
        System.out.println();
    }

    // Boards are represented as arrays where each cell
    // holds the column number of the queen in that row

    final int[] sofar;
    volatile int solutions;
    AsyncNQueensCS(AsyncNQueensCS parent, int[] a) {
        super(parent);
        this.sofar = a;
    }

    public final boolean exec() {
        int bs = boardSize;
        int row = sofar.length;
        if (row >= bs)
            solutions = 1;
        else {
            outer:
            for (int q = 0; q < bs; ++q) {
                for (int i = 0; i < row; i++) {
                    int p = sofar[i];
                    if (q == p || q == p - (row - i) || q == p + (row - i))
                        continue outer; // attacked
                }
                int[] next = Arrays.copyOf(sofar, row+1);
                next[row] = q;
                new AsyncNQueensCS(this, next).fork();
            }
        }
        complete();
        return false;
    }

    protected void onCompletion() {
        LinkedAsyncAction p;
        int n = solutions;
        if (n != 0 && (p = getParent()) != null)
            solutionUpdater.addAndGet((AsyncNQueensCS)p, n);
    }

    static final AtomicIntegerFieldUpdater<AsyncNQueensCS> solutionUpdater =
        AtomicIntegerFieldUpdater.newUpdater(AsyncNQueensCS.class, "solutions");
}
Revision:	1.6
Committed:	Thu Jan 15 18:34:18 2015 UTC (9 years, 3 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.5:	+0 -2 lines
Log Message:	delete extraneous blank lines
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4	jsr166	1.4	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7	jsr166	1.5	import java.util.*;
8	dl	1.1	import java.util.concurrent.*;
9			import java.util.concurrent.atomic.*;
10
11			public final class AsyncNQueensCS extends LinkedAsyncAction {
12
13			static long lastStealCount;
14			static int boardSize;
15
16			static final int[] expectedSolutions = new int[] {
17			0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200,
18			73712, 365596, 2279184, 14772512, 95815104, 666090624
19			}; // see http://www.durangobill.com/N_Queens.html
20
21			static final int FIRST_SIZE = 8; // smaller ones too short to measure well
22			static final int LAST_SIZE = 15; // bigger ones too long to wait for
23
24			/** for time conversion */
25			static final long NPS = (1000L * 1000 * 1000);
26	jsr166	1.2
27	dl	1.1	public static void main(String[] args) throws Exception {
28			int procs = 0;
29			try {
30			if (args.length > 0)
31			procs = Integer.parseInt(args[0]);
32			}
33			catch (Exception e) {
34			System.out.println("Usage: java AsyncNQueensCS <threads> ");
35			return;
36			}
37			for (int reps = 0; reps < 2; ++reps) {
38	jsr166	1.3	ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
39	dl	1.1	new ForkJoinPool(procs);
40			System.out.println("Number of procs=" + g.getParallelism());
41			lastStealCount = g.getStealCount();
42			for (int i = FIRST_SIZE; i <= LAST_SIZE; i++)
43			test(g, i);
44	jsr166	1.2	g.shutdown();
45	dl	1.1	}
46			}
47
48			static void test(ForkJoinPool g, int i) throws Exception {
49			boardSize = i;
50			int ps = g.getParallelism();
51			long start = System.nanoTime();
52			AsyncNQueensCS task = new AsyncNQueensCS(null, new int[0]);
53			g.invoke(task);
54			int solutions = task.solutions;
55			long time = System.nanoTime() - start;
56			double secs = ((double)time) / NPS;
57			if (solutions != expectedSolutions[i])
58			throw new Error();
59			System.out.printf("AsyncNQueensCS %3d", i);
60			System.out.printf(" Time: %7.3f", secs);
61			long sc = g.getStealCount();
62			long ns = sc - lastStealCount;
63			lastStealCount = sc;
64			System.out.printf(" Steals/t: %5d", ns/ps);
65			System.out.println();
66	jsr166	1.2	}
67	dl	1.1
68	jsr166	1.2	// Boards are represented as arrays where each cell
69	dl	1.1	// holds the column number of the queen in that row
70
71			final int[] sofar;
72			volatile int solutions;
73	jsr166	1.2	AsyncNQueensCS(AsyncNQueensCS parent, int[] a) {
74	dl	1.1	super(parent);
75	jsr166	1.2	this.sofar = a;
76	dl	1.1	}
77
78			public final boolean exec() {
79			int bs = boardSize;
80			int row = sofar.length;
81			if (row >= bs)
82			solutions = 1;
83			else {
84			outer:
85			for (int q = 0; q < bs; ++q) {
86			for (int i = 0; i < row; i++) {
87			int p = sofar[i];
88			if (q == p \|\| q == p - (row - i) \|\| q == p + (row - i))
89			continue outer; // attacked
90			}
91			int[] next = Arrays.copyOf(sofar, row+1);
92			next[row] = q;
93			new AsyncNQueensCS(this, next).fork();
94			}
95			}
96			complete();
97			return false;
98			}
99
100			protected void onCompletion() {
101			LinkedAsyncAction p;
102			int n = solutions;
103			if (n != 0 && (p = getParent()) != null)
104			solutionUpdater.addAndGet((AsyncNQueensCS)p, n);
105			}
106
107			static final AtomicIntegerFieldUpdater<AsyncNQueensCS> solutionUpdater =
108			AtomicIntegerFieldUpdater.newUpdater(AsyncNQueensCS.class, "solutions");
109			}