c++ - 为什么当远远超过 CPU 缓存大小时内存访问时间会增加
问题描述
在查看涉及 CPU 缓存大小之外的大量访问的性能问题时,我进行了一个测试,该测试“随机”地增加块大小的内存访问次数。我看到 L1、2、3 缓存块大小的预期变化,但惊讶地看到访问时间继续减少,远远超出缓存能力。
例如,从 256MB 块到 4GB 块的访问时间减半。从每 uS 50 次读取/写入到每 uS 25 次读取/写入。减少持续到系统内存限制。我为其他应用程序和操作系统留出了 8GB(或 4GB)的额外空间。
L3 缓存为 8MB,因此我预计对较大块大小的缓存影响很小。
该算法使用原始多项式“随机”寻址每个 64 位字。这有效地以相当随机的方式访问地址,但确保除了 0 索引之外的所有地址在每次通过时都被访问一次。在经过足够多的通过以使每个通过一秒钟左右之后,将结果制成表格。
我无法解释这种持续的访问时间减少远远超出缓存限制。有什么解释吗?
以下是 3 台不同的 Windows 10 机器的结果:
| Memory block (bytes)
| | 64 bit words incremented per us
-- desktop I7 980 24GB -- -- Surface Book 16GB -- --HP Envy 8GB --
128 544.80 128 948.43 128 774.22
256 554.01 256 1034.15 256 715.50
512 560.12 512 993.28 512 665.23
1.02k 512.93 1.02k 944.24 1.02k 665.19
2.05k 527.47 2.05k 947.09 2.05k 664.84
4.10k 517.41 4.10k 931.48 4.10k 664.94
8.19k 517.55 8.19k 939.61 8.19k 666.40
16.38k 518.30 16.38k 941.18 16.38k 666.88
32.77k 518.10 32.77k 938.77 32.77k 663.33
65.54k 505.93 65.54k 889.42 65.54k 645.61
131.07k 501.91 131.07k 855.01 131.07k 577.49
262.14k 495.61 262.14k 882.75 262.14k 507.57
524.29k 356.98 524.29k 774.23 524.29k 445.47
1.05m 281.87 1.05m 695.35 1.05m 417.13
2.10m 240.41 2.10m 650.26 2.10m 366.45
4.19m 210.10 4.19m 229.06 4.19m 129.21
8.39m 158.72 8.39m 114.95 8.39m 77.27
16.78m 99.08 16.78m 84.95 16.78m 62.47
33.55m 79.12 33.55m 60.14 33.55m 54.94
67.11m 68.22 67.11m 34.56 67.11m 49.89
134.22m 56.17 134.22m 22.52 134.22m 39.66
268.44m 50.03 268.44m 23.81 268.44m 35.16
536.87m 46.24 536.87m 39.66 536.87m 32.50
1073.74m 43.29 1073.74m 30.33 1073.74m 25.28
2147.48m 33.33 2147.48m 25.19 2147.48m 15.94
4294.97m 24.85 4294.97m 10.83 4294.97m 13.18
8589.93m 19.96 8589.93m 9.61
17179.87m 17.05
这是C++代码:
// Memory access times for randomly distributed read/writes
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <chrono>
#include <array>
using namespace std;
// primitive polynomials over gf(2^N)
// these form simple shift registers that cycle through all possible numbers in 2^N except for 0
const array<uint32_t, 28> gf = {
0x13, 0x25, 0x67, 0xcb, 0x1cf, 0x233, 0x64f, 0xbb7,
0x130f, 0x357f, 0x4f9f, 0x9e47, 0x11b2b, 0x2df4f, 0x472f3, 0xdf6af,
0x16b04f, 0x2e0fd5, 0x611fa7, 0xa81be1, 0x11f21c7, 0x202d219, 0x67833df, 0xbc08c6b,
0x123b83c7, 0x2dbf7ea3, 0x6268545f, 0xe6fc6257
};
int main()
{
typedef uint64_t TestType;
printf(" | Memory block (bytes)\n | | %d bit words incremented per us\n", 8 * (int)sizeof(TestType));
TestType *const memory = new TestType[0x8000'0000u];
for (int N = 4; N < 32-0; N++)
{
const uint32_t gfx = gf[N - 4];
const uint32_t seg_size = 1 << N;
int repCount=1+static_cast<int>(gf[25]/(static_cast<float>(seg_size)));
fill(&memory[1], &memory[seg_size], 0);
chrono::high_resolution_clock::time_point timerx(chrono::high_resolution_clock::now());
for (int rep = 0; rep < repCount; rep++)
{
uint32_t start = 1;
for (uint32_t i = 0; i < seg_size - 1; i++) { // cycles from 1 back to 1 includes all values except 0
++memory[start];
start <<= 1;
if (start & seg_size)
start ^= gfx;
}
if (start != 1)
{
cout << "ERROR\n";
exit(-1);
}
}
auto time_done = chrono::duration<double>(chrono::high_resolution_clock::now()-timerx).count();
auto x = find_if_not(&memory[1], &memory[seg_size], [repCount](auto v) {return v == static_cast<TestType>(repCount); });
if (x != &memory[seg_size])
{
printf("Failed at memory offset %lld\n", x - &memory[0]);
return -1;
}
long long int blksize = 4ll << N;
if ((sizeof(TestType) << N) < 1000)
printf("%9.0f %6.2f\n", 1.0*(sizeof(TestType) << N), (seg_size - 1)*repCount / (time_done * 1'000'000));
else if ((sizeof(TestType) << N) < 1000'000)
printf("%8.2fk %6.2f\n", .001*(sizeof(TestType) << N), (seg_size - 1)*repCount / (time_done * 1'000'000));
else
printf("%8.2fm %6.2f\n", .000001*((long long int)sizeof(TestType) << N), (seg_size - 1.)*repCount /(time_done * 1'000'000));
}
cout << "Done\n";
return 0;
}
解决方案
吞吐量继续下降,因为随着元素总数的增加,每个元素的页面行走时间增加。也就是说,填充 TLB 所花费的时间不会随着元素的数量而增加。DTLB_LOAD_MISSES.WALK_DURATION
您可以使用性能计数器和其他与页面遍历硬件相关的计数器来观察这一点。这是意料之中的,因为当访问的 4K 页数增加时,映射工作集的页表的深度和广度也会变大,因此不太可能在更接近的内存级别找到所需的页表条目。核。
推荐阅读
- php - MySQL - phpmyadmin 警报消息
- python - 有没有办法在 seaborn 中获得特定数量的地块?
- hibernate - 我应该如何在具有复合主键的实体中覆盖 equals/hashCode?
- google-sheets - Google 表格 googlefinance 查询在 if 语句中不起作用
- r - 我可以使用 mapply 拟合不同的回归模型吗?
- sql - 数据字段 - 在新数据字段中搜索和写入值 (Oracle)
- javascript - ESLint 规则确保 JSX 文本节点不与其他节点混合
- c# - 绑定 TabItem 模板
- boto3 - Boto3 忽略 AWS_CONTAINER_CREDENTIALS_RELATIVE_URI
- c++ - 使用 GTest 多次重复多线程测试的正确方法是什么?