1#! /usr/bin/python3 -B 2# 3# SPDX-License-Identifier: BSD-2-Clause 4# 5# Copyright (c) 2018-2021 Gavin D. Howard and contributors. 6# 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. 28# 29 30import os 31import sys 32import subprocess 33import time 34 35# Print the usage and exit with an error. 36def usage(): 37 print("usage: {} [num_iterations test_num exe]".format(script)) 38 print("\n num_iterations is the number of times to run each karatsuba number; default is 4") 39 print("\n test_num is the last Karatsuba number to run through tests") 40 sys.exit(1) 41 42# Run a command. This is basically an alias. 43def run(cmd, env=None): 44 return subprocess.run(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env) 45 46script = sys.argv[0] 47testdir = os.path.dirname(script) 48 49if testdir == "": 50 testdir = os.getcwd() 51 52# We want to be in the root directory. 53os.chdir(testdir + "/..") 54 55print("\nWARNING: This script is for distro and package maintainers.") 56print("It is for finding the optimal Karatsuba number.") 57print("Though it only needs to be run once per release/platform,") 58print("it takes forever to run.") 59print("You have been warned.\n") 60print("Note: If you send an interrupt, it will report the current best number.\n") 61 62# This script has to be run by itself. 63if __name__ != "__main__": 64 usage() 65 66# These constants can be changed, but I found they work well enough. 67mx = 520 68mx2 = mx // 2 69mn = 16 70 71num = "9" * mx 72 73args_idx = 4 74 75# Command-line processing. 76if len(sys.argv) >= 2: 77 num_iterations = int(sys.argv[1]) 78else: 79 num_iterations = 4 80 81if len(sys.argv) >= 3: 82 test_num = int(sys.argv[2]) 83else: 84 test_num = 0 85 86if len(sys.argv) >= args_idx: 87 exe = sys.argv[3] 88else: 89 exe = testdir + "/bin/bc" 90 91exedir = os.path.dirname(exe) 92 93# Some basic tests. 94indata = "for (i = 0; i < 100; ++i) {} * {}\n" 95indata += "1.23456789^100000\n1.23456789^100000\nhalt" 96indata = indata.format(num, num).encode() 97 98times = [] 99nums = [] 100runs = [] 101nruns = num_iterations + 1 102 103# We build the list first because I want to just edit slots. 104for i in range(0, nruns): 105 runs.append(0) 106 107tests = [ "multiply", "modulus", "power", "sqrt" ] 108scripts = [ "multiply" ] 109 110# Test Link-Time Optimization. 111print("Testing CFLAGS=\"-flto\"...") 112 113flags = dict(os.environ) 114try: 115 flags["CFLAGS"] = flags["CFLAGS"] + " " + "-flto" 116except KeyError: 117 flags["CFLAGS"] = "-flto" 118 119p = run([ "./configure.sh", "-O3" ], flags) 120if p.returncode != 0: 121 print("configure.sh returned an error ({}); exiting...".format(p.returncode)) 122 sys.exit(p.returncode) 123 124p = run([ "make" ]) 125 126if p.returncode == 0: 127 config_env = flags 128 print("Using CFLAGS=\"-flto\"") 129else: 130 config_env = os.environ 131 print("Not using CFLAGS=\"-flto\"") 132 133p = run([ "make", "clean" ]) 134 135# Test parallel build. My machine has 16 cores. 136print("Testing \"make -j16\"") 137 138if p.returncode != 0: 139 print("make returned an error ({}); exiting...".format(p.returncode)) 140 sys.exit(p.returncode) 141 142p = run([ "make", "-j16" ]) 143 144if p.returncode == 0: 145 makecmd = [ "make", "-j16" ] 146 print("Using \"make -j16\"") 147else: 148 makecmd = [ "make" ] 149 print("Not using \"make -j16\"") 150 151# Set the max if the user did. 152if test_num != 0: 153 mx2 = test_num 154 155# This is the meat here. 156try: 157 158 # For each possible KARATSUBA_LEN... 159 for i in range(mn, mx2 + 1): 160 161 # Configure and compile. 162 print("\nCompiling...\n") 163 164 p = run([ "./configure.sh", "-O3", "-k{}".format(i) ], config_env) 165 166 if p.returncode != 0: 167 print("configure.sh returned an error ({}); exiting...".format(p.returncode)) 168 sys.exit(p.returncode) 169 170 p = run(makecmd) 171 172 if p.returncode != 0: 173 print("make returned an error ({}); exiting...".format(p.returncode)) 174 sys.exit(p.returncode) 175 176 # Test if desired. 177 if (test_num >= i): 178 179 print("Running tests for Karatsuba Num: {}\n".format(i)) 180 181 for test in tests: 182 183 cmd = [ "{}/../tests/test.sh".format(testdir), "bc", test, "0", "0", exe ] 184 185 p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE) 186 187 if p.returncode != 0: 188 print("{} test failed:\n".format(test, p.returncode)) 189 print(p.stderr.decode()) 190 print("\nexiting...") 191 sys.exit(p.returncode) 192 193 print("") 194 195 for script in scripts: 196 197 cmd = [ "{}/../tests/script.sh".format(testdir), "bc", script + ".bc", 198 "0", "1", "1", "0", exe ] 199 200 p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE) 201 202 if p.returncode != 0: 203 print("{} test failed:\n".format(test, p.returncode)) 204 print(p.stderr.decode()) 205 print("\nexiting...") 206 sys.exit(p.returncode) 207 208 print("") 209 210 # If testing was *not* desired, assume the user wanted to time it. 211 elif test_num == 0: 212 213 print("Timing Karatsuba Num: {}".format(i), end='', flush=True) 214 215 for j in range(0, nruns): 216 217 cmd = [ exe, "{}/../tests/bc/power.txt".format(testdir) ] 218 219 start = time.perf_counter() 220 p = subprocess.run(cmd, input=indata, stdout=subprocess.PIPE, stderr=subprocess.PIPE) 221 end = time.perf_counter() 222 223 if p.returncode != 0: 224 print("bc returned an error; exiting...") 225 sys.exit(p.returncode) 226 227 runs[j] = end - start 228 229 run_times = runs[1:] 230 avg = sum(run_times) / len(run_times) 231 232 times.append(avg) 233 nums.append(i) 234 print(", Time: {}".format(times[i - mn])) 235 236except KeyboardInterrupt: 237 # When timing, we want to quit when the user tells us to. However, we also 238 # want to report the best run, so we make sure to grab the times here before 239 # moving on. 240 nums = nums[0:i] 241 times = times[0:i] 242 243# If running timed tests... 244if test_num == 0: 245 246 # Report the optimal KARATSUBA_LEN 247 opt = nums[times.index(min(times))] 248 249 print("\n\nOptimal Karatsuba Num (for this machine): {}".format(opt)) 250 print("Run the following:\n") 251 if "-flto" in config_env["CFLAGS"]: 252 print("CFLAGS=\"-flto\" ./configure.sh -O3 -k {}".format(opt)) 253 else: 254 print("./configure.sh -O3 -k {}".format(opt)) 255 print("make") 256