为了优化并发链表访问，我尝试对 x86_64 中取消引用所需的平均时间进行基准测试（我的特定处理器是 Ryzen）。
虽然我知道每条指令一个周期的美好时光已经一去不复返了，但我并没有怀疑我会从基准测试中得到什么，而且我感到非常惊讶！
结果表明：
很明显，事情没有按预期进行，而且至少据我所知，在编程时几乎没有人考虑这些因素。
我的问题是一个非常具体的编程问题：
继续使用我的处理器（AMD或Intel x86_64架构）并继续使用我的操作系统（Ubuntu），我是否有可能运行上述测试并且能够解引用最多比3.6周期慢10倍，而不是基准测试显示慢了 110 倍？ 不惜一切代价去做！！！
很明显，数据分散在大内存空间上的结构是频繁且必要的，因此应该找到一种解决方案，能够在不出现上述 110 倍慢的极端延迟的情况下取消引用内存。
以下是实现上述基准测试并显示结果的代码。
https://godbolt.org/z/9GEWe4cdd
#include <iostream>
#include <iomanip>
#include <cstdint>
#define repeat_0x10(x) x x x x x x x x x x x x x x x x
#define repeat_0x100(x) repeat_0x10(repeat_0x10(x))
#define repeat_0x1000(x) repeat_0x100(repeat_0x10(x))
const int loopn=0x4000;
#define asmTimes 0x100
#define tt(x) repeat_0x100(x)
#include <x86intrin.h>
#include <unistd.h>
using namespace std;
int64_t aaa=0x0;
typedef void fT();
// given a function the bench0 executes it for n times returning the number of processor clock ticks that were necessary to execute it.
// morover before hand it loads the register R15 with the address of variable aaa
auto bench0(fT f,size_t n=loopn){
auto s1=__rdtsc();
asm ("lea %0,%%r15" : : "m" (aaa));
for(int i=n;i--!=0;) f();
auto s2=__rdtsc();
return s2-s1;
}
// given a function formed from rep number of repetitions of code, it loops over it for n times and returns a float giving the number of clocks necessary for each single repeated code.
auto bench(fT f,size_t n=loopn,size_t rep=asmTimes){
return (float)bench0(f,n)/n/rep;
}
#define countof(A) (sizeof(A)/sizeof(*A))
void* P[0x1000000];
// a linked list is formed, sequential entries in the linked list are distant "step"
void initP(size_t step){
void* p=nullptr;
for(size_t i=0;i!=step;i++)
for(size_t j=0;j!=countof(P);j+=step){*(P+j+i)=p;p=P+j+i;}
p=P+countof(P)-1;
//for(size_t i=countof(P);i--!=0;) p=*(void**)p; std::cout<<" p="<<p<<endl;
}
void walkP(){repeat_0x100(asm("mov (%r15),%r15");)}
auto cpuFrequency(){
const int sleepN=500000;
auto t1=__rdtsc();
usleep(sleepN);
auto t2=__rdtsc();
return double(t2-t1)/(sleepN*1e-6);
}
int main(int argc, char **argv)
{
cout<<" cpuFrequency()="<<cpuFrequency()<<" sizeof(void*)="<<sizeof(void*)<<endl;
for(size_t i=0;i<0x10;i++){
aaa=(uintptr_t)(P+countof(P)-1);
size_t step=1<<i;
initP(step);cout<<"bench(walkP("<<step<<"))="<<bench(walkP,0x10000,0x100)<<endl;
}
return 0;
}
我的结果是：
cpuFrequency()=3.69355e+09 sizeof(void*)=8
p=0
bench(walkP(1))=3.6146
p=0
bench(walkP(2))=4.48525
p=0
bench(walkP(4))=8.33419
p=0
bench(walkP(8))=16.4063
p=0
bench(walkP(16))=126.335
p=0
bench(walkP(32))=177.424
p=0
bench(walkP(64))=336.674
p=0
bench(walkP(128))=340.422
p=0
bench(walkP(256))=350.896
p=0
bench(walkP(512))=360.694
p=0
bench(walkP(1024))=362.763
p=0
bench(walkP(2048))=367.925
p=0
bench(walkP(4096))=391.085
p=0
bench(walkP(8192))=386.941
p=0
bench(walkP(16384))=398.989
p=0
bench(walkP(32768))=389.542
内存很慢。缓存可以工作（大多数时候）。 要更改比率，唯一可以做的就是将 CPU 时钟速度降低很多，这样内存延迟就会少很多核心周期。但显然这不会让任何事情变得更快！
尝试编写在大多数情况下避免最坏情况（L3 缓存未命中）的代码。另请参阅 “每个程序员应该了解的内存知识”有多少仍然有效？（几乎全部；请阅读 Ulrich Drepper 的优秀文章。）
但请记住，在这 390 个周期内可能会发生许多其他工作，包括其他缓存未命中加载（具有命中未命中和未命中未命中的内存流水线，允许同时发生多个缓存未命中）。除非你编写这样的代码，除了负载延迟（而不是吞吐量）上的瓶颈之外，什么也不做。 （另请参阅 预测现代超标量处理器上的操作延迟需要考虑哪些因素以及如何手动计算它们？ / https://agner.org/optimize/ Assembly - 如何对 CPU 进行评分通过延迟和吞吐量进行指令）
特别是，请参阅现代微处理器 90 分钟指南！ 了解自过去糟糕的日子以来发生的变化，当时非流水线 CPU（例如 386）甚至每个周期都运行 1 条指令，或者像 MIPS 这样的标量流水线最多只能维持 1 条指令。
这就是为什么链表在现代系统上迭代速度很慢，尤其是当它们不按顺序分配时； 更喜欢数组，因此下一个地址不依赖于先前的加载结果。然后，您将看到 Ryzen CPU 在 Zen1/2 上每个时钟周期能够运行 2 个负载，在 Zen3/4 上每个时钟周期运行 3 个负载。 （https://uops.info/ 测量吞吐量、延迟和 uops。）
基于树的数据结构也受到这个问题的影响，但只要它们是平衡的，深度就只是 log2(size)，而不是大小线性。只要分支预测正确，隐式树（或数组的二分搜索）就可以提前计算下一次访问的位置。 （除非编译器进行无分支汇编，否则您对加载结果具有数据依赖性。）
另请注意，Zen 的加载使用延迟实际上是 4 个核心周期。您正在测量 3.6 个参考周期。参考时钟速度通常与非升压（又称涡轮）频率相似，因此在运行测试时，您的 Ryzen 时钟频率可能高达基本频率的 1.11 倍左右。有关 TSC 的更多信息，请参阅如何从 C++ 获取 x86_64 中的 CPU 周期计数？。