...
Run Format

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

View as plain text