// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package testing

import (
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
)

func initBenchmarkFlags() {
	matchBenchmarks = flag.String("test.bench", "", "run only benchmarks matching `regexp`")
	benchmarkMemory = flag.Bool("test.benchmem", false, "print memory allocations for benchmarks")
	flag.Var(&benchTime, "test.benchtime", "run each benchmark for duration `d`")
}

var (
	matchBenchmarks *string
	benchmarkMemory *bool

	benchTime = benchTimeFlag{d: 1 * time.Second} // changed during test of testing package
)

type benchTimeFlag struct {
	d time.Duration
	n int
}

func ( *benchTimeFlag) () string {
	if .n > 0 {
		return fmt.Sprintf("%dx", .n)
	}
	return time.Duration(.d).String()
}

func ( *benchTimeFlag) ( string) error {
	if strings.HasSuffix(, "x") {
		,  := strconv.ParseInt([:len()-1], 10, 0)
		if  != nil ||  <= 0 {
			return fmt.Errorf("invalid count")
		}
		* = benchTimeFlag{n: int()}
		return nil
	}
	,  := time.ParseDuration()
	if  != nil ||  <= 0 {
		return fmt.Errorf("invalid duration")
	}
	* = benchTimeFlag{d: }
	return nil
}

// Global lock to ensure only one benchmark runs at a time.
var benchmarkLock sync.Mutex

// Used for every benchmark for measuring memory.
var memStats runtime.MemStats

// InternalBenchmark is an internal type but exported because it is cross-package;
// it is part of the implementation of the "go test" command.
type InternalBenchmark struct {
	Name string
	F    func(b *B)
}

// B is a type passed to Benchmark functions to manage benchmark
// timing and to specify the number of iterations to run.
//
// A benchmark ends when its Benchmark function returns or calls any of the methods
// FailNow, Fatal, Fatalf, SkipNow, Skip, or Skipf. Those methods must be called
// only from the goroutine running the Benchmark function.
// The other reporting methods, such as the variations of Log and Error,
// may be called simultaneously from multiple goroutines.
//
// Like in tests, benchmark logs are accumulated during execution
// and dumped to standard output when done. Unlike in tests, benchmark logs
// are always printed, so as not to hide output whose existence may be
// affecting benchmark results.
type B struct {
	common
	importPath       string // import path of the package containing the benchmark
	context          *benchContext
	N                int
	previousN        int           // number of iterations in the previous run
	previousDuration time.Duration // total duration of the previous run
	benchFunc        func(b *B)
	benchTime        benchTimeFlag
	bytes            int64
	missingBytes     bool // one of the subbenchmarks does not have bytes set.
	timerOn          bool
	showAllocResult  bool
	result           BenchmarkResult
	parallelism      int // RunParallel creates parallelism*GOMAXPROCS goroutines
	// The initial states of memStats.Mallocs and memStats.TotalAlloc.
	startAllocs uint64
	startBytes  uint64
	// The net total of this test after being run.
	netAllocs uint64
	netBytes  uint64
	// Extra metrics collected by ReportMetric.
	extra map[string]float64
}

// StartTimer starts timing a test. This function is called automatically
// before a benchmark starts, but it can also be used to resume timing after
// a call to StopTimer.
func ( *B) () {
	if !.timerOn {
		runtime.ReadMemStats(&memStats)
		.startAllocs = memStats.Mallocs
		.startBytes = memStats.TotalAlloc
		.start = time.Now()
		.timerOn = true
	}
}

// StopTimer stops timing a test. This can be used to pause the timer
// while performing complex initialization that you don't
// want to measure.
func ( *B) () {
	if .timerOn {
		.duration += time.Since(.start)
		runtime.ReadMemStats(&memStats)
		.netAllocs += memStats.Mallocs - .startAllocs
		.netBytes += memStats.TotalAlloc - .startBytes
		.timerOn = false
	}
}

// ResetTimer zeroes the elapsed benchmark time and memory allocation counters
// and deletes user-reported metrics.
// It does not affect whether the timer is running.
func ( *B) () {
	if .extra == nil {
		// Allocate the extra map before reading memory stats.
		// Pre-size it to make more allocation unlikely.
		.extra = make(map[string]float64, 16)
	} else {
		for  := range .extra {
			delete(.extra, )
		}
	}
	if .timerOn {
		runtime.ReadMemStats(&memStats)
		.startAllocs = memStats.Mallocs
		.startBytes = memStats.TotalAlloc
		.start = time.Now()
	}
	.duration = 0
	.netAllocs = 0
	.netBytes = 0
}

// SetBytes records the number of bytes processed in a single operation.
// If this is called, the benchmark will report ns/op and MB/s.
func ( *B) ( int64) { .bytes =  }

// ReportAllocs enables malloc statistics for this benchmark.
// It is equivalent to setting -test.benchmem, but it only affects the
// benchmark function that calls ReportAllocs.
func ( *B) () {
	.showAllocResult = true
}

// runN runs a single benchmark for the specified number of iterations.
func ( *B) ( int) {
	benchmarkLock.Lock()
	defer benchmarkLock.Unlock()
	defer .runCleanup(normalPanic)
	// Try to get a comparable environment for each run
	// by clearing garbage from previous runs.
	runtime.GC()
	.raceErrors = -race.Errors()
	.N = 
	.parallelism = 1
	.ResetTimer()
	.StartTimer()
	.benchFunc()
	.StopTimer()
	.previousN = 
	.previousDuration = .duration
	.raceErrors += race.Errors()
	if .raceErrors > 0 {
		.Errorf("race detected during execution of benchmark")
	}
}

func min(,  int64) int64 {
	if  >  {
		return 
	}
	return 
}

func max(,  int64) int64 {
	if  <  {
		return 
	}
	return 
}

// run1 runs the first iteration of benchFunc. It reports whether more
// iterations of this benchmarks should be run.
func ( *B) () bool {
	if  := .context;  != nil {
		// Extend maxLen, if needed.
		if  := len(.name) + .extLen + 1;  > .maxLen {
			.maxLen =  + 8 // Add additional slack to avoid too many jumps in size.
		}
	}
	go func() {
		// Signal that we're done whether we return normally
		// or by FailNow's runtime.Goexit.
		defer func() {
			.signal <- true
		}()

		.runN(1)
	}()
	<-.signal
	if .failed {
		fmt.Fprintf(.w, "--- FAIL: %s\n%s", .name, .output)
		return false
	}
	// Only print the output if we know we are not going to proceed.
	// Otherwise it is printed in processBench.
	.mu.RLock()
	 := .finished
	.mu.RUnlock()
	if atomic.LoadInt32(&.hasSub) != 0 ||  {
		 := "BENCH"
		if .skipped {
			 = "SKIP"
		}
		if .chatty != nil && (len(.output) > 0 || ) {
			.trimOutput()
			fmt.Fprintf(.w, "--- %s: %s\n%s", , .name, .output)
		}
		return false
	}
	return true
}

var labelsOnce sync.Once

// run executes the benchmark in a separate goroutine, including all of its
// subbenchmarks. b must not have subbenchmarks.
func ( *B) () {
	labelsOnce.Do(func() {
		fmt.Fprintf(.w, "goos: %s\n", runtime.GOOS)
		fmt.Fprintf(.w, "goarch: %s\n", runtime.GOARCH)
		if .importPath != "" {
			fmt.Fprintf(.w, "pkg: %s\n", .importPath)
		}
		if  := sysinfo.CPU.Name();  != "" {
			fmt.Fprintf(.w, "cpu: %s\n", )
		}
	})
	if .context != nil {
		// Running go test --test.bench
		.context.processBench() // Must call doBench.
	} else {
		// Running func Benchmark.
		.doBench()
	}
}

func ( *B) () BenchmarkResult {
	go .launch()
	<-.signal
	return .result
}

// launch launches the benchmark function. It gradually increases the number
// of benchmark iterations until the benchmark runs for the requested benchtime.
// launch is run by the doBench function as a separate goroutine.
// run1 must have been called on b.
func ( *B) () {
	// Signal that we're done whether we return normally
	// or by FailNow's runtime.Goexit.
	defer func() {
		.signal <- true
	}()

	// Run the benchmark for at least the specified amount of time.
	if .benchTime.n > 0 {
		.runN(.benchTime.n)
	} else {
		 := .benchTime.d
		for  := int64(1); !.failed && .duration <  &&  < 1e9; {
			 := 
			// Predict required iterations.
			 := .Nanoseconds()
			 := int64(.N)
			 := .duration.Nanoseconds()
			if  <= 0 {
				// Round up, to avoid div by zero.
				 = 1
			}
			// Order of operations matters.
			// For very fast benchmarks, prevIters ~= prevns.
			// If you divide first, you get 0 or 1,
			// which can hide an order of magnitude in execution time.
			// So multiply first, then divide.
			 =  *  / 
			// Run more iterations than we think we'll need (1.2x).
			 +=  / 5
			// Don't grow too fast in case we had timing errors previously.
			 = min(, 100*)
			// Be sure to run at least one more than last time.
			 = max(, +1)
			// Don't run more than 1e9 times. (This also keeps n in int range on 32 bit platforms.)
			 = min(, 1e9)
			.runN(int())
		}
	}
	.result = BenchmarkResult{.N, .duration, .bytes, .netAllocs, .netBytes, .extra}
}

// ReportMetric adds "n unit" to the reported benchmark results.
// If the metric is per-iteration, the caller should divide by b.N,
// and by convention units should end in "/op".
// ReportMetric overrides any previously reported value for the same unit.
// ReportMetric panics if unit is the empty string or if unit contains
// any whitespace.
// If unit is a unit normally reported by the benchmark framework itself
// (such as "allocs/op"), ReportMetric will override that metric.
// Setting "ns/op" to 0 will suppress that built-in metric.
func ( *B) ( float64,  string) {
	if  == "" {
		panic("metric unit must not be empty")
	}
	if strings.IndexFunc(, unicode.IsSpace) >= 0 {
		panic("metric unit must not contain whitespace")
	}
	.extra[] = 
}

// BenchmarkResult contains the results of a benchmark run.
type BenchmarkResult struct {
	N         int           // The number of iterations.
	T         time.Duration // The total time taken.
	Bytes     int64         // Bytes processed in one iteration.
	MemAllocs uint64        // The total number of memory allocations.
	MemBytes  uint64        // The total number of bytes allocated.

	// Extra records additional metrics reported by ReportMetric.
	Extra map[string]float64
}

// NsPerOp returns the "ns/op" metric.
func ( BenchmarkResult) () int64 {
	if ,  := .Extra["ns/op"];  {
		return int64()
	}
	if .N <= 0 {
		return 0
	}
	return .T.Nanoseconds() / int64(.N)
}

// mbPerSec returns the "MB/s" metric.
func ( BenchmarkResult) () float64 {
	if ,  := .Extra["MB/s"];  {
		return 
	}
	if .Bytes <= 0 || .T <= 0 || .N <= 0 {
		return 0
	}
	return (float64(.Bytes) * float64(.N) / 1e6) / .T.Seconds()
}

// AllocsPerOp returns the "allocs/op" metric,
// which is calculated as r.MemAllocs / r.N.
func ( BenchmarkResult) () int64 {
	if ,  := .Extra["allocs/op"];  {
		return int64()
	}
	if .N <= 0 {
		return 0
	}
	return int64(.MemAllocs) / int64(.N)
}

// AllocedBytesPerOp returns the "B/op" metric,
// which is calculated as r.MemBytes / r.N.
func ( BenchmarkResult) () int64 {
	if ,  := .Extra["B/op"];  {
		return int64()
	}
	if .N <= 0 {
		return 0
	}
	return int64(.MemBytes) / int64(.N)
}

// String returns a summary of the benchmark results.
// It follows the benchmark result line format from
// https://golang.org/design/14313-benchmark-format, not including the
// benchmark name.
// Extra metrics override built-in metrics of the same name.
// String does not include allocs/op or B/op, since those are reported
// by MemString.
func ( BenchmarkResult) () string {
	 := new(strings.Builder)
	fmt.Fprintf(, "%8d", .N)

	// Get ns/op as a float.
	,  := .Extra["ns/op"]
	if ! {
		 = float64(.T.Nanoseconds()) / float64(.N)
	}
	if  != 0 {
		.WriteByte('\t')
		prettyPrint(, , "ns/op")
	}

	if  := .mbPerSec();  != 0 {
		fmt.Fprintf(, "\t%7.2f MB/s", )
	}

	// Print extra metrics that aren't represented in the standard
	// metrics.
	var  []string
	for  := range .Extra {
		switch  {
		case "ns/op", "MB/s", "B/op", "allocs/op":
			// Built-in metrics reported elsewhere.
			continue
		}
		 = append(, )
	}
	sort.Strings()
	for ,  := range  {
		.WriteByte('\t')
		prettyPrint(, .Extra[], )
	}
	return .String()
}

func prettyPrint( io.Writer,  float64,  string) {
	// Print all numbers with 10 places before the decimal point
	// and small numbers with four sig figs. Field widths are
	// chosen to fit the whole part in 10 places while aligning
	// the decimal point of all fractional formats.
	var  string
	switch  := math.Abs(); {
	case  == 0 ||  >= 999.95:
		 = "%10.0f %s"
	case  >= 99.995:
		 = "%12.1f %s"
	case  >= 9.9995:
		 = "%13.2f %s"
	case  >= 0.99995:
		 = "%14.3f %s"
	case  >= 0.099995:
		 = "%15.4f %s"
	case  >= 0.0099995:
		 = "%16.5f %s"
	case  >= 0.00099995:
		 = "%17.6f %s"
	default:
		 = "%18.7f %s"
	}
	fmt.Fprintf(, , , )
}

// MemString returns r.AllocedBytesPerOp and r.AllocsPerOp in the same format as 'go test'.
func ( BenchmarkResult) () string {
	return fmt.Sprintf("%8d B/op\t%8d allocs/op",
		.AllocedBytesPerOp(), .AllocsPerOp())
}

// benchmarkName returns full name of benchmark including procs suffix.
func benchmarkName( string,  int) string {
	if  != 1 {
		return fmt.Sprintf("%s-%d", , )
	}
	return 
}

type benchContext struct {
	match *matcher

	maxLen int // The largest recorded benchmark name.
	extLen int // Maximum extension length.
}

// RunBenchmarks is an internal function but exported because it is cross-package;
// it is part of the implementation of the "go test" command.
func ( func(,  string) (bool, error),  []InternalBenchmark) {
	runBenchmarks("", , )
}

func runBenchmarks( string,  func(,  string) (bool, error),  []InternalBenchmark) bool {
	// If no flag was specified, don't run benchmarks.
	if len(*matchBenchmarks) == 0 {
		return true
	}
	// Collect matching benchmarks and determine longest name.
	 := 1
	for ,  := range cpuList {
		if  >  {
			 = 
		}
	}
	 := &benchContext{
		match:  newMatcher(, *matchBenchmarks, "-test.bench"),
		extLen: len(benchmarkName("", )),
	}
	var  []InternalBenchmark
	for ,  := range  {
		if , ,  := .match.fullName(nil, .Name);  {
			 = append(, )
			 := benchmarkName(.Name, )
			if  := len() + .extLen + 1;  > .maxLen {
				.maxLen = 
			}
		}
	}
	 := &B{
		common: common{
			name:  "Main",
			w:     os.Stdout,
			bench: true,
		},
		importPath: ,
		benchFunc: func( *B) {
			for ,  := range  {
				.Run(.Name, .F)
			}
		},
		benchTime: benchTime,
		context:   ,
	}
	if Verbose() {
		.chatty = newChattyPrinter(.w)
	}
	.runN(1)
	return !.failed
}

// processBench runs bench b for the configured CPU counts and prints the results.
func ( *benchContext) ( *B) {
	for ,  := range cpuList {
		for  := uint(0);  < *count; ++ {
			runtime.GOMAXPROCS()
			 := benchmarkName(.name, )

			// If it's chatty, we've already printed this information.
			if .chatty == nil {
				fmt.Fprintf(.w, "%-*s\t", .maxLen, )
			}
			// Recompute the running time for all but the first iteration.
			if  > 0 ||  > 0 {
				 = &B{
					common: common{
						signal: make(chan bool),
						name:   .name,
						w:      .w,
						chatty: .chatty,
						bench:  true,
					},
					benchFunc: .benchFunc,
					benchTime: .benchTime,
				}
				.run1()
			}
			 := .doBench()
			if .failed {
				// The output could be very long here, but probably isn't.
				// We print it all, regardless, because we don't want to trim the reason
				// the benchmark failed.
				fmt.Fprintf(.w, "--- FAIL: %s\n%s", , .output)
				continue
			}
			 := .String()
			if .chatty != nil {
				fmt.Fprintf(.w, "%-*s\t", .maxLen, )
			}
			if *benchmarkMemory || .showAllocResult {
				 += "\t" + .MemString()
			}
			fmt.Fprintln(.w, )
			// Unlike with tests, we ignore the -chatty flag and always print output for
			// benchmarks since the output generation time will skew the results.
			if len(.output) > 0 {
				.trimOutput()
				fmt.Fprintf(.w, "--- BENCH: %s\n%s", , .output)
			}
			if  := runtime.GOMAXPROCS(-1);  !=  {
				fmt.Fprintf(os.Stderr, "testing: %s left GOMAXPROCS set to %d\n", , )
			}
		}
	}
}

// Run benchmarks f as a subbenchmark with the given name. It reports
// whether there were any failures.
//
// A subbenchmark is like any other benchmark. A benchmark that calls Run at
// least once will not be measured itself and will be called once with N=1.
func ( *B) ( string,  func( *B)) bool {
	// Since b has subbenchmarks, we will no longer run it as a benchmark itself.
	// Release the lock and acquire it on exit to ensure locks stay paired.
	atomic.StoreInt32(&.hasSub, 1)
	benchmarkLock.Unlock()
	defer benchmarkLock.Lock()

	, ,  := .name, true, false
	if .context != nil {
		, ,  = .context.match.fullName(&.common, )
	}
	if ! {
		return true
	}
	var  [maxStackLen]uintptr
	 := runtime.Callers(2, [:])
	 := &B{
		common: common{
			signal:  make(chan bool),
			name:    ,
			parent:  &.common,
			level:   .level + 1,
			creator: [:],
			w:       .w,
			chatty:  .chatty,
			bench:   true,
		},
		importPath: .importPath,
		benchFunc:  ,
		benchTime:  .benchTime,
		context:    .context,
	}
	if  {
		// Partial name match, like -bench=X/Y matching BenchmarkX.
		// Only process sub-benchmarks, if any.
		atomic.StoreInt32(&.hasSub, 1)
	}

	if .chatty != nil {
		labelsOnce.Do(func() {
			fmt.Printf("goos: %s\n", runtime.GOOS)
			fmt.Printf("goarch: %s\n", runtime.GOARCH)
			if .importPath != "" {
				fmt.Printf("pkg: %s\n", .importPath)
			}
			if  := sysinfo.CPU.Name();  != "" {
				fmt.Printf("cpu: %s\n", )
			}
		})

		fmt.Println()
	}

	if .run1() {
		.run()
	}
	.add(.result)
	return !.failed
}

// add simulates running benchmarks in sequence in a single iteration. It is
// used to give some meaningful results in case func Benchmark is used in
// combination with Run.
func ( *B) ( BenchmarkResult) {
	 := &.result
	// The aggregated BenchmarkResults resemble running all subbenchmarks as
	// in sequence in a single benchmark.
	.N = 1
	.T += time.Duration(.NsPerOp())
	if .Bytes == 0 {
		// Summing Bytes is meaningless in aggregate if not all subbenchmarks
		// set it.
		.missingBytes = true
		.Bytes = 0
	}
	if !.missingBytes {
		.Bytes += .Bytes
	}
	.MemAllocs += uint64(.AllocsPerOp())
	.MemBytes += uint64(.AllocedBytesPerOp())
}

// trimOutput shortens the output from a benchmark, which can be very long.
func ( *B) () {
	// The output is likely to appear multiple times because the benchmark
	// is run multiple times, but at least it will be seen. This is not a big deal
	// because benchmarks rarely print, but just in case, we trim it if it's too long.
	const  = 10
	for ,  := 0, 0;  < len(.output); ++ {
		if .output[] == '\n' {
			++
			if  >=  {
				.output = append(.output[:], "\n\t... [output truncated]\n"...)
				break
			}
		}
	}
}

// A PB is used by RunParallel for running parallel benchmarks.
type PB struct {
	globalN *uint64 // shared between all worker goroutines iteration counter
	grain   uint64  // acquire that many iterations from globalN at once
	cache   uint64  // local cache of acquired iterations
	bN      uint64  // total number of iterations to execute (b.N)
}

// Next reports whether there are more iterations to execute.
func ( *PB) () bool {
	if .cache == 0 {
		 := atomic.AddUint64(.globalN, .grain)
		if  <= .bN {
			.cache = .grain
		} else if  < .bN+.grain {
			.cache = .bN + .grain - 
		} else {
			return false
		}
	}
	.cache--
	return true
}

// RunParallel runs a benchmark in parallel.
// It creates multiple goroutines and distributes b.N iterations among them.
// The number of goroutines defaults to GOMAXPROCS. To increase parallelism for
// non-CPU-bound benchmarks, call SetParallelism before RunParallel.
// RunParallel is usually used with the go test -cpu flag.
//
// The body function will be run in each goroutine. It should set up any
// goroutine-local state and then iterate until pb.Next returns false.
// It should not use the StartTimer, StopTimer, or ResetTimer functions,
// because they have global effect. It should also not call Run.
func ( *B) ( func(*PB)) {
	if .N == 0 {
		return // Nothing to do when probing.
	}
	// Calculate grain size as number of iterations that take ~100µs.
	// 100µs is enough to amortize the overhead and provide sufficient
	// dynamic load balancing.
	 := uint64(0)
	if .previousN > 0 && .previousDuration > 0 {
		 = 1e5 * uint64(.previousN) / uint64(.previousDuration)
	}
	if  < 1 {
		 = 1
	}
	// We expect the inner loop and function call to take at least 10ns,
	// so do not do more than 100µs/10ns=1e4 iterations.
	if  > 1e4 {
		 = 1e4
	}

	 := uint64(0)
	 := .parallelism * runtime.GOMAXPROCS(0)
	var  sync.WaitGroup
	.Add()
	for  := 0;  < ; ++ {
		go func() {
			defer .Done()
			 := &PB{
				globalN: &,
				grain:   ,
				bN:      uint64(.N),
			}
			()
		}()
	}
	.Wait()
	if  <= uint64(.N) && !.Failed() {
		.Fatal("RunParallel: body exited without pb.Next() == false")
	}
}

// SetParallelism sets the number of goroutines used by RunParallel to p*GOMAXPROCS.
// There is usually no need to call SetParallelism for CPU-bound benchmarks.
// If p is less than 1, this call will have no effect.
func ( *B) ( int) {
	if  >= 1 {
		.parallelism = 
	}
}

// Benchmark benchmarks a single function. It is useful for creating
// custom benchmarks that do not use the "go test" command.
//
// If f depends on testing flags, then Init must be used to register
// those flags before calling Benchmark and before calling flag.Parse.
//
// If f calls Run, the result will be an estimate of running all its
// subbenchmarks that don't call Run in sequence in a single benchmark.
func ( func( *B)) BenchmarkResult {
	 := &B{
		common: common{
			signal: make(chan bool),
			w:      discard{},
		},
		benchFunc: ,
		benchTime: benchTime,
	}
	if .run1() {
		.run()
	}
	return .result
}

type discard struct{}

func (discard) ( []byte) ( int,  error) { return len(), nil }