RecursiveAction.java revision 51b1b6997fd3f980076b8081f7f1165ccc2a4008
1/* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25/* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Doug Lea with assistance from members of JCP JSR-166 32 * Expert Group and released to the public domain, as explained at 33 * http://creativecommons.org/publicdomain/zero/1.0/ 34 */ 35 36package java.util.concurrent; 37 38/** 39 * A recursive resultless {@link ForkJoinTask}. This class 40 * establishes conventions to parameterize resultless actions as 41 * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the 42 * only valid value of type {@code Void}, methods such as join always 43 * return {@code null} upon completion. 44 * 45 * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that 46 * sorts a given {@code long[]} array: 47 * 48 * <pre> {@code 49 * class SortTask extends RecursiveAction { 50 * final long[] array; final int lo; final int hi; 51 * SortTask(long[] array, int lo, int hi) { 52 * this.array = array; this.lo = lo; this.hi = hi; 53 * } 54 * protected void compute() { 55 * if (hi - lo < THRESHOLD) 56 * sequentiallySort(array, lo, hi); 57 * else { 58 * int mid = (lo + hi) >>> 1; 59 * invokeAll(new SortTask(array, lo, mid), 60 * new SortTask(array, mid, hi)); 61 * merge(array, lo, hi); 62 * } 63 * } 64 * }}</pre> 65 * 66 * You could then sort {@code anArray} by creating {@code new 67 * SortTask(anArray, 0, anArray.length-1) } and invoking it in a 68 * ForkJoinPool. As a more concrete simple example, the following 69 * task increments each element of an array: 70 * <pre> {@code 71 * class IncrementTask extends RecursiveAction { 72 * final long[] array; final int lo; final int hi; 73 * IncrementTask(long[] array, int lo, int hi) { 74 * this.array = array; this.lo = lo; this.hi = hi; 75 * } 76 * protected void compute() { 77 * if (hi - lo < THRESHOLD) { 78 * for (int i = lo; i < hi; ++i) 79 * array[i]++; 80 * } 81 * else { 82 * int mid = (lo + hi) >>> 1; 83 * invokeAll(new IncrementTask(array, lo, mid), 84 * new IncrementTask(array, mid, hi)); 85 * } 86 * } 87 * }}</pre> 88 * 89 * <p>The following example illustrates some refinements and idioms 90 * that may lead to better performance: RecursiveActions need not be 91 * fully recursive, so long as they maintain the basic 92 * divide-and-conquer approach. Here is a class that sums the squares 93 * of each element of a double array, by subdividing out only the 94 * right-hand-sides of repeated divisions by two, and keeping track of 95 * them with a chain of {@code next} references. It uses a dynamic 96 * threshold based on method {@code getSurplusQueuedTaskCount}, but 97 * counterbalances potential excess partitioning by directly 98 * performing leaf actions on unstolen tasks rather than further 99 * subdividing. 100 * 101 * <pre> {@code 102 * double sumOfSquares(ForkJoinPool pool, double[] array) { 103 * int n = array.length; 104 * Applyer a = new Applyer(array, 0, n, null); 105 * pool.invoke(a); 106 * return a.result; 107 * } 108 * 109 * class Applyer extends RecursiveAction { 110 * final double[] array; 111 * final int lo, hi; 112 * double result; 113 * Applyer next; // keeps track of right-hand-side tasks 114 * Applyer(double[] array, int lo, int hi, Applyer next) { 115 * this.array = array; this.lo = lo; this.hi = hi; 116 * this.next = next; 117 * } 118 * 119 * double atLeaf(int l, int h) { 120 * double sum = 0; 121 * for (int i = l; i < h; ++i) // perform leftmost base step 122 * sum += array[i] * array[i]; 123 * return sum; 124 * } 125 * 126 * protected void compute() { 127 * int l = lo; 128 * int h = hi; 129 * Applyer right = null; 130 * while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) { 131 * int mid = (l + h) >>> 1; 132 * right = new Applyer(array, mid, h, right); 133 * right.fork(); 134 * h = mid; 135 * } 136 * double sum = atLeaf(l, h); 137 * while (right != null) { 138 * if (right.tryUnfork()) // directly calculate if not stolen 139 * sum += right.atLeaf(right.lo, right.hi); 140 * else { 141 * right.join(); 142 * sum += right.result; 143 * } 144 * right = right.next; 145 * } 146 * result = sum; 147 * } 148 * }}</pre> 149 * 150 * @since 1.7 151 * @author Doug Lea 152 */ 153public abstract class RecursiveAction extends ForkJoinTask<Void> { 154 private static final long serialVersionUID = 5232453952276485070L; 155 156 /** 157 * The main computation performed by this task. 158 */ 159 protected abstract void compute(); 160 161 /** 162 * Always returns {@code null}. 163 * 164 * @return {@code null} always 165 */ 166 public final Void getRawResult() { return null; } 167 168 /** 169 * Requires null completion value. 170 */ 171 protected final void setRawResult(Void mustBeNull) { } 172 173 /** 174 * Implements execution conventions for RecursiveActions. 175 */ 176 protected final boolean exec() { 177 compute(); 178 return true; 179 } 180 181} 182