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