OLD | NEW |
(Empty) | |
| 1 // Copyright 2009 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 file computes the Karatsuba threshold as a "test". |
| 6 // Usage: gotest -calibrate |
| 7 |
| 8 package big |
| 9 |
| 10 import ( |
| 11 "flag" |
| 12 "fmt" |
| 13 "testing" |
| 14 "time" |
| 15 "unsafe" // for Sizeof |
| 16 ) |
| 17 |
| 18 |
| 19 var calibrate = flag.Bool("calibrate", false, "run calibration test") |
| 20 |
| 21 |
| 22 // makeNumber creates an n-word number 0xffff...ffff |
| 23 func makeNumber(n int) *Int { |
| 24 var w Word |
| 25 b := make([]byte, n*unsafe.Sizeof(w)) |
| 26 for i := range b { |
| 27 b[i] = 0xff |
| 28 } |
| 29 var x Int |
| 30 x.SetBytes(b) |
| 31 return &x |
| 32 } |
| 33 |
| 34 |
| 35 // measure returns the time to compute x*x in nanoseconds |
| 36 func measure(f func()) int64 { |
| 37 const N = 100 |
| 38 start := time.Nanoseconds() |
| 39 for i := N; i > 0; i-- { |
| 40 f() |
| 41 } |
| 42 stop := time.Nanoseconds() |
| 43 return (stop - start) / N |
| 44 } |
| 45 |
| 46 |
| 47 func computeThreshold(t *testing.T) int { |
| 48 // use a mix of numbers as work load |
| 49 x := make([]*Int, 20) |
| 50 for i := range x { |
| 51 x[i] = makeNumber(10 * (i + 1)) |
| 52 } |
| 53 |
| 54 threshold := -1 |
| 55 for n := 8; threshold < 0 || n <= threshold+20; n += 2 { |
| 56 // set work load |
| 57 f := func() { |
| 58 var t Int |
| 59 for _, x := range x { |
| 60 t.Mul(x, x) |
| 61 } |
| 62 } |
| 63 |
| 64 karatsubaThreshold = 1e9 // disable karatsuba |
| 65 t1 := measure(f) |
| 66 |
| 67 karatsubaThreshold = n // enable karatsuba |
| 68 t2 := measure(f) |
| 69 |
| 70 c := '<' |
| 71 mark := "" |
| 72 if t1 > t2 { |
| 73 c = '>' |
| 74 if threshold < 0 { |
| 75 threshold = n |
| 76 mark = " *" |
| 77 } |
| 78 } |
| 79 |
| 80 fmt.Printf("%4d: %8d %c %8d%s\n", n, t1, c, t2, mark) |
| 81 } |
| 82 return threshold |
| 83 } |
| 84 |
| 85 |
| 86 func TestCalibrate(t *testing.T) { |
| 87 if *calibrate { |
| 88 fmt.Printf("Computing Karatsuba threshold\n") |
| 89 fmt.Printf("threshold = %d\n", computeThreshold(t)) |
| 90 } |
| 91 } |
OLD | NEW |