这学期计组实验排到cache参数测量班里好几个人第一反应都是cache长在CPU里又不是一个独立器件怎么能用一段程序把它的大小和cache line长度测出来我当时第一版代码跑出来的数据跟没测一样后来把原理从头捋了一遍才明白这个实验本质上不是“写代码”的实验而是“设计实验”的实验——你得先想清楚cache的行为会怎么影响程序的时间再用时间当尺子去量它。这篇文章就把整套思路、代码以及我踩过的所有坑完整记录下来给正在做计组课设、或者想搞清自己机器缓存结构的同学一份可以直接参考的完整方案。1. 计时测缓存先搞清楚为什么“时间能当尺子”1.1 cache不是黑盒它把数据切成行来缓存处理器访问内存的最小逻辑单位不是字节而是cache line。一个cache line通常是64字节也就是CPU从内存搬数据的时候一次搬回来的一整块数据就是64字节。你读一个int表面上只用了4字节但硬件会把包含这4字节的整条64字节line一起加载到cache里。下次你访问同一个line里的其他字节就直接命中cache不用再碰内存。这个设计依赖一个很朴素的事实程序访问内存存在空间局部性。数组遍历、结构体连续访问、函数栈上的局部变量都是“附近的数据大概率马上会被用到”的典型场景。所以cache line的大小直接决定了空间局部性能被利用到什么程度——line太小加载一次覆盖不了太多未来需要的数据line太大搬运成本高而且可能把用不上的数据也搬进来。业界经过几十年权衡主流x86定在64字节Apple M系列用128字节这就是后面要测的东西。cache的容量同理。L1、L2、L3每一级都是有限的行数按某种映射规则把内存地址对应到固定的组里。当程序访问的数据总量超过某级cache能容纳的行数先前加载进来的line还没等再被访问就被新数据挤出去了。于是每次访问都不得不重新从下一级存储取延迟立刻上一个台阶。1.2 命中与缺失的延迟差是整套实验的测量基础必须在同一时刻明确一件事cache实验能成立依赖的是命中与缺失之间的时间差足够大。如果命中和缺失都是1纳秒那你根本测不出任何东西。以下是一份典型的x86处理器存储层次延迟参考值不同架构会有差异但量级关系基本一致存储层次典型容量访问延迟约对应本实验的现象寄存器几十~几百字节0.3 ns不可直接测量L1 cache32~64 KB1 ns数组小于L1时循环遍历极快L2 cache256 KB~2 MB3~5 ns超过L1后延迟出现一个小台阶L3 cache4~64 MB10~15 ns超过L2后再次上升主存8~64 GB50~100 ns数组超过L3后延迟大幅飙升从表格里能看到L1命中和主存访问的延迟差了一个数量级以上。这个数量级差异意味着只要在程序里循环访问一个数组平均单次访问时间就会随数组大小与cache容量的关系发生肉眼可见的变化。1.3 两种扫描对应两个待测参数本实验要测两个参数方法对应两种“扫描”测cache总容量固定一个跨行步长不断增大数组尺寸观察平均访问延迟什么时候突然上升。数组尺寸超过cache容量时cache装不下整个数组持续发生容量缺失平均延迟跳变。测cache line大小把数组固定在一个远小于L1容量的尺寸然后从1字节开始逐步增大访问步长观察平均访问延迟什么时候突然上升。步长超过cache line长度后每走一步都要跨进一个新的line空间局部性失效每次访问都触发新line加载。两种方法本质是同一件事的两个侧面一个扫容量一个扫粒度。明白了这两条主线代码就只是填空。2. 环境准备用C、用对时钟、把进程钉在一个核上2.1 为什么选C而不是Python这个实验第一忌讳就是用解释型语言做计时核心。Python每执行一次循环都有解释器开销而且对象模型、引用计数、内存分配都会混进访问时间里噪声比要测的cache信号还大。如果你硬要用Python做也不是完全不行但必须用array模块配合memoryview把内层循环交给C实现的numpy向量化操作并且每次只测批量操作的总时间。这等于变相绕开了Python的解释开销但那样做的代码复杂度比C还高调试也更麻烦。直接上C配合gcc编译。编译命令一行gcc -O0 -o cache_probe cache_probe.c-O0非常关键。后面会用volatile关键字阻止优化但实验刚开始阶段-O0能保证你写的循环结构原样保留不会被变换掉。2.2 clock_gettime与绑核高精度计时优先选clock_gettime(CLOCK_MONOTONIC)。它返回纳秒级时间戳走Linux的VDSO机制一次调用开销在几十纳秒量级。我们做的是批量测时不是逐次测时这个开销会被大量循环步数摊薄完全不影响结论。很多人会想到更底层的rdtsc指令直接读CPU周期计数器。能用但有两个前提需要配合lfence/mfence防止CPU乱序执行污染测量窗口必须把进程绑定在固定核上否则线程在不同核心间迁移后读取的TSC可能来自不同核心数值没有可比性。对于课设和日常分析clock_gettime精度已经足够而且不用处理乱序问题。真正要处理的是进程迁移本身——哪怕你用clock_gettime进程从一个核迁到另一个核新核的cache是冷的第一轮访问会全部miss数据直接报废。绑核代码很简单#include sched.h cpu_set_t set; CPU_ZERO(set); CPU_SET(0, set); sched_setaffinity(0, sizeof(set), set);这段代码把当前进程绑定到CPU 0。注意绑核只限制了当前进程如果CPU 0上还有其他负载依然会和你抢核心、抢L1/L2。测的时候最好用htop确认一下目标核心基本空闲。2.3 先读一下系统的标准答案便于对照实验前先看一眼Linux自己记录的cache参数后面测量结果出来了才能判断自己测对了没有。lscpu | grep -i cache更详细的在sysfs里每个CPU核的cache目录下ls /sys/devices/system/cpu/cpu0/cache/ cat /sys/devices/system/cpu/cpu0/cache/index0/size cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_sizeindex0、index1这类编号在不同机器上对应不同的cache层级可以通过cat .../level和cat .../type确认。coherency_line_size就是硬件上报的cache line大小。这些数字不是“标准答案”本身但可以作为校验自己测量结果的参照物。我自己实测下来用下面的方法得到的拐点和sysfs里写的基本吻合误差在一个档次以内。3. 测cache总容量数组尺寸扫描法3.1 实验设计步长、尺寸序列、遍历次数怎么定容量测量的关键变量是数组大小所以要把其他因素全部按住。步长选多少是这个实验第一个容易翻车的点。步长太小比如1字节那么一个cache line加载进来后会被连续访问几十次空间局部性帮了大忙就算数组总量超过cache容量平均延迟也不会明显上升因为每次加载的line都能服务后续多次访问。步长太大比如1024字节则每隔16个line才访问一次相当于数组里只有十六分之一的line被真正使用测出来的“容量”会偏大好几倍。最合理的步长是恰好等于cache line大小。这样每个line只被访问一次既没有空间局部性帮倒忙也不会跳过大量line。主流x86是64字节所以初始版本把步长设为64即可如果你的机器是128字节的line先用第4章的方法测出来再改这个宏。数组尺寸序列从2KB起步一直扫到64MB按2倍递增。太小没有意义因为L1至少也有16KB。太大没必要超过L3容量后已经明显进入主存延迟平台再往后只是浪费时间。每个尺寸重复测量16轮每轮内部把整个数组完整遍历20遍取16轮里的最小值作为该尺寸的最终结果。取最小值而不是平均值是这组实验里非常关键的一个细节。平均值会被中断、系统调度、其他进程干扰拉高而最小值最接近“这个访问模式下硬件能达到的极限速度”对应的是没有外部干扰的理想情况。我对比过同一组数据的平均数和最小值平均数曲线明显更抖有些本来清晰的拐点会被抹平。3.2 容量测量的完整代码#include stdio.h #include stdlib.h #include time.h #include stdint.h #define STEP 64 // 先按64B步长测完line size后可以改 #define REPEAT 16 // 每个尺寸重复16轮 #define ROUNDS 20 // 每轮完整遍历20遍 static double now_ns(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, ts); return ts.tv_sec * 1e9 ts.tv_nsec; } int main(void) { size_t sizes[] { 2*1024, 4*1024, 8*1024, 16*1024, 32*1024, 64*1024, 128*1024, 256*1024, 512*1024, 1024*1024, 2*1024*1024, 4*1024*1024, 8*1024*1024, 16*1024*1024, 32*1024*1024, 64*1024*1024 }; int n sizeof(sizes) / sizeof(sizes[0]); for (int i 0; i n; i) { size_t sz sizes[i]; volatile char *buf (volatile char *)malloc(sz); if (!buf) continue; // 预热让所有页面驻留避免page fault进入计时区间 for (size_t k 0; k sz; k 4096) buf[k] 0; double best 1e18; for (int r 0; r REPEAT; r) { volatile uint64_t sum 0; double t0 now_ns(); for (int round 0; round ROUNDS; round) { for (size_t off 0; off sz; off STEP) { sum buf[off]; } } double t1 now_ns(); double ns_per_step (t1 - t0) / (ROUNDS * (double)(sz / STEP)); if (ns_per_step best) best ns_per_step; } printf(size %7zu KB, best %.3f ns/step\n, sz / 1024, best); free((void *)buf); } return 0; }volatile char *buf是防止编译器优化读取的关键。如果去掉volatile编译器可能认为循环里反复读同一块内存没有意义直接把循环删掉或者只读一次然后复用结果。volatile告诉编译器“这个内存内容随时可能被外部改变必须每次都老老实实访问”从而保留内存访问指令。sum同样声明为volatile uint64_t是为了让累加操作产生真实依赖阻止编译器跳过读取。正常工程代码里不会到处用volatile但在这种“故意制造内存压力”的微基准测试里它是必不可少的存在。3.3 数据怎么读从平台上识别每一级cache在一台常见的x86笔记本上L1 32KB、L2 1.25MB、L3 24MB实测数据大致是下面的趋势数组大小平均每步访问耗时典型值对应状态2 KB ~ 16 KB0.8 ~ 1.0 nsL1命中32 KB1.0 ns接近L1容量上限64 KB ~ 256 KB2.5 ~ 3.5 ns超过L1L2命中512 KB ~ 1 MB3.5 ~ 5.0 nsL2命中但访问密度变大2 MB6 ~ 8 ns接近L2上限4 MB ~ 8 MB10 ~ 15 nsL3命中16 MB ~ 64 MB30 ns 以上主存访问注意这不是标准答案你完全可能测出不同的绝对值。判定方法看相对跳变延迟曲线在某个尺寸区间明显抬升抬升后不再回落到原来的水平这个位置就对应一级cache的容量上限。为什么有的机器上L1到L2的拐点不是那么陡因为cache不是全相联组相联映射下会出现组内冲突数组尺寸略小于L1时也可能有一部分访问发生组冲突缺失导致延迟提前小幅上升。另外现代CPU的硬件预取器会提前把后面的数据拉进cache也会让“超过容量”的现象延迟出现。所以读数据不要追求“延迟突然翻两倍”而是看“出现一个稳定的平台抬升”。多测两轮找稳定重现的那个转折点比纠结具体数字有意义得多。4. 测cache line长度固定数组变步长扫描法4.1 为什么数组要小于L1步长要按2倍递增测line大小比测容量要更精细一点。核心思路是让数组整体常驻L1 cache排除容量因素只观察“跨步”造成的空间局部性变化。数组尺寸必须远小于L1容量。选16KB是因为大多数x86的L1数据cache至少是32KB16KB可以确保整个数组被完整装进L1。如果数组选得比L1还大那每次循环遍历都已经在产生容量缺失步长造成的差异会被掩盖在更高延迟背景里拐点会非常模糊。步长从1字节开始按2的幂递增到1024字节。1、2、4、8、16、32字节都小于64字节的line size所以每次访问都大概率落在已经加载好的line里命中率高单步延迟保持低位。当步长跳变到64字节每走一步就跨进一个全新的line之前加载的line只能服务一次访问空间局部性优势彻底消失延迟立刻抬升。也就是说延迟曲线的第一个明显台阶所在的位置就是cache line的大小。步长上限选择1024字节足够再大只有一个效果内层循环访问次数减少循环指令本身的固定开销占比变大曲线变得不平稳但拐点位置不会变。4.2 line测量代码与典型输出#include stdio.h #include stdlib.h #include time.h #include stdint.h #define SIZE (16 * 1024) // 固定数组远小于L1 #define REPEAT 16 // 每个步长重复16轮 #define ROUNDS 200 // 每轮完整遍历200遍 static double now_ns(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, ts); return ts.tv_sec * 1e9 ts.tv_nsec; } int main(void) { int strides[] {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}; int n sizeof(strides) / sizeof(strides[0]); volatile char *buf (volatile char *)malloc(SIZE); for (size_t k 0; k SIZE; k 4096) buf[k] 0; for (int i 0; i n; i) { int stride strides[i]; double best 1e18; for (int r 0; r REPEAT; r) { volatile uint64_t sum 0; double t0 now_ns(); for (int round 0; round ROUNDS; round) { for (size_t off 0; off SIZE; off stride) { sum buf[off]; } } double t1 now_ns(); double ns_per_step (t1 - t0) / (double)(ROUNDS * (SIZE / stride)); if (ns_per_step best) best ns_per_step; } printf(stride %4d B, best %.3f ns/step\n, stride, best); } free((void *)buf); return 0; }在一台line size为64字节的机器上输出大致是stride 1 B, best 0.512 ns/step stride 2 B, best 0.508 ns/step stride 4 B, best 0.511 ns/step stride 8 B, best 0.515 ns/step stride 16 B, best 0.522 ns/step stride 32 B, best 0.531 ns/step stride 64 B, best 0.786 ns/step stride 128 B, best 0.812 ns/step stride 256 B, best 0.835 ns/step stride 512 B, best 0.859 ns/step stride 1024 B, best 0.881 ns/step注意看从1到32字节单步延迟几乎贴着0.52 ns这条平线走到64字节突然跳到0.78 ns以上后续缓步上升但不再回到低位。那个突然抬升的位置就是你机器上cache line的大小。4.3 拐点判读与和其它途径的对照为什么64字节以后还会有缓慢上升因为步长继续增大后每次访问落在不同4KB内存页的概率更高。跨页访问需要额外的TLB查表开销如果TLB miss还会产生一次页表遍历这些开销虽然不及主存访问但会叠加在结果里。另外更大的步长会让循环总次数减少循环指令本身的固定开销被分摊到更少的步数上单步耗时自然也会稍微变高。这两个因素导致曲线在64B之后缓慢爬升而不是维持水平。判定时要看“第一个台阶”不是“最低点和最高点之间的差”。如果系统里能读到coherency_line_size直接对照cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size我实测出来的台阶位置和这个文件返回的数值是一致的。有些同学的机器上台阶位置在128字节那就是128字节的line不用惊讶Apple的M系列和部分ARM服务器就是这么设计的。测出这个结果的时候你已经比99%只看lscpu输出的人更理解自己机器的存储层次了。5. 这些坑我全踩过按排查顺序列给你5.1 数据结果异常平坦先检查编译器有没有把代码“优化没”我第一次跑容量测量所有尺寸的输出都是0.00几ns曲线完全平坦。第一反应是代码有bug折腾了半天才发现是编译器优化干的。我当时的编译命令是gcc -O2。优化器发现循环里sum buf[off]虽然是读取内存但buf指向的内存从来没有被写连续读同一个地址结果是确定的于是直接把整个内层循环优化成只读一次。这就是为什么实验代码里必须用volatile char *buf并且累加结果sum也要是volatile。排查方法很简单如果所有数据点都小得离谱且几乎相等先检查是不是用了-O1以上的优化级别或者看看生成的汇编里内层循环还在不在objdump -d cache_probe | less如果循环体不见了volatile没加对或者编译器在更高优化级别下仍然做了某种变换。最稳妥的做法是-O0配合volatile双保险。5.2 第一次跑特别慢后面稳定page fault进了计时区间另一个让我困惑的现象是同一个数组大小第一次循环耗时是后面几次的十倍以上取平均后曲线跳得很诡异。原因在于malloc只是分配了虚拟地址空间内存页面还没真正映射到物理内存。第一次访问每个4KB页面时操作系统要触发缺页异常分配物理页、建立页表映射这个开销轻松达到微秒级。一个64MB的数组有16384个页面全部触发一次page fault足以毁掉整段测量数据。解决办法是在计时之前先把整个数组完整走一遍代码里的prefault循环就是在干这件事。只遍历数组不行还得确保每个4KB页面都被触碰过所以prefault用4096字节为步长就足够了。加了这个预热以后正式计时的所有访问都打在已驻留的物理页上page fault不再出现。5.3 同一实验两次结果差30%以上CPU调频和核迁移在捣乱相同参数下两次测量一组数据曲线清晰另一组延迟整体高了30%而且台阶位置往大尺寸方向偏移。这两个现象的元凶分别是动态调频和进程迁移。现代CPU的睿频频率会随负载快速变化。测量L1命中时整个循环极快CPU可能瞬间冲上最高频率导致测出来的ns数偏小但测量主存访问时CPU大部分时间在等待内存频率又掉下去延迟数字被拉大。这样一来不同尺寸之间的延迟差被夸大曲线形态失真。对策分三步正式测试前先跑两轮热身循环让CPU频率先升上来每个尺寸取16轮里的最小值而不是平均值在有条件的情况下把CPU调频策略改成performance模式。注意改系统电源策略需要管理员权限只在自己的开发机上操作实验室公用服务器不要乱动。进程迁移的问题是线程被调度到另一个物理核心后L1/L2里的全部数据作废同时各个核心的TSC时钟可能不同步。即便用clock_gettime不受TSC同步影响冷cache这一条也足以让结果失真。绑核代码加在main函数最前面即可一劳永逸。5.4 大数组延迟不按预期上升硬件预取器在“帮忙”容量测量做到后面发现一个奇怪现象数组都超过L3容量了延迟却没有预期那样飙升到主存级别曲线依然维持在L3延迟附近。这是因为现代CPU有硬件预取器它在检测到顺序访问模式后会自动把接下来要用的line提前搬进cache。预取器对实际程序的性能是福音对cache测量实验则是干扰源。顺序遍历buf[0]、buf[64]、buf[128]……这种规律性极强的访问模式恰好是预取器最容易识别的场景。预取进来的line让缺失延迟被隐藏导致“超过cache容量”的现象被推迟拐点变得不明显。想验证是不是预取器在捣乱可以把顺序访问改成伪随机访问预先打乱一个索引数组然后按下标间接访问缓冲区。随机访问破坏了顺序模式预取器无法预判容量效应立刻显现。代价是额外访问一个索引数组但索引数组可以做得远小于L1不影响主测量。对于课设来说如果顺序遍历已经能看到清晰拐点不必额外做这一步如果曲线平台区分明不明显就值得加上。5.5 测L3曲线一直在抖多核共享缓存被其他进程污染最后一个是测大数组时特有的问题。L3是多个核共享的其他核上的进程也在持续往L3里塞数据相当于你的测试数组和别人的数据抢同一块缓存。结果就是L3这一档的测量曲线抖动非常厉害有时一个尺寸的16轮最小值之间能差两倍。最直接的解决办法是找一台空闲的机器测大数组部分。如果只能在自己笔记本上做至少做到两点用htop观察测试期间其他CPU的负载尽量选一个空闲时段同时只保留绑核运行其他高负载进程能关就关。共享缓存这一层确实不如L1/L2干净但多测几轮取最小值以后趋势还是能稳定下来的。最后说一点做完实验的体会这套实验做完以后再看那些“理论上很美好”的数据结构复杂度分析感觉完全不一样了。复杂度分析假设内存访问代价均匀但真实CPU的cache结构会让“均匀”这个词变成一句空话——一个数组是8KB还是16KB在L1边界上的性能差异可能比算法常数大得多。这个实验的真正价值不在那几条曲线而是建立了“用现象反推硬件结构”的思路。以后你在性能分析工具里看到缓存命中率、cache miss rate这些指标不会再觉得它们是抽象数字而是能联想到一片片物理cache line在CPU里被载入、命中、驱逐的过程。更进一步这套计时探针的思路完全可以扩展用同样的方法可以测TLB有多少项、测组相联的组数、测预取器的触发规则。把试探的思路留下来比背会几个cache参数有用得多。
这学期计组实验排到cache参数测量班里好几个人第一反应都是cache长在CPU里又不是一个独立器件怎么能用一段程序把它的大小和cache line长度测出来我当时第一版代码跑出来的数据跟没测一样后来把原理从头捋了一遍才明白这个实验本质上不是“写代码”的实验而是“设计实验”的实验——你得先想清楚cache的行为会怎么影响程序的时间再用时间当尺子去量它。这篇文章就把整套思路、代码以及我踩过的所有坑完整记录下来给正在做计组课设、或者想搞清自己机器缓存结构的同学一份可以直接参考的完整方案。1. 计时测缓存先搞清楚为什么“时间能当尺子”1.1 cache不是黑盒它把数据切成行来缓存处理器访问内存的最小逻辑单位不是字节而是cache line。一个cache line通常是64字节也就是CPU从内存搬数据的时候一次搬回来的一整块数据就是64字节。你读一个int表面上只用了4字节但硬件会把包含这4字节的整条64字节line一起加载到cache里。下次你访问同一个line里的其他字节就直接命中cache不用再碰内存。这个设计依赖一个很朴素的事实程序访问内存存在空间局部性。数组遍历、结构体连续访问、函数栈上的局部变量都是“附近的数据大概率马上会被用到”的典型场景。所以cache line的大小直接决定了空间局部性能被利用到什么程度——line太小加载一次覆盖不了太多未来需要的数据line太大搬运成本高而且可能把用不上的数据也搬进来。业界经过几十年权衡主流x86定在64字节Apple M系列用128字节这就是后面要测的东西。cache的容量同理。L1、L2、L3每一级都是有限的行数按某种映射规则把内存地址对应到固定的组里。当程序访问的数据总量超过某级cache能容纳的行数先前加载进来的line还没等再被访问就被新数据挤出去了。于是每次访问都不得不重新从下一级存储取延迟立刻上一个台阶。1.2 命中与缺失的延迟差是整套实验的测量基础必须在同一时刻明确一件事cache实验能成立依赖的是命中与缺失之间的时间差足够大。如果命中和缺失都是1纳秒那你根本测不出任何东西。以下是一份典型的x86处理器存储层次延迟参考值不同架构会有差异但量级关系基本一致存储层次典型容量访问延迟约对应本实验的现象寄存器几十~几百字节0.3 ns不可直接测量L1 cache32~64 KB1 ns数组小于L1时循环遍历极快L2 cache256 KB~2 MB3~5 ns超过L1后延迟出现一个小台阶L3 cache4~64 MB10~15 ns超过L2后再次上升主存8~64 GB50~100 ns数组超过L3后延迟大幅飙升从表格里能看到L1命中和主存访问的延迟差了一个数量级以上。这个数量级差异意味着只要在程序里循环访问一个数组平均单次访问时间就会随数组大小与cache容量的关系发生肉眼可见的变化。1.3 两种扫描对应两个待测参数本实验要测两个参数方法对应两种“扫描”测cache总容量固定一个跨行步长不断增大数组尺寸观察平均访问延迟什么时候突然上升。数组尺寸超过cache容量时cache装不下整个数组持续发生容量缺失平均延迟跳变。测cache line大小把数组固定在一个远小于L1容量的尺寸然后从1字节开始逐步增大访问步长观察平均访问延迟什么时候突然上升。步长超过cache line长度后每走一步都要跨进一个新的line空间局部性失效每次访问都触发新line加载。两种方法本质是同一件事的两个侧面一个扫容量一个扫粒度。明白了这两条主线代码就只是填空。2. 环境准备用C、用对时钟、把进程钉在一个核上2.1 为什么选C而不是Python这个实验第一忌讳就是用解释型语言做计时核心。Python每执行一次循环都有解释器开销而且对象模型、引用计数、内存分配都会混进访问时间里噪声比要测的cache信号还大。如果你硬要用Python做也不是完全不行但必须用array模块配合memoryview把内层循环交给C实现的numpy向量化操作并且每次只测批量操作的总时间。这等于变相绕开了Python的解释开销但那样做的代码复杂度比C还高调试也更麻烦。直接上C配合gcc编译。编译命令一行gcc -O0 -o cache_probe cache_probe.c-O0非常关键。后面会用volatile关键字阻止优化但实验刚开始阶段-O0能保证你写的循环结构原样保留不会被变换掉。2.2 clock_gettime与绑核高精度计时优先选clock_gettime(CLOCK_MONOTONIC)。它返回纳秒级时间戳走Linux的VDSO机制一次调用开销在几十纳秒量级。我们做的是批量测时不是逐次测时这个开销会被大量循环步数摊薄完全不影响结论。很多人会想到更底层的rdtsc指令直接读CPU周期计数器。能用但有两个前提需要配合lfence/mfence防止CPU乱序执行污染测量窗口必须把进程绑定在固定核上否则线程在不同核心间迁移后读取的TSC可能来自不同核心数值没有可比性。对于课设和日常分析clock_gettime精度已经足够而且不用处理乱序问题。真正要处理的是进程迁移本身——哪怕你用clock_gettime进程从一个核迁到另一个核新核的cache是冷的第一轮访问会全部miss数据直接报废。绑核代码很简单#include sched.h cpu_set_t set; CPU_ZERO(set); CPU_SET(0, set); sched_setaffinity(0, sizeof(set), set);这段代码把当前进程绑定到CPU 0。注意绑核只限制了当前进程如果CPU 0上还有其他负载依然会和你抢核心、抢L1/L2。测的时候最好用htop确认一下目标核心基本空闲。2.3 先读一下系统的标准答案便于对照实验前先看一眼Linux自己记录的cache参数后面测量结果出来了才能判断自己测对了没有。lscpu | grep -i cache更详细的在sysfs里每个CPU核的cache目录下ls /sys/devices/system/cpu/cpu0/cache/ cat /sys/devices/system/cpu/cpu0/cache/index0/size cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_sizeindex0、index1这类编号在不同机器上对应不同的cache层级可以通过cat .../level和cat .../type确认。coherency_line_size就是硬件上报的cache line大小。这些数字不是“标准答案”本身但可以作为校验自己测量结果的参照物。我自己实测下来用下面的方法得到的拐点和sysfs里写的基本吻合误差在一个档次以内。3. 测cache总容量数组尺寸扫描法3.1 实验设计步长、尺寸序列、遍历次数怎么定容量测量的关键变量是数组大小所以要把其他因素全部按住。步长选多少是这个实验第一个容易翻车的点。步长太小比如1字节那么一个cache line加载进来后会被连续访问几十次空间局部性帮了大忙就算数组总量超过cache容量平均延迟也不会明显上升因为每次加载的line都能服务后续多次访问。步长太大比如1024字节则每隔16个line才访问一次相当于数组里只有十六分之一的line被真正使用测出来的“容量”会偏大好几倍。最合理的步长是恰好等于cache line大小。这样每个line只被访问一次既没有空间局部性帮倒忙也不会跳过大量line。主流x86是64字节所以初始版本把步长设为64即可如果你的机器是128字节的line先用第4章的方法测出来再改这个宏。数组尺寸序列从2KB起步一直扫到64MB按2倍递增。太小没有意义因为L1至少也有16KB。太大没必要超过L3容量后已经明显进入主存延迟平台再往后只是浪费时间。每个尺寸重复测量16轮每轮内部把整个数组完整遍历20遍取16轮里的最小值作为该尺寸的最终结果。取最小值而不是平均值是这组实验里非常关键的一个细节。平均值会被中断、系统调度、其他进程干扰拉高而最小值最接近“这个访问模式下硬件能达到的极限速度”对应的是没有外部干扰的理想情况。我对比过同一组数据的平均数和最小值平均数曲线明显更抖有些本来清晰的拐点会被抹平。3.2 容量测量的完整代码#include stdio.h #include stdlib.h #include time.h #include stdint.h #define STEP 64 // 先按64B步长测完line size后可以改 #define REPEAT 16 // 每个尺寸重复16轮 #define ROUNDS 20 // 每轮完整遍历20遍 static double now_ns(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, ts); return ts.tv_sec * 1e9 ts.tv_nsec; } int main(void) { size_t sizes[] { 2*1024, 4*1024, 8*1024, 16*1024, 32*1024, 64*1024, 128*1024, 256*1024, 512*1024, 1024*1024, 2*1024*1024, 4*1024*1024, 8*1024*1024, 16*1024*1024, 32*1024*1024, 64*1024*1024 }; int n sizeof(sizes) / sizeof(sizes[0]); for (int i 0; i n; i) { size_t sz sizes[i]; volatile char *buf (volatile char *)malloc(sz); if (!buf) continue; // 预热让所有页面驻留避免page fault进入计时区间 for (size_t k 0; k sz; k 4096) buf[k] 0; double best 1e18; for (int r 0; r REPEAT; r) { volatile uint64_t sum 0; double t0 now_ns(); for (int round 0; round ROUNDS; round) { for (size_t off 0; off sz; off STEP) { sum buf[off]; } } double t1 now_ns(); double ns_per_step (t1 - t0) / (ROUNDS * (double)(sz / STEP)); if (ns_per_step best) best ns_per_step; } printf(size %7zu KB, best %.3f ns/step\n, sz / 1024, best); free((void *)buf); } return 0; }volatile char *buf是防止编译器优化读取的关键。如果去掉volatile编译器可能认为循环里反复读同一块内存没有意义直接把循环删掉或者只读一次然后复用结果。volatile告诉编译器“这个内存内容随时可能被外部改变必须每次都老老实实访问”从而保留内存访问指令。sum同样声明为volatile uint64_t是为了让累加操作产生真实依赖阻止编译器跳过读取。正常工程代码里不会到处用volatile但在这种“故意制造内存压力”的微基准测试里它是必不可少的存在。3.3 数据怎么读从平台上识别每一级cache在一台常见的x86笔记本上L1 32KB、L2 1.25MB、L3 24MB实测数据大致是下面的趋势数组大小平均每步访问耗时典型值对应状态2 KB ~ 16 KB0.8 ~ 1.0 nsL1命中32 KB1.0 ns接近L1容量上限64 KB ~ 256 KB2.5 ~ 3.5 ns超过L1L2命中512 KB ~ 1 MB3.5 ~ 5.0 nsL2命中但访问密度变大2 MB6 ~ 8 ns接近L2上限4 MB ~ 8 MB10 ~ 15 nsL3命中16 MB ~ 64 MB30 ns 以上主存访问注意这不是标准答案你完全可能测出不同的绝对值。判定方法看相对跳变延迟曲线在某个尺寸区间明显抬升抬升后不再回落到原来的水平这个位置就对应一级cache的容量上限。为什么有的机器上L1到L2的拐点不是那么陡因为cache不是全相联组相联映射下会出现组内冲突数组尺寸略小于L1时也可能有一部分访问发生组冲突缺失导致延迟提前小幅上升。另外现代CPU的硬件预取器会提前把后面的数据拉进cache也会让“超过容量”的现象延迟出现。所以读数据不要追求“延迟突然翻两倍”而是看“出现一个稳定的平台抬升”。多测两轮找稳定重现的那个转折点比纠结具体数字有意义得多。4. 测cache line长度固定数组变步长扫描法4.1 为什么数组要小于L1步长要按2倍递增测line大小比测容量要更精细一点。核心思路是让数组整体常驻L1 cache排除容量因素只观察“跨步”造成的空间局部性变化。数组尺寸必须远小于L1容量。选16KB是因为大多数x86的L1数据cache至少是32KB16KB可以确保整个数组被完整装进L1。如果数组选得比L1还大那每次循环遍历都已经在产生容量缺失步长造成的差异会被掩盖在更高延迟背景里拐点会非常模糊。步长从1字节开始按2的幂递增到1024字节。1、2、4、8、16、32字节都小于64字节的line size所以每次访问都大概率落在已经加载好的line里命中率高单步延迟保持低位。当步长跳变到64字节每走一步就跨进一个全新的line之前加载的line只能服务一次访问空间局部性优势彻底消失延迟立刻抬升。也就是说延迟曲线的第一个明显台阶所在的位置就是cache line的大小。步长上限选择1024字节足够再大只有一个效果内层循环访问次数减少循环指令本身的固定开销占比变大曲线变得不平稳但拐点位置不会变。4.2 line测量代码与典型输出#include stdio.h #include stdlib.h #include time.h #include stdint.h #define SIZE (16 * 1024) // 固定数组远小于L1 #define REPEAT 16 // 每个步长重复16轮 #define ROUNDS 200 // 每轮完整遍历200遍 static double now_ns(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, ts); return ts.tv_sec * 1e9 ts.tv_nsec; } int main(void) { int strides[] {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}; int n sizeof(strides) / sizeof(strides[0]); volatile char *buf (volatile char *)malloc(SIZE); for (size_t k 0; k SIZE; k 4096) buf[k] 0; for (int i 0; i n; i) { int stride strides[i]; double best 1e18; for (int r 0; r REPEAT; r) { volatile uint64_t sum 0; double t0 now_ns(); for (int round 0; round ROUNDS; round) { for (size_t off 0; off SIZE; off stride) { sum buf[off]; } } double t1 now_ns(); double ns_per_step (t1 - t0) / (double)(ROUNDS * (SIZE / stride)); if (ns_per_step best) best ns_per_step; } printf(stride %4d B, best %.3f ns/step\n, stride, best); } free((void *)buf); return 0; }在一台line size为64字节的机器上输出大致是stride 1 B, best 0.512 ns/step stride 2 B, best 0.508 ns/step stride 4 B, best 0.511 ns/step stride 8 B, best 0.515 ns/step stride 16 B, best 0.522 ns/step stride 32 B, best 0.531 ns/step stride 64 B, best 0.786 ns/step stride 128 B, best 0.812 ns/step stride 256 B, best 0.835 ns/step stride 512 B, best 0.859 ns/step stride 1024 B, best 0.881 ns/step注意看从1到32字节单步延迟几乎贴着0.52 ns这条平线走到64字节突然跳到0.78 ns以上后续缓步上升但不再回到低位。那个突然抬升的位置就是你机器上cache line的大小。4.3 拐点判读与和其它途径的对照为什么64字节以后还会有缓慢上升因为步长继续增大后每次访问落在不同4KB内存页的概率更高。跨页访问需要额外的TLB查表开销如果TLB miss还会产生一次页表遍历这些开销虽然不及主存访问但会叠加在结果里。另外更大的步长会让循环总次数减少循环指令本身的固定开销被分摊到更少的步数上单步耗时自然也会稍微变高。这两个因素导致曲线在64B之后缓慢爬升而不是维持水平。判定时要看“第一个台阶”不是“最低点和最高点之间的差”。如果系统里能读到coherency_line_size直接对照cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size我实测出来的台阶位置和这个文件返回的数值是一致的。有些同学的机器上台阶位置在128字节那就是128字节的line不用惊讶Apple的M系列和部分ARM服务器就是这么设计的。测出这个结果的时候你已经比99%只看lscpu输出的人更理解自己机器的存储层次了。5. 这些坑我全踩过按排查顺序列给你5.1 数据结果异常平坦先检查编译器有没有把代码“优化没”我第一次跑容量测量所有尺寸的输出都是0.00几ns曲线完全平坦。第一反应是代码有bug折腾了半天才发现是编译器优化干的。我当时的编译命令是gcc -O2。优化器发现循环里sum buf[off]虽然是读取内存但buf指向的内存从来没有被写连续读同一个地址结果是确定的于是直接把整个内层循环优化成只读一次。这就是为什么实验代码里必须用volatile char *buf并且累加结果sum也要是volatile。排查方法很简单如果所有数据点都小得离谱且几乎相等先检查是不是用了-O1以上的优化级别或者看看生成的汇编里内层循环还在不在objdump -d cache_probe | less如果循环体不见了volatile没加对或者编译器在更高优化级别下仍然做了某种变换。最稳妥的做法是-O0配合volatile双保险。5.2 第一次跑特别慢后面稳定page fault进了计时区间另一个让我困惑的现象是同一个数组大小第一次循环耗时是后面几次的十倍以上取平均后曲线跳得很诡异。原因在于malloc只是分配了虚拟地址空间内存页面还没真正映射到物理内存。第一次访问每个4KB页面时操作系统要触发缺页异常分配物理页、建立页表映射这个开销轻松达到微秒级。一个64MB的数组有16384个页面全部触发一次page fault足以毁掉整段测量数据。解决办法是在计时之前先把整个数组完整走一遍代码里的prefault循环就是在干这件事。只遍历数组不行还得确保每个4KB页面都被触碰过所以prefault用4096字节为步长就足够了。加了这个预热以后正式计时的所有访问都打在已驻留的物理页上page fault不再出现。5.3 同一实验两次结果差30%以上CPU调频和核迁移在捣乱相同参数下两次测量一组数据曲线清晰另一组延迟整体高了30%而且台阶位置往大尺寸方向偏移。这两个现象的元凶分别是动态调频和进程迁移。现代CPU的睿频频率会随负载快速变化。测量L1命中时整个循环极快CPU可能瞬间冲上最高频率导致测出来的ns数偏小但测量主存访问时CPU大部分时间在等待内存频率又掉下去延迟数字被拉大。这样一来不同尺寸之间的延迟差被夸大曲线形态失真。对策分三步正式测试前先跑两轮热身循环让CPU频率先升上来每个尺寸取16轮里的最小值而不是平均值在有条件的情况下把CPU调频策略改成performance模式。注意改系统电源策略需要管理员权限只在自己的开发机上操作实验室公用服务器不要乱动。进程迁移的问题是线程被调度到另一个物理核心后L1/L2里的全部数据作废同时各个核心的TSC时钟可能不同步。即便用clock_gettime不受TSC同步影响冷cache这一条也足以让结果失真。绑核代码加在main函数最前面即可一劳永逸。5.4 大数组延迟不按预期上升硬件预取器在“帮忙”容量测量做到后面发现一个奇怪现象数组都超过L3容量了延迟却没有预期那样飙升到主存级别曲线依然维持在L3延迟附近。这是因为现代CPU有硬件预取器它在检测到顺序访问模式后会自动把接下来要用的line提前搬进cache。预取器对实际程序的性能是福音对cache测量实验则是干扰源。顺序遍历buf[0]、buf[64]、buf[128]……这种规律性极强的访问模式恰好是预取器最容易识别的场景。预取进来的line让缺失延迟被隐藏导致“超过cache容量”的现象被推迟拐点变得不明显。想验证是不是预取器在捣乱可以把顺序访问改成伪随机访问预先打乱一个索引数组然后按下标间接访问缓冲区。随机访问破坏了顺序模式预取器无法预判容量效应立刻显现。代价是额外访问一个索引数组但索引数组可以做得远小于L1不影响主测量。对于课设来说如果顺序遍历已经能看到清晰拐点不必额外做这一步如果曲线平台区分明不明显就值得加上。5.5 测L3曲线一直在抖多核共享缓存被其他进程污染最后一个是测大数组时特有的问题。L3是多个核共享的其他核上的进程也在持续往L3里塞数据相当于你的测试数组和别人的数据抢同一块缓存。结果就是L3这一档的测量曲线抖动非常厉害有时一个尺寸的16轮最小值之间能差两倍。最直接的解决办法是找一台空闲的机器测大数组部分。如果只能在自己笔记本上做至少做到两点用htop观察测试期间其他CPU的负载尽量选一个空闲时段同时只保留绑核运行其他高负载进程能关就关。共享缓存这一层确实不如L1/L2干净但多测几轮取最小值以后趋势还是能稳定下来的。最后说一点做完实验的体会这套实验做完以后再看那些“理论上很美好”的数据结构复杂度分析感觉完全不一样了。复杂度分析假设内存访问代价均匀但真实CPU的cache结构会让“均匀”这个词变成一句空话——一个数组是8KB还是16KB在L1边界上的性能差异可能比算法常数大得多。这个实验的真正价值不在那几条曲线而是建立了“用现象反推硬件结构”的思路。以后你在性能分析工具里看到缓存命中率、cache miss rate这些指标不会再觉得它们是抽象数字而是能联想到一片片物理cache line在CPU里被载入、命中、驱逐的过程。更进一步这套计时探针的思路完全可以扩展用同样的方法可以测TLB有多少项、测组相联的组数、测预取器的触发规则。把试探的思路留下来比背会几个cache参数有用得多。
