contrib/bc/scripts/karatsuba.py

   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
  30 import os
  31 import sys
  32 import subprocess
  33 import time
  34
  35 # Print the usage and exit with an error.
  36 def 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.
  43 def run(cmd, env=None):
  44         return subprocess.run(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env)
  45
  46 script = sys.argv[0]
  47 testdir = os.path.dirname(script)
  48
  49 if testdir == "":
  50         testdir = os.getcwd()
  51
  52 # We want to be in the root directory.
  53 os.chdir(testdir + "/..")
  54
  55 print("\nWARNING: This script is for distro and package maintainers.")
  56 print("It is for finding the optimal Karatsuba number.")
  57 print("Though it only needs to be run once per release/platform,")
  58 print("it takes forever to run.")
  59 print("You have been warned.\n")
  60 print("Note: If you send an interrupt, it will report the current best number.\n")
  61
  62 # This script has to be run by itself.
  63 if __name__ != "__main__":
  64         usage()
  65
  66 # These constants can be changed, but I found they work well enough.
  67 mx = 520
  68 mx2 = mx // 2
  69 mn = 16
  70
  71 num = "9" * mx
  72
  73 args_idx = 4
  74
  75 # Command-line processing.
  76 if len(sys.argv) >= 2:
  77         num_iterations = int(sys.argv[1])
  78 else:
  79         num_iterations = 4
  80
  81 if len(sys.argv) >= 3:
  82         test_num = int(sys.argv[2])
  83 else:
  84         test_num = 0
  85
  86 if len(sys.argv) >= args_idx:
  87         exe = sys.argv[3]
  88 else:
  89         exe = testdir + "/bin/bc"
  90
  91 exedir = os.path.dirname(exe)
  92
  93 # Some basic tests.
  94 indata = "for (i = 0; i < 100; ++i) {} * {}\n"
  95 indata += "1.23456789^100000\n1.23456789^100000\nhalt"
  96 indata = indata.format(num, num).encode()
  97
  98 times = []
  99 nums = []
 100 runs = []
 101 nruns = num_iterations + 1
 102
 103 # We build the list first because I want to just edit slots.
 104 for i in range(0, nruns):
 105         runs.append(0)
 106
 107 tests = [ "multiply", "modulus", "power", "sqrt" ]
 108 scripts = [ "multiply" ]
 109
 110 # Test Link-Time Optimization.
 111 print("Testing CFLAGS=\"-flto\"...")
 112
 113 flags = dict(os.environ)
 114 try:
 115         flags["CFLAGS"] = flags["CFLAGS"] + " " + "-flto"
 116 except KeyError:
 117         flags["CFLAGS"] = "-flto"
 118
 119 p = run([ "./configure.sh", "-O3" ], flags)
 120 if p.returncode != 0:
 121         print("configure.sh returned an error ({}); exiting...".format(p.returncode))
 122         sys.exit(p.returncode)
 123
 124 p = run([ "make" ])
 125
 126 if p.returncode == 0:
 127         config_env = flags
 128         print("Using CFLAGS=\"-flto\"")
 129 else:
 130         config_env = os.environ
 131         print("Not using CFLAGS=\"-flto\"")
 132
 133 p = run([ "make", "clean" ])
 134
 135 # Test parallel build. My machine has 16 cores.
 136 print("Testing \"make -j16\"")
 137
 138 if p.returncode != 0:
 139         print("make returned an error ({}); exiting...".format(p.returncode))
 140         sys.exit(p.returncode)
 141
 142 p = run([ "make", "-j16" ])
 143
 144 if p.returncode == 0:
 145         makecmd = [ "make", "-j16" ]
 146         print("Using \"make -j16\"")
 147 else:
 148         makecmd = [ "make" ]
 149         print("Not using \"make -j16\"")
 150
 151 # Set the max if the user did.
 152 if test_num != 0:
 153         mx2 = test_num
 154
 155 # This is the meat here.
 156 try:
 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
 236 except 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...
 244 if 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")