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

Comparing jsr166/src/test/loops/DynamicLeftSpineFib.java (file contents):
Revision 1.3 by jsr166, Thu Oct 29 23:14:43 2009 UTC vs.
Revision 1.11 by jsr166, Mon Sep 20 20:42:37 2010 UTC

# Line 1 | Line 1
1 – //import jsr166y.*;
2 – import java.util.*;
1   import java.util.concurrent.*;
2 + import java.util.*;
3 + import java.util.concurrent.TimeUnit;
4 + //import java.util.concurrent.*;
5  
6   public final class DynamicLeftSpineFib extends RecursiveAction {
7  
7 –    // Performance-tuning constant:
8      static long lastStealCount;
9  
10      public static void main(String[] args) throws Exception {
11          int procs = 0;
12 <        int num = 43;
12 >        int num = 45;
13          try {
14              if (args.length > 0)
15                  procs = Integer.parseInt(args[0]);
# Line 17 | Line 17 | public final class DynamicLeftSpineFib e
17                  num = Integer.parseInt(args[1]);
18          }
19          catch (Exception e) {
20 <            System.out.println("Usage: java DynamicLeftSpineFib <threads> <number> [<sequentialThreshold>]");
20 >            System.out.println("Usage: java DynamicLeftSpineFib <threads> <number> [<sequntialThreshold>]");
21              return;
22          }
23  
# Line 26 | Line 26 | public final class DynamicLeftSpineFib e
26              ForkJoinPool g = procs == 0? new ForkJoinPool() :
27                  new ForkJoinPool(procs);
28              lastStealCount = g.getStealCount();
29 <            for (int i = 0; i < 10; ++i) {
29 >            for (int i = 0; i < 20; ++i) {
30                  test(g, num);
31              }
32              System.out.println(g);
33              g.shutdown();
34 +            if (!g.awaitTermination(10, TimeUnit.SECONDS))
35 +                throw new Error();
36 +            Thread.sleep(1000);
37          }
38      }
39  
# Line 42 | Line 45 | public final class DynamicLeftSpineFib e
45          long time = System.currentTimeMillis() - start;
46          double secs = ((double)time) / 1000.0;
47          long result = f.getAnswer();
48 <        System.out.print("DynamicLeftSpineFib " + num + " = " + result);
48 >        System.out.print("DLSFib " + num + " = " + result);
49          System.out.printf("\tTime: %7.3f", secs);
50          long sc = g.getStealCount();
51          long ns = sc - lastStealCount;
# Line 64 | Line 67 | public final class DynamicLeftSpineFib e
67      int getAnswer() {
68          return number;
69      }
70 +    public void compute() {
71 +        number = fib(number);
72 +    }
73  
74 <    public final void compute() {
75 <        int n = number;
76 <        if (n > 1) {
77 <            DynamicLeftSpineFib rt = null;
78 <            while (n > 1 && getSurplusQueuedTaskCount() <= 3) {
79 <                (rt = new DynamicLeftSpineFib(n - 2, rt)).fork();
80 <                n -= 1;
74 >    static final int fib(int n) {
75 >        if (n <= 1)
76 >            return n;
77 >        int r = 0;
78 >        DynamicLeftSpineFib rt = null;
79 >        while (getSurplusQueuedTaskCount() <= 3) {
80 >            int m = n - 2;
81 >            n -= 1;
82 >            if (m <= 1) {
83 >                r += m;
84 >                if (n > 1) {
85 >                    r += n - 2;
86 >                    n -= 1;
87 >                }
88 >                break;
89              }
90 <            int r = seqFib(n);
91 <            while (rt != null) {
92 <                if (rt.tryUnfork()) rt.compute(); else rt.helpJoin();
90 >            (rt = new DynamicLeftSpineFib(m, rt)).fork();
91 >        }
92 >        if (n <= 1)
93 >            r += n;
94 >        else
95 >            r += seqFib(n - 2) + fib(n - 1);
96 >        if (rt != null)
97 >            r += collectRights(rt);
98 >        return r;
99 >    }
100 >
101 >    static final int collectRights(DynamicLeftSpineFib rt) {
102 >        int r = 0;
103 >        while (rt != null) {
104 >            DynamicLeftSpineFib rn = rt.next;
105 >            rt.next = null;
106 >            if (rt.tryUnfork())
107 >                r += fib(rt.number);
108 >            else {
109 >                rt.join();
110                  r += rt.number;
80 –                rt = rt.next;
111              }
112 <            number = r;
112 >            rt = rn;
113          }
114 +        return r;
115      }
116  
117      // Sequential version for arguments less than threshold
118 <    static int seqFib(int n) {
119 <        if (n <= 1)
120 <            return n;
121 <        else
122 <            return seqFib(n-1) + seqFib(n-2);
118 >    static final int seqFib(int n) { // unroll left only
119 >        int r = 1;
120 >        do {
121 >            int m = n - 2;
122 >            r += m <= 1 ? m : seqFib(m);
123 >        } while (--n > 1);
124 >        return r;
125      }
126  
127   }
128 +

Diff Legend

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