Gecko [ 167.86.127.34 ]

Name	Size	Permission
accuracy_string.go	414 B	-rw-r--r--
arith.go	5.68 KB	-rw-r--r--
arith_386.s	4.67 KB	-rw-r--r--
arith_amd64.go	277 B	-rw-r--r--
arith_amd64.s	9.71 KB	-rw-r--r--
arith_arm.s	4.47 KB	-rw-r--r--
arith_arm64.s	9.94 KB	-rw-r--r--
arith_decl.go	707 B	-rw-r--r--
arith_decl_pure.go	1.24 KB	-rw-r--r--
arith_decl_s390x.go	791 B	-rw-r--r--
arith_mips64x.s	917 B	-rw-r--r--
arith_mipsx.s	913 B	-rw-r--r--
arith_ppc64x.s	12.62 KB	-rw-r--r--
arith_s390x.s	29.12 KB	-rw-r--r--
arith_s390x_test.go	1014 B	-rw-r--r--
arith_test.go	12.29 KB	-rw-r--r--
arith_wasm.s	757 B	-rw-r--r--
bits_test.go	5.07 KB	-rw-r--r--
calibrate_test.go	4.63 KB	-rw-r--r--
decimal.go	6.52 KB	-rw-r--r--
decimal_test.go	3.33 KB	-rw-r--r--
doc.go	3.79 KB	-rw-r--r--
example_rat_test.go	1.68 KB	-rw-r--r--
example_test.go	3.94 KB	-rw-r--r--
float.go	44.14 KB	-rw-r--r--
float_test.go	51.94 KB	-rw-r--r--
floatconv.go	8.36 KB	-rw-r--r--
floatconv_test.go	24.28 KB	-rw-r--r--
floatexample_test.go	3.63 KB	-rw-r--r--
floatmarsh.go	3.34 KB	-rw-r--r--
floatmarsh_test.go	3.64 KB	-rw-r--r--
ftoa.go	13.55 KB	-rw-r--r--
gcd_test.go	2.16 KB	-rw-r--r--
hilbert_test.go	2.88 KB	-rw-r--r--
int.go	29.56 KB	-rw-r--r--
int_test.go	51.93 KB	-rw-r--r--
intconv.go	6.68 KB	-rw-r--r--
intconv_test.go	10.01 KB	-rw-r--r--
intmarsh.go	2.09 KB	-rw-r--r--
intmarsh_test.go	2.8 KB	-rw-r--r--
nat.go	33.76 KB	-rw-r--r--
nat_test.go	18.87 KB	-rw-r--r--
natconv.go	14.57 KB	-rw-r--r--
natconv_test.go	16.85 KB	-rw-r--r--
prime.go	10.34 KB	-rw-r--r--
prime_test.go	7.1 KB	-rw-r--r--
rat.go	13.49 KB	-rw-r--r--
rat_test.go	18.54 KB	-rw-r--r--
ratconv.go	9.49 KB	-rw-r--r--
ratconv_test.go	14.96 KB	-rw-r--r--
ratmarsh.go	1.95 KB	-rw-r--r--
ratmarsh_test.go	3.04 KB	-rw-r--r--
roundingmode_string.go	501 B	-rw-r--r--
sqrt.go	3.59 KB	-rw-r--r--
sqrt_test.go	4.81 KB	-rw-r--r--

Code Editor : calibrate_test.go

// 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.

// Calibration used to determine thresholds for using
// different algorithms.  Ideally, this would be converted
// to go generate to create thresholds.go

// This file prints execution times for the Mul benchmark
// given different Karatsuba thresholds. The result may be
// used to manually fine-tune the threshold constant. The
// results are somewhat fragile; use repeated runs to get
// a clear picture.

// Calculates lower and upper thresholds for when basicSqr
// is faster than standard multiplication.

// Usage: go test -run=TestCalibrate -v -calibrate

package big

import (
	"flag"
	"fmt"
	"testing"
	"time"
)

var calibrate = flag.Bool("calibrate", false, "run calibration test")

const (
	sqrModeMul       = "mul(x, x)"
	sqrModeBasic     = "basicSqr(x)"
	sqrModeKaratsuba = "karatsubaSqr(x)"
)

func TestCalibrate(t *testing.T) {
	if !*calibrate {
		return
	}

computeKaratsubaThresholds()

// compute basicSqrThreshold where overhead becomes negligible
	minSqr := computeSqrThreshold(10, 30, 1, 3, sqrModeMul, sqrModeBasic)
	// compute karatsubaSqrThreshold where karatsuba is faster
	maxSqr := computeSqrThreshold(200, 500, 10, 3, sqrModeBasic, sqrModeKaratsuba)
	if minSqr != 0 {
		fmt.Printf("found basicSqrThreshold = %d\n", minSqr)
	} else {
		fmt.Println("no basicSqrThreshold found")
	}
	if maxSqr != 0 {
		fmt.Printf("found karatsubaSqrThreshold = %d\n", maxSqr)
	} else {
		fmt.Println("no karatsubaSqrThreshold found")
	}
}

func karatsubaLoad(b *testing.B) {
	BenchmarkMul(b)
}

// measureKaratsuba returns the time to run a Karatsuba-relevant benchmark
// given Karatsuba threshold th.
func measureKaratsuba(th int) time.Duration {
	th, karatsubaThreshold = karatsubaThreshold, th
	res := testing.Benchmark(karatsubaLoad)
	karatsubaThreshold = th
	return time.Duration(res.NsPerOp())
}

func computeKaratsubaThresholds() {
	fmt.Printf("Multiplication times for varying Karatsuba thresholds\n")
	fmt.Printf("(run repeatedly for good results)\n")

// determine Tk, the work load execution time using basic multiplication
	Tb := measureKaratsuba(1e9) // th == 1e9 => Karatsuba multiplication disabled
	fmt.Printf("Tb = %10s\n", Tb)

// thresholds
	th := 4
	th1 := -1
	th2 := -1

var deltaOld time.Duration
	for count := -1; count != 0 && th < 128; count-- {
		// determine Tk, the work load execution time using Karatsuba multiplication
		Tk := measureKaratsuba(th)

// improvement over Tb
		delta := (Tb - Tk) * 100 / Tb

fmt.Printf("th = %3d  Tk = %10s  %4d%%", th, Tk, delta)

// determine break-even point
		if Tk < Tb && th1 < 0 {
			th1 = th
			fmt.Print("  break-even point")
		}

// determine diminishing return
		if 0 < delta && delta < deltaOld && th2 < 0 {
			th2 = th
			fmt.Print("  diminishing return")
		}
		deltaOld = delta

fmt.Println()

// trigger counter
		if th1 >= 0 && th2 >= 0 && count < 0 {
			count = 10 // this many extra measurements after we got both thresholds
		}

th++
	}
}

func measureSqr(words, nruns int, mode string) time.Duration {
	// more runs for better statistics
	initBasicSqr, initKaratsubaSqr := basicSqrThreshold, karatsubaSqrThreshold

switch mode {
	case sqrModeMul:
		basicSqrThreshold = words + 1
	case sqrModeBasic:
		basicSqrThreshold, karatsubaSqrThreshold = words-1, words+1
	case sqrModeKaratsuba:
		karatsubaSqrThreshold = words - 1
	}

var testval int64
	for i := 0; i < nruns; i++ {
		res := testing.Benchmark(func(b *testing.B) { benchmarkNatSqr(b, words) })
		testval += res.NsPerOp()
	}
	testval /= int64(nruns)

basicSqrThreshold, karatsubaSqrThreshold = initBasicSqr, initKaratsubaSqr

return time.Duration(testval)
}

func computeSqrThreshold(from, to, step, nruns int, lower, upper string) int {
	fmt.Printf("Calibrating threshold between %s and %s\n", lower, upper)
	fmt.Printf("Looking for a timing difference for x between %d - %d words by %d step\n", from, to, step)
	var initPos bool
	var threshold int
	for i := from; i <= to; i += step {
		baseline := measureSqr(i, nruns, lower)
		testval := measureSqr(i, nruns, upper)
		pos := baseline > testval
		delta := baseline - testval
		percent := delta * 100 / baseline
		fmt.Printf("words = %3d deltaT = %10s (%4d%%) is %s better: %v", i, delta, percent, upper, pos)
		if i == from {
			initPos = pos
		}
		if threshold == 0 && pos != initPos {
			threshold = i
			fmt.Printf("  threshold  found")
		}
		fmt.Println()

}
	if threshold != 0 {
		fmt.Printf("Found threshold = %d between %d - %d\n", threshold, from, to)
	} else {
		fmt.Printf("Found NO threshold between %d - %d\n", from, to)
	}
	return threshold
}

${this.title}

Code Editor : calibrate_test.go