Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 1 | #! /usr/bin/python3 -B |
| 2 | # |
Gavin Howard | 29e00ba | 2020-06-30 09:25:21 -0600 | [diff] [blame] | 3 | # SPDX-License-Identifier: BSD-2-Clause |
| 4 | # |
Gavin Howard | 4feb708 | 2021-01-26 01:19:25 -0700 | [diff] [blame] | 5 | # Copyright (c) 2018-2021 Gavin D. Howard and contributors. |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 6 | # |
Gavin Howard | 7345cb9 | 2019-04-08 14:13:43 -0600 | [diff] [blame] | 7 | # Redistribution and use in source and binary forms, with or without |
| 8 | # modification, are permitted provided that the following conditions are met: |
| 9 | # |
| 10 | # * Redistributions of source code must retain the above copyright notice, this |
| 11 | # list of conditions and the following disclaimer. |
| 12 | # |
| 13 | # * Redistributions in binary form must reproduce the above copyright notice, |
| 14 | # this list of conditions and the following disclaimer in the documentation |
| 15 | # and/or other materials provided with the distribution. |
| 16 | # |
| 17 | # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| 18 | # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 19 | # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 20 | # ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
| 21 | # LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| 22 | # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| 23 | # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| 24 | # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| 25 | # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 26 | # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 27 | # POSSIBILITY OF SUCH DAMAGE. |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 28 | # |
| 29 | |
| 30 | import os |
| 31 | import sys |
| 32 | import subprocess |
| 33 | import time |
| 34 | |
| 35 | def usage(): |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 36 | print("usage: {} [num_iterations test_num exe]".format(script)) |
| 37 | print("\n num_iterations is the number of times to run each karatsuba number; default is 4") |
Gavin Howard | dcaf230 | 2018-10-17 16:30:38 -0600 | [diff] [blame] | 38 | print("\n test_num is the last Karatsuba number to run through tests") |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 39 | sys.exit(1) |
| 40 | |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 41 | def run(cmd, env=None): |
| 42 | return subprocess.run(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env) |
| 43 | |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 44 | script = sys.argv[0] |
| 45 | testdir = os.path.dirname(script) |
| 46 | |
Gavin Howard | 63ce8b0 | 2020-07-03 16:12:24 -0600 | [diff] [blame] | 47 | if testdir == "": |
| 48 | testdir = os.getcwd() |
| 49 | |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 50 | print("\nWARNING: This script is for distro and package maintainers.") |
| 51 | print("It is for finding the optimal Karatsuba number.") |
Gavin Howard | 8c9288d | 2019-05-10 12:31:42 -0600 | [diff] [blame] | 52 | print("Though it only needs to be run once per release/platform,") |
| 53 | print("it takes forever to run.") |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 54 | print("You have been warned.\n") |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 55 | print("Note: If you send an interrupt, it will report the current best number.\n") |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 56 | |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 57 | if __name__ != "__main__": |
| 58 | usage() |
| 59 | |
Gavin Howard | 977767f | 2019-04-24 10:46:23 -0600 | [diff] [blame] | 60 | mx = 520 |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 61 | mx2 = mx // 2 |
Gavin Howard | 8c9288d | 2019-05-10 12:31:42 -0600 | [diff] [blame] | 62 | mn = 16 |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 63 | |
| 64 | num = "9" * mx |
| 65 | |
Gavin Howard | ba0605b | 2020-05-14 13:40:28 -0600 | [diff] [blame] | 66 | args_idx = 4 |
| 67 | |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 68 | if len(sys.argv) >= 2: |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 69 | num_iterations = int(sys.argv[1]) |
| 70 | else: |
| 71 | num_iterations = 4 |
| 72 | |
| 73 | if len(sys.argv) >= 3: |
| 74 | test_num = int(sys.argv[2]) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 75 | else: |
| 76 | test_num = 0 |
| 77 | |
Gavin Howard | ba0605b | 2020-05-14 13:40:28 -0600 | [diff] [blame] | 78 | if len(sys.argv) >= args_idx: |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 79 | exe = sys.argv[3] |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 80 | else: |
| 81 | exe = testdir + "/bin/bc" |
| 82 | |
| 83 | exedir = os.path.dirname(exe) |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 84 | |
Gavin Howard | 8c9288d | 2019-05-10 12:31:42 -0600 | [diff] [blame] | 85 | indata = "for (i = 0; i < 100; ++i) {} * {}\n" |
| 86 | indata += "1.23456789^100000\n1.23456789^100000\nhalt" |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 87 | indata = indata.format(num, num).encode() |
Gavin Howard | 36d3534 | 2018-10-15 20:25:31 -0600 | [diff] [blame] | 88 | |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 89 | times = [] |
| 90 | nums = [] |
| 91 | runs = [] |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 92 | nruns = num_iterations + 1 |
Gavin Howard | 977767f | 2019-04-24 10:46:23 -0600 | [diff] [blame] | 93 | |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 94 | for i in range(0, nruns): |
| 95 | runs.append(0) |
| 96 | |
| 97 | tests = [ "multiply", "modulus", "power", "sqrt" ] |
Gavin Howard | bc332b8 | 2019-05-15 11:19:58 -0600 | [diff] [blame] | 98 | scripts = [ "multiply" ] |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 99 | |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 100 | print("Testing CFLAGS=\"-flto\"...") |
| 101 | |
| 102 | flags = dict(os.environ) |
| 103 | try: |
| 104 | flags["CFLAGS"] = flags["CFLAGS"] + " " + "-flto" |
| 105 | except KeyError: |
| 106 | flags["CFLAGS"] = "-flto" |
| 107 | |
| 108 | p = run([ "./configure.sh", "-O3" ], flags) |
| 109 | if p.returncode != 0: |
| 110 | print("configure.sh returned an error ({}); exiting...".format(p.returncode)) |
| 111 | sys.exit(p.returncode) |
| 112 | |
| 113 | p = run([ "make" ]) |
| 114 | |
| 115 | if p.returncode == 0: |
| 116 | config_env = flags |
| 117 | print("Using CFLAGS=\"-flto\"") |
| 118 | else: |
| 119 | config_env = os.environ |
| 120 | print("Not using CFLAGS=\"-flto\"") |
| 121 | |
| 122 | p = run([ "make", "clean" ]) |
| 123 | |
Gavin Howard | 160490c | 2021-03-31 21:46:11 -0600 | [diff] [blame] | 124 | print("Testing \"make -j16\"") |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 125 | |
| 126 | if p.returncode != 0: |
| 127 | print("make returned an error ({}); exiting...".format(p.returncode)) |
| 128 | sys.exit(p.returncode) |
| 129 | |
Gavin Howard | 160490c | 2021-03-31 21:46:11 -0600 | [diff] [blame] | 130 | p = run([ "make", "-j16" ]) |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 131 | |
| 132 | if p.returncode == 0: |
Gavin Howard | 160490c | 2021-03-31 21:46:11 -0600 | [diff] [blame] | 133 | makecmd = [ "make", "-j16" ] |
| 134 | print("Using \"make -j16\"") |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 135 | else: |
| 136 | makecmd = [ "make" ] |
Gavin Howard | 160490c | 2021-03-31 21:46:11 -0600 | [diff] [blame] | 137 | print("Not using \"make -j16\"") |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 138 | |
Gavin Howard | 030ef05 | 2019-05-10 10:59:24 -0600 | [diff] [blame] | 139 | if test_num != 0: |
| 140 | mx2 = test_num |
| 141 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 142 | try: |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 143 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 144 | for i in range(mn, mx2 + 1): |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 145 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 146 | print("\nCompiling...\n") |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 147 | |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 148 | p = run([ "./configure.sh", "-O3", "-k{}".format(i) ], config_env) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 149 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 150 | if p.returncode != 0: |
| 151 | print("configure.sh returned an error ({}); exiting...".format(p.returncode)) |
| 152 | sys.exit(p.returncode) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 153 | |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 154 | p = run(makecmd) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 155 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 156 | if p.returncode != 0: |
| 157 | print("make returned an error ({}); exiting...".format(p.returncode)) |
| 158 | sys.exit(p.returncode) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 159 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 160 | if (test_num >= i): |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 161 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 162 | print("Running tests for Karatsuba Num: {}\n".format(i)) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 163 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 164 | for test in tests: |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 165 | |
Gavin Howard | f2c997b | 2020-05-14 08:02:44 -0600 | [diff] [blame] | 166 | cmd = [ "{}/tests/test.sh".format(testdir), "bc", test, "0", "0", exe ] |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 167 | |
Gavin Howard | ba0605b | 2020-05-14 13:40:28 -0600 | [diff] [blame] | 168 | p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 169 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 170 | if p.returncode != 0: |
| 171 | print("{} test failed:\n".format(test, p.returncode)) |
| 172 | print(p.stderr.decode()) |
| 173 | print("\nexiting...") |
| 174 | sys.exit(p.returncode) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 175 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 176 | print("") |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 177 | |
Gavin Howard | bc332b8 | 2019-05-15 11:19:58 -0600 | [diff] [blame] | 178 | for script in scripts: |
| 179 | |
| 180 | cmd = [ "{}/tests/script.sh".format(testdir), "bc", script + ".bc", |
Gavin Howard | ba0605b | 2020-05-14 13:40:28 -0600 | [diff] [blame] | 181 | "0", "1", "1", "0", exe ] |
Gavin Howard | bc332b8 | 2019-05-15 11:19:58 -0600 | [diff] [blame] | 182 | |
Gavin Howard | ba0605b | 2020-05-14 13:40:28 -0600 | [diff] [blame] | 183 | p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE) |
Gavin Howard | bc332b8 | 2019-05-15 11:19:58 -0600 | [diff] [blame] | 184 | |
| 185 | if p.returncode != 0: |
| 186 | print("{} test failed:\n".format(test, p.returncode)) |
| 187 | print(p.stderr.decode()) |
| 188 | print("\nexiting...") |
| 189 | sys.exit(p.returncode) |
| 190 | |
| 191 | print("") |
| 192 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 193 | elif test_num == 0: |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 194 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 195 | print("Timing Karatsuba Num: {}".format(i), end='', flush=True) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 196 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 197 | for j in range(0, nruns): |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 198 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 199 | cmd = [ exe, "{}/tests/bc/power.txt".format(testdir) ] |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 200 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 201 | start = time.perf_counter() |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 202 | p = subprocess.run(cmd, input=indata, stdout=subprocess.PIPE, stderr=subprocess.PIPE) |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 203 | end = time.perf_counter() |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 204 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 205 | if p.returncode != 0: |
| 206 | print("bc returned an error; exiting...") |
| 207 | sys.exit(p.returncode) |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 208 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 209 | runs[j] = end - start |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 210 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 211 | run_times = runs[1:] |
| 212 | avg = sum(run_times) / len(run_times) |
| 213 | |
| 214 | times.append(avg) |
| 215 | nums.append(i) |
| 216 | print(", Time: {}".format(times[i - mn])) |
| 217 | |
| 218 | except KeyboardInterrupt: |
| 219 | nums = nums[0:i] |
| 220 | times = times[0:i] |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 221 | |
Gavin Howard | 030ef05 | 2019-05-10 10:59:24 -0600 | [diff] [blame] | 222 | if test_num == 0: |
Gavin Howard | ab6ba68 | 2019-05-10 08:42:15 -0600 | [diff] [blame] | 223 | |
Gavin Howard | 030ef05 | 2019-05-10 10:59:24 -0600 | [diff] [blame] | 224 | opt = nums[times.index(min(times))] |
| 225 | |
Gavin Howard | 2a65988 | 2019-05-10 12:47:33 -0600 | [diff] [blame] | 226 | print("\n\nOptimal Karatsuba Num (for this machine): {}".format(opt)) |
Gavin Howard | 030ef05 | 2019-05-10 10:59:24 -0600 | [diff] [blame] | 227 | print("Run the following:\n") |
Gavin Howard | 3efeb91 | 2020-05-14 12:38:59 -0600 | [diff] [blame] | 228 | if "-flto" in config_env["CFLAGS"]: |
| 229 | print("CFLAGS=\"-flto\" ./configure.sh -O3 -k {}".format(opt)) |
| 230 | else: |
| 231 | print("./configure.sh -O3 -k {}".format(opt)) |
Gavin Howard | 030ef05 | 2019-05-10 10:59:24 -0600 | [diff] [blame] | 232 | print("make") |