Subversion Repositories openrisc

// Copyright 2011 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This benchmark, taken from the shootout, tests array indexing
// and array bounds elimination performance.

package go1

import "testing"

func fannkuch(n int) int {
        if n < 1 {
                return 0
        }

        n1 := n - 1
        perm := make([]int, n)
        perm1 := make([]int, n)
        count := make([]int, n)

        for i := 0; i < n; i++ {
                perm1[i] = i // initial (trivial) permutation
        }

        r := n
        didpr := 0
        flipsMax := 0
        for {
                if didpr < 30 {
                        didpr++
                }
                for ; r != 1; r-- {
                        count[r-1] = r
                }

                if perm1[0] != 0 && perm1[n1] != n1 {
                        flips := 0
                        for i := 1; i < n; i++ { // perm = perm1
                                perm[i] = perm1[i]
                        }
                        k := perm1[0] // cache perm[0] in k
                        for {         // k!=0 ==> k>0
                                for i, j := 1, k-1; i < j; i, j = i+1, j-1 {
                                        perm[i], perm[j] = perm[j], perm[i]
                                }
                                flips++
                                // Now exchange k (caching perm[0]) and perm[k]... with care!
                                j := perm[k]
                                perm[k] = k
                                k = j
                                if k == 0 {
                                        break
                                }
                        }
                        if flipsMax < flips {
                                flipsMax = flips
                        }
                }

                for ; r < n; r++ {
                        // rotate down perm[0..r] by one
                        perm0 := perm1[0]
                        for i := 0; i < r; i++ {
                                perm1[i] = perm1[i+1]
                        }
                        perm1[r] = perm0
                        count[r]--
                        if count[r] > 0 {
                                break
                        }
                }
                if r == n {
                        return flipsMax
                }
        }
        return 0
}

func BenchmarkFannkuch11(b *testing.B) {
        for i := 0; i < b.N; i++ {
                fannkuch(11)
        }
}