forked from springside/springside4
-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
- Loading branch information
1 parent
157905e
commit 684f28d
Showing
9 changed files
with
250 additions
and
47 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
166 changes: 166 additions & 0 deletions
166
.../utils/src/main/java/org/springside/modules/utils/concurrent/jsr166e/RecursiveAction.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,166 @@ | ||
| /* | ||
| * 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/ | ||
| */ | ||
|
|
||
| package org.springside.modules.utils.concurrent.jsr166e; | ||
|
|
||
| /** | ||
| * http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/RecursiveAction.java 1.3 | ||
| * | ||
| * A recursive resultless {@link ForkJoinTask}. This class | ||
| * establishes conventions to parameterize resultless actions as | ||
| * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the | ||
| * only valid value of type {@code Void}, methods such as {@code join} | ||
| * always return {@code null} upon completion. | ||
| * | ||
| * <p><b>Sample Usages.</b> Here is a simple but complete ForkJoin | ||
| * sort that sorts a given {@code long[]} array: | ||
| * | ||
| * <pre> {@code | ||
| * static class SortTask extends RecursiveAction { | ||
| * final long[] array; final int lo, hi; | ||
| * SortTask(long[] array, int lo, int hi) { | ||
| * this.array = array; this.lo = lo; this.hi = hi; | ||
| * } | ||
| * SortTask(long[] array) { this(array, 0, array.length); } | ||
| * protected void compute() { | ||
| * if (hi - lo < THRESHOLD) | ||
| * sortSequentially(lo, hi); | ||
| * else { | ||
| * int mid = (lo + hi) >>> 1; | ||
| * invokeAll(new SortTask(array, lo, mid), | ||
| * new SortTask(array, mid, hi)); | ||
| * merge(lo, mid, hi); | ||
| * } | ||
| * } | ||
| * // implementation details follow: | ||
| * static final int THRESHOLD = 1000; | ||
| * void sortSequentially(int lo, int hi) { | ||
| * Arrays.sort(array, lo, hi); | ||
| * } | ||
| * void merge(int lo, int mid, int hi) { | ||
| * long[] buf = Arrays.copyOfRange(array, lo, mid); | ||
| * for (int i = 0, j = lo, k = mid; i < buf.length; j++) | ||
| * array[j] = (k == hi || buf[i] < array[k]) ? | ||
| * buf[i++] : array[k++]; | ||
| * } | ||
| * }}</pre> | ||
| * | ||
| * You could then sort {@code anArray} by creating {@code new | ||
| * SortTask(anArray)} and invoking it in a ForkJoinPool. As a more | ||
| * concrete simple example, the following task increments each element | ||
| * of an array: | ||
| * <pre> {@code | ||
| * class IncrementTask extends RecursiveAction { | ||
| * final long[] array; final int lo, hi; | ||
| * IncrementTask(long[] array, int lo, int hi) { | ||
| * this.array = array; this.lo = lo; this.hi = hi; | ||
| * } | ||
| * protected void compute() { | ||
| * if (hi - lo < THRESHOLD) { | ||
| * for (int i = lo; i < hi; ++i) | ||
| * array[i]++; | ||
| * } | ||
| * else { | ||
| * int mid = (lo + hi) >>> 1; | ||
| * invokeAll(new IncrementTask(array, lo, mid), | ||
| * new IncrementTask(array, mid, hi)); | ||
| * } | ||
| * } | ||
| * }}</pre> | ||
| * | ||
| * <p>The following example illustrates some refinements and idioms | ||
| * that may lead to better performance: RecursiveActions need not be | ||
| * fully recursive, so long as they maintain the basic | ||
| * divide-and-conquer approach. Here is a class that sums the squares | ||
| * of each element of a double array, by subdividing out only the | ||
| * right-hand-sides of repeated divisions by two, and keeping track of | ||
| * them with a chain of {@code next} references. It uses a dynamic | ||
| * threshold based on method {@code getSurplusQueuedTaskCount}, but | ||
| * counterbalances potential excess partitioning by directly | ||
| * performing leaf actions on unstolen tasks rather than further | ||
| * subdividing. | ||
| * | ||
| * <pre> {@code | ||
| * double sumOfSquares(ForkJoinPool pool, double[] array) { | ||
| * int n = array.length; | ||
| * Applyer a = new Applyer(array, 0, n, null); | ||
| * pool.invoke(a); | ||
| * return a.result; | ||
| * } | ||
| * | ||
| * class Applyer extends RecursiveAction { | ||
| * final double[] array; | ||
| * final int lo, hi; | ||
| * double result; | ||
| * Applyer next; // keeps track of right-hand-side tasks | ||
| * Applyer(double[] array, int lo, int hi, Applyer next) { | ||
| * this.array = array; this.lo = lo; this.hi = hi; | ||
| * this.next = next; | ||
| * } | ||
| * | ||
| * double atLeaf(int l, int h) { | ||
| * double sum = 0; | ||
| * for (int i = l; i < h; ++i) // perform leftmost base step | ||
| * sum += array[i] * array[i]; | ||
| * return sum; | ||
| * } | ||
| * | ||
| * protected void compute() { | ||
| * int l = lo; | ||
| * int h = hi; | ||
| * Applyer right = null; | ||
| * while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) { | ||
| * int mid = (l + h) >>> 1; | ||
| * right = new Applyer(array, mid, h, right); | ||
| * right.fork(); | ||
| * h = mid; | ||
| * } | ||
| * double sum = atLeaf(l, h); | ||
| * while (right != null) { | ||
| * if (right.tryUnfork()) // directly calculate if not stolen | ||
| * sum += right.atLeaf(right.lo, right.hi); | ||
| * else { | ||
| * right.join(); | ||
| * sum += right.result; | ||
| * } | ||
| * right = right.next; | ||
| * } | ||
| * result = sum; | ||
| * } | ||
| * }}</pre> | ||
| * | ||
| * @since 1.7 | ||
| * @author Doug Lea | ||
| */ | ||
| public abstract class RecursiveAction extends ForkJoinTask<Void> { | ||
| private static final long serialVersionUID = 5232453952276485070L; | ||
|
|
||
| /** | ||
| * The main computation performed by this task. | ||
| */ | ||
| protected abstract void compute(); | ||
|
|
||
| /** | ||
| * Always returns {@code null}. | ||
| * | ||
| * @return {@code null} always | ||
| */ | ||
| public final Void getRawResult() { return null; } | ||
|
|
||
| /** | ||
| * Requires null completion value. | ||
| */ | ||
| protected final void setRawResult(Void mustBeNull) { } | ||
|
|
||
| /** | ||
| * Implements execution conventions for RecursiveActions. | ||
| */ | ||
| protected final boolean exec() { | ||
| compute(); | ||
| return true; | ||
| } | ||
|
|
||
| } |
71 changes: 71 additions & 0 deletions
71
...es/utils/src/main/java/org/springside/modules/utils/concurrent/jsr166e/RecursiveTask.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,71 @@ | ||
| /* | ||
| * 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/ | ||
| */ | ||
|
|
||
| package org.springside.modules.utils.concurrent.jsr166e; | ||
|
|
||
| /** | ||
| * http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/RecursiveTask.java 1.4 | ||
| * | ||
| * A recursive result-bearing {@link ForkJoinTask}. | ||
| * | ||
| * <p>For a classic example, here is a task computing Fibonacci numbers: | ||
| * | ||
| * <pre> {@code | ||
| * class Fibonacci extends RecursiveTask<Integer> { | ||
| * final int n; | ||
| * Fibonacci(int n) { this.n = n; } | ||
| * protected Integer compute() { | ||
| * if (n <= 1) | ||
| * return n; | ||
| * Fibonacci f1 = new Fibonacci(n - 1); | ||
| * f1.fork(); | ||
| * Fibonacci f2 = new Fibonacci(n - 2); | ||
| * return f2.compute() + f1.join(); | ||
| * } | ||
| * }}</pre> | ||
| * | ||
| * However, besides being a dumb way to compute Fibonacci functions | ||
| * (there is a simple fast linear algorithm that you'd use in | ||
| * practice), this is likely to perform poorly because the smallest | ||
| * subtasks are too small to be worthwhile splitting up. Instead, as | ||
| * is the case for nearly all fork/join applications, you'd pick some | ||
| * minimum granularity size (for example 10 here) for which you always | ||
| * sequentially solve rather than subdividing. | ||
| * | ||
| * @since 1.7 | ||
| * @author Doug Lea | ||
| */ | ||
| public abstract class RecursiveTask<V> extends ForkJoinTask<V> { | ||
| private static final long serialVersionUID = 5232453952276485270L; | ||
|
|
||
| /** | ||
| * The result of the computation. | ||
| */ | ||
| V result; | ||
|
|
||
| /** | ||
| * The main computation performed by this task. | ||
| * @return the result of the computation | ||
| */ | ||
| protected abstract V compute(); | ||
|
|
||
| public final V getRawResult() { | ||
| return result; | ||
| } | ||
|
|
||
| protected final void setRawResult(V value) { | ||
| result = value; | ||
| } | ||
|
|
||
| /** | ||
| * Implements execution conventions for RecursiveTask. | ||
| */ | ||
| protected final boolean exec() { | ||
| result = compute(); | ||
| return true; | ||
| } | ||
|
|
||
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters