root/trunk/benchmark/fannkuch.md

Revision 362, 1.4 kB (checked in by JarrettBillingsley, 3 months ago)

Fixed a bug where array data was being allocated but not initialized, causing some GC cycles to try to scan garbage data (and crash). Updated the benchmarks and all that I've tested have worked fine, not to mention being at least 15% faster in most cases :)

Line 
1 module benchmark.fannkuch
2
3 // n = 10, 79.13 sec
4 // n = 11, 975 sec
5 // laptop: n = 10, 44.54 sec
6
7 function fannkuch(n)
8 {
9     local perm = array.new(n, 0)
10     local perm1 = array.range(n)
11     local count = array.new(n, 0)
12
13     local i = 0
14     local j = 0
15     local k = 0
16     local t = 0
17     local flips = 0
18     local r = n
19     local maxFlipsCount = 0
20     local check = 0
21
22     while(true)
23     {
24         if(check < 30)
25         {
26             foreach(p; perm1)
27                 writef(p + 1)
28
29             writefln()
30             check++
31         }
32
33         while(r != 1)
34         {
35             count[r - 1] = r
36             r--
37         }
38
39         if(!(perm1[0] == 0 || perm1[n - 1] == n - 1))
40         {
41             perm[] = perm1
42
43             flips = 0
44             i = perm[0]
45
46             do
47             {
48                 j = 1
49                 k = i - 1
50
51                 while(j < k)
52                 {
53                     t = perm[j]
54                     perm[j] = perm[k]
55                     perm[k] = t
56
57                     j++
58                     k--
59                 }
60
61                 flips++
62                 t = perm[i]
63                 perm[i] = i
64                 i = t
65             } while(i)
66
67             if(flips > maxFlipsCount)
68                 maxFlipsCount = flips
69         }
70
71         while(true)
72         {
73             if(r == n)
74                 return maxFlipsCount
75
76             t = perm1[0]
77
78             for(i = 0; i < r;)
79             {
80                 j = i + 1
81                 perm1[i] = perm1[j]
82                 i = j
83             }
84
85             perm1[r] = t
86             count[r]--
87
88             if(count[r] > 0)
89                 break
90
91             r++
92         }
93     }
94 }
95
96 function main(N)
97 {
98     local n = 10
99
100     if(isString(N))
101         try n = toInt(N); catch(e) {}
102
103     local timer = time.Timer.clone()
104     timer.start()
105
106     writefln("Pfannkuchen({}) = {}", n, fannkuch(n))
107
108     timer.stop()
109     writefln("Took {} sec", timer.seconds())
110 }
Note: See TracBrowser for help on using the browser.