Add Python script for benchmarking catch_discover_tests

4 files changed, 411 insertions, 1 deletions

diff --git a/benchmarks/discover_tests/benchmark_discovery.py b/benchmarks/discover_tests/benchmark_discovery.py
new file mode 100644
index 00000000..b3358607
--- /dev/null
+++ b/benchmarks/discover_tests/benchmark_discovery.py
@@ -0,0 +1,200 @@
+#!/usr/bin/env python3
+
+#              Copyright Catch2 Authors
+# Distributed under the Boost Software License, Version 1.0.
+#   (See accompanying file LICENSE.txt or copy at
+#        https://www.boost.org/LICENSE_1_0.txt)
+
+# SPDX-License-Identifier: BSL-1.0
+
+import argparse
+import json
+import os
+import re
+import statistics
+import subprocess
+import sys
+import tempfile
+import time
+
+HERE = os.path.dirname(os.path.abspath(__file__))
+TEMPLATE = os.path.join(HERE, "listing_template.json")
+SHIM = os.path.join(HERE, "copy_shim.cmake")
+COUNTS = [1, 10, 500, 1000, 2000, 4000, 8000]
+#COUNTS = [1, 10, 100]
+REPEATS = 5
+
+def load_template(path: str) -> dict:
+    with open(path, encoding="utf-8") as f:
+        catch_out = json.load(f)
+    if 'listings' not in catch_out or 'tests' not in catch_out['listings']:
+        sys.exit(f"Template '{path}' does not contain the expected 'listings.tests' data")
+
+    return catch_out
+
+
+def synthesize_listing(template_doc: dict, count: int, file) -> str:
+    """Writes JSON listing with exactly `count` test cases into `file`.
+
+    The template entries are cycled through, and each name is made unique by
+    appending an index, so that every registered CTest test has a distinct name.
+    """
+    doc_copy = template_doc.copy()
+    template_tests = template_doc['listings']['tests']
+    num_original = len(template_tests)
+
+    out_tests = []
+    for i in range(count):
+        entry = template_tests[i % num_original].copy()
+        entry["name"] = f"{entry['name']} #{i // num_original}"
+        out_tests.append(entry)
+
+    doc_copy['listings']['tests'] = out_tests
+
+    # indent=2 matches Catch2's pretty printing
+    json.dump(doc_copy, file, indent=2)
+    file.write('\n')
+
+
+def build_command(args, listing_path: str, ctest_file: str, add_tags: bool) -> list[str]:
+    # The executor needs to be a CMake list, so it has to be separated by ';'
+    executor = ";".join(['cmake', f"-DBENCH_LISTING={listing_path}", "-P", SHIM, "--"])
+    return [
+        'cmake',
+        "-DTEST_TARGET=benchmark",
+        f"-DTEST_EXECUTABLE={listing_path}",
+        f"-DTEST_EXECUTOR={executor}",
+        f"-DTEST_WORKING_DIR={os.path.dirname(ctest_file)}",
+        f"-DCTEST_FILE={ctest_file}",
+        f"-DADD_TAGS_AS_LABELS={'TRUE' if add_tags else 'FALSE'}",
+        "-P",
+        args.script,
+    ]
+
+
+def run_once(cmd: list[str]) -> float:
+    start = time.monotonic()
+    result = subprocess.run(cmd, capture_output=True, text=True)
+    elapsed = time.monotonic() - start
+    if result.returncode != 0:
+        sys.stderr.write("Benchmark invocation failed:\n")
+        sys.stderr.write(f"  cmd: {' '.join(cmd)}\n")
+        sys.stderr.write(f"  stdout: {result.stdout}\n")
+        sys.stderr.write(f"  stderr: {result.stderr}\n")
+        sys.exit(1)
+    return elapsed
+
+
+def verify_output(ctest_file: str, count: int, add_tags: bool):
+    """Sanity-check the generated CTest script and return its add_test count."""
+    with open(ctest_file, encoding="utf-8") as f:
+        content = f.read()
+    add_test_lines = sum(1 for line in content.splitlines() if line.startswith("add_test("))
+    if add_test_lines != count:
+        sys.exit(
+            f"Sanity check failed: expected {count} add_test() lines, "
+            f"found {add_test_lines} in {ctest_file}"
+        )
+    if add_tags and count > 0 and "LABELS" not in content:
+        sys.exit(
+            f"Sanity check failed: ADD_TAGS_AS_LABELS was on but no LABELS found "
+            f"in {ctest_file}"
+        )
+
+
+def cmake_version() -> str:
+    stdout = subprocess.run(
+        ['cmake', "--version"], capture_output=True, text=True, check=True
+    ).stdout
+    match = re.match("cmake version (.+)", stdout)
+    return match.group(1)
+
+
+def print_table(counts, tag_modes, results):
+    timing_by_ct = {(count, tags): median_time for (count, tags, median_time) in results}
+
+    headers = ["N"]
+    if False in tag_modes:
+        headers.append("tags:off")
+    if True in tag_modes:
+        headers.append("tags:on")
+
+    def fmt_cell(count, tags_on):
+        median_time = timing_by_ct[(count, tags_on)]
+        return f"{median_time:8.1f} ms"
+
+    # Header
+    row = f"{headers[0]:>6}"
+    if False in tag_modes:
+        row += f"  {headers[1]:>14}"
+    if True in tag_modes:
+        row += f"  {headers[2]:>14}"
+ 
+    print()
+    print("-" * len(row))
+    print(row)
+    print("-" * len(row))
+
+    for count in counts:
+        row = f"{count:>6}"
+        if False in tag_modes:
+            row += f"  {fmt_cell(count, False):>14}"
+        if True in tag_modes:
+            row += f"  {fmt_cell(count, True):>14}"
+        print(row)
+
+
+def main():
+    parser = argparse.ArgumentParser(
+        description="Benchmark the CMake-side cost of catch_discover_tests."
+    )
+    parser.add_argument(
+        "--script",
+        required=True,
+        help="Path to the CatchAddTests.cmake to benchmark.",
+    )
+    args = parser.parse_args()
+
+    if not os.path.exists(args.script):
+        sys.exit(f"Script to benchmark '{args.script}' does not exist")
+    if not os.path.exists(SHIM):
+        sys.exit(f"Copy-shim '{SHIM}' does not exist")
+
+    tag_modes = [False, True]
+
+    template_doc = load_template(TEMPLATE)
+
+    print(f"Benchmarking:  {os.path.abspath(args.script)}")
+    print(f"CMake version: {cmake_version()}")
+    print(f"Ns:            {COUNTS}")
+    print(f"Repeats:       {REPEATS}")
+    print()
+
+
+    results = []  # (count, tags_on, median_ms)
+    with tempfile.TemporaryDirectory() as workdir:
+        os.makedirs(workdir, exist_ok=True)
+        for count in COUNTS:
+            listing_path = os.path.join(workdir, f"listing-{count}.json")
+            with open(listing_path, "w", encoding="utf-8") as f:
+                synthesize_listing(template_doc, count, f)
+
+            for add_tags in tag_modes:
+                mode = "on" if add_tags else "off"
+                ctest_file = os.path.join(workdir, f"ctest-{count}-{mode}.cmake")
+                cmd = build_command(args, listing_path, ctest_file, add_tags)
+
+                # Untimed warmup run (populates any filesystem/OS caches).
+                run_once(cmd)
+                verify_output(ctest_file, count, add_tags)
+
+                timings = [run_once(cmd) for _ in range(REPEATS)]
+                median_ms = statistics.median(timings) * 1000.0
+                results.append((count, add_tags, median_ms))
+            print(f'N = {count} done in ~{len(tag_modes) * sum(timings):.2f} s')
+
+    print_table(COUNTS, tag_modes, results)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/benchmarks/discover_tests/copy_shim.cmake b/benchmarks/discover_tests/copy_shim.cmake
new file mode 100644
index 00000000..d1babc1b
--- /dev/null
+++ b/benchmarks/discover_tests/copy_shim.cmake
@@ -0,0 +1,40 @@
+# SPDX-License-Identifier: BSL-1.0
+
+# Fake Catch2 binary used by benchmark_discovery.py.
+#
+# catch_discover_tests_impl discovers tests by running
+#
+#     ${TEST_EXECUTOR} "${TEST_EXECUTABLE}" ... --list-tests --reporter json --out <file>
+#
+# and then reading the JSON listing back from <file>. This script fakes
+# being Catch2 binary by taking the fake JSON listing prepared by
+# `benchmark_discovery.py` and copying it over to the file path specified
+# after the `--out` argument.
+#
+# The fake JSON listing is passed as BENCH_LISTING CMake argument.
+
+if(NOT DEFINED BENCH_LISTING)
+  message(FATAL_ERROR "copy_shim: BENCH_LISTING is not set")
+endif()
+if(NOT EXISTS "${BENCH_LISTING}")
+  message(FATAL_ERROR "copy_shim: BENCH_LISTING '${BENCH_LISTING}' does not exist")
+endif()
+
+
+# FIXME: better handling of bad --out
+# Find the "--out <file>" argument pair among the forwarded arguments.
+set(_out_file "")
+math(EXPR _last "${CMAKE_ARGC} - 1")
+foreach(_i RANGE 0 ${_last})
+  if("${CMAKE_ARGV${_i}}" STREQUAL "--out")
+    math(EXPR _next "${_i} + 1")
+    set(_out_file "${CMAKE_ARGV${_next}}")
+    break()
+  endif()
+endforeach()
+
+if(_out_file STREQUAL "")
+  message(FATAL_ERROR "copy_shim: could not find '--out <file>' in arguments")
+endif()
+
+file(COPY_FILE "${BENCH_LISTING}" "${_out_file}")
diff --git a/benchmarks/discover_tests/listing_template.json b/benchmarks/discover_tests/listing_template.json
new file mode 100644
index 00000000..43861ffd
--- /dev/null
+++ b/benchmarks/discover_tests/listing_template.json
@@ -0,0 +1,134 @@
+{
+  "version": 1,
+  "metadata": {
+    "name": "benchmark-template",
+    "catch2-version": "3.15.2"
+  },
+  "listings": {
+    "tests": [
+      {
+        "name": "Comparing function pointers",
+        "class-name": "",
+        "tags": [
+          "function pointer",
+          "Tricky"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/Tricky.tests.cpp",
+          "line": 266
+        }
+      },
+      {
+        "name": "Testing checked-if 4",
+        "class-name": "",
+        "tags": [
+          "!shouldfail",
+          "checked-if"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/Misc.tests.cpp",
+          "line": 216
+        }
+      },
+      {
+        "name": "count_equidistant_floats - double",
+        "class-name": "",
+        "tags": [
+          "approvals",
+          "distance",
+          "floating-point"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/IntrospectiveTests/FloatingPoint.tests.cpp",
+          "line": 103
+        }
+      },
+      {
+        "name": "Usage of AllTrue range matcher",
+        "class-name": "",
+        "tags": [
+          "matchers",
+          "quantifiers",
+          "templated"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/MatchersRanges.tests.cpp",
+          "line": 372
+        }
+      },
+      {
+        "name": "Exception matchers that succeed",
+        "class-name": "",
+        "tags": [
+          "!throws",
+          "exceptions",
+          "matchers"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/Matchers.tests.cpp",
+          "line": 428
+        }
+      },
+      {
+        "name": "A TEMPLATE_TEST_CASE_METHOD based test run that succeeds - float",
+        "class-name": "Template_Fixture",
+        "tags": [
+          "class",
+          "template"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/Class.tests.cpp",
+          "line": 82
+        }
+      },
+      {
+        "name": "Approximate PI",
+        "class-name": "",
+        "tags": [
+          "Approx",
+          "PI"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/Approx.tests.cpp",
+          "line": 134
+        }
+      },
+      {
+        "name": "TextFlow::Column respects width setting",
+        "class-name": "",
+        "tags": [
+          "approvals",
+          "column",
+          "TextFlow"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/IntrospectiveTests/TextFlow.tests.cpp",
+          "line": 38
+        }
+      },
+      {
+        "name": "Generators internals",
+        "class-name": "",
+        "tags": [
+          "generators",
+          "internals"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/IntrospectiveTests/GeneratorsImpl.tests.cpp",
+          "line": 24
+        }
+      },
+      {
+        "name": "Mayfail test case with nested sections",
+        "class-name": "",
+        "tags": [
+          "!mayfail"
+        ],
+        "source-location": {
+          "filename": "/mnt/c/ubuntu/Catch2/tests/SelfTest/UsageTests/Condition.tests.cpp",
+          "line": 83
+        }
+      }
+    ]
+  }
+}
diff --git a/benchmarks/readme.md b/benchmarks/readme.md
index 9ef82532..52d557c5 100644
--- a/benchmarks/readme.md
+++ b/benchmarks/readme.md
@@ -56,9 +56,9 @@ _Note that we redirect the output to `/dev/null` to reduce the overhead of the a
 
 TODO:
   * Start empty binary (set up cost base)
-  * Start binary with X (100/1k/10k) tests (test registration cost)
   * Section tracking
 
+
 ## Compilation benchmarks
 
 As tests are often iterated upon and relinked, the compilation cost of
@@ -79,3 +79,39 @@ hyperfine --warmup 2 --parameter-list version old,vas --prepare 'find ~/benches/
 
 TODO:
   * Link-only recipe
+
+
+## Misc. benchmarks
+
+### `catch_discover_tests`
+
+The first JSON-based implementation of `catch_discover_tests` turned out
+to have quadratic complexity in number of tests, which meant that registering
+say 1k test cases took ~4s , and it became unusably slow with larger
+test suites.
+
+To prevent backsliding, and enable future optimizations, there is now
+a benchmarking script for `catch_discover_tests` in the `discover_tests`
+directory.
+
+`discover_tests/benchmark_discovery.py` runs the real `catch_discover_tests`
+implementation (through CMake script-mode) on a synthesized JSON listing
+(generated from `discover_tests/listing_template.json`) through an executor
+shim (`discover_tests/copy_shim.cmake`). This means it can run even without
+real test binary.
+
+If the JSON output from Catch2 changes, the synthesized JSON listing
+can be updated by taking a real listing from `SelfTest` binary, and pruning
+it down to keep only ~10 entries.
+
+
+#### Examples
+
+**Benchmark the current `catch_discover_tests`, with and without tags-as-labels**
+```text
+./benchmarks/discover_tests/benchmark_discovery.py --script ./extras/CatchAddTests.cmake
+```
+
+Note that 8k test cases is unrealistically high, but still useful to see scaling.
+Benchmark for single test case is useful to provide estimate of the flat
+overhead from using `catch_discover_tests` at all.