144d4804dSStefan Eßer#! /usr/bin/python3 -B 244d4804dSStefan Eßer# 344d4804dSStefan Eßer# SPDX-License-Identifier: BSD-2-Clause 444d4804dSStefan Eßer# 5d101cdd6SStefan Eßer# Copyright (c) 2018-2023 Gavin D. Howard and contributors. 644d4804dSStefan Eßer# 744d4804dSStefan Eßer# Redistribution and use in source and binary forms, with or without 844d4804dSStefan Eßer# modification, are permitted provided that the following conditions are met: 944d4804dSStefan Eßer# 1044d4804dSStefan Eßer# * Redistributions of source code must retain the above copyright notice, this 1144d4804dSStefan Eßer# list of conditions and the following disclaimer. 1244d4804dSStefan Eßer# 1344d4804dSStefan Eßer# * Redistributions in binary form must reproduce the above copyright notice, 1444d4804dSStefan Eßer# this list of conditions and the following disclaimer in the documentation 1544d4804dSStefan Eßer# and/or other materials provided with the distribution. 1644d4804dSStefan Eßer# 1744d4804dSStefan Eßer# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1844d4804dSStefan Eßer# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1944d4804dSStefan Eßer# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2044d4804dSStefan Eßer# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 2144d4804dSStefan Eßer# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2244d4804dSStefan Eßer# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2344d4804dSStefan Eßer# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2444d4804dSStefan Eßer# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2544d4804dSStefan Eßer# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2644d4804dSStefan Eßer# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2744d4804dSStefan Eßer# POSSIBILITY OF SUCH DAMAGE. 2844d4804dSStefan Eßer# 2944d4804dSStefan Eßer 3044d4804dSStefan Eßerimport os 3144d4804dSStefan Eßerimport sys 3244d4804dSStefan Eßerimport subprocess 3344d4804dSStefan Eßerimport time 3444d4804dSStefan Eßer 3544d4804dSStefan Eßer# Print the usage and exit with an error. 3644d4804dSStefan Eßerdef usage(): 3744d4804dSStefan Eßer print("usage: {} [num_iterations test_num exe]".format(script)) 3844d4804dSStefan Eßer print("\n num_iterations is the number of times to run each karatsuba number; default is 4") 3944d4804dSStefan Eßer print("\n test_num is the last Karatsuba number to run through tests") 4044d4804dSStefan Eßer sys.exit(1) 4144d4804dSStefan Eßer 4244d4804dSStefan Eßer# Run a command. This is basically an alias. 4344d4804dSStefan Eßerdef run(cmd, env=None): 4444d4804dSStefan Eßer return subprocess.run(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env) 4544d4804dSStefan Eßer 4644d4804dSStefan Eßerscript = sys.argv[0] 4744d4804dSStefan Eßertestdir = os.path.dirname(script) 4844d4804dSStefan Eßer 4944d4804dSStefan Eßerif testdir == "": 5044d4804dSStefan Eßer testdir = os.getcwd() 5144d4804dSStefan Eßer 5244d4804dSStefan Eßerprint("\nWARNING: This script is for distro and package maintainers.") 5344d4804dSStefan Eßerprint("It is for finding the optimal Karatsuba number.") 5444d4804dSStefan Eßerprint("Though it only needs to be run once per release/platform,") 5544d4804dSStefan Eßerprint("it takes forever to run.") 5644d4804dSStefan Eßerprint("You have been warned.\n") 5744d4804dSStefan Eßerprint("Note: If you send an interrupt, it will report the current best number.\n") 5844d4804dSStefan Eßer 5944d4804dSStefan Eßer# This script has to be run by itself. 6044d4804dSStefan Eßerif __name__ != "__main__": 6144d4804dSStefan Eßer usage() 6244d4804dSStefan Eßer 6344d4804dSStefan Eßer# These constants can be changed, but I found they work well enough. 6444d4804dSStefan Eßermx = 520 6544d4804dSStefan Eßermx2 = mx // 2 6644d4804dSStefan Eßermn = 16 6744d4804dSStefan Eßer 6844d4804dSStefan Eßernum = "9" * mx 6944d4804dSStefan Eßer 7044d4804dSStefan Eßerargs_idx = 4 7144d4804dSStefan Eßer 7244d4804dSStefan Eßer# Command-line processing. 7344d4804dSStefan Eßerif len(sys.argv) >= 2: 7444d4804dSStefan Eßer num_iterations = int(sys.argv[1]) 7544d4804dSStefan Eßerelse: 7644d4804dSStefan Eßer num_iterations = 4 7744d4804dSStefan Eßer 7844d4804dSStefan Eßerif len(sys.argv) >= 3: 7944d4804dSStefan Eßer test_num = int(sys.argv[2]) 8044d4804dSStefan Eßerelse: 8144d4804dSStefan Eßer test_num = 0 8244d4804dSStefan Eßer 8344d4804dSStefan Eßerif len(sys.argv) >= args_idx: 8444d4804dSStefan Eßer exe = sys.argv[3] 8544d4804dSStefan Eßerelse: 8644d4804dSStefan Eßer exe = testdir + "/bin/bc" 8744d4804dSStefan Eßer 8844d4804dSStefan Eßerexedir = os.path.dirname(exe) 8944d4804dSStefan Eßer 9044d4804dSStefan Eßer# Some basic tests. 9144d4804dSStefan Eßerindata = "for (i = 0; i < 100; ++i) {} * {}\n" 9244d4804dSStefan Eßerindata += "1.23456789^100000\n1.23456789^100000\nhalt" 9344d4804dSStefan Eßerindata = indata.format(num, num).encode() 9444d4804dSStefan Eßer 9544d4804dSStefan Eßertimes = [] 9644d4804dSStefan Eßernums = [] 9744d4804dSStefan Eßerruns = [] 9844d4804dSStefan Eßernruns = num_iterations + 1 9944d4804dSStefan Eßer 10044d4804dSStefan Eßer# We build the list first because I want to just edit slots. 10144d4804dSStefan Eßerfor i in range(0, nruns): 10244d4804dSStefan Eßer runs.append(0) 10344d4804dSStefan Eßer 10444d4804dSStefan Eßertests = [ "multiply", "modulus", "power", "sqrt" ] 10544d4804dSStefan Eßerscripts = [ "multiply" ] 10644d4804dSStefan Eßer 10744d4804dSStefan Eßer# Test Link-Time Optimization. 10844d4804dSStefan Eßerprint("Testing CFLAGS=\"-flto\"...") 10944d4804dSStefan Eßer 11044d4804dSStefan Eßerflags = dict(os.environ) 11144d4804dSStefan Eßertry: 11244d4804dSStefan Eßer flags["CFLAGS"] = flags["CFLAGS"] + " " + "-flto" 11344d4804dSStefan Eßerexcept KeyError: 11444d4804dSStefan Eßer flags["CFLAGS"] = "-flto" 11544d4804dSStefan Eßer 11610041e99SStefan Eßerp = run([ "{}/../configure.sh".format(testdir), "-O3" ], flags) 11744d4804dSStefan Eßerif p.returncode != 0: 11844d4804dSStefan Eßer print("configure.sh returned an error ({}); exiting...".format(p.returncode)) 11944d4804dSStefan Eßer sys.exit(p.returncode) 12044d4804dSStefan Eßer 12144d4804dSStefan Eßerp = run([ "make" ]) 12244d4804dSStefan Eßer 12344d4804dSStefan Eßerif p.returncode == 0: 12444d4804dSStefan Eßer config_env = flags 12544d4804dSStefan Eßer print("Using CFLAGS=\"-flto\"") 12644d4804dSStefan Eßerelse: 12744d4804dSStefan Eßer config_env = os.environ 12844d4804dSStefan Eßer print("Not using CFLAGS=\"-flto\"") 12944d4804dSStefan Eßer 13044d4804dSStefan Eßerp = run([ "make", "clean" ]) 13144d4804dSStefan Eßer 13244d4804dSStefan Eßer# Test parallel build. My machine has 16 cores. 13344d4804dSStefan Eßerprint("Testing \"make -j16\"") 13444d4804dSStefan Eßer 13544d4804dSStefan Eßerif p.returncode != 0: 13644d4804dSStefan Eßer print("make returned an error ({}); exiting...".format(p.returncode)) 13744d4804dSStefan Eßer sys.exit(p.returncode) 13844d4804dSStefan Eßer 13944d4804dSStefan Eßerp = run([ "make", "-j16" ]) 14044d4804dSStefan Eßer 14144d4804dSStefan Eßerif p.returncode == 0: 14244d4804dSStefan Eßer makecmd = [ "make", "-j16" ] 14344d4804dSStefan Eßer print("Using \"make -j16\"") 14444d4804dSStefan Eßerelse: 14544d4804dSStefan Eßer makecmd = [ "make" ] 14644d4804dSStefan Eßer print("Not using \"make -j16\"") 14744d4804dSStefan Eßer 14844d4804dSStefan Eßer# Set the max if the user did. 14944d4804dSStefan Eßerif test_num != 0: 15044d4804dSStefan Eßer mx2 = test_num 15144d4804dSStefan Eßer 15244d4804dSStefan Eßer# This is the meat here. 15344d4804dSStefan Eßertry: 15444d4804dSStefan Eßer 15544d4804dSStefan Eßer # For each possible KARATSUBA_LEN... 15644d4804dSStefan Eßer for i in range(mn, mx2 + 1): 15744d4804dSStefan Eßer 15844d4804dSStefan Eßer # Configure and compile. 15944d4804dSStefan Eßer print("\nCompiling...\n") 16044d4804dSStefan Eßer 16110041e99SStefan Eßer p = run([ "{}/../configure.sh".format(testdir), "-O3", "-k{}".format(i) ], config_env) 16244d4804dSStefan Eßer 16344d4804dSStefan Eßer if p.returncode != 0: 16444d4804dSStefan Eßer print("configure.sh returned an error ({}); exiting...".format(p.returncode)) 16544d4804dSStefan Eßer sys.exit(p.returncode) 16644d4804dSStefan Eßer 16744d4804dSStefan Eßer p = run(makecmd) 16844d4804dSStefan Eßer 16944d4804dSStefan Eßer if p.returncode != 0: 17044d4804dSStefan Eßer print("make returned an error ({}); exiting...".format(p.returncode)) 17144d4804dSStefan Eßer sys.exit(p.returncode) 17244d4804dSStefan Eßer 17344d4804dSStefan Eßer # Test if desired. 17444d4804dSStefan Eßer if (test_num >= i): 17544d4804dSStefan Eßer 17644d4804dSStefan Eßer print("Running tests for Karatsuba Num: {}\n".format(i)) 17744d4804dSStefan Eßer 17844d4804dSStefan Eßer for test in tests: 17944d4804dSStefan Eßer 18044d4804dSStefan Eßer cmd = [ "{}/../tests/test.sh".format(testdir), "bc", test, "0", "0", exe ] 18144d4804dSStefan Eßer 18244d4804dSStefan Eßer p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE) 18344d4804dSStefan Eßer 18444d4804dSStefan Eßer if p.returncode != 0: 18544d4804dSStefan Eßer print("{} test failed:\n".format(test, p.returncode)) 18644d4804dSStefan Eßer print(p.stderr.decode()) 18744d4804dSStefan Eßer print("\nexiting...") 18844d4804dSStefan Eßer sys.exit(p.returncode) 18944d4804dSStefan Eßer 19044d4804dSStefan Eßer print("") 19144d4804dSStefan Eßer 19244d4804dSStefan Eßer for script in scripts: 19344d4804dSStefan Eßer 19444d4804dSStefan Eßer cmd = [ "{}/../tests/script.sh".format(testdir), "bc", script + ".bc", 19544d4804dSStefan Eßer "0", "1", "1", "0", exe ] 19644d4804dSStefan Eßer 19744d4804dSStefan Eßer p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE) 19844d4804dSStefan Eßer 19944d4804dSStefan Eßer if p.returncode != 0: 20044d4804dSStefan Eßer print("{} test failed:\n".format(test, p.returncode)) 20144d4804dSStefan Eßer print(p.stderr.decode()) 20244d4804dSStefan Eßer print("\nexiting...") 20344d4804dSStefan Eßer sys.exit(p.returncode) 20444d4804dSStefan Eßer 20544d4804dSStefan Eßer print("") 20644d4804dSStefan Eßer 20744d4804dSStefan Eßer # If testing was *not* desired, assume the user wanted to time it. 20844d4804dSStefan Eßer elif test_num == 0: 20944d4804dSStefan Eßer 21044d4804dSStefan Eßer print("Timing Karatsuba Num: {}".format(i), end='', flush=True) 21144d4804dSStefan Eßer 21244d4804dSStefan Eßer for j in range(0, nruns): 21344d4804dSStefan Eßer 21444d4804dSStefan Eßer cmd = [ exe, "{}/../tests/bc/power.txt".format(testdir) ] 21544d4804dSStefan Eßer 21644d4804dSStefan Eßer start = time.perf_counter() 21744d4804dSStefan Eßer p = subprocess.run(cmd, input=indata, stdout=subprocess.PIPE, stderr=subprocess.PIPE) 21844d4804dSStefan Eßer end = time.perf_counter() 21944d4804dSStefan Eßer 22044d4804dSStefan Eßer if p.returncode != 0: 22144d4804dSStefan Eßer print("bc returned an error; exiting...") 22244d4804dSStefan Eßer sys.exit(p.returncode) 22344d4804dSStefan Eßer 22444d4804dSStefan Eßer runs[j] = end - start 22544d4804dSStefan Eßer 22644d4804dSStefan Eßer run_times = runs[1:] 22744d4804dSStefan Eßer avg = sum(run_times) / len(run_times) 22844d4804dSStefan Eßer 22944d4804dSStefan Eßer times.append(avg) 23044d4804dSStefan Eßer nums.append(i) 23144d4804dSStefan Eßer print(", Time: {}".format(times[i - mn])) 23244d4804dSStefan Eßer 23344d4804dSStefan Eßerexcept KeyboardInterrupt: 23444d4804dSStefan Eßer # When timing, we want to quit when the user tells us to. However, we also 23544d4804dSStefan Eßer # want to report the best run, so we make sure to grab the times here before 23644d4804dSStefan Eßer # moving on. 23744d4804dSStefan Eßer nums = nums[0:i] 23844d4804dSStefan Eßer times = times[0:i] 23944d4804dSStefan Eßer 24044d4804dSStefan Eßer# If running timed tests... 24144d4804dSStefan Eßerif test_num == 0: 24244d4804dSStefan Eßer 24344d4804dSStefan Eßer # Report the optimal KARATSUBA_LEN 24444d4804dSStefan Eßer opt = nums[times.index(min(times))] 24544d4804dSStefan Eßer 24644d4804dSStefan Eßer print("\n\nOptimal Karatsuba Num (for this machine): {}".format(opt)) 24744d4804dSStefan Eßer print("Run the following:\n") 24844d4804dSStefan Eßer if "-flto" in config_env["CFLAGS"]: 24944d4804dSStefan Eßer print("CFLAGS=\"-flto\" ./configure.sh -O3 -k {}".format(opt)) 25044d4804dSStefan Eßer else: 25144d4804dSStefan Eßer print("./configure.sh -O3 -k {}".format(opt)) 25244d4804dSStefan Eßer print("make") 253