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  }
    85
View as plain text