test/loops/NQueensCS.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 jsr166y.*;
import java.util.*;
import java.util.concurrent.*;

public final class NQueensCS extends RecursiveAction {

    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 = 16; // 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 NQueensCS <threads> ");
            return;
        }
        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool g = (procs == 0) ? ForkJoinPool.commonPool() :
                new ForkJoinPool(procs);
            lastStealCount = g.getStealCount();
            for (int i = FIRST_SIZE; i <= LAST_SIZE; i++)
                test(g, i);
            System.out.println(g);
            if (g != ForkJoinPool.commonPool())
                g.shutdown();
            Thread.sleep(100);
        }
    }

    static void test(ForkJoinPool g, int i) throws Exception {
        boardSize = i;
        int ps = g.getParallelism();
        long start = System.nanoTime();
        NQueensCS task = new NQueensCS(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("NQueensCS %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;
    NQueensCS nextSubtask; // to link subtasks
    int solutions;
    NQueensCS(int[] a) {
        this.sofar = a;
    }

    public final void compute() {
        NQueensCS subtasks;
        int bs = boardSize;
        if (sofar.length >= bs)
            solutions = 1;
        else if ((subtasks = explore(sofar, bs)) != null)
            solutions = processSubtasks(subtasks);
    }

    private static NQueensCS explore(int[] array, int bs) {
        int row = array.length;
        NQueensCS s = null; // subtask list
        outer:
        for (int q = 0; q < bs; ++q) {
            for (int i = 0; i < row; i++) {
                int p = array[i];
                if (q == p || q == p - (row - i) || q == p + (row - i))
                    continue outer; // attacked
            }
            NQueensCS first = s; // lag forks to ensure 1 kept
            if (first != null)
                first.fork();
            int[] next = Arrays.copyOf(array, row+1);
            next[row] = q;
            NQueensCS subtask = new NQueensCS(next);
            subtask.nextSubtask = first;
            s = subtask;
        }
        return s;
    }

    private static int processSubtasks(NQueensCS s) {
        // Always run first the task held instead of forked
        s.compute();
        int ns = s.solutions;
        s = s.nextSubtask;
        /* comment out to stress join
        // Then the unstolen ones
        while (s != null && s.tryUnfork()) {
            s.compute();
            ns += s.solutions;
            s = s.nextSubtask;
        }
        */
        // Then wait for the stolen ones
        while (s != null) {
            s.join();
            ns += s.solutions;
            s = s.nextSubtask;
        }
        return ns;
    }
}
Revision:	1.9
Committed:	Sat Sep 12 19:53:04 2015 UTC (8 years, 7 months ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.8:	+7 -3 lines
Log Message:	Use commonPool
#	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.8	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7			//import jsr166y.*;
8			import java.util.*;
9			import java.util.concurrent.*;
10
11			public final class NQueensCS extends RecursiveAction {
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	dl	1.9	static final int LAST_SIZE = 16; // bigger ones too long to wait for
23	dl	1.1
24			/** for time conversion */
25			static final long NPS = (1000L * 1000 * 1000);
26	jsr166	1.6
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 NQueensCS <threads> ");
35			return;
36			}
37			for (int reps = 0; reps < 2; ++reps) {
38	dl	1.9	ForkJoinPool g = (procs == 0) ? ForkJoinPool.commonPool() :
39	dl	1.1	new ForkJoinPool(procs);
40			lastStealCount = g.getStealCount();
41			for (int i = FIRST_SIZE; i <= LAST_SIZE; i++)
42			test(g, i);
43			System.out.println(g);
44	dl	1.9	if (g != ForkJoinPool.commonPool())
45			g.shutdown();
46			Thread.sleep(100);
47	dl	1.1	}
48			}
49
50			static void test(ForkJoinPool g, int i) throws Exception {
51			boardSize = i;
52			int ps = g.getParallelism();
53			long start = System.nanoTime();
54			NQueensCS task = new NQueensCS(new int[0]);
55			g.invoke(task);
56			int solutions = task.solutions;
57			long time = System.nanoTime() - start;
58	dl	1.5	double secs = ((double)time) / NPS;
59	dl	1.1	if (solutions != expectedSolutions[i])
60			throw new Error();
61			System.out.printf("NQueensCS %3d", i);
62			System.out.printf(" Time: %7.3f", secs);
63			long sc = g.getStealCount();
64			long ns = sc - lastStealCount;
65			lastStealCount = sc;
66			System.out.printf(" Steals/t: %5d", ns/ps);
67			System.out.println();
68	jsr166	1.6	}
69	dl	1.1
70	jsr166	1.6	// Boards are represented as arrays where each cell
71	dl	1.1	// holds the column number of the queen in that row
72
73			final int[] sofar;
74			NQueensCS nextSubtask; // to link subtasks
75			int solutions;
76	jsr166	1.6	NQueensCS(int[] a) {
77			this.sofar = a;
78	dl	1.1	}
79
80			public final void compute() {
81			NQueensCS subtasks;
82			int bs = boardSize;
83			if (sofar.length >= bs)
84			solutions = 1;
85			else if ((subtasks = explore(sofar, bs)) != null)
86			solutions = processSubtasks(subtasks);
87			}
88
89			private static NQueensCS explore(int[] array, int bs) {
90			int row = array.length;
91			NQueensCS s = null; // subtask list
92			outer:
93			for (int q = 0; q < bs; ++q) {
94			for (int i = 0; i < row; i++) {
95			int p = array[i];
96			if (q == p \|\| q == p - (row - i) \|\| q == p + (row - i))
97			continue outer; // attacked
98			}
99			NQueensCS first = s; // lag forks to ensure 1 kept
100			if (first != null)
101			first.fork();
102			int[] next = Arrays.copyOf(array, row+1);
103			next[row] = q;
104			NQueensCS subtask = new NQueensCS(next);
105			subtask.nextSubtask = first;
106			s = subtask;
107			}
108			return s;
109			}
110
111			private static int processSubtasks(NQueensCS s) {
112			// Always run first the task held instead of forked
113	jsr166	1.6	s.compute();
114	dl	1.1	int ns = s.solutions;
115			s = s.nextSubtask;
116	dl	1.9	/* comment out to stress join
117	dl	1.1	// Then the unstolen ones
118			while (s != null && s.tryUnfork()) {
119			s.compute();
120			ns += s.solutions;
121			s = s.nextSubtask;
122			}
123	dl	1.9	*/
124	dl	1.1	// Then wait for the stolen ones
125			while (s != null) {
126			s.join();
127			ns += s.solutions;
128			s = s.nextSubtask;
129			}
130			return ns;
131			}
132			}