可信测量、原始样本与性能模型

先定义一次测量包含什么

假设你把 reduction 的耗时从 10 毫秒变成 6 毫秒。若旧版本包含分配和数据生成，新版本只计求和，就无法说明算法快了多少。计时边界是实验定义的一部分：端到端时间包含用户真正等待的准备、计算、传输和同步；kernel 时间只描述其中一段。两者都有价值，但不能混用分母。

选择单调时钟 steady_clock 测量经过时间，避免系统校时导致倒退。记录输入规模、数据类型、编译器、优化选项、线程数、设备和电源条件。测试先验证输出，再讨论速度。不能让编译器把没有可观察结果的循环删除，因此结果需进入校验或输出；对非常小的代码仍应检查汇编，必要时采用专门的 benchmark 屏障工具。

warmup 要提前定义

第一次执行可能包含页面首次触碰、缓存预热、动态加载或工具链初始化。先做明确次数的预热可以研究稳态表现，但如果真实用户每次只执行一次，那么首次延迟也必须单独报告。不要看见慢样本后临时决定“这次算预热”，那会把统计变成挑数据。第一个例子用标为教学输入的固定耗时序列练习统计：90 是预先指定的 warmup，之后的 10、11、9、100、10 全部保留。

五个正式样本的中位数是 10，平均值是 28。慢的 100 可能来自调度，也可能是真实尾延迟；未经诊断不能直接丢弃。中位数描述典型样本，均值受长尾影响，p95 在只有五次测量时解释力很有限。应保留原始顺序与样本数，报告离散程度，并在任务需要时增加重复。只报告最小值容易描绘一个用户很少遇到的世界。

可运行测量的诚实边界

iota先填好已有元素，之后才计时（补充，另估15分钟）

26-b的元素类型先读SYS-00 S1固定宽度整数；这里再读输入生成接口。

<numeric>中的std::iota(first,last,value)向已经存在的半开范围逐项赋值，每写一项就把内部value加1；它不返回求和结果，不创建或扩容vector。长度3、初值1时，依次写位置0=1、位置1=2、位置2=3，得到[1,2,3]。空范围不写任何元素。初值自身也会递增，须让当前类型下的递增和目标赋值都符合范围合同，不能只检查最后一个保存值。iota合同

26-b先用数量构造建立100000个元素，再从1ULL填到100000，之后才计求和。ULL是unsigned long long字面量后缀，让本调用的递增值使用该无符号类型；这里的数值与一次后续递增均可表示。这组有界整数的总和100000×100001÷2为5000050000。把长度3的容器改成只reserve(3)而不创建元素，得到的仍是空范围，不会神奇地出现1、2、3。

按已有时间点合同读纳秒样本（补充，另估5分钟）

先复用NET N6的now、时间点差值、duration_cast与count，再读26-b和Reduction Lab的完整计时链。std::chrono::nanoseconds以十亿分之一秒为单位；给定差值是2微秒，转换为纳秒再count得到2000。这个数字只是单位换算，不是本次程序的耗时。输出单位为纳秒也不保证时钟拥有1纳秒分辨率或测量准确度；空输入仍有调用与计时开销，不能预设耗时为0。

第二例实际计时五次 CPU 求和，默认仅输出稳定的样本数和结果校验；传入 --csv 会把真实纳秒样本输出为 CSV。保存方式例如编译后运行 ./26-b --csv > samples.csv。这些样本每次不同，不在教材中伪造固定耗时。这里的输入规模很小，示例用于学习计时与归档机制，不能作为跨机器排名或性能宣传。

把seed、引擎和分布分开记录（补充，另估20分钟）

包含<random>后，std::mt19937 rng(7);建立一个用整数种子7初始化的伪随机引擎。rng保存状态；给同一状态和操作序列，会继续生成确定的结果，不是每次调用都重新从7开始。std::uniform_int_distribution<int> value(-2,2);指定输出int的闭区间[-2,2]，两端都可能出现；value(rng)请求一个样本，并消耗、推进引擎状态。一个样本可能消耗不止一个底层引擎输出，不把两者次数硬绑。引擎、整数分布

先建立5个已有int元素，再对每个元素执行一次x=value(rng)，记录得到的五项。重建另一个种子7的引擎与同样分布，在相同工具链/标准库环境下重做，五项应逐项相同且每项都在[-2,2]；继续用原rng生成下一组则不会自动回到第一组。这里不预写五个跨平台固定答案。一个可直接预测的边界是把分布两端都设成2：五项均为2；空容器执行零次取样，不推进引擎。下限不能大于上限。

Reduction Lab将这组配置换成seed=20260905、闭区间[-1000000,1000000]，读法相同。复现需记录引擎名称、seed、分布参数和标准库环境，并保存实际输入；只给相同seed不保证不同标准库的分布映射产生完全相同的序列。随机用例还要与手写空输入、单元素及范围边界分开保存，iota产生的递增序列也不是随机数据。分布算法的实现范围

下面的完整文件把两组engine和distribution分别命名为first/again、first_value/again_value，都从seed=7和区间[-2,2]开始；两套状态各自推进，逐项检查两组输出相同且没有越界。

#include <cstddef>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::mt19937 first{7};
    std::mt19937 again{7};
    std::uniform_int_distribution<int> first_value{-2, 2};
    std::uniform_int_distribution<int> again_value{-2, 2};
    std::vector<int> values(5);
    std::vector<int> repeated(5);
    bool in_range{true};
    bool same{true};
    for (std::size_t i{0}; i < values.size(); ++i) {
        values[i] = first_value(first);
        repeated[i] = again_value(again);
        if (values[i] < -2 || values[i] > 2 || repeated[i] < -2 || repeated[i] > 2)
            in_range = false;
        if (values[i] != repeated[i]) same = false;
    }
    std::cout << "first:";
    for (int value : values) std::cout << ' ' << value;
    std::cout << "\nagain:";
    for (int value : repeated) std::cout << ' ' << value;
    std::cout << "\ncount=" << values.size() << " repeat=" << same << " in-range=" << in_range << '\n';
    return values.size() == 5 && repeated.size() == 5 && same && in_range ? 0 : 1;
}

下载这份同源seeded-input.cpp。程序输出三行：第一行是first:及五个整数，第二行是again:及五个整数，第三行应为count=5 repeat=1 in-range=1。前两行的五项在本次同实现内逐项相等；本页不固定跨标准库的五个数。最终返回0还要求两组长度都为5、重复与范围检查均通过，不能只看打印了三行就宣布正确。

正式实验要增加规模与重复，报告计时器开销，避免把 sanitizer 运行与优化 release 运行相比较。温度、频率、后台程序与线程亲和性都可能改变结果。改动前后交替测量可以减弱时间漂移影响；固定随机种子保证数据可复现，但也要测试多种分布。

Amdahl 先估算最大收益

若总时间的 80% 可以加速四倍，剩下 20% 不变，新时间比例是 0.2 + 0.8/4 = 0.4，整体加速为 2.5 倍。即使那 80% 无限快，上限也只有 5 倍。这个模型假定问题规模固定、加速比例可信，并没有自动包含线程创建、通信或竞争新增的代价。把这些开销加回总时间，才是实际方案。

Roofline 则比较计算能力与数据搬运能力。算术强度 I 是每搬运一字节执行多少运算，性能上限可写成 min(峰值算力, 带宽 × I)。使用哪层带宽、如何计 FLOP、读写多少字节都必须说明。reduction 通常数据流量大而每元素运算少，因此优化数据移动常比减少一次整数索引更值得优先验证。模型提出上限和假设，真正测量检验这些假设，两者不能互相冒充。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <vector>
int main() {
    const std::vector<double> raw{90,10,11,9,100,10};
    std::vector<double> samples(raw.begin()+1,raw.end());
    const double mean=std::accumulate(samples.begin(),samples.end(),0.0)/static_cast<double>(samples.size());
    std::sort(samples.begin(),samples.end());const double median=samples[samples.size()/2];
    const double speedup=1.0/(0.2+0.8/4.0);
    if(median!=10 || mean!=28 || std::abs(speedup-2.5)>1e-12) throw std::runtime_error("statistics");
    std::cout<<"median="<<median<<" mean="<<mean<<" speedup="<<speedup<<'\n';
}

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 26-a.cpp -o example && ./example

median=10 mean=28 speedup=2.5

#include <chrono>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string_view>
#include <vector>
int main(int argc,char** argv) {
    if(argc>2 || (argc==2 && std::string_view(argv[1])!="--csv")) throw std::invalid_argument("use --csv");
    std::vector<std::uint64_t> values(100000);std::iota(values.begin(),values.end(),1ULL);
    constexpr std::uint64_t baseline=5000050000ULL;
    if(std::accumulate(values.begin(),values.end(),0ULL)!=baseline) throw std::runtime_error("warmup");
    std::vector<long long> samples;std::uint64_t checksum=0;
    for(std::uint64_t trial=0;trial<5;++trial) {
        values[0]=1+trial;
        const auto start=std::chrono::steady_clock::now();
        const auto sum=std::accumulate(values.begin(),values.end(),0ULL);
        const auto stop=std::chrono::steady_clock::now();
        if(sum!=baseline+trial) throw std::runtime_error("sum");
        samples.push_back(std::chrono::duration_cast<std::chrono::nanoseconds>(stop-start).count());
        checksum+=sum;
    }
    if(checksum!=25000250010ULL) throw std::runtime_error("checksum");
    if(argc==2) {
        std::cout<<"trial,elapsed_ns\n";
        for(std::size_t i=0;i<samples.size();++i) std::cout<<i<<','<<samples[i]<<'\n';
    } else std::cout<<"samples="<<samples.size()<<" checksum="<<checksum<<'\n';
}

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 26-b.cpp -o example && ./example

samples=5 checksum=25000250010