fork/rust

git clone https://git.julia.blue/fork/rust

borsAuto merge of #103046 - JanBeh:PR_clarify_cmp_terminology, r=workingjubilee3bcad65fbf6

master
12.2 KiB394 linesraw
1#!/usr/bin/env python3
2
3"""
4Testing dec2flt
5===============
6These are *really* extensive tests. Expect them to run for hours. Due to the
7nature of the problem (the input is a string of arbitrary length), exhaustive
8testing is not really possible. Instead, there are exhaustive tests for some
9classes of inputs for which that is feasible and a bunch of deterministic and
10random non-exhaustive tests for covering everything else.
11
12The actual tests (generating decimal strings and feeding them to dec2flt) is
13performed by a set of stand-along rust programs. This script compiles, runs,
14and supervises them. The programs report the strings they generate and the
15floating point numbers they converted those strings to, and this script
16checks that the results are correct.
17
18You can run specific tests rather than all of them by giving their names
19(without .rs extension) as command line parameters.
20
21Verification
22------------
23The tricky part is not generating those inputs but verifying the outputs.
24Comparing with the result of Python's float() does not cut it because
25(and this is apparently undocumented) although Python includes a version of
26Martin Gay's code including the decimal-to-float part, it doesn't actually use
27it for float() (only for round()) instead relying on the system scanf() which
28is not necessarily completely accurate.
29
30Instead, we take the input and compute the true value with bignum arithmetic
31(as a fraction, using the ``fractions`` module).
32
33Given an input string and the corresponding float computed via Rust, simply
34decode the float into f * 2^k (for integers f, k) and the ULP.
35We can now easily compute the error and check if it is within 0.5 ULP as it
36should be. Zero and infinites are handled similarly:
37
38- If the approximation is 0.0, the exact value should be *less or equal*
39  half the smallest denormal float: the smallest denormal floating point
40  number has an odd mantissa (00...001) and thus half of that is rounded
41  to 00...00, i.e., zero.
42- If the approximation is Inf, the exact value should be *greater or equal*
43  to the largest finite float + 0.5 ULP: the largest finite float has an odd
44  mantissa (11...11), so that plus half an ULP is rounded up to the nearest
45  even number, which overflows.
46
47Implementation details
48----------------------
49This directory contains a set of single-file Rust programs that perform
50tests with a particular class of inputs. Each is compiled and run without
51parameters, outputs (f64, f32, decimal) pairs to verify externally, and
52in any case either exits gracefully or with a panic.
53
54If a test binary writes *anything at all* to stderr or exits with an
55exit code that's not 0, the test fails.
56The output on stdout is treated as (f64, f32, decimal) record, encoded thusly:
57
58- First, the bits of the f64 encoded as an ASCII hex string.
59- Second, the bits of the f32 encoded as an ASCII hex string.
60- Then the corresponding string input, in ASCII
61- The record is terminated with a newline.
62
63Incomplete records are an error. Not-a-Number bit patterns are invalid too.
64
65The tests run serially but the validation for a single test is parallelized
66with ``multiprocessing``. Each test is launched as a subprocess.
67One thread supervises it: Accepts and enqueues records to validate, observe
68stderr, and waits for the process to exit. A set of worker processes perform
69the validation work for the outputs enqueued there. Another thread listens
70for progress updates from the workers.
71
72Known issues
73------------
74Some errors (e.g., NaN outputs) aren't handled very gracefully.
75Also, if there is an exception or the process is interrupted (at least on
76Windows) the worker processes are leaked and stick around forever.
77They're only a few megabytes each, but still, this script should not be run
78if you aren't prepared to manually kill a lot of orphaned processes.
79"""
80from __future__ import print_function
81import sys
82import os.path
83import time
84import struct
85from fractions import Fraction
86from collections import namedtuple
87from subprocess import Popen, check_call, PIPE
88from glob import glob
89import multiprocessing
90import threading
91import ctypes
92import binascii
93
94try:  # Python 3
95    import queue as Queue
96except ImportError:  # Python 2
97    import Queue
98
99NUM_WORKERS = 2
100UPDATE_EVERY_N = 50000
101INF = namedtuple('INF', '')()
102NEG_INF = namedtuple('NEG_INF', '')()
103ZERO = namedtuple('ZERO', '')()
104MAILBOX = None  # The queue for reporting errors to the main process.
105STDOUT_LOCK = threading.Lock()
106test_name = None
107child_processes = []
108exit_status = 0
109
110def msg(*args):
111    with STDOUT_LOCK:
112        print("[" + test_name + "]", *args)
113        sys.stdout.flush()
114
115
116def write_errors():
117    global exit_status
118    f = open("errors.txt", 'w')
119    have_seen_error = False
120    while True:
121        args = MAILBOX.get()
122        if args is None:
123            f.close()
124            break
125        print(*args, file=f)
126        f.flush()
127        if not have_seen_error:
128            have_seen_error = True
129            msg("Something is broken:", *args)
130            msg("Future errors will be logged to errors.txt")
131            exit_status = 101
132
133
134def cargo():
135    print("compiling tests")
136    sys.stdout.flush()
137    check_call(['cargo', 'build', '--release'])
138
139
140def run(test):
141    global test_name
142    test_name = test
143
144    t0 = time.perf_counter()
145    msg("setting up supervisor")
146    command = ['cargo', 'run', '--bin', test, '--release']
147    proc = Popen(command, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE)
148    done = multiprocessing.Value(ctypes.c_bool)
149    queue = multiprocessing.Queue(maxsize=5)#(maxsize=1024)
150    workers = []
151    for n in range(NUM_WORKERS):
152        worker = multiprocessing.Process(name='Worker-' + str(n + 1),
153                                         target=init_worker,
154                                         args=[test, MAILBOX, queue, done])
155        workers.append(worker)
156        child_processes.append(worker)
157    for worker in workers:
158        worker.start()
159    msg("running test")
160    interact(proc, queue)
161    with done.get_lock():
162        done.value = True
163    for worker in workers:
164        worker.join()
165    msg("python is done")
166    assert queue.empty(), "did not validate everything"
167    dt = time.perf_counter() - t0
168    msg("took", round(dt, 3), "seconds")
169
170
171def interact(proc, queue):
172    n = 0
173    while proc.poll() is None:
174        line = proc.stdout.readline()
175        if not line:
176            continue
177        assert line.endswith(b'\n'), "incomplete line: " + repr(line)
178        queue.put(line)
179        n += 1
180        if n % UPDATE_EVERY_N == 0:
181            msg("got", str(n // 1000) + "k", "records")
182    msg("rust is done. exit code:", proc.returncode)
183    rest, stderr = proc.communicate()
184    if stderr:
185        msg("rust stderr output:", stderr)
186    for line in rest.split(b'\n'):
187        if not line:
188            continue
189        queue.put(line)
190
191
192def main():
193    global MAILBOX
194    files = glob('src/bin/*.rs')
195    basenames = [os.path.basename(i) for i in files]
196    all_tests = [os.path.splitext(f)[0] for f in basenames if not f.startswith('_')]
197    args = sys.argv[1:]
198    if args:
199        tests = [test for test in all_tests if test in args]
200    else:
201        tests = all_tests
202    if not tests:
203        print("Error: No tests to run")
204        sys.exit(1)
205    # Compile first for quicker feedback
206    cargo()
207    # Set up mailbox once for all tests
208    MAILBOX = multiprocessing.Queue()
209    mailman = threading.Thread(target=write_errors)
210    mailman.daemon = True
211    mailman.start()
212    for test in tests:
213        run(test)
214    MAILBOX.put(None)
215    mailman.join()
216
217
218# ---- Worker thread code ----
219
220
221POW2 = { e: Fraction(2) ** e for e in range(-1100, 1100) }
222HALF_ULP = { e: (Fraction(2) ** e)/2 for e in range(-1100, 1100) }
223DONE_FLAG = None
224
225
226def send_error_to_supervisor(*args):
227    MAILBOX.put(args)
228
229
230def init_worker(test, mailbox, queue, done):
231    global test_name, MAILBOX, DONE_FLAG
232    test_name = test
233    MAILBOX = mailbox
234    DONE_FLAG = done
235    do_work(queue)
236
237
238def is_done():
239    with DONE_FLAG.get_lock():
240        return DONE_FLAG.value
241
242
243def do_work(queue):
244    while True:
245        try:
246            line = queue.get(timeout=0.01)
247        except Queue.Empty:
248            if queue.empty() and is_done():
249                return
250            else:
251                continue
252        bin64, bin32, text = line.rstrip().split()
253        validate(bin64, bin32, text.decode('utf-8'))
254
255
256def decode_binary64(x):
257    """
258    Turn a IEEE 754 binary64 into (mantissa, exponent), except 0.0 and
259    infinity (positive and negative), which return ZERO, INF, and NEG_INF
260    respectively.
261    """
262    x = binascii.unhexlify(x)
263    assert len(x) == 8, repr(x)
264    [bits] = struct.unpack(b'>Q', x)
265    if bits == 0:
266        return ZERO
267    exponent = (bits >> 52) & 0x7FF
268    negative = bits >> 63
269    low_bits = bits & 0xFFFFFFFFFFFFF
270    if exponent == 0:
271        mantissa = low_bits
272        exponent += 1
273        if mantissa == 0:
274            return ZERO
275    elif exponent == 0x7FF:
276        assert low_bits == 0, "NaN"
277        if negative:
278            return NEG_INF
279        else:
280            return INF
281    else:
282        mantissa = low_bits | (1 << 52)
283    exponent -= 1023 + 52
284    if negative:
285        mantissa = -mantissa
286    return (mantissa, exponent)
287
288
289def decode_binary32(x):
290    """
291    Turn a IEEE 754 binary32 into (mantissa, exponent), except 0.0 and
292    infinity (positive and negative), which return ZERO, INF, and NEG_INF
293    respectively.
294    """
295    x = binascii.unhexlify(x)
296    assert len(x) == 4, repr(x)
297    [bits] = struct.unpack(b'>I', x)
298    if bits == 0:
299        return ZERO
300    exponent = (bits >> 23) & 0xFF
301    negative = bits >> 31
302    low_bits = bits & 0x7FFFFF
303    if exponent == 0:
304        mantissa = low_bits
305        exponent += 1
306        if mantissa == 0:
307            return ZERO
308    elif exponent == 0xFF:
309        if negative:
310            return NEG_INF
311        else:
312            return INF
313    else:
314        mantissa = low_bits | (1 << 23)
315    exponent -= 127 + 23
316    if negative:
317        mantissa = -mantissa
318    return (mantissa, exponent)
319
320
321MIN_SUBNORMAL_DOUBLE = Fraction(2) ** -1074
322MIN_SUBNORMAL_SINGLE = Fraction(2) ** -149  # XXX unsure
323MAX_DOUBLE = (2 - Fraction(2) ** -52) * (2 ** 1023)
324MAX_SINGLE = (2 - Fraction(2) ** -23) * (2 ** 127)
325MAX_ULP_DOUBLE = 1023 - 52
326MAX_ULP_SINGLE = 127 - 23
327DOUBLE_ZERO_CUTOFF = MIN_SUBNORMAL_DOUBLE / 2
328DOUBLE_INF_CUTOFF = MAX_DOUBLE + 2 ** (MAX_ULP_DOUBLE - 1)
329SINGLE_ZERO_CUTOFF = MIN_SUBNORMAL_SINGLE / 2
330SINGLE_INF_CUTOFF = MAX_SINGLE + 2 ** (MAX_ULP_SINGLE - 1)
331
332def validate(bin64, bin32, text):
333    try:
334        double = decode_binary64(bin64)
335    except AssertionError:
336        print(bin64, bin32, text)
337        raise
338    single = decode_binary32(bin32)
339    real = Fraction(text)
340
341    if double is ZERO:
342        if real > DOUBLE_ZERO_CUTOFF:
343            record_special_error(text, "f64 zero")
344    elif double is INF:
345        if real < DOUBLE_INF_CUTOFF:
346            record_special_error(text, "f64 inf")
347    elif double is NEG_INF:
348        if -real < DOUBLE_INF_CUTOFF:
349            record_special_error(text, "f64 -inf")
350    elif len(double) == 2:
351        sig, k = double
352        validate_normal(text, real, sig, k, "f64")
353    else:
354        assert 0, "didn't handle binary64"
355    if single is ZERO:
356        if real > SINGLE_ZERO_CUTOFF:
357            record_special_error(text, "f32 zero")
358    elif single is INF:
359        if real < SINGLE_INF_CUTOFF:
360            record_special_error(text, "f32 inf")
361    elif single is NEG_INF:
362        if -real < SINGLE_INF_CUTOFF:
363            record_special_error(text, "f32 -inf")
364    elif len(single) == 2:
365        sig, k = single
366        validate_normal(text, real, sig, k, "f32")
367    else:
368        assert 0, "didn't handle binary32"
369
370def record_special_error(text, descr):
371    send_error_to_supervisor(text.strip(), "wrongly rounded to", descr)
372
373
374def validate_normal(text, real, sig, k, kind):
375    approx = sig * POW2[k]
376    error = abs(approx - real)
377    if error > HALF_ULP[k]:
378        record_normal_error(text, error, k, kind)
379
380
381def record_normal_error(text, error, k, kind):
382    one_ulp = HALF_ULP[k + 1]
383    assert one_ulp == 2 * HALF_ULP[k]
384    relative_error = error / one_ulp
385    text = text.strip()
386    try:
387        err_repr = float(relative_error)
388    except ValueError:
389        err_repr = str(err_repr).replace('/', ' / ')
390    send_error_to_supervisor(err_repr, "ULP error on", text, "(" + kind + ")")
391
392
393if __name__ == '__main__':
394    main()