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.3 by jsr166, Wed Sep 1 07:47:27 2010 UTC vs.
Revision 1.4 by dl, Sun Sep 19 12:55:37 2010 UTC

# Line 4 | Line 4
4   * http://creativecommons.org/licenses/publicdomain
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;
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 +        try {
22 +            if (args.length > 0)
23 +                procs = Integer.parseInt(args[0]);
24 +            if (args.length > 1)
25 +                n = Integer.parseInt(args[1]);
26 +            if (args.length > 2)
27 +                reps = Integer.parseInt(args[1]);
28 +        }
29 +        catch (Exception e) {
30 +            System.out.println("Usage: java ScalarLongSort threads n reps");
31 +            return;
32 +        }
33 +        ForkJoinPool pool = procs == 0? new ForkJoinPool() :
34 +            new ForkJoinPool(procs);
35 +
36          long[] a = new long[n];
37 +        seqRandomFill(a, 0, n);
38  
39          if (warmup) {
40              System.out.printf("Sorting %d longs, %d replications\n", n, 1);
# Line 31 | Line 46 | class ScalarLongSort {
46              checkSorted(a);
47          }
48  
34 –        ForkJoinPool pool = new ForkJoinPool();
49          // for now hardwire 8 * #CPUs leaf tasks
50          THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism();
51          //        THRESHOLD = 1 + ((n + 15) >>> 4) / pool.getParallelism();
# Line 66 | Line 80 | class ScalarLongSort {
80      }
81  
82      static final class Sorter extends RecursiveAction {
83 <        final long[] a;
83 >        final long[] a;
84          final long[] w;
85 <        final int origin;
85 >        final int origin;
86          final int n;
87          Sorter(long[] a, long[] w, int origin, int n) {
88              this.a = a; this.w = w; this.origin = origin; this.n = n;
# Line 79 | Line 93 | class ScalarLongSort {
93              if (n <= THRESHOLD)
94                  Arrays.sort(a, l, l+n);
95              else { // divide in quarters to ensure sorted array in a not w
82 –                SubSorter rs;
96                  int h = n >>> 1;
97                  int q = n >>> 2;
98                  int u = h + q;
99 <                (rs = new SubSorter
100 <                 (new Sorter(a, w, l+h, q),
101 <                  new Sorter(a, w, l+u, n-u),
102 <                  new Merger(a, w, l+h, q, l+u, n-u, l+h, null))).fork();
103 <                (new SubSorter
104 <                 (new Sorter(a, w, l,   q),
105 <                  new Sorter(a, w, l+q, h-q),
106 <                  new Merger(a, w, l,   q, l+q, h-q, l, null))).compute();
99 >                SubSorter rs = new SubSorter
100 >                    (new Sorter(a, w, l+h, q),
101 >                     new Sorter(a, w, l+u, n-u),
102 >                     new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
103 >                rs.fork();
104 >                Sorter rl = new Sorter(a, w, l+q, h-q);
105 >                rl.fork();
106 >                (new Sorter(a, w, l,   q)).compute();
107 >                rl.join();
108 >                (new Merger(a, w, l,   q, l+q, h-q, l, null)).compute();
109                  rs.join();
110                  new Merger(w, a, l, h, l+h, n-h, l, null).compute();
111              }
112          }
113      }
114 <
114 >    
115      static final class SubSorter extends RecursiveAction {
116          final Sorter left;
117          final Sorter right;
# Line 115 | Line 130 | class ScalarLongSort {
130      static final class Merger extends RecursiveAction {
131          final long[] a; final long[] w;
132          final int lo; final int ln; final int ro; final int rn; final int wo;
133 <        final Merger next;
133 >        Merger next;
134          Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo,
135                 Merger next) {
136              this.a = a;    this.w = w;
# Line 130 | Line 145 | class ScalarLongSort {
145           * and finding index of right closest to split point.
146           * Uses left-spine decomposition to generate all
147           * merge tasks before bottomming out at base case.
148 <         *
148 >         *
149           */
150 <        public void compute() {
150 >        public final void compute() {
151              Merger rights = null;
152              int nleft = ln;
153              int nright = rn;
# Line 154 | Line 169 | class ScalarLongSort {
169                  nleft = lh;
170                  nright = rh;
171              }
172 +            
173 +            merge(nleft, nright);
174 +            if (rights != null)
175 +                collectRights(rights);
176 +            
177 +        }
178  
179 <            // Base case -- merge left and right
179 >        final void merge(int nleft, int nright) {
180              int l = lo;
181              int lFence = lo + nleft;
182              int r = ro;
# Line 172 | Line 193 | class ScalarLongSort {
193                  w[k++] = a[l++];
194              while (r < rFence)
195                  w[k++] = a[r++];
196 +        }
197  
198 <            while (rights != null) {
199 <                rights.join();
200 <                rights = rights.next;
198 >        static void collectRights(Merger rt) {
199 >            while (rt != null) {
200 >                Merger next = rt.next;
201 >                rt.next = null;
202 >                if (rt.tryUnfork()) rt.compute(); else rt.join();
203 >                rt = next;
204              }
205          }
206  
207      }
208  
209 <    static void checkSorted(long[] a)  {
209 >    static void checkSorted (long[] a)  {
210          int n = a.length;
211          for (int i = 0; i < n - 1; i++) {
212              if (a[i] > a[i+1]) {
213 <                throw new Error("Unsorted at " + i + ": " +
213 >                throw new Error("Unsorted at " + i + ": " +
214                                  a[i] + " / " + a[i+1]);
215              }
216          }
# Line 204 | Line 229 | class ScalarLongSort {
229              this.array = array; this.lo = lo; this.hi = hi;
230          }
231          public void compute() {
232 <            if (hi - lo <= THRESHOLD)
233 <                seqRandomFill(array, lo, hi);
232 >            if (hi - lo <= THRESHOLD) {
233 >                long[] a = array;
234 >                ThreadLocalRandom rng = ThreadLocalRandom.current();
235 >                for (int i = lo; i < hi; ++i)
236 >                    a[i] = rng.nextLong();
237 >            }
238              else {
239                  int mid = (lo + hi) >>> 1;
240                  RandomFiller r = new RandomFiller(array, mid, hi);

Diff Legend

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