Inside Bitcoin

2251        } else {
2252            mNumIters = mBench.minEpochIterations();
2253            mState = State::upscaling_runtime;
2254        }
2255    }
2256
2257    // directly calculates new iters based on elapsed&iters, and adds a 10% noise. Makes sure we don't underflow.
2258    ANKERL_NANOBENCH(NODISCARD) uint64_t calcBestNumIters(std::chrono::nanoseconds elapsed, uint64_t iters) noexcept {
2259        auto doubleElapsed = d(elapsed);
2260        auto doubleTargetRuntimePerEpoch = d(mTargetRuntimePerEpoch);
2261        auto doubleNewIters = doubleTargetRuntimePerEpoch / doubleElapsed * d(iters);
2262
2263        auto doubleMinEpochIters = d(mBench.minEpochIterations());
2264        if (doubleNewIters < doubleMinEpochIters) {
2265            doubleNewIters = doubleMinEpochIters;
2266        }
2267        doubleNewIters *= 1.0 + 0.2 * mRng.uniform01();
2268
2269        // +0.5 for correct rounding when casting
2270        // NOLINTNEXTLINE(bugprone-incorrect-roundings)
2271        return static_cast<uint64_t>(doubleNewIters + 0.5);
2272    }
2273
2274    ANKERL_NANOBENCH_NO_SANITIZE("integer", "undefined") void upscale(std::chrono::nanoseconds elapsed) {
2275        if (elapsed * 10 < mTargetRuntimePerEpoch) {
2276            // we are far below the target runtime. Multiply iterations by 10 (with overflow check)
2277            if (mNumIters * 10 < mNumIters) {
2278                // overflow :-(
2279                showResult("iterations overflow. Maybe your code got optimized away?");
2280                mNumIters = 0;
2281                return;
2282            }
2283            mNumIters *= 10;
2284        } else {
2285            mNumIters = calcBestNumIters(elapsed, mNumIters);
2286        }
2287    }
2288
2289    void add(std::chrono::nanoseconds elapsed, PerformanceCounters const& pc) noexcept {
2290#    if defined(ANKERL_NANOBENCH_LOG_ENABLED)
2291        auto oldIters = mNumIters;
2292#    endif
2293
2294        switch (mState) {
2295        case State::warmup:
2296            if (isCloseEnoughForMeasurements(elapsed)) {
2297                // if elapsed is close enough, we can skip upscaling and go right to measurements
2298                // still, we don't add the result to the measurements.
2299                mState = State::measuring;
2300                mNumIters = calcBestNumIters(elapsed, mNumIters);
2301            } else {
2302                // not close enough: switch to upscaling
2303                mState = State::upscaling_runtime;
2304                upscale(elapsed);
2305            }
2306            break;
2307
2308        case State::upscaling_runtime:
2309            if (isCloseEnoughForMeasurements(elapsed)) {
2310                // if we are close enough, add measurement and switch to always measuring
2311                mState = State::measuring;
2312                mTotalElapsed += elapsed;
2313                mTotalNumIters += mNumIters;
2314                mResult.add(elapsed, mNumIters, pc);
2315                mNumIters = calcBestNumIters(mTotalElapsed, mTotalNumIters);
2316            } else {
2317                upscale(elapsed);
2318            }
2319            break;
2320
2321        case State::measuring:
2322            // just add measurements - no questions asked. Even when runtime is low. But we can't ignore
2323            // that fluctuation, or else we would bias the result
2324            mTotalElapsed += elapsed;
2325            mTotalNumIters += mNumIters;
2326            mResult.add(elapsed, mNumIters, pc);
2327            if (0 != mBench.epochIterations()) {
2328                mNumIters = mBench.epochIterations();
2329            } else {
2330                mNumIters = calcBestNumIters(mTotalElapsed, mTotalNumIters);
2331            }
2332            break;
2333
2334        case State::endless:
2335            mNumIters = (std::numeric_limits<uint64_t>::max)();
2336            break;
2337        }
2338
2339        if (static_cast<uint64_t>(mResult.size()) == mBench.epochs()) {
2340            // we got all the results that we need, finish it
2341            showResult("");
2342            mNumIters = 0;
2343        }
2344
2345        ANKERL_NANOBENCH_LOG(mBench.name() << ": " << detail::fmt::Number(20, 3, d(elapsed.count())) << " elapsed, "
2346                                           << detail::fmt::Number(20, 3, d(mTargetRuntimePerEpoch.count())) << " target. oldIters="
2347                                           << oldIters << ", mNumIters=" << mNumIters << ", mState=" << static_cast<int>(mState));
2348    }
2349
2350    // NOLINTNEXTLINE(readability-function-cognitive-complexity)
2351    void showResult(std::string const& errorMessage) const {
2352        ANKERL_NANOBENCH_LOG(errorMessage);
2353
2354        if (mBench.output() != nullptr) {
2355            // prepare column data ///////
2356            std::vector<fmt::MarkDownColumn> columns;
2357
2358            auto rMedian = mResult.median(Result::Measure::elapsed);
2359
2360            if (mBench.relative()) {
2361                double d = 100.0;
2362                if (!mBench.results().empty()) {
2363                    d = rMedian <= 0.0 ? 0.0 : mBench.results().front().median(Result::Measure::elapsed) / rMedian * 100.0;
2364                }
2365                columns.emplace_back(11, 1, "relative", "%", d);
2366            }
2367
2368            if (mBench.complexityN() > 0) {
2369                columns.emplace_back(14, 0, "complexityN", "", mBench.complexityN());
2370            }
2371
2372            columns.emplace_back(22, 2, mBench.timeUnitName() + "/" + mBench.unit(), "",
2373                                 rMedian / (mBench.timeUnit().count() * mBench.batch()));
2374            columns.emplace_back(22, 2, mBench.unit() + "/s", "", rMedian <= 0.0 ? 0.0 : mBench.batch() / rMedian);
2375
2376            double const rErrorMedian = mResult.medianAbsolutePercentError(Result::Measure::elapsed);
2377            columns.emplace_back(10, 1, "err%", "%", rErrorMedian * 100.0);
2378
2379            double rInsMedian = -1.0;
2380            if (mBench.performanceCounters() && mResult.has(Result::Measure::instructions)) {
2381                rInsMedian = mResult.median(Result::Measure::instructions);
2382                columns.emplace_back(18, 2, "ins/" + mBench.unit(), "", rInsMedian / mBench.batch());
2383            }
2384
2385            double rCycMedian = -1.0;
2386            if (mBench.performanceCounters() && mResult.has(Result::Measure::cpucycles)) {
2387                rCycMedian = mResult.median(Result::Measure::cpucycles);
2388                columns.emplace_back(18, 2, "cyc/" + mBench.unit(), "", rCycMedian / mBench.batch());
2389            }
2390            if (rInsMedian > 0.0 && rCycMedian > 0.0) {
2391                columns.emplace_back(9, 3, "IPC", "", rCycMedian <= 0.0 ? 0.0 : rInsMedian / rCycMedian);
2392            }
2393            if (mBench.performanceCounters() && mResult.has(Result::Measure::branchinstructions)) {
2394                double const rBraMedian = mResult.median(Result::Measure::branchinstructions);
2395                columns.emplace_back(17, 2, "bra/" + mBench.unit(), "", rBraMedian / mBench.batch());
2396                if (mResult.has(Result::Measure::branchmisses)) {
2397                    double p = 0.0;
2398                    if (rBraMedian >= 1e-9) {
2399                        p = 100.0 * mResult.median(Result::Measure::branchmisses) / rBraMedian;
2400                    }
2401                    columns.emplace_back(10, 1, "miss%", "%", p);
2402                }
2403            }
2404
2405            columns.emplace_back(12, 2, "total", "", mResult.sumProduct(Result::Measure::iterations, Result::Measure::elapsed));
2406
2407            // write everything
2408            auto& os = *mBench.output();
2409
2410            // combine all elements that are relevant for printing the header
2411            uint64_t hash = 0;
2412            hash = hash_combine(std::hash<std::string>{}(mBench.unit()), hash);
2413            hash = hash_combine(std::hash<std::string>{}(mBench.title()), hash);
2414            hash = hash_combine(std::hash<std::string>{}(mBench.timeUnitName()), hash);
2415            hash = hash_combine(std::hash<double>{}(mBench.timeUnit().count()), hash);
2416            hash = hash_combine(std::hash<bool>{}(mBench.relative()), hash);
2417            hash = hash_combine(std::hash<bool>{}(mBench.performanceCounters()), hash);
2418
2419            if (hash != singletonHeaderHash()) {
2420                singletonHeaderHash() = hash;
2421
2422                // no result yet, print header
2423                os << std::endl;
2424                for (auto const& col : columns) {
2425                    os << col.title();
2426                }
2427                os << "| " << mBench.title() << std::endl;
2428
2429                for (auto const& col : columns) {
2430                    os << col.separator();
2431                }
2432                os << "|:" << std::string(mBench.title().size() + 1U, '-') << std::endl;
2433            }
2434
2435            if (!errorMessage.empty()) {
2436                for (auto const& col : columns) {
2437                    os << col.invalid();
2438                }
2439                os << "| :boom: " << fmt::MarkDownCode(mBench.name()) << " (" << errorMessage << ')' << std::endl;
2440            } else {
2441                for (auto const& col : columns) {
2442                    os << col.value();
2443                }
2444                os << "| ";
2445                auto showUnstable = isWarningsEnabled() && rErrorMedian >= 0.05;
2446                if (showUnstable) {
2447                    os << ":wavy_dash: ";
2448                }
2449                os << fmt::MarkDownCode(mBench.name());
2450                if (showUnstable) {
2451                    auto avgIters = d(mTotalNumIters) / d(mBench.epochs());
2452                    // NOLINTNEXTLINE(bugprone-incorrect-roundings)
2453                    auto suggestedIters = static_cast<uint64_t>(avgIters * 10 + 0.5);
2454
2455                    os << " (Unstable with ~" << detail::fmt::Number(1, 1, avgIters)
2456                       << " iters. Increase `minEpochIterations` to e.g. " << suggestedIters << ")";
2457                }
2458                os << std::endl;
2459            }
2460        }
2461    }
2462
2463    ANKERL_NANOBENCH(NODISCARD) bool isCloseEnoughForMeasurements(std::chrono::nanoseconds elapsed) const noexcept {
2464        return elapsed * 3 >= mTargetRuntimePerEpoch * 2;
2465    }
2466
2467    uint64_t mNumIters = 1;                            // NOLINT(misc-non-private-member-variables-in-classes)
2468    Bench const& mBench;                               // NOLINT(misc-non-private-member-variables-in-classes)
2469    std::chrono::nanoseconds mTargetRuntimePerEpoch{}; // NOLINT(misc-non-private-member-variables-in-classes)
2470    Result mResult;                                    // NOLINT(misc-non-private-member-variables-in-classes)
2471    Rng mRng{123};                                     // NOLINT(misc-non-private-member-variables-in-classes)
2472    std::chrono::nanoseconds mTotalElapsed{};          // NOLINT(misc-non-private-member-variables-in-classes)
2473    uint64_t mTotalNumIters = 0;                       // NOLINT(misc-non-private-member-variables-in-classes)
2474    State mState = State::upscaling_runtime;           // NOLINT(misc-non-private-member-variables-in-classes)
2475};
2476ANKERL_NANOBENCH(IGNORE_PADDED_POP)
2477
2478IterationLogic::IterationLogic(Bench const& bench)
2479    : mPimpl(new Impl(bench)) {}
2480
2481IterationLogic::~IterationLogic() {
2482    delete mPimpl;
2483}
2484
2485uint64_t IterationLogic::numIters() const noexcept {
2486    ANKERL_NANOBENCH_LOG(mPimpl->mBench.name() << ": mNumIters=" << mPimpl->mNumIters);
2487    return mPimpl->mNumIters;
2488}
2489
2490void IterationLogic::add(std::chrono::nanoseconds elapsed, PerformanceCounters const& pc) noexcept {
2491    mPimpl->add(elapsed, pc);
2492}
2493
2494void IterationLogic::moveResultTo(std::vector<Result>& results) noexcept {
2495    results.emplace_back(std::move(mPimpl->mResult));
2496}
2497
2498#    if ANKERL_NANOBENCH(PERF_COUNTERS)
2499
2500ANKERL_NANOBENCH(IGNORE_PADDED_PUSH)