--- jsr166/src/test/loops/TorusSpanningTree.java	2009/11/02 14:08:38	1.1
+++ jsr166/src/test/loops/TorusSpanningTree.java	2015/09/12 20:24:33	1.9
@@ -1,7 +1,7 @@
 /*
  * 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/licenses/publicdomain
+ * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
 //import jsr166y.*;
@@ -14,7 +14,7 @@ import java.util.concurrent.atomic.*;
  * paper: Guojing Cong, Sreedhar Kodali, Sriram Krishnamoorty, Doug
  * Lea, Vijay Saraswat and Tong Wen, "Solving irregular graph problems
  * using adaptive work-stealing", ICPP, 2008.
- * 
+ *
  * It runs the main batching algorithm discussed there for spanning
  * trees, for a simple regular torus graph, where each node is
  * connected to its left. right, up, and down neighbors.
@@ -22,7 +22,7 @@ import java.util.concurrent.atomic.*;
 public class TorusSpanningTree {
     static final int NCPUS = Runtime.getRuntime().availableProcessors();
 
-    // Dimensions for test runs. 
+    // Dimensions for test runs.
     // graphs have side*side nodes, each with 4 neighbors
     static final int MIN_SIDE = 1000;
     static final int MAX_SIDE = 3000;
@@ -42,10 +42,11 @@ public class TorusSpanningTree {
         System.out.println("Number of threads: " + procs);
         System.out.println("Printing nanosec per edge across replications");
         System.out.print("for Toruses with side lengths");
-        System.out.printf(" from %5d to %5d step %5d\n", 
+        System.out.printf(" from %5d to %5d step %5d\n",
                           MIN_SIDE, MAX_SIDE, SIDE_STEP);
         ForkJoinPool pool = new ForkJoinPool(procs);
 
+        boolean checked = false;
         for (int side = MIN_SIDE; side <= MAX_SIDE; side += SIDE_STEP) {
             int n = side * side;
             Node[] graph = makeGraph(side);
@@ -55,36 +56,31 @@ public class TorusSpanningTree {
                 long start = System.nanoTime();
                 pool.invoke(new Driver(root));
                 long elapsed = System.nanoTime() - start;
-                double nanosPerEdge = (double)elapsed / (4 * n);
-            	System.out.printf(" %7.2f", nanosPerEdge);
-                if (j == 0)
+                double nanosPerEdge = (double) elapsed / (4 * n);
+                System.out.printf(" %7.2f", nanosPerEdge);
+                if (!checked) {
+                    checked = true;
                     checkSpanningTree(graph, root);
-                resetAll(graph);
+                }
+                pool.invoke(new Resetter(graph, 0, graph.length));
             }
+            graph = null;
             System.out.println();
-        }   
-        pool.shutdown(); 
+        }
+        System.out.println(pool);
+        pool.shutdown();
     }
 
     static final class Node extends ForkJoinTask<Void> {
-        final Node[] neighbors; 
+        final Node[] neighbors;
         Node parent;
         Node next;
-        volatile int mark;
-        
+
         Node(Node[] nbrs) {
             neighbors = nbrs;
             parent = this;
         }
 
-        static final AtomicIntegerFieldUpdater<Node> markUpdater =
-            AtomicIntegerFieldUpdater.newUpdater(Node.class, "mark");
-
-        boolean tryMark() {
-            return mark == 0 && markUpdater.compareAndSet(this, 0, 1);
-        }
-        void setMark() { mark = 1; }
-
         /*
          * Traverse the list ("oldList") embedded across .next fields,
          * starting at this node, placing newly discovered neighboring
@@ -113,13 +109,14 @@ public class TorusSpanningTree {
                 int nedges = edges.length;
                 for (int k = 0; k < nedges; ++k) {
                     Node e = edges[k];
-                    if (e != null && e.tryMark()) {
+                    if (e != null && 
+                        e.compareAndSetForkJoinTaskTag((short)0, (short)1)) {
                         e.parent = par;
                         e.next = newList;
                         newList = e;
                         if (batchSize == 0) {
                             int s = getQueuedTaskCount();
-                            batchSize = ((s >= LOG_MAX_BATCH_SIZE)? 
+                            batchSize = ((s >= LOG_MAX_BATCH_SIZE) ?
                                          (1 << LOG_MAX_BATCH_SIZE) :
                                          (1 << s));
                         }
@@ -151,18 +148,17 @@ public class TorusSpanningTree {
             reinitialize();
             parent = this;
             next = null;
-            mark = 0;
         }
 
     }
 
     static final class Driver extends RecursiveAction {
         final Node root;
-        Driver(Node root) { 
+        Driver(Node root) {
             this.root = root;
         }
         public void compute() {
-            root.setMark();
+            root.setForkJoinTaskTag((short)1);
             root.fork();
             helpQuiesce();
         }
@@ -177,13 +173,13 @@ public class TorusSpanningTree {
         // connect each node to left, right, up, down neighbors
         int maxcol = n - sideLength;
         int col = 0;
-        for(int i = 0; i < sideLength; ++i) {
-            for(int j = 0; j < sideLength; ++j) {
+        for (int i = 0; i < sideLength; ++i) {
+            for (int j = 0; j < sideLength; ++j) {
                 Node[] a = vs[col + j].neighbors;
-                a[0] = vs[col + ((j < sideLength-1)? (j+1) : 0)];
-                a[1] = vs[col + ((j != 0)? (j-1) : (sideLength-1))];
-                a[2] = vs[j + ((i < sideLength-1)? (col + sideLength) : 0)];
-                a[3] = vs[j + ((i != 0)? (col - sideLength) : maxcol)];
+                a[0] = vs[col + ((j < sideLength-1) ? (j+1) : 0)];
+                a[1] = vs[col + ((j != 0) ? (j-1) : (sideLength-1))];
+                a[2] = vs[j + ((i < sideLength-1) ? (col + sideLength) : 0)];
+                a[3] = vs[j + ((i != 0) ? (col - sideLength) : maxcol)];
             }
             col += sideLength;
         }
@@ -212,6 +208,21 @@ public class TorusSpanningTree {
             v.parent = root;
         }
     }
-    
-}
 
+    static final class Resetter extends RecursiveAction {
+        final Node[] g;
+        final int lo, hi;
+        Resetter(Node[] g, int lo, int hi) {
+            this.g = g; this.lo = lo; this.hi = hi;
+        }
+        public void compute() {
+            int mid = (lo + hi) >>> 1;
+            if (mid == lo || getSurplusQueuedTaskCount() > 3) {
+                for (int i = lo; i < hi; ++i)
+                    g[i].reset();
+            }
+            else
+                invokeAll(new Resetter(g, lo, mid), new Resetter(g, mid, hi));
+        }
+    }
+}