SUBCASE in a loop became quadratic in v2.5.x

A SUBCASE inside a loop is much slower in the 2.5.x line than in 2.4.12. In our test suite one binary went from 112 s to 2420 s.

The cause is TraversalState::tryEnterSubcase, introduced by #1056 (commit c2717dc9, released in v2.5.0). It finds a sibling by scanning the decision point linearly and the comparison itself is costly.

Affected versions

Good in v2.4.12. Regressed in v2.5.0, v2.5.1, v2.5.2, v2.5.3 and current dev.

Suggested fix

Adding an index beside the vector:

struct DecisionPoint {
    std::vector<SubcaseSignature> subcases;              // source order, unchanged
    std::unordered_map<SubcaseSignature, size_t> index;  // signature -> position
    size_t branch_count;
};

tryEnterSubcase then becomes a lookup, with push_back plus an insert on first sight, and branch_count stays subcases.size(). This requires to reintroduce the hash() helpers over m_line, m_file and m_name. I would suggest to cache that hash in the signature at construction.

Since this is about performance, you could also optimize the following when touching it anyway:

1. Compare m_file by pointer before falling back to strcmp. They share same __FILE__ literals that should live under the same address.
2. Compare m_name before m_file it is cheaper and more likely a false.

Note on measurements

• Nothing in scripts/bench/tests.json uses SUBCASE. That is probably why it slipped through.
• In #1047 GENERATE was reported to be roughly 5x faster than a varying-name SUBCASE at run time. This number should probably be rechecked against 2.4.12.

Steps to reproduce

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <doctest/doctest.h>

// Vary N over 64, 128, 256, 512. Assertions per leaf are constant, so only the
// subcase bookkeeping changes.
constexpr int N = 256;

TEST_CASE("loop generated subcases") {
    for (int i = 0; i < N; ++i) {
        SUBCASE(doctest::toString(i).c_str()) {
            CHECK(i >= 0);
        }
    }
}

Build the same file against 2.4.12 and against 2.5.3 and time the binary. Wall time grows with roughly the cube of N on 2.5.x and the square of N on 2.4.12. If it is compiled on a long absolute path, it is even worse.

doctest version

2.5.3

Operating system

Linux, macOS

Architecture

ARM, x86

Compiler

clang-20

Context

No response