由于缓存，为什么访问 int8_t 的数组并不比 int32_t 快？
Why accessing an array of int8_t is not faster than int32_t, due to cache?
我在大步访问时读过
for (int i = 0; i < aSize; i++) a[i] *= 3;
for (int i = 0; i < aSize; i += 16) a[i] *= 3;
两个循环的执行应该相似，因为内存访问的顺序高于乘法。
我正在研究 google 基准测试，在测试类似的缓存行为时，我得到了我不理解的结果。
template <class IntegerType>
void BM_FillArray(benchmark::State& state) {
for (auto _ : state)
{
IntegerType a[15360 * 1024 * 2]; // Reserve array that doesn't fit in L3
for (size_t i = 0; i < sizeof(a) / sizeof(IntegerType); ++i)
benchmark::DoNotOptimize(a[i] = 0); // I have compiler optimizations disabled anyway
}
}
BENCHMARK_TEMPLATE(BM_FillArray, int32_t);
BENCHMARK_TEMPLATE(BM_FillArray, int8_t);
Run on (12 X 3592 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x6)
L1 Instruction 32 KiB (x6)
L2 Unified 256 KiB (x6)
L3 Unified 15360 KiB (x1)
---------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------
BM_FillArray<int32_t> 196577075 ns 156250000 ns 4
BM_FillArray<int8_t> 205476725 ns 160156250 ns 4
我希望访问字节数组比访问整数数组更快，因为更多元素适合缓存行，但事实并非如此。
以下是启用优化后的结果：
BM_FillArray<int32_t> 47279657 ns 47991071 ns 14
BM_FillArray<int8_t> 49374830 ns 50000000 ns 10
谁能澄清一下？谢谢:)
更新 1：
我读了旧文《程序员应该知道的关于内存的知识》，现在一切都清楚了。但是，我尝试了以下基准测试：
template <int32_t CacheLineSize>
void BM_ReadArraySeqCacheLine(benchmark::State& state) {
struct CacheLine
{
int8_t a[CacheLineSize];
};
vector<CacheLine> cl;
int32_t workingSetSize = state.range(0);
int32_t arraySize = workingSetSize / sizeof(CacheLine);
cl.resize(arraySize);
const int32_t iterations = 1536 * 1024;
for (auto _ : state)
{
srand(time(NULL));
int8_t res = 0;
int32_t i = 0;
while (i++ < iterations)
{
//size_t idx = i% arraySize;
int idx = (rand() / float(RAND_MAX)) * arraySize;
benchmark::DoNotOptimize(res += cl[idx].a[0]);
}
}
}
BENCHMARK_TEMPLATE(BM_ReadArraySeqCacheLine, 1)
->Arg(32 * 1024) // L1 Data 32 KiB(x6)
->Arg(256 * 1024) // L2 Unified 256 KiB(x6)
->Arg(15360 * 1024);// L3 Unified 15360 KiB(x1)
BENCHMARK_TEMPLATE(BM_ReadArraySeqCacheLine, 64)
->Arg(32 * 1024) // L1 Data 32 KiB(x6)
->Arg(256 * 1024) // L2 Unified 256 KiB(x6)
->Arg(15360 * 1024);// L3 Unified 15360 KiB(x1)
BENCHMARK_TEMPLATE(BM_ReadArraySeqCacheLine, 128)
->Arg(32 * 1024) // L1 Data 32 KiB(x6)
->Arg(256 * 1024) // L2 Unified 256 KiB(x6)
->Arg(15360 * 1024);// L3 Unified 15360 KiB(x1)
我预计当工作大小不适合缓存时，随机访问的性能会更差。然而，这些是结果：
BM_ReadArraySeqCacheLine<1>/32768 39936129 ns 38690476 ns 21
BM_ReadArraySeqCacheLine<1>/262144 40822781 ns 39062500 ns 16
BM_ReadArraySeqCacheLine<1>/15728640 58144300 ns 57812500 ns 10
BM_ReadArraySeqCacheLine<64>/32768 32786576 ns 33088235 ns 17
BM_ReadArraySeqCacheLine<64>/262144 32066729 ns 31994048 ns 21
BM_ReadArraySeqCacheLine<64>/15728640 50734420 ns 50000000 ns 10
BM_ReadArraySeqCacheLine<128>/32768 29122832 ns 28782895 ns 19
BM_ReadArraySeqCacheLine<128>/262144 31991964 ns 31875000 ns 25
BM_ReadArraySeqCacheLine<128>/15728640 68437327 ns 68181818 ns 11
我错过了什么？
更新 2：
我现在正在使用您建议的 (linear_congruential_engine) 来生成随机数，而且我只使用静态数组，但现在的结果让我更加困惑。
这是更新后的代码：
template <int32_t WorkingSetSize, int32_t ElementSize>
void BM_ReadArrayRndCacheLine(benchmark::State& state) {
struct Element
{
int8_t data[ElementSize];
};
constexpr int32_t ArraySize = WorkingSetSize / sizeof(ElementSize);
Element a[ArraySize];
constexpr int32_t iterations = 1536 * 1024;
linear_congruential_engine<size_t, ArraySize/10, ArraySize/10, ArraySize> lcg; // I've tried with many params...
for (auto _ : state)
{
int8_t res = 0;
int32_t i = 0;
while (i++ < iterations)
{
size_t idx = lcg();
benchmark::DoNotOptimize(res += a[idx].data[0]);
}
}
}
// L1 Data 32 KiB(x6)
// L2 Unified 256 KiB(x6)
// L3 Unified 15360 KiB(x1)
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 32 * 1024, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 32 * 1024, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 32 * 1024, 128);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 256 * 1024, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 256 * 1024, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 256 * 1024, 128);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024, 128);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024 * 4, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024 * 4, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024 * 4, 128);
结果如下（已启用优化）：
// First template parameter is working set size.
// Second template parameter is array elemeent size.
BM_ReadArrayRndCacheLine<32 * 1024, 1> 2833786 ns 2823795 ns 249
BM_ReadArrayRndCacheLine<32 * 1024, 64> 2960200 ns 2979343 ns 236
BM_ReadArrayRndCacheLine<32 * 1024, 128> 2896079 ns 2910539 ns 204
BM_ReadArrayRndCacheLine<256 * 1024, 1> 3114670 ns 3111758 ns 236
BM_ReadArrayRndCacheLine<256 * 1024, 64> 3629689 ns 3643135 ns 193
BM_ReadArrayRndCacheLine<256 * 1024, 128> 3213500 ns 3187189 ns 201
BM_ReadArrayRndCacheLine<15360 * 1024, 1> 5782703 ns 5729167 ns 90
BM_ReadArrayRndCacheLine<15360 * 1024, 64> 5958600 ns 6009615 ns 130
BM_ReadArrayRndCacheLine<15360 * 1024, 128> 5958221 ns 5998884 ns 112
BM_ReadArrayRndCacheLine<15360 * 1024 * 4, 1> 6143701 ns 6076389 ns 90
BM_ReadArrayRndCacheLine<15360 * 1024 * 4, 64> 5800649 ns 5902778 ns 90
BM_ReadArrayRndCacheLine<15360 * 1024 * 4, 128> 5826414 ns 5729167 ns 90
(L1d < workingSet < L2) 结果怎么可能与 (workingSet < L1d) 差别不大？ L2 的吞吐量和延迟仍然非常高，但通过随机访问，我试图防止预取和强制缓存未命中。那么，为什么我什至没有注意到最小的增量？
即使尝试从主内存 (workingSet > L3) 获取数据，我的性能也没有大幅下降。你提到最新的架构可以保持每个时钟高达 8 字节的带宽，但我知道他们必须复制一个保持缓存行，并且如果不使用可预测的线性模式进行预取，延迟在我的测试中应该更明显......为什么是不是这样？
我怀疑页面错误和 tlb 可能也有关系。
（我下载了 vtune 分析器试图更好地理解所有这些东西，但它挂在我的机器上，我正在等待支持）
非常感谢 Peter Cordes 的帮助:)
我只是一名 GAME 程序员，试图向我的队友展示在我们的代码中使用某些整数类型是否可能（或不）对我们的游戏性能产生影响。例如，我们是否应该担心使用快速类型（例如 int_fast16_t）或在我们的变量中使用尽可能少的字节以更好地打包（例如 int8_t）。
回复：终极问题：int_fast16_t 是数组的垃圾，因为不幸的是 x86-64 上的 glibc 将其定义为 64 位类型（而非 32 位），因此它浪费了大量缓存空间.问题是“快速用于什么目的”，而 glibc 回答“快速用作数组索引/循环计数器”，显然，即使它在一些较旧的 CPU 上除法或乘法较慢（这是当前的做出选择时）。 IMO 这是一个糟糕的设计决定。
- Cpp uint32_fast_t resolves to uint64_t but is slower for nearly all operations than a uint32_t (x86_64). Why does it resolve to uint64_t?
- How should the [u]int_fastN_t types be defined for x86_64, with or without the x32 ABI?
通常对数组使用小整数类型很好；通常高速缓存未命中是一个问题，因此减少占用空间是很好的，即使这意味着使用 movzx 或 movsx 加载而不是内存源操作数来将其与 int 或 [=14 一起使用=] 32 位本地。如果 SIMD 成为可能，每个固定宽度向量有更多元素意味着每条指令可以完成更多工作。
但不幸的是，int_fast16_t 不会帮助您使用某些库实现这一目标，但 short 会，或者 int_least16_t.
请参阅我在问题下的评论以获取早期部分的答案：200 个停顿周期是延迟，而不是吞吐量。硬件预取和内存级并行性隐藏了这一点。 Modern Microprocessors - A 90 Minute Guide! is excellent, and has a section on memory. See also What Every Programmer Should Know About Memory? 在 2021 年仍然高度相关。（除了一些关于预取线程的内容。）
您的更新 2 具有更快的 PRNG
回复：为什么 L2 不比 L1 慢：乱序执行足以隐藏 L2 延迟，甚至你的 LGC 也太慢而无法强调 L2 吞吐量 .很难以足够快的速度生成随机数，从而给可用的内存级并行性带来很多麻烦。
您的 Skylake 派生 CPU 具有 97 微指令的无序调度程序 (RS)，以及 224 微指令的 ROB 大小（如 https://realworldtech.com/haswell-cpu/3 but larger), and 12 LFBs to track cache lines it's waiting for. As long as the CPU can keep track of enough in-flight loads (latency * bandwidth), having to go to L2 is not a big deal. Ability to hide cache misses is one way to measure out-of-order window size in the first place: https://blog.stuffedcow.net/2013/05/measuring-rob-capacity
L2 命中的延迟为 12 个周期 (https://www.7-cpu.com/cpu/Skylake.html)。 Skylake 每个时钟可以从 L1d 缓存执行 2 次加载，但不能从 L2 执行。 （它不能在每个时钟 IIRC 维持 1 个高速缓存线，但是每 2 个时钟 1 个甚至更好是可行的）。
您的 LCG RNG 在延迟方面阻碍了循环：2 的幂数组大小为 5 个周期，或者像“L3”这样的非 2 的幂数组大小为 13 个周期测试尝试1。因此，这大约是 L1d 可以处理的访问速率的 1/10，即使每次访问都未命中 L1d 但在 L2 中命中，您甚至不会从 L2 保留超过一个负载。 OoO exec + 加载缓冲区甚至不会出汗。所以 L1d 和 L2 将是相同的速度，因为它们都使用 2 的幂数组大小。
注 1：x = a * x + c 的 imul(3c) + add(1c)，然后 remainder = x - (x/m * m) 使用 a multiplicative inverse，可能 mul（4 个周期用于高半size_t?) + shr(1) + imul(3c) + sub(1c)。或者使用 2 的幂大小，模只是 AND 和一个常量，如 (1UL<<n) - 1.
显然我的估计不太正确 因为你的非 2 次方数组小于 L1d / L2 的两倍，而不是我的 13/5即使 L3 latency/bandwidth 不是一个因素，估计也会预测。
运行 展开循环中的多个独立 LCG 可能会有所作为。 （使用不同的种子。）但是 LCG 的非 2 次幂 m 仍然意味着相当多的指令，因此您会在 CPU 前端吞吐量（和后端执行端口）上出现瓶颈，特别是乘数）。
具有乘数 (a) = ArraySize/10 的 LCG 可能只是一个足够大的步幅，硬件预取器不会从锁定它中获益太多。但通常 IIRC 你想要一个大的奇数或其他东西（自从我看了 LCG 参数选择的数学以来已经有一段时间了），否则你可能只会接触有限数量的数组元素，而不是最终覆盖它们。 （您可以通过在随机循环中将 1 存储到每个数组元素来进行测试，然后计算触摸了多少数组元素，即如果其他元素为 0，则对数组求和。）
a 和 c 绝对 而不是 都是 m 的因数，否则您正在访问每次都使用相同的 10 个缓存行，排除其他所有内容。
正如我之前所说，击败硬件预取并不需要太多的随机性。 c=0、a= 奇数（可能是质数）和 m=UINT_MAX 的 LCG 可能很好，字面意思就是 imul。您可以分别对每个 LCG 结果的数组大小取模，从而使该操作脱离关键路径。在这一点上，您不妨将标准库排除在外，从字面上看只是 unsigned rng = 1; 开始，而 rng *= 1234567; 作为您的更新步骤。然后使用 arr[rng % arraysize].
这比使用 xorshift+ 或 xorshft* 做的任何事情都要便宜。
基准缓存延迟：
你 可以 生成一个随机数组 uint16_t 或 uint32_t 索引一次（例如在静态初始化程序或构造函数中）并重复循环，在这些位置访问另一个数组。这将交织顺序访问和随机访问，并使代码可能每个时钟执行 2 次加载并使用 L1d 命中，特别是如果您使用 gcc -O3 -funroll-loops。 （使用 -march=native 它可能会使用 AVX2 收集指令自动矢量化，但仅适用于 32 位或更宽的元素，因此如果您想排除仅来自从中获取索引的混杂因素，请使用 -fno-tree-vectorize一个数组。）
为了测试高速缓存/内存延迟，通常的技术是创建一个围绕数组随机分布的链表。遍历列表，下一个加载可以在前一个加载完成后立即开始（但不能早于）。因为一个依赖另一个。这称为“加载使用延迟”。另见 for a trick Intel CPUs use to optimistically speed up workloads like that (the 4-cycle L1d latency case, instead of the usual 5 cycle). Semi-related: PyPy 17x faster than Python. Can Python be sped up? 是另一个依赖于指针追踪延迟的测试。
我在大步访问时读过
for (int i = 0; i < aSize; i++) a[i] *= 3;
for (int i = 0; i < aSize; i += 16) a[i] *= 3;
两个循环的执行应该相似，因为内存访问的顺序高于乘法。
我正在研究 google 基准测试，在测试类似的缓存行为时，我得到了我不理解的结果。
template <class IntegerType>
void BM_FillArray(benchmark::State& state) {
for (auto _ : state)
{
IntegerType a[15360 * 1024 * 2]; // Reserve array that doesn't fit in L3
for (size_t i = 0; i < sizeof(a) / sizeof(IntegerType); ++i)
benchmark::DoNotOptimize(a[i] = 0); // I have compiler optimizations disabled anyway
}
}
BENCHMARK_TEMPLATE(BM_FillArray, int32_t);
BENCHMARK_TEMPLATE(BM_FillArray, int8_t);
Run on (12 X 3592 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x6)
L1 Instruction 32 KiB (x6)
L2 Unified 256 KiB (x6)
L3 Unified 15360 KiB (x1)
---------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------
BM_FillArray<int32_t> 196577075 ns 156250000 ns 4
BM_FillArray<int8_t> 205476725 ns 160156250 ns 4
我希望访问字节数组比访问整数数组更快，因为更多元素适合缓存行，但事实并非如此。
以下是启用优化后的结果：
BM_FillArray<int32_t> 47279657 ns 47991071 ns 14
BM_FillArray<int8_t> 49374830 ns 50000000 ns 10
谁能澄清一下？谢谢:)
更新 1：
我读了旧文《程序员应该知道的关于内存的知识》，现在一切都清楚了。但是，我尝试了以下基准测试：
template <int32_t CacheLineSize>
void BM_ReadArraySeqCacheLine(benchmark::State& state) {
struct CacheLine
{
int8_t a[CacheLineSize];
};
vector<CacheLine> cl;
int32_t workingSetSize = state.range(0);
int32_t arraySize = workingSetSize / sizeof(CacheLine);
cl.resize(arraySize);
const int32_t iterations = 1536 * 1024;
for (auto _ : state)
{
srand(time(NULL));
int8_t res = 0;
int32_t i = 0;
while (i++ < iterations)
{
//size_t idx = i% arraySize;
int idx = (rand() / float(RAND_MAX)) * arraySize;
benchmark::DoNotOptimize(res += cl[idx].a[0]);
}
}
}
BENCHMARK_TEMPLATE(BM_ReadArraySeqCacheLine, 1)
->Arg(32 * 1024) // L1 Data 32 KiB(x6)
->Arg(256 * 1024) // L2 Unified 256 KiB(x6)
->Arg(15360 * 1024);// L3 Unified 15360 KiB(x1)
BENCHMARK_TEMPLATE(BM_ReadArraySeqCacheLine, 64)
->Arg(32 * 1024) // L1 Data 32 KiB(x6)
->Arg(256 * 1024) // L2 Unified 256 KiB(x6)
->Arg(15360 * 1024);// L3 Unified 15360 KiB(x1)
BENCHMARK_TEMPLATE(BM_ReadArraySeqCacheLine, 128)
->Arg(32 * 1024) // L1 Data 32 KiB(x6)
->Arg(256 * 1024) // L2 Unified 256 KiB(x6)
->Arg(15360 * 1024);// L3 Unified 15360 KiB(x1)
我预计当工作大小不适合缓存时，随机访问的性能会更差。然而，这些是结果：
BM_ReadArraySeqCacheLine<1>/32768 39936129 ns 38690476 ns 21
BM_ReadArraySeqCacheLine<1>/262144 40822781 ns 39062500 ns 16
BM_ReadArraySeqCacheLine<1>/15728640 58144300 ns 57812500 ns 10
BM_ReadArraySeqCacheLine<64>/32768 32786576 ns 33088235 ns 17
BM_ReadArraySeqCacheLine<64>/262144 32066729 ns 31994048 ns 21
BM_ReadArraySeqCacheLine<64>/15728640 50734420 ns 50000000 ns 10
BM_ReadArraySeqCacheLine<128>/32768 29122832 ns 28782895 ns 19
BM_ReadArraySeqCacheLine<128>/262144 31991964 ns 31875000 ns 25
BM_ReadArraySeqCacheLine<128>/15728640 68437327 ns 68181818 ns 11
我错过了什么？
更新 2：
我现在正在使用您建议的 (linear_congruential_engine) 来生成随机数，而且我只使用静态数组，但现在的结果让我更加困惑。
这是更新后的代码：
template <int32_t WorkingSetSize, int32_t ElementSize>
void BM_ReadArrayRndCacheLine(benchmark::State& state) {
struct Element
{
int8_t data[ElementSize];
};
constexpr int32_t ArraySize = WorkingSetSize / sizeof(ElementSize);
Element a[ArraySize];
constexpr int32_t iterations = 1536 * 1024;
linear_congruential_engine<size_t, ArraySize/10, ArraySize/10, ArraySize> lcg; // I've tried with many params...
for (auto _ : state)
{
int8_t res = 0;
int32_t i = 0;
while (i++ < iterations)
{
size_t idx = lcg();
benchmark::DoNotOptimize(res += a[idx].data[0]);
}
}
}
// L1 Data 32 KiB(x6)
// L2 Unified 256 KiB(x6)
// L3 Unified 15360 KiB(x1)
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 32 * 1024, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 32 * 1024, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 32 * 1024, 128);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 256 * 1024, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 256 * 1024, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 256 * 1024, 128);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024, 128);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024 * 4, 1);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024 * 4, 64);
BENCHMARK_TEMPLATE(BM_ReadArrayRndCacheLine, 15360 * 1024 * 4, 128);
结果如下（已启用优化）：
// First template parameter is working set size.
// Second template parameter is array elemeent size.
BM_ReadArrayRndCacheLine<32 * 1024, 1> 2833786 ns 2823795 ns 249
BM_ReadArrayRndCacheLine<32 * 1024, 64> 2960200 ns 2979343 ns 236
BM_ReadArrayRndCacheLine<32 * 1024, 128> 2896079 ns 2910539 ns 204
BM_ReadArrayRndCacheLine<256 * 1024, 1> 3114670 ns 3111758 ns 236
BM_ReadArrayRndCacheLine<256 * 1024, 64> 3629689 ns 3643135 ns 193
BM_ReadArrayRndCacheLine<256 * 1024, 128> 3213500 ns 3187189 ns 201
BM_ReadArrayRndCacheLine<15360 * 1024, 1> 5782703 ns 5729167 ns 90
BM_ReadArrayRndCacheLine<15360 * 1024, 64> 5958600 ns 6009615 ns 130
BM_ReadArrayRndCacheLine<15360 * 1024, 128> 5958221 ns 5998884 ns 112
BM_ReadArrayRndCacheLine<15360 * 1024 * 4, 1> 6143701 ns 6076389 ns 90
BM_ReadArrayRndCacheLine<15360 * 1024 * 4, 64> 5800649 ns 5902778 ns 90
BM_ReadArrayRndCacheLine<15360 * 1024 * 4, 128> 5826414 ns 5729167 ns 90
(L1d < workingSet < L2) 结果怎么可能与 (workingSet < L1d) 差别不大？ L2 的吞吐量和延迟仍然非常高，但通过随机访问，我试图防止预取和强制缓存未命中。那么，为什么我什至没有注意到最小的增量？
即使尝试从主内存 (workingSet > L3) 获取数据，我的性能也没有大幅下降。你提到最新的架构可以保持每个时钟高达 8 字节的带宽，但我知道他们必须复制一个保持缓存行，并且如果不使用可预测的线性模式进行预取，延迟在我的测试中应该更明显......为什么是不是这样？
我怀疑页面错误和 tlb 可能也有关系。
（我下载了 vtune 分析器试图更好地理解所有这些东西，但它挂在我的机器上，我正在等待支持）
非常感谢 Peter Cordes 的帮助:)
我只是一名 GAME 程序员，试图向我的队友展示在我们的代码中使用某些整数类型是否可能（或不）对我们的游戏性能产生影响。例如，我们是否应该担心使用快速类型（例如 int_fast16_t）或在我们的变量中使用尽可能少的字节以更好地打包（例如 int8_t）。
回复：终极问题：int_fast16_t 是数组的垃圾，因为不幸的是 x86-64 上的 glibc 将其定义为 64 位类型（而非 32 位），因此它浪费了大量缓存空间.问题是“快速用于什么目的”，而 glibc 回答“快速用作数组索引/循环计数器”，显然，即使它在一些较旧的 CPU 上除法或乘法较慢（这是当前的做出选择时）。 IMO 这是一个糟糕的设计决定。
- Cpp uint32_fast_t resolves to uint64_t but is slower for nearly all operations than a uint32_t (x86_64). Why does it resolve to uint64_t?
- How should the [u]int_fastN_t types be defined for x86_64, with or without the x32 ABI?
通常对数组使用小整数类型很好；通常高速缓存未命中是一个问题，因此减少占用空间是很好的，即使这意味着使用 movzx 或 movsx 加载而不是内存源操作数来将其与 int 或 [=14 一起使用=] 32 位本地。如果 SIMD 成为可能，每个固定宽度向量有更多元素意味着每条指令可以完成更多工作。
但不幸的是，int_fast16_t 不会帮助您使用某些库实现这一目标，但 short 会，或者 int_least16_t.
请参阅我在问题下的评论以获取早期部分的答案：200 个停顿周期是延迟，而不是吞吐量。硬件预取和内存级并行性隐藏了这一点。 Modern Microprocessors - A 90 Minute Guide! is excellent, and has a section on memory. See also What Every Programmer Should Know About Memory? 在 2021 年仍然高度相关。（除了一些关于预取线程的内容。）
您的更新 2 具有更快的 PRNG
回复：为什么 L2 不比 L1 慢：乱序执行足以隐藏 L2 延迟，甚至你的 LGC 也太慢而无法强调 L2 吞吐量 .很难以足够快的速度生成随机数，从而给可用的内存级并行性带来很多麻烦。
您的 Skylake 派生 CPU 具有 97 微指令的无序调度程序 (RS)，以及 224 微指令的 ROB 大小（如 https://realworldtech.com/haswell-cpu/3 but larger), and 12 LFBs to track cache lines it's waiting for. As long as the CPU can keep track of enough in-flight loads (latency * bandwidth), having to go to L2 is not a big deal. Ability to hide cache misses is one way to measure out-of-order window size in the first place: https://blog.stuffedcow.net/2013/05/measuring-rob-capacity
L2 命中的延迟为 12 个周期 (https://www.7-cpu.com/cpu/Skylake.html)。 Skylake 每个时钟可以从 L1d 缓存执行 2 次加载，但不能从 L2 执行。 （它不能在每个时钟 IIRC 维持 1 个高速缓存线，但是每 2 个时钟 1 个甚至更好是可行的）。
您的 LCG RNG 在延迟方面阻碍了循环：2 的幂数组大小为 5 个周期，或者像“L3”这样的非 2 的幂数组大小为 13 个周期测试尝试1。因此，这大约是 L1d 可以处理的访问速率的 1/10，即使每次访问都未命中 L1d 但在 L2 中命中，您甚至不会从 L2 保留超过一个负载。 OoO exec + 加载缓冲区甚至不会出汗。所以 L1d 和 L2 将是相同的速度，因为它们都使用 2 的幂数组大小。
注 1：x = a * x + c 的 imul(3c) + add(1c)，然后 remainder = x - (x/m * m) 使用 a multiplicative inverse，可能 mul（4 个周期用于高半size_t?) + shr(1) + imul(3c) + sub(1c)。或者使用 2 的幂大小，模只是 AND 和一个常量，如 (1UL<<n) - 1.
显然我的估计不太正确 因为你的非 2 次方数组小于 L1d / L2 的两倍，而不是我的 13/5即使 L3 latency/bandwidth 不是一个因素，估计也会预测。
运行 展开循环中的多个独立 LCG 可能会有所作为。 （使用不同的种子。）但是 LCG 的非 2 次幂 m 仍然意味着相当多的指令，因此您会在 CPU 前端吞吐量（和后端执行端口）上出现瓶颈，特别是乘数）。
具有乘数 (a) = ArraySize/10 的 LCG 可能只是一个足够大的步幅，硬件预取器不会从锁定它中获益太多。但通常 IIRC 你想要一个大的奇数或其他东西（自从我看了 LCG 参数选择的数学以来已经有一段时间了），否则你可能只会接触有限数量的数组元素，而不是最终覆盖它们。 （您可以通过在随机循环中将 1 存储到每个数组元素来进行测试，然后计算触摸了多少数组元素，即如果其他元素为 0，则对数组求和。）
a 和 c 绝对 而不是 都是 m 的因数，否则您正在访问每次都使用相同的 10 个缓存行，排除其他所有内容。
正如我之前所说，击败硬件预取并不需要太多的随机性。 c=0、a= 奇数（可能是质数）和 m=UINT_MAX 的 LCG 可能很好，字面意思就是 imul。您可以分别对每个 LCG 结果的数组大小取模，从而使该操作脱离关键路径。在这一点上，您不妨将标准库排除在外，从字面上看只是 unsigned rng = 1; 开始，而 rng *= 1234567; 作为您的更新步骤。然后使用 arr[rng % arraysize].
这比使用 xorshift+ 或 xorshft* 做的任何事情都要便宜。
基准缓存延迟：
你 可以 生成一个随机数组 uint16_t 或 uint32_t 索引一次（例如在静态初始化程序或构造函数中）并重复循环，在这些位置访问另一个数组。这将交织顺序访问和随机访问，并使代码可能每个时钟执行 2 次加载并使用 L1d 命中，特别是如果您使用 gcc -O3 -funroll-loops。 （使用 -march=native 它可能会使用 AVX2 收集指令自动矢量化，但仅适用于 32 位或更宽的元素，因此如果您想排除仅来自从中获取索引的混杂因素，请使用 -fno-tree-vectorize一个数组。）
为了测试高速缓存/内存延迟，通常的技术是创建一个围绕数组随机分布的链表。遍历列表，下一个加载可以在前一个加载完成后立即开始（但不能早于）。因为一个依赖另一个。这称为“加载使用延迟”。另见