diff options
Diffstat (limited to 'test/bench/fannkuch-parallel.go')
| -rw-r--r-- | test/bench/fannkuch-parallel.go | 224 |
1 files changed, 0 insertions, 224 deletions
diff --git a/test/bench/fannkuch-parallel.go b/test/bench/fannkuch-parallel.go deleted file mode 100644 index 7e9b98d50..000000000 --- a/test/bench/fannkuch-parallel.go +++ /dev/null @@ -1,224 +0,0 @@ -/* -Redistribution and use in source and binary forms, with or without -modification, are permitted provided that the following conditions are met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - - * Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in the - documentation and/or other materials provided with the distribution. - - * Neither the name of "The Computer Language Benchmarks Game" nor the - name of "The Computer Language Shootout Benchmarks" nor the names of - its contributors may be used to endorse or promote products derived - from this software without specific prior written permission. - -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" -AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE -LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR -CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF -SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS -INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN -CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) -ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE -POSSIBILITY OF SUCH DAMAGE. -*/ - -/* - * The Computer Language Benchmarks Game - * http://shootout.alioth.debian.org/ - * - * contributed by The Go Authors. - * Based on fannkuch.scala by Rex Kerr - */ - -package main - -import ( - "flag" - "fmt" - "runtime" -) - -var n = flag.Int("n", 7, "count") -var nCPU = flag.Int("ncpu", 4, "number of cpus") - -type Job struct { - start []int - n int -} - -type Found struct { - who *Kucher - k int -} - -type Kucher struct { - perm []int - temp []int - flip []int - in chan Job -} - -func NewKucher(length int) *Kucher { - return &Kucher{ - perm: make([]int, length), - temp: make([]int, length), - flip: make([]int, length), - in: make(chan Job), - } -} - -func (k *Kucher) permute(n int) bool { - i := 0 - for ; i < n-1 && k.flip[i] == 0; i++ { - t := k.perm[0] - j := 0 - for ; j <= i; j++ { - k.perm[j] = k.perm[j+1] - } - k.perm[j] = t - } - k.flip[i]-- - for i > 0 { - i-- - k.flip[i] = i - } - return k.flip[n-1] >= 0 -} - -func (k *Kucher) count() int { - K := 0 - copy(k.temp, k.perm) - for k.temp[0] != 0 { - m := k.temp[0] - for i := 0; i < m; i++ { - k.temp[i], k.temp[m] = k.temp[m], k.temp[i] - m-- - } - K++ - } - return K -} - -func (k *Kucher) Run(foreman chan<- Found) { - for job := range k.in { - verbose := 30 - copy(k.perm, job.start) - for i, v := range k.perm { - if v != i { - verbose = 0 - } - k.flip[i] = i - } - K := 0 - for { - if verbose > 0 { - for _, p := range k.perm { - fmt.Print(p + 1) - } - fmt.Println() - verbose-- - } - count := k.count() - if count > K { - K = count - } - if !k.permute(job.n) { - break - } - } - foreman <- Found{k, K} - } -} - -type Fanner struct { - jobind int - jobsdone int - k int - jobs []Job - workers []*Kucher - in chan Found - result chan int -} - -func NewFanner(jobs []Job, workers []*Kucher) *Fanner { - return &Fanner{ - jobs: jobs, workers: workers, - in: make(chan Found), - result: make(chan int), - } -} - -func (f *Fanner) Run(N int) { - for msg := range f.in { - if msg.k > f.k { - f.k = msg.k - } - if msg.k >= 0 { - f.jobsdone++ - } - if f.jobind < len(f.jobs) { - msg.who.in <- f.jobs[f.jobind] - f.jobind++ - } else if f.jobsdone == len(f.jobs) { - f.result <- f.k - return - } - } -} - -func swapped(a []int, i, j int) []int { - b := make([]int, len(a)) - copy(b, a) - b[i], b[j] = a[j], a[i] - return b -} - -func main() { - flag.Parse() - runtime.GOMAXPROCS(*nCPU) - N := *n - base := make([]int, N) - for i := range base { - base[i] = i - } - - njobs := 1 - if N > 8 { - njobs += (N*(N-1))/2 - 28 // njobs = 1 + sum(8..N-1) = 1 + sum(1..N-1) - sum(1..7) - } - jobs := make([]Job, njobs) - jobsind := 0 - - firstN := N - if firstN > 8 { - firstN = 8 - } - jobs[jobsind] = Job{base, firstN} - jobsind++ - for i := N - 1; i >= 8; i-- { - for j := 0; j < i; j++ { - jobs[jobsind] = Job{swapped(base, i, j), i} - jobsind++ - } - } - - nworkers := *nCPU - if njobs < nworkers { - nworkers = njobs - } - workers := make([]*Kucher, nworkers) - foreman := NewFanner(jobs, workers) - go foreman.Run(N) - for i := range workers { - k := NewKucher(N) - workers[i] = k - go k.Run(foreman.in) - foreman.in <- Found{k, -1} - } - fmt.Printf("Pfannkuchen(%d) = %d\n", N, <-foreman.result) -} |