Home | History | Annotate | Download | only in go1 
      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