ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/loops/ScalarLongSort.java
(Generate patch)

Comparing jsr166/src/test/loops/ScalarLongSort.java (file contents):
Revision 1.1 by dl, Tue Mar 16 11:42:46 2010 UTC vs.
Revision 1.11 by jsr166, Sun Oct 21 06:14:12 2012 UTC

# Line 1 | Line 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 < * http://creativecommons.org/licenses/publicdomain
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   */
6  
7 – import java.util.*;
7   import java.util.concurrent.*;
8 <
10 < // Based very loosely on cilksort
8 > import java.util.*;
9  
10   class ScalarLongSort {
11 <    static final long NPS = (1000L * 1000 * 1000); // time conversion
11 >    static final long NPS = (1000L * 1000 * 1000);
12  
13 <    static int THRESHOLD;
13 >    static int THRESHOLD = -1;
14      static final boolean warmup = true;
15  
16 <    public static void main (String[] args) throws Exception {
16 >    public static void main(String[] args) throws Exception {
17 >        int procs = 0;
18          int n = 1 << 22;
20 –        int sreps = 2;
19          int reps = 20;
20 +        int sreps = 2;
21 +        int st = -1;
22 +        try {
23 +            if (args.length > 0)
24 +                procs = Integer.parseInt(args[0]);
25 +            if (args.length > 1)
26 +                n = Integer.parseInt(args[1]);
27 +            if (args.length > 2)
28 +                reps = Integer.parseInt(args[2]);
29 +            if (args.length > 3)
30 +                st = Integer.parseInt(args[3]);
31 +        }
32 +        catch (Exception e) {
33 +            System.out.println("Usage: java ScalarLongSort threads n reps sequential-threshold");
34 +            return;
35 +        }
36 +        ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() :
37 +            new ForkJoinPool(procs);
38 +
39          long[] a = new long[n];
40 +        seqRandomFill(a, 0, n);
41  
42          if (warmup) {
43              System.out.printf("Sorting %d longs, %d replications\n", n, 1);
# Line 31 | Line 49 | class ScalarLongSort {
49              checkSorted(a);
50          }
51  
52 <        ForkJoinPool pool = new ForkJoinPool();
53 <        // for now hardwire 8 * #CPUs leaf tasks
54 <        THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism();
55 <        //        THRESHOLD = 1 + ((n + 15) >>> 4) / pool.getParallelism();
38 <        //        THRESHOLD = 1 + ((n + 31) >>> 5) / pool.getParallelism();
52 >        if (st <= 0) // for now hardwire 8 * #CPUs leaf tasks
53 >            THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism();
54 >        else
55 >            THRESHOLD = st;
56  
57          System.out.printf("Sorting %d longs, %d replications\n", n, reps);
58          for (int i = 0; i < reps; ++i) {
# Line 66 | Line 83 | class ScalarLongSort {
83      }
84  
85      static final class Sorter extends RecursiveAction {
86 <        final long[] a;
86 >        final long[] a;
87          final long[] w;
88 <        final int origin;
88 >        final int origin;
89          final int n;
90          Sorter(long[] a, long[] w, int origin, int n) {
91              this.a = a; this.w = w; this.origin = origin; this.n = n;
92          }
93  
94 <        public void compute()  {
94 >        public void compute() {
95              int l = origin;
96              if (n <= THRESHOLD)
97                  Arrays.sort(a, l, l+n);
98              else { // divide in quarters to ensure sorted array in a not w
82 –                SubSorter rs;
99                  int h = n >>> 1;
100                  int q = n >>> 2;
101                  int u = h + q;
102 <                (rs = new SubSorter
103 <                 (new Sorter(a, w, l+h, q),
104 <                  new Sorter(a, w, l+u, n-u),
105 <                  new Merger(a, w, l+h, q, l+u, n-u, l+h, null))).fork();
106 <                (new SubSorter
107 <                 (new Sorter(a, w, l,   q),
108 <                  new Sorter(a, w, l+q, h-q),
109 <                  new Merger(a, w, l,   q, l+q, h-q, l, null))).compute();
102 >                SubSorter rs = new SubSorter
103 >                    (new Sorter(a, w, l+h, q),
104 >                     new Sorter(a, w, l+u, n-u),
105 >                     new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
106 >                rs.fork();
107 >                Sorter rl = new Sorter(a, w, l+q, h-q);
108 >                rl.fork();
109 >                (new Sorter(a, w, l,   q)).compute();
110 >                rl.join();
111 >                (new Merger(a, w, l,   q, l+q, h-q, l, null)).compute();
112                  rs.join();
113                  new Merger(w, a, l, h, l+h, n-h, l, null).compute();
114              }
115          }
116      }
117 <    
117 >
118      static final class SubSorter extends RecursiveAction {
119          final Sorter left;
120          final Sorter right;
# Line 115 | Line 133 | class ScalarLongSort {
133      static final class Merger extends RecursiveAction {
134          final long[] a; final long[] w;
135          final int lo; final int ln; final int ro; final int rn; final int wo;
136 <        final Merger next;
136 >        Merger next;
137          Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo,
138                 Merger next) {
139              this.a = a;    this.w = w;
# Line 130 | Line 148 | class ScalarLongSort {
148           * and finding index of right closest to split point.
149           * Uses left-spine decomposition to generate all
150           * merge tasks before bottomming out at base case.
133 –         *
151           */
152 <        public void compute() {
152 >        public final void compute() {
153              Merger rights = null;
154              int nleft = ln;
155              int nright = rn;
# Line 155 | Line 172 | class ScalarLongSort {
172                  nright = rh;
173              }
174  
175 <            // Base case -- merge left and right
175 >            merge(nleft, nright);
176 >            if (rights != null)
177 >                collectRights(rights);
178 >
179 >        }
180 >
181 >        final void merge(int nleft, int nright) {
182              int l = lo;
183              int lFence = lo + nleft;
184              int r = ro;
# Line 172 | Line 195 | class ScalarLongSort {
195                  w[k++] = a[l++];
196              while (r < rFence)
197                  w[k++] = a[r++];
198 <            
199 <            while (rights != null) {
200 <                rights.join();
201 <                rights = rights.next;
198 >        }
199 >
200 >        static void collectRights(Merger rt) {
201 >            while (rt != null) {
202 >                Merger next = rt.next;
203 >                rt.next = null;
204 >                if (rt.tryUnfork()) rt.compute(); else rt.join();
205 >                rt = next;
206              }
207          }
208  
209      }
210  
211 <    static void checkSorted (long[] a)  {
211 >    static void checkSorted(long[] a) {
212          int n = a.length;
213          for (int i = 0; i < n - 1; i++) {
214              if (a[i] > a[i+1]) {
215 <                throw new Error("Unsorted at " + i + ": " +
215 >                throw new Error("Unsorted at " + i + ": " +
216                                  a[i] + " / " + a[i+1]);
217              }
218          }
# Line 204 | Line 231 | class ScalarLongSort {
231              this.array = array; this.lo = lo; this.hi = hi;
232          }
233          public void compute() {
234 <            if (hi - lo <= THRESHOLD)
235 <                seqRandomFill(array, lo, hi);
234 >            if (hi - lo <= THRESHOLD) {
235 >                long[] a = array;
236 >                ThreadLocalRandom rng = ThreadLocalRandom.current();
237 >                for (int i = lo; i < hi; ++i)
238 >                    a[i] = rng.nextLong();
239 >            }
240              else {
241                  int mid = (lo + hi) >>> 1;
242                  RandomFiller r = new RandomFiller(array, mid, hi);

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines