test/bench/go1/fannkuch_test.go

   1 // Copyright 2011 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // This benchmark, taken from the shootout, tests array indexing
   6 // and array bounds elimination performance.
   7
   8 package go1
   9
  10 import "testing"
  11
  12 func fannkuch(n int) int {
  13         if n < 1 {
  14                 return 0
  15         }
  16
  17         n1 := n - 1
  18         perm := make([]int, n)
  19         perm1 := make([]int, n)
  20         count := make([]int, n)
  21
  22         for i := 0; i < n; i++ {
  23                 perm1[i] = i // initial (trivial) permutation
  24         }
  25
  26         r := n
  27         didpr := 0
  28         flipsMax := 0
  29         for {
  30                 if didpr < 30 {
  31                         didpr++
  32                 }
  33                 for ; r != 1; r-- {
  34                         count[r-1] = r
  35                 }
  36
  37                 if perm1[0] != 0 && perm1[n1] != n1 {
  38                         flips := 0
  39                         for i := 1; i < n; i++ { // perm = perm1
  40                                 perm[i] = perm1[i]
  41                         }
  42                         k := perm1[0] // cache perm[0] in k
  43                         for {         // k!=0 ==> k>0
  44                                 for i, j := 1, k-1; i < j; i, j = i+1, j-1 {
  45                                         perm[i], perm[j] = perm[j], perm[i]
  46                                 }
  47                                 flips++
  48                                 // Now exchange k (caching perm[0]) and perm[k]... with care!
  49                                 j := perm[k]
  50                                 perm[k] = k
  51                                 k = j
  52                                 if k == 0 {
  53                                         break
  54                                 }
  55                         }
  56                         if flipsMax < flips {
  57                                 flipsMax = flips
  58                         }
  59                 }
  60
  61                 for ; r < n; r++ {
  62                         // rotate down perm[0..r] by one
  63                         perm0 := perm1[0]
  64                         for i := 0; i < r; i++ {
  65                                 perm1[i] = perm1[i+1]
  66                         }
  67                         perm1[r] = perm0
  68                         count[r]--
  69                         if count[r] > 0 {
  70                                 break
  71                         }
  72                 }
  73                 if r == n {
  74                         return flipsMax
  75                 }
  76         }
  77         return 0
  78 }
  79
  80 func BenchmarkFannkuch11(b *testing.B) {
  81         for i := 0; i < b.N; i++ {
  82                 fannkuch(11)
  83         }
  84 }