1b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak/* 2242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * 4242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * This code is free software; you can redistribute it and/or modify it 5242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 6242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * published by the Free Software Foundation. Oracle designates this 7242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * particular file as subject to the "Classpath" exception as provided 8242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 9242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * 10242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 11242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 14242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * accompanied this code). 15242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * 16242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * You should have received a copy of the GNU General Public License version 17242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 18242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * 20242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * or visit www.oracle.com if you need additional information or have any 22242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * questions. 23242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer */ 24242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer 25242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer/* 26242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * This file is available under and governed by the GNU General Public 27242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 28242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * However, the following notice accompanied the original version of this 29242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * file: 30242e5bfd7e912be174c03a3c887369a6a9d6cbc2Tobias Thierer * 31b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Written by Doug Lea with assistance from members of JCP JSR-166 32b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Expert Group and released to the public domain, as explained at 33b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * http://creativecommons.org/publicdomain/zero/1.0/ 34b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 35b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 36b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakpackage java.util; 37b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 38b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.concurrent.CountedCompleter; 39b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.concurrent.ForkJoinPool; 40b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.BinaryOperator; 41b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.DoubleBinaryOperator; 42b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.IntBinaryOperator; 43b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.LongBinaryOperator; 44b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 45b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak/** 46b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * ForkJoin tasks to perform Arrays.parallelPrefix operations. 47b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 48b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @author Doug Lea 49b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @since 1.8 50b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 51b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakclass ArrayPrefixHelpers { 52b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private ArrayPrefixHelpers() {} // non-instantiable 53b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 54b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /* 55b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Parallel prefix (aka cumulate, scan) task classes 56b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * are based loosely on Guy Blelloch's original 57b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * algorithm (http://www.cs.cmu.edu/~scandal/alg/scan.html): 58b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Keep dividing by two to threshold segment size, and then: 59b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Pass 1: Create tree of partial sums for each segment 60b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Pass 2: For each segment, cumulate with offset of left sibling 61b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 62b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * This version improves performance within FJ framework mainly by 63b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * allowing the second pass of ready left-hand sides to proceed 64b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * even if some right-hand side first passes are still executing. 65b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * It also combines first and second pass for leftmost segment, 66b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * and skips the first pass for rightmost segment (whose result is 67b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * not needed for second pass). It similarly manages to avoid 68b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * requiring that users supply an identity basis for accumulations 69b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * by tracking those segments/subtasks for which the first 70b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * existing element is used as base. 71b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 72b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Managing this relies on ORing some bits in the pendingCount for 73b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * phases/states: CUMULATE, SUMMED, and FINISHED. CUMULATE is the 74b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * main phase bit. When false, segments compute only their sum. 75b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * When true, they cumulate array elements. CUMULATE is set at 76b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * root at beginning of second pass and then propagated down. But 77b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * it may also be set earlier for subtrees with lo==0 (the left 78b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * spine of tree). SUMMED is a one bit join count. For leafs, it 79b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * is set when summed. For internal nodes, it becomes true when 80b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * one child is summed. When the second child finishes summing, 81b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * we then moves up tree to trigger the cumulate phase. FINISHED 82b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * is also a one bit join count. For leafs, it is set when 83b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * cumulated. For internal nodes, it becomes true when one child 84b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * is cumulated. When the second child finishes cumulating, it 85b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * then moves up tree, completing at the root. 86b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 87b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * To better exploit locality and reduce overhead, the compute 88b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * method loops starting with the current task, moving if possible 89b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * to one of its subtasks rather than forking. 90b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 91b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * As usual for this sort of utility, there are 4 versions, that 92b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * are simple copy/paste/adapt variants of each other. (The 93b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * double and int versions differ from long version solely by 94b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * replacing "long" (with case-matching)). 95b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 96b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 97b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // see above 98b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int CUMULATE = 1; 99b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int SUMMED = 2; 100b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int FINISHED = 4; 101b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 102b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** The smallest subtask array partition size to use as threshold */ 103b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int MIN_PARTITION = 16; 104b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 105b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final class CumulateTask<T> extends CountedCompleter<Void> { 106b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final T[] array; 107b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final BinaryOperator<T> function; 108b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak CumulateTask<T> left, right; 109b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T in, out; 110b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final int lo, hi, origin, fence, threshold; 111b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 112b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Root task constructor */ 113b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public CumulateTask(CumulateTask<T> parent, 114b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak BinaryOperator<T> function, 115b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T[] array, int lo, int hi) { 116b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 117b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 118b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = this.origin = lo; this.hi = this.fence = hi; 119b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int p; 120b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = 121b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 122b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak <= MIN_PARTITION ? MIN_PARTITION : p; 123b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 124b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 125b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Subtask constructor */ 126b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak CumulateTask(CumulateTask<T> parent, BinaryOperator<T> function, 127b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T[] array, int origin, int fence, int threshold, 128b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int lo, int hi) { 129b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 130b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 131b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.origin = origin; this.fence = fence; 132b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = threshold; 133b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = lo; this.hi = hi; 134b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 135b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 136b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public final void compute() { 137b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final BinaryOperator<T> fn; 138b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final T[] a; 139b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((fn = this.function) == null || (a = this.array) == null) 140b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new NullPointerException(); // hoist checks 141b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int th = threshold, org = origin, fnc = fence, l, h; 142b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak CumulateTask<T> t = this; 143b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 144b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (h - l > th) { 145b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak CumulateTask<T> lt = t.left, rt = t.right, f; 146b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt == null) { // first pass 147b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int mid = (l + h) >>> 1; 148b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = rt = t.right = 149b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new CumulateTask<T>(t, fn, a, org, fnc, th, mid, h); 150b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt = t.left = 151b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new CumulateTask<T>(t, fn, a, org, fnc, th, l, mid); 152b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 153b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { // possibly refork 154b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T pin = t.in; 155b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak lt.in = pin; 156b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t = null; 157b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt != null) { 158b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T lout = lt.out; 159b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rt.in = (l == org ? lout : 160b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.apply(pin, lout)); 161b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 162b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = rt.getPendingCount()) & CUMULATE) != 0) 163b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 164b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 165b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = rt; 166b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 167b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 168b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 169b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 170b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 171b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = lt.getPendingCount()) & CUMULATE) != 0) 172b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 173b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 174b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t != null) 175b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t; 176b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt; 177b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 178b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 179b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 180b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t == null) 181b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 182b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 183b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (f != null) 184b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f.fork(); 185b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 186b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 187b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int state; // Transition to sum, cumulate, or both 188b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int b;;) { 189b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((b = t.getPendingCount()) & FINISHED) != 0) 190b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // already done 191b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = ((b & CUMULATE) != 0 ? FINISHED : 192b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (l > org) ? SUMMED : (SUMMED|FINISHED)); 193b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t.compareAndSetPendingCount(b, b|state)) 194b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 195b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 196b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 197b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T sum; 198b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (state != SUMMED) { 199b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int first; 200b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (l == org) { // leftmost; no in 201b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[org]; 202b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = org + 1; 203b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 204b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 205b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 206b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = l; 207b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 208b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = first; i < h; ++i) // cumulate 209b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a[i] = sum = fn.apply(sum, a[i]); 210b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 211b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (h < fnc) { // skip rightmost 212b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[l]; 213b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = l + 1; i < h; ++i) // sum only 214b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = fn.apply(sum, a[i]); 215b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 216b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else 217b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 218b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.out = sum; 219b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (CumulateTask<T> par;;) { // propagate 220b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") CumulateTask<T> partmp 221b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak = (CumulateTask<T>)t.getCompleter(); 222b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((par = partmp) == null) { 223b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((state & FINISHED) != 0) // enable join 224b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.quietlyComplete(); 225b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; 226b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 227b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int b = par.getPendingCount(); 228b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((b & state & FINISHED) != 0) 229b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; // both done 230b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if ((b & state & SUMMED) != 0) { // both summed 231b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int nextState; CumulateTask<T> lt, rt; 232b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((lt = par.left) != null && 233b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (rt = par.right) != null) { 234b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak T lout = lt.out; 235b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.out = (rt.hi == fnc ? lout : 236b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.apply(lout, rt.out)); 237b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 238b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int refork = (((b & CUMULATE) == 0 && 239b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.lo == org) ? CUMULATE : 0); 240b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((nextState = b|state|refork) == b || 241b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.compareAndSetPendingCount(b, nextState)) { 242b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = SUMMED; // drop finished 243b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; 244b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (refork != 0) 245b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.fork(); 246b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 247b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 248b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (par.compareAndSetPendingCount(b, b|state)) 249b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // sib not ready 250b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 251b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 252b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 253b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 254b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long serialVersionUID = 5293554502939613543L; 255b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 256b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 257b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final class LongCumulateTask extends CountedCompleter<Void> { 258b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final long[] array; 259b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final LongBinaryOperator function; 260b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LongCumulateTask left, right; 261b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long in, out; 262b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final int lo, hi, origin, fence, threshold; 263b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 264b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Root task constructor */ 265b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public LongCumulateTask(LongCumulateTask parent, 266b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LongBinaryOperator function, 267b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long[] array, int lo, int hi) { 268b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 269b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 270b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = this.origin = lo; this.hi = this.fence = hi; 271b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int p; 272b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = 273b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 274b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak <= MIN_PARTITION ? MIN_PARTITION : p; 275b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 276b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 277b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Subtask constructor */ 278b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LongCumulateTask(LongCumulateTask parent, LongBinaryOperator function, 279b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long[] array, int origin, int fence, int threshold, 280b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int lo, int hi) { 281b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 282b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 283b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.origin = origin; this.fence = fence; 284b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = threshold; 285b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = lo; this.hi = hi; 286b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 287b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 288b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public final void compute() { 289b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final LongBinaryOperator fn; 290b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final long[] a; 291b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((fn = this.function) == null || (a = this.array) == null) 292b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new NullPointerException(); // hoist checks 293b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int th = threshold, org = origin, fnc = fence, l, h; 294b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LongCumulateTask t = this; 295b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 296b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (h - l > th) { 297b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LongCumulateTask lt = t.left, rt = t.right, f; 298b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt == null) { // first pass 299b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int mid = (l + h) >>> 1; 300b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = rt = t.right = 301b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new LongCumulateTask(t, fn, a, org, fnc, th, mid, h); 302b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt = t.left = 303b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new LongCumulateTask(t, fn, a, org, fnc, th, l, mid); 304b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 305b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { // possibly refork 306b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long pin = t.in; 307b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak lt.in = pin; 308b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t = null; 309b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt != null) { 310b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long lout = lt.out; 311b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rt.in = (l == org ? lout : 312b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.applyAsLong(pin, lout)); 313b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 314b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = rt.getPendingCount()) & CUMULATE) != 0) 315b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 316b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 317b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = rt; 318b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 319b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 320b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 321b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 322b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 323b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = lt.getPendingCount()) & CUMULATE) != 0) 324b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 325b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 326b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t != null) 327b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t; 328b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt; 329b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 330b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 331b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 332b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t == null) 333b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 334b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 335b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (f != null) 336b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f.fork(); 337b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 338b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 339b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int state; // Transition to sum, cumulate, or both 340b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int b;;) { 341b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((b = t.getPendingCount()) & FINISHED) != 0) 342b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // already done 343b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = ((b & CUMULATE) != 0 ? FINISHED : 344b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (l > org) ? SUMMED : (SUMMED|FINISHED)); 345b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t.compareAndSetPendingCount(b, b|state)) 346b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 347b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 348b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 349b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long sum; 350b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (state != SUMMED) { 351b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int first; 352b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (l == org) { // leftmost; no in 353b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[org]; 354b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = org + 1; 355b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 356b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 357b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 358b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = l; 359b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 360b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = first; i < h; ++i) // cumulate 361b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a[i] = sum = fn.applyAsLong(sum, a[i]); 362b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 363b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (h < fnc) { // skip rightmost 364b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[l]; 365b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = l + 1; i < h; ++i) // sum only 366b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = fn.applyAsLong(sum, a[i]); 367b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 368b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else 369b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 370b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.out = sum; 371b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (LongCumulateTask par;;) { // propagate 372b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((par = (LongCumulateTask)t.getCompleter()) == null) { 373b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((state & FINISHED) != 0) // enable join 374b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.quietlyComplete(); 375b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; 376b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 377b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int b = par.getPendingCount(); 378b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((b & state & FINISHED) != 0) 379b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; // both done 380b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if ((b & state & SUMMED) != 0) { // both summed 381b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int nextState; LongCumulateTask lt, rt; 382b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((lt = par.left) != null && 383b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (rt = par.right) != null) { 384b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak long lout = lt.out; 385b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.out = (rt.hi == fnc ? lout : 386b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.applyAsLong(lout, rt.out)); 387b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 388b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int refork = (((b & CUMULATE) == 0 && 389b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.lo == org) ? CUMULATE : 0); 390b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((nextState = b|state|refork) == b || 391b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.compareAndSetPendingCount(b, nextState)) { 392b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = SUMMED; // drop finished 393b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; 394b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (refork != 0) 395b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.fork(); 396b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 397b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 398b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (par.compareAndSetPendingCount(b, b|state)) 399b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // sib not ready 400b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 401b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 402b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 403b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 404b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long serialVersionUID = -5074099945909284273L; 405b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 406b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 407b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final class DoubleCumulateTask extends CountedCompleter<Void> { 408b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final double[] array; 409b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final DoubleBinaryOperator function; 410b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak DoubleCumulateTask left, right; 411b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double in, out; 412b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final int lo, hi, origin, fence, threshold; 413b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 414b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Root task constructor */ 415b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public DoubleCumulateTask(DoubleCumulateTask parent, 416b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak DoubleBinaryOperator function, 417b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double[] array, int lo, int hi) { 418b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 419b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 420b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = this.origin = lo; this.hi = this.fence = hi; 421b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int p; 422b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = 423b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 424b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak <= MIN_PARTITION ? MIN_PARTITION : p; 425b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 426b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 427b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Subtask constructor */ 428b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak DoubleCumulateTask(DoubleCumulateTask parent, DoubleBinaryOperator function, 429b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double[] array, int origin, int fence, int threshold, 430b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int lo, int hi) { 431b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 432b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 433b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.origin = origin; this.fence = fence; 434b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = threshold; 435b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = lo; this.hi = hi; 436b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 437b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 438b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public final void compute() { 439b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final DoubleBinaryOperator fn; 440b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final double[] a; 441b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((fn = this.function) == null || (a = this.array) == null) 442b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new NullPointerException(); // hoist checks 443b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int th = threshold, org = origin, fnc = fence, l, h; 444b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak DoubleCumulateTask t = this; 445b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 446b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (h - l > th) { 447b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak DoubleCumulateTask lt = t.left, rt = t.right, f; 448b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt == null) { // first pass 449b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int mid = (l + h) >>> 1; 450b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = rt = t.right = 451b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new DoubleCumulateTask(t, fn, a, org, fnc, th, mid, h); 452b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt = t.left = 453b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new DoubleCumulateTask(t, fn, a, org, fnc, th, l, mid); 454b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 455b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { // possibly refork 456b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double pin = t.in; 457b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak lt.in = pin; 458b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t = null; 459b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt != null) { 460b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double lout = lt.out; 461b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rt.in = (l == org ? lout : 462b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.applyAsDouble(pin, lout)); 463b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 464b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = rt.getPendingCount()) & CUMULATE) != 0) 465b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 466b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 467b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = rt; 468b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 469b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 470b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 471b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 472b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 473b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = lt.getPendingCount()) & CUMULATE) != 0) 474b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 475b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 476b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t != null) 477b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t; 478b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt; 479b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 480b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 481b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 482b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t == null) 483b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 484b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 485b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (f != null) 486b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f.fork(); 487b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 488b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 489b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int state; // Transition to sum, cumulate, or both 490b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int b;;) { 491b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((b = t.getPendingCount()) & FINISHED) != 0) 492b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // already done 493b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = ((b & CUMULATE) != 0 ? FINISHED : 494b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (l > org) ? SUMMED : (SUMMED|FINISHED)); 495b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t.compareAndSetPendingCount(b, b|state)) 496b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 497b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 498b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 499b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double sum; 500b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (state != SUMMED) { 501b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int first; 502b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (l == org) { // leftmost; no in 503b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[org]; 504b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = org + 1; 505b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 506b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 507b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 508b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = l; 509b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 510b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = first; i < h; ++i) // cumulate 511b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a[i] = sum = fn.applyAsDouble(sum, a[i]); 512b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 513b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (h < fnc) { // skip rightmost 514b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[l]; 515b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = l + 1; i < h; ++i) // sum only 516b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = fn.applyAsDouble(sum, a[i]); 517b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 518b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else 519b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 520b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.out = sum; 521b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (DoubleCumulateTask par;;) { // propagate 522b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((par = (DoubleCumulateTask)t.getCompleter()) == null) { 523b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((state & FINISHED) != 0) // enable join 524b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.quietlyComplete(); 525b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; 526b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 527b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int b = par.getPendingCount(); 528b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((b & state & FINISHED) != 0) 529b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; // both done 530b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if ((b & state & SUMMED) != 0) { // both summed 531b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int nextState; DoubleCumulateTask lt, rt; 532b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((lt = par.left) != null && 533b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (rt = par.right) != null) { 534b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double lout = lt.out; 535b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.out = (rt.hi == fnc ? lout : 536b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.applyAsDouble(lout, rt.out)); 537b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 538b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int refork = (((b & CUMULATE) == 0 && 539b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.lo == org) ? CUMULATE : 0); 540b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((nextState = b|state|refork) == b || 541b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.compareAndSetPendingCount(b, nextState)) { 542b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = SUMMED; // drop finished 543b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; 544b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (refork != 0) 545b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.fork(); 546b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 547b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 548b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (par.compareAndSetPendingCount(b, b|state)) 549b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // sib not ready 550b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 551b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 552b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 553b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 554b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long serialVersionUID = -586947823794232033L; 555b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 556b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 557b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final class IntCumulateTask extends CountedCompleter<Void> { 558b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final int[] array; 559b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final IntBinaryOperator function; 560b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak IntCumulateTask left, right; 561b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int in, out; 562b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final int lo, hi, origin, fence, threshold; 563b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 564b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Root task constructor */ 565b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public IntCumulateTask(IntCumulateTask parent, 566b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak IntBinaryOperator function, 567b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int[] array, int lo, int hi) { 568b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 569b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 570b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = this.origin = lo; this.hi = this.fence = hi; 571b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int p; 572b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = 573b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 574b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak <= MIN_PARTITION ? MIN_PARTITION : p; 575b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 576b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 577b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Subtask constructor */ 578b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak IntCumulateTask(IntCumulateTask parent, IntBinaryOperator function, 579b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int[] array, int origin, int fence, int threshold, 580b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int lo, int hi) { 581b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak super(parent); 582b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.function = function; this.array = array; 583b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.origin = origin; this.fence = fence; 584b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.threshold = threshold; 585b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.lo = lo; this.hi = hi; 586b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 587b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 588b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public final void compute() { 589b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final IntBinaryOperator fn; 590b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final int[] a; 591b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((fn = this.function) == null || (a = this.array) == null) 592b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new NullPointerException(); // hoist checks 593b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int th = threshold, org = origin, fnc = fence, l, h; 594b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak IntCumulateTask t = this; 595b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 596b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (h - l > th) { 597b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak IntCumulateTask lt = t.left, rt = t.right, f; 598b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt == null) { // first pass 599b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int mid = (l + h) >>> 1; 600b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = rt = t.right = 601b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new IntCumulateTask(t, fn, a, org, fnc, th, mid, h); 602b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt = t.left = 603b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak new IntCumulateTask(t, fn, a, org, fnc, th, l, mid); 604b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 605b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { // possibly refork 606b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int pin = t.in; 607b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak lt.in = pin; 608b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t = null; 609b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt != null) { 610b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int lout = lt.out; 611b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rt.in = (l == org ? lout : 612b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.applyAsInt(pin, lout)); 613b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 614b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = rt.getPendingCount()) & CUMULATE) != 0) 615b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 616b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 617b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = rt; 618b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 619b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 620b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 621b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 622b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int c;;) { 623b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((c = lt.getPendingCount()) & CUMULATE) != 0) 624b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 625b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 626b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t != null) 627b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f = t; 628b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = lt; 629b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 630b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 631b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 632b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t == null) 633b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 634b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 635b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (f != null) 636b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak f.fork(); 637b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 638b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 639b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int state; // Transition to sum, cumulate, or both 640b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int b;;) { 641b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (((b = t.getPendingCount()) & FINISHED) != 0) 642b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // already done 643b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = ((b & CUMULATE) != 0 ? FINISHED : 644b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (l > org) ? SUMMED : (SUMMED|FINISHED)); 645b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t.compareAndSetPendingCount(b, b|state)) 646b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 647b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 648b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 649b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int sum; 650b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (state != SUMMED) { 651b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int first; 652b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (l == org) { // leftmost; no in 653b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[org]; 654b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = org + 1; 655b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 656b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else { 657b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 658b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak first = l; 659b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 660b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = first; i < h; ++i) // cumulate 661b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a[i] = sum = fn.applyAsInt(sum, a[i]); 662b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 663b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (h < fnc) { // skip rightmost 664b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = a[l]; 665b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (int i = l + 1; i < h; ++i) // sum only 666b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = fn.applyAsInt(sum, a[i]); 667b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 668b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else 669b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak sum = t.in; 670b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.out = sum; 671b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (IntCumulateTask par;;) { // propagate 672b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((par = (IntCumulateTask)t.getCompleter()) == null) { 673b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((state & FINISHED) != 0) // enable join 674b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t.quietlyComplete(); 675b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; 676b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 677b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int b = par.getPendingCount(); 678b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((b & state & FINISHED) != 0) 679b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; // both done 680b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if ((b & state & SUMMED) != 0) { // both summed 681b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int nextState; IntCumulateTask lt, rt; 682b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((lt = par.left) != null && 683b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (rt = par.right) != null) { 684b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int lout = lt.out; 685b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.out = (rt.hi == fnc ? lout : 686b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak fn.applyAsInt(lout, rt.out)); 687b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 688b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int refork = (((b & CUMULATE) == 0 && 689b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.lo == org) ? CUMULATE : 0); 690b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((nextState = b|state|refork) == b || 691b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.compareAndSetPendingCount(b, nextState)) { 692b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak state = SUMMED; // drop finished 693b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak t = par; 694b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (refork != 0) 695b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak par.fork(); 696b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 697b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 698b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (par.compareAndSetPendingCount(b, b|state)) 699b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break outer; // sib not ready 700b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 701b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 702b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 703b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 704b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long serialVersionUID = 3731755594596840961L; 705b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 706b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak} 707