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 } 85