check-scaling

#!/usr/bin/env python
import os
import statistics
import subprocess
from time import time as _time


class time:
    def __init__(self):
        self._start = None
        self._value = None

    @property
    def value(self):
        value = self._value
        if value is None:
            raise AttributeError('timer is not done')
        return value

    def __enter__(self):
        self._value = None  # reset the timer
        self._start = _time()
        return self

    def __exit__(self, *exc_info):
        self._value = _time() - self._start


def fib(n):
    """Reference implementation of fib to confirm that the witness is correct.
    """
    a = b = 1
    for _ in range(n - 1):
        c = a + b
        a = b
        b = c

    return b


value_template = r"""
#include <iostream>

constexpr std::size_t n = {n};

template<std::size_t n>
constexpr std::size_t fib = fib<n - 1> + fib<n - 2>;

template<>
constexpr std::size_t fib<0> = 1;

template<>
constexpr std::size_t fib<1> = 1;

int main() {{
    std::cout << fib<n> << '\n';
    return 0;
}}
"""

struct_template = r"""
#include <iostream>

constexpr std::size_t n = {n};

template<std::size_t n>
struct fib {{
    static constexpr std::size_t value = fib<n - 1>::value + fib<n - 2>::value;
}};

template<>
struct fib<0> {{
    static constexpr std::size_t value = 1;
}};

template<>
struct fib<1> {{
    static constexpr std::size_t value = 1;
}};

int main() {{
    std::cout << fib<n>::value << '\n';
    return 0;
}}
"""


def timed_compile(template, n, *, witness=False):
    """Time how long it takes for gcc to compile fib(n).

    Parameters
    ----------
    template : str
        The source code to compile, formatting in ``n`.
    n : int
        The compile-time argument to fib.
    witness : bool, optional
        Should the result be checked against the Python reference
        implementation?

    Returns
    -------
    time : float
        The time (in seconds) it took to compile fib(n).
    """
    source = template.format(n=n).encode('ascii')

    # -x c++ is needed because we are reading the source from stdin and gcc
    # can't look at the file extension
    args = ['g++', '-std=c++17', '-x', 'c++']
    if not witness:
        # don't write the output to a file if we are not witnessing the result
        args.extend(['-o', '/dev/null'])

    # read source file from stdin
    args.append('-')

    with time() as timer:
        p = subprocess.run(
            args,
            input=source,
            stderr=subprocess.PIPE,
        )
    p.check_returncode()

    if witness:
        p = subprocess.run(['./a.out'], stdout=subprocess.PIPE)
        p.check_returncode()
        witness_value = int(p.stdout.strip())
        expected_value = fib(n)
        if witness_value != expected_value:
            raise ValueError(
                f'witness produced incorrect value: {witness_value} !='
                f' {expected_value}',
            )

        try:
            os.remove('a.out')
        except FileNotFoundError:
            pass

    return timer.value


def profile_compilation(template, n):
    """Profile how long it takes gcc to compile fib(n).

    Parameters
    ----------
    template : str
       The source code to compile, formatting in ``n`.
    n : int
       The compile-time argument to fib.

    Returns
    -------
    median : float
        The median compilation time (in seconds) across 10 runs.
    std : float
        The standard deviation of the compilation time (in seconds) across
        10 runs.
    """
    # witness the result once to ensure we computed the correct value
    times = [timed_compile(template, n, witness=True)]
    # compile 9 more times (total of 10 runs) to get a more significant sample
    times.extend(timed_compile(template, n) for _ in range(9))

    return statistics.median(times), statistics.stdev(times)


def profile_source(name, template):
    print(f'profiling compilation using {name} templates:')
    for n in range(50):
        median, std = profile_compilation(template, n)
        print(
            f'  fib(n={n}):{" " if n < 10 else ""} {median:.2f} +- {std:.3f}'
            ' seconds',
        )


def main():
    profile_source('struct', struct_template)
    profile_source('value', value_template)


if __name__ == '__main__':
    main()

out

profiling compilation using struct templates:
  fib(n=0):  0.29 +- 0.004 seconds
  fib(n=1):  0.29 +- 0.005 seconds
  fib(n=2):  0.29 +- 0.004 seconds
  fib(n=3):  0.29 +- 0.016 seconds
  fib(n=4):  0.29 +- 0.010 seconds
  fib(n=5):  0.29 +- 0.004 seconds
  fib(n=6):  0.29 +- 0.035 seconds
  fib(n=7):  0.34 +- 0.047 seconds
  fib(n=8):  0.36 +- 0.075 seconds
  fib(n=9):  0.30 +- 0.033 seconds
  fib(n=10): 0.31 +- 0.023 seconds
  fib(n=11): 0.30 +- 0.019 seconds
  fib(n=12): 0.29 +- 0.010 seconds
  fib(n=13): 0.29 +- 0.003 seconds
  fib(n=14): 0.29 +- 0.005 seconds
  fib(n=15): 0.29 +- 0.005 seconds
  fib(n=16): 0.30 +- 0.013 seconds
  fib(n=17): 0.29 +- 0.002 seconds
  fib(n=18): 0.30 +- 0.004 seconds
  fib(n=19): 0.29 +- 0.007 seconds
  fib(n=20): 0.29 +- 0.003 seconds
  fib(n=21): 0.30 +- 0.004 seconds
  fib(n=22): 0.29 +- 0.003 seconds
  fib(n=23): 0.40 +- 0.064 seconds
  fib(n=24): 0.33 +- 0.017 seconds
  fib(n=25): 0.34 +- 0.011 seconds
  fib(n=26): 0.42 +- 0.063 seconds
  fib(n=27): 0.30 +- 0.037 seconds
  fib(n=28): 0.30 +- 0.017 seconds
  fib(n=29): 0.29 +- 0.004 seconds
  fib(n=30): 0.30 +- 0.016 seconds
  fib(n=31): 0.31 +- 0.025 seconds
  fib(n=32): 0.30 +- 0.024 seconds
  fib(n=33): 0.30 +- 0.008 seconds
  fib(n=34): 0.30 +- 0.030 seconds
  fib(n=35): 0.32 +- 0.024 seconds
  fib(n=36): 0.39 +- 0.072 seconds
  fib(n=37): 0.30 +- 0.034 seconds
  fib(n=38): 0.35 +- 0.031 seconds
  fib(n=39): 0.30 +- 0.007 seconds
  fib(n=40): 0.30 +- 0.029 seconds
  fib(n=41): 0.30 +- 0.023 seconds
  fib(n=42): 0.30 +- 0.038 seconds
  fib(n=43): 0.30 +- 0.017 seconds
  fib(n=44): 0.29 +- 0.008 seconds
  fib(n=45): 0.30 +- 0.016 seconds
  fib(n=46): 0.29 +- 0.003 seconds
  fib(n=47): 0.29 +- 0.004 seconds
  fib(n=48): 0.30 +- 0.004 seconds
  fib(n=49): 0.29 +- 0.004 seconds
profiling compilation using value templates:
  fib(n=0):  0.29 +- 0.008 seconds
  fib(n=1):  0.30 +- 0.003 seconds
  fib(n=2):  0.29 +- 0.002 seconds
  fib(n=3):  0.29 +- 0.004 seconds
  fib(n=4):  0.30 +- 0.005 seconds
  fib(n=5):  0.29 +- 0.003 seconds
  fib(n=6):  0.30 +- 0.005 seconds
  fib(n=7):  0.30 +- 0.028 seconds
  fib(n=8):  0.29 +- 0.006 seconds
  fib(n=9):  0.29 +- 0.002 seconds
  fib(n=10): 0.30 +- 0.003 seconds
  fib(n=11): 0.29 +- 0.004 seconds
  fib(n=12): 0.29 +- 0.002 seconds
  fib(n=13): 0.30 +- 0.004 seconds
  fib(n=14): 0.30 +- 0.004 seconds
  fib(n=15): 0.29 +- 0.017 seconds
  fib(n=16): 0.29 +- 0.022 seconds
  fib(n=17): 0.29 +- 0.009 seconds
  fib(n=18): 0.29 +- 0.004 seconds
  fib(n=19): 0.32 +- 0.018 seconds
  fib(n=20): 0.36 +- 0.121 seconds
  fib(n=21): 0.30 +- 0.051 seconds
  fib(n=22): 0.30 +- 0.005 seconds
  fib(n=23): 0.37 +- 0.045 seconds
  fib(n=24): 0.39 +- 0.057 seconds
  fib(n=25): 0.33 +- 0.045 seconds
  fib(n=26): 0.43 +- 0.082 seconds
  fib(n=27): 0.39 +- 0.043 seconds
  fib(n=28): 0.32 +- 0.025 seconds
  fib(n=29): 0.30 +- 0.030 seconds
  fib(n=30): 0.33 +- 0.018 seconds
  fib(n=31): 0.31 +- 0.018 seconds
  fib(n=32): 0.30 +- 0.007 seconds
  fib(n=33): 0.30 +- 0.005 seconds
  fib(n=34): 0.30 +- 0.014 seconds
  fib(n=35): 0.29 +- 0.017 seconds
  fib(n=36): 0.29 +- 0.008 seconds
  fib(n=37): 0.29 +- 0.005 seconds
  fib(n=38): 0.30 +- 0.003 seconds
  fib(n=39): 0.30 +- 0.036 seconds
  fib(n=40): 0.30 +- 0.005 seconds
  fib(n=41): 0.29 +- 0.016 seconds
  fib(n=42): 0.34 +- 0.032 seconds
  fib(n=43): 0.30 +- 0.039 seconds
  fib(n=44): 0.29 +- 0.007 seconds
  fib(n=45): 0.30 +- 0.031 seconds
  fib(n=46): 0.30 +- 0.020 seconds
  fib(n=47): 0.30 +- 0.021 seconds
  fib(n=48): 0.30 +- 0.013 seconds
  fib(n=49): 0.29 +- 0.014 seconds