假设a1, b1, c1, 和d1指向堆内存,我的数字代码有以下核心循环。
a1
b1
c1
d1
const int n = 100000; for (int j = 0; j < n; j++) { a1[j] += b1[j]; c1[j] += d1[j]; }
该循环通过另一个外部for循环执行 10,000 次。为了加快速度,我将代码更改为:
for
for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; }
在Microsoft Visual C++ 10.0上编译,并在Intel Core 2 Duo (x64)上为 32 位启用了SSE2并进行了全面优化,第一个示例需要 5.5 秒,双循环示例只需 1.9 秒。
第一个循环的反汇编基本上是这样的(这个块在整个程序中重复了大约五次):
movsd xmm0,mmword ptr [edx+18h] addsd xmm0,mmword ptr [ecx+20h] movsd mmword ptr [ecx+20h],xmm0 movsd xmm0,mmword ptr [esi+10h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [edx+20h] addsd xmm0,mmword ptr [ecx+28h] movsd mmword ptr [ecx+28h],xmm0 movsd xmm0,mmword ptr [esi+18h] addsd xmm0,mmword ptr [eax+38h]
双循环示例的每个循环都会生成此代码(以下代码块重复大约 3 次):
addsd xmm0,mmword ptr [eax+28h] movsd mmword ptr [eax+28h],xmm0 movsd xmm0,mmword ptr [ecx+20h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [ecx+28h] addsd xmm0,mmword ptr [eax+38h] movsd mmword ptr [eax+38h],xmm0 movsd xmm0,mmword ptr [ecx+30h] addsd xmm0,mmword ptr [eax+40h] movsd mmword ptr [eax+40h],xmm0
这个问题被证明是无关紧要的,因为行为严重依赖于数组 (n) 的大小和 CPU 缓存。因此,如果有进一步的兴趣,我会重新提出这个问题:
这是完整的代码。它使用TBB Tick_Count获得更高分辨率的时序,可以通过不定义TBB_TIMING宏来禁用它:
Tick_Count
TBB_TIMING
#include <iostream> #include <iomanip> #include <cmath> #include <string> //#define TBB_TIMING #ifdef TBB_TIMING #include <tbb/tick_count.h> using tbb::tick_count; #else #include <time.h> #endif using namespace std; //#define preallocate_memory new_cont enum { new_cont, new_sep }; double *a1, *b1, *c1, *d1; void allo(int cont, int n) { switch(cont) { case new_cont: a1 = new double[n*4]; b1 = a1 + n; c1 = b1 + n; d1 = c1 + n; break; case new_sep: a1 = new double[n]; b1 = new double[n]; c1 = new double[n]; d1 = new double[n]; break; } for (int i = 0; i < n; i++) { a1[i] = 1.0; d1[i] = 1.0; c1[i] = 1.0; b1[i] = 1.0; } } void ff(int cont) { switch(cont){ case new_sep: delete[] b1; delete[] c1; delete[] d1; case new_cont: delete[] a1; } } double plain(int n, int m, int cont, int loops) { #ifndef preallocate_memory allo(cont,n); #endif #ifdef TBB_TIMING tick_count t0 = tick_count::now(); #else clock_t start = clock(); #endif if (loops == 1) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++){ a1[j] += b1[j]; c1[j] += d1[j]; } } } else { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } } } double ret; #ifdef TBB_TIMING tick_count t1 = tick_count::now(); ret = 2.0*double(n)*double(m)/(t1-t0).seconds(); #else clock_t end = clock(); ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC); #endif #ifndef preallocate_memory ff(cont); #endif return ret; } void main() { freopen("C:\\test.csv", "w", stdout); char *s = " "; string na[2] ={"new_cont", "new_sep"}; cout << "n"; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) #ifdef preallocate_memory cout << s << i << "_loops_" << na[preallocate_memory]; #else cout << s << i << "_loops_" << na[j]; #endif cout << endl; long long nmax = 1000000; #ifdef preallocate_memory allo(preallocate_memory, nmax); #endif for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2))) { const long long m = 10000000/n; cout << n; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) cout << s << plain(n, m, j, i); cout << endl; } }
它显示 FLOP/s 的不同值n。
n
经过进一步分析,我认为这是(至少部分)由四指针的数据对齐引起的。这将导致某种程度的缓存组/方式冲突。
如果我猜对了您如何分配数组,它们很可能与 page line 对齐。
这意味着您在每个循环中的所有访问都将落在相同的缓存方式上。然而,英特尔处理器拥有 8 路 L1 缓存关联性已有一段时间了。但实际上,性能并不完全一致。访问 4 路仍然比说 2 路慢。
编辑:实际上看起来您正在分别分配所有数组。 通常当请求如此大的分配时,分配器会从操作系统请求新的页面。因此,大型分配很有可能出现在与页面边界相同的偏移处。
这是测试代码:
int main(){ const int n = 100000; #ifdef ALLOCATE_SEPERATE double *a1 = (double*)malloc(n * sizeof(double)); double *b1 = (double*)malloc(n * sizeof(double)); double *c1 = (double*)malloc(n * sizeof(double)); double *d1 = (double*)malloc(n * sizeof(double)); #else double *a1 = (double*)malloc(n * sizeof(double) * 4); double *b1 = a1 + n; double *c1 = b1 + n; double *d1 = c1 + n; #endif // Zero the data to prevent any chance of denormals. memset(a1,0,n * sizeof(double)); memset(b1,0,n * sizeof(double)); memset(c1,0,n * sizeof(double)); memset(d1,0,n * sizeof(double)); // Print the addresses cout << a1 << endl; cout << b1 << endl; cout << c1 << endl; cout << d1 << endl; clock_t start = clock(); int c = 0; while (c++ < 10000){ #if ONE_LOOP for(int j=0;j<n;j++){ a1[j] += b1[j]; c1[j] += d1[j]; } #else for(int j=0;j<n;j++){ a1[j] += b1[j]; } for(int j=0;j<n;j++){ c1[j] += d1[j]; } #endif } clock_t end = clock(); cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl; system("pause"); return 0; }
基准测试结果:
2 个英特尔至强 X5482 Harpertown @ 3.2 GHz:
#define ALLOCATE_SEPERATE #define ONE_LOOP 00600020 006D0020 007A0020 00870020 seconds = 6.206 #define ALLOCATE_SEPERATE //#define ONE_LOOP 005E0020 006B0020 00780020 00850020 seconds = 2.116 //#define ALLOCATE_SEPERATE #define ONE_LOOP 00570020 00633520 006F6A20 007B9F20 seconds = 1.894 //#define ALLOCATE_SEPERATE //#define ONE_LOOP 008C0020 00983520 00A46A20 00B09F20 seconds = 1.993
观察:
正如@Stephen Cannon 在评论中指出的那样,这种对齐很可能会导致加载/存储单元或缓存中出现错误的别名。我在谷歌上搜索了一下,发现英特尔实际上有一个用于部分地址别名停顿的硬件计数器:
http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html
区域 1:
这很容易。数据集非常小,以至于性能主要受循环和分支等开销的支配。
区域 2:
在这里,随着数据大小的增加,相对开销的数量下降并且性能“饱和”。这里两个循环比较慢,因为它有两倍的循环和分支开销。
我不确定这里到底发生了什么……对齐仍然可以发挥作用,因为 Agner Fog 提到了缓存库冲突。(那个链接是关于 Sandy Bridge 的,但这个想法应该仍然适用于 Core 2。)
区域 3:
此时,数据不再适合 L1 缓存。因此,性能受到 L1 <-> L2 缓存带宽的限制。
区域 4:
我们观察到的是单循环中的性能下降。如前所述,这是由于对齐(最有可能)导致处理器加载/存储单元中的错误混叠停止。
但是,为了发生错误的混叠,数据集之间必须有足够大的步幅。这就是为什么您在区域 3 中看不到这一点的原因。
区域 5:
此时,缓存中没有任何内容。所以你受到内存带宽的限制。