contrib/bc/karatsuba.py

   1 #! /usr/bin/python3 -B
   2 #
   3 # SPDX-License-Identifier: BSD-2-Clause
   4 #
   5 # Copyright (c) 2018-2020 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 def usage():
  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")
  38         print("\n    test_num is the last Karatsuba number to run through tests")
  39         sys.exit(1)
  40
  41 def run(cmd, env=None):
  42         return subprocess.run(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env)
  43
  44 script = sys.argv[0]
  45 testdir = os.path.dirname(script)
  46
  47 if testdir == "":
  48         testdir = os.getcwd()
  49
  50 print("\nWARNING: This script is for distro and package maintainers.")
  51 print("It is for finding the optimal Karatsuba number.")
  52 print("Though it only needs to be run once per release/platform,")
  53 print("it takes forever to run.")
  54 print("You have been warned.\n")
  55 print("Note: If you send an interrupt, it will report the current best number.\n")
  56
  57 if __name__ != "__main__":
  58         usage()
  59
  60 mx = 520
  61 mx2 = mx // 2
  62 mn = 16
  63
  64 num = "9" * mx
  65
  66 args_idx = 4
  67
  68 if len(sys.argv) >= 2:
  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])
  75 else:
  76         test_num = 0
  77
  78 if len(sys.argv) >= args_idx:
  79         exe = sys.argv[3]
  80 else:
  81         exe = testdir + "/bin/bc"
  82
  83 exedir = os.path.dirname(exe)
  84
  85 indata = "for (i = 0; i < 100; ++i) {} * {}\n"
  86 indata += "1.23456789^100000\n1.23456789^100000\nhalt"
  87 indata = indata.format(num, num).encode()
  88
  89 times = []
  90 nums = []
  91 runs = []
  92 nruns = num_iterations + 1
  93
  94 for i in range(0, nruns):
  95         runs.append(0)
  96
  97 tests = [ "multiply", "modulus", "power", "sqrt" ]
  98 scripts = [ "multiply" ]
  99
 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
 124 print("Testing \"make -j4\"")
 125
 126 if p.returncode != 0:
 127         print("make returned an error ({}); exiting...".format(p.returncode))
 128         sys.exit(p.returncode)
 129
 130 p = run([ "make", "-j4" ])
 131
 132 if p.returncode == 0:
 133         makecmd = [ "make", "-j4" ]
 134         print("Using \"make -j4\"")
 135 else:
 136         makecmd = [ "make" ]
 137         print("Not using \"make -j4\"")
 138
 139 if test_num != 0:
 140         mx2 = test_num
 141
 142 try:
 143
 144         for i in range(mn, mx2 + 1):
 145
 146                 print("\nCompiling...\n")
 147
 148                 p = run([ "./configure.sh", "-O3", "-k{}".format(i) ], config_env)
 149
 150                 if p.returncode != 0:
 151                         print("configure.sh returned an error ({}); exiting...".format(p.returncode))
 152                         sys.exit(p.returncode)
 153
 154                 p = run(makecmd)
 155
 156                 if p.returncode != 0:
 157                         print("make returned an error ({}); exiting...".format(p.returncode))
 158                         sys.exit(p.returncode)
 159
 160                 if (test_num >= i):
 161
 162                         print("Running tests for Karatsuba Num: {}\n".format(i))
 163
 164                         for test in tests:
 165
 166                                 cmd = [ "{}/tests/test.sh".format(testdir), "bc", test, "0", "0", exe ]
 167
 168                                 p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE)
 169
 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)
 175
 176                         print("")
 177
 178                         for script in scripts:
 179
 180                                 cmd = [ "{}/tests/script.sh".format(testdir), "bc", script + ".bc",
 181                                         "0", "1", "1", "0", exe ]
 182
 183                                 p = subprocess.run(cmd + sys.argv[args_idx:], stderr=subprocess.PIPE)
 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
 193                 elif test_num == 0:
 194
 195                         print("Timing Karatsuba Num: {}".format(i), end='', flush=True)
 196
 197                         for j in range(0, nruns):
 198
 199                                 cmd = [ exe, "{}/tests/bc/power.txt".format(testdir) ]
 200
 201                                 start = time.perf_counter()
 202                                 p = subprocess.run(cmd, input=indata, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
 203                                 end = time.perf_counter()
 204
 205                                 if p.returncode != 0:
 206                                         print("bc returned an error; exiting...")
 207                                         sys.exit(p.returncode)
 208
 209                                 runs[j] = end - start
 210
 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]
 221
 222 if test_num == 0:
 223
 224         opt = nums[times.index(min(times))]
 225
 226         print("\n\nOptimal Karatsuba Num (for this machine): {}".format(opt))
 227         print("Run the following:\n")
 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))
 232         print("make")