首頁(yè) 猿問(wèn) 為什么元素級(jí)的添加在單獨(dú)的循環(huán)中比...

為什么元素級(jí)的添加在單獨(dú)的循環(huán)中比在組合循環(huán)中要快得多？

C++ C

翻翻過(guò)去那場(chǎng)雪 2019-07-05 16:19:16

為什么元素級(jí)的添加在單獨(dú)的循環(huán)中比在組合循環(huán)中要快得多？假設(shè)a1, b1, c1，和d1指向堆內(nèi)存，我的數(shù)字代碼有下面的核心循環(huán)。const int n = 100000;for (int j = 0; j < n; j++) { a1[j] += b1[j]; c1[j] += d1[j];}此循環(huán)通過(guò)另一個(gè)外部執(zhí)行10，000次。for循環(huán)。為了加快速度，我將代碼更改為：for (int j = 0; j < n; j++) { a1[j] += b1[j];}for (int j = 0; j < n; j++) { c1[j] += d1[j];}在MS上編譯Visual C+10.0完全優(yōu)化SSE 2上的32位啟用。英特爾核心2Duo(X64)，第一個(gè)示例耗時(shí)5.5秒，雙循環(huán)示例只需1.9秒。我的問(wèn)題是：(請(qǐng)參閱下面的我重新措辭的問(wèn)題)PS：我不確定，這是否有幫助：第一個(gè)循環(huán)的反匯編基本上如下所示(這個(gè)塊在整個(gè)程序中重復(fù)了五次)：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]雙循環(huán)示例的每個(gè)循環(huán)都生成以下代碼(以下塊大約重復(fù)三次)：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這個(gè)問(wèn)題被證明是無(wú)關(guān)的，因?yàn)樾袨閲?yán)重依賴于數(shù)組(N)和CPU緩存的大小。因此，如果有更多的人感興趣，我會(huì)重新提出這個(gè)問(wèn)題：您能提供一些關(guān)于導(dǎo)致不同緩存行為的詳細(xì)信息，如下圖中的五個(gè)區(qū)域所示嗎？通過(guò)為CPU提供類似的圖表，指出CPU/緩存體系結(jié)構(gòu)之間的差異也可能很有趣。

查看完整描述

3 回答

鳳凰求蠱

TA貢獻(xiàn)1825條經(jīng)驗(yàn) 獲得超4個(gè)贊

好的，正確的答案一定要對(duì)CPU緩存做些什么。但是使用緩存參數(shù)是相當(dāng)困難的，特別是沒(méi)有數(shù)據(jù)。

有許多答案，這導(dǎo)致了很多討論，但讓我們面對(duì)它：緩存問(wèn)題可能是非常復(fù)雜的，不是一維的。它們?cè)诤艽蟪潭壬先Q于數(shù)據(jù)的大小，所以我的問(wèn)題是不公平的：結(jié)果是緩存圖中的一個(gè)非常有趣的點(diǎn)。

@神秘的答案說(shuō)服了很多人(包括我)，可能是因?yàn)樗俏ㄒ灰粋€(gè)似乎依賴事實(shí)的答案，但它只是真理的一個(gè)“數(shù)據(jù)點(diǎn)”。

這就是為什么我結(jié)合了他的測(cè)試(使用連續(xù)的和單獨(dú)的分配)和@James的答案的建議。

下面的圖表顯示，大多數(shù)答案，特別是對(duì)問(wèn)題和答案的大多數(shù)評(píng)論，都可以被認(rèn)為是完全錯(cuò)誤或正確的，這取決于所使用的確切場(chǎng)景和參數(shù)。

請(qǐng)注意，我最初的問(wèn)題是n=100.000..這一點(diǎn)(偶然)表現(xiàn)出特殊的行為：

它有一個(gè)和兩個(gè)循環(huán)版本之間最大的差異(幾乎是三倍)。
這是唯一的一點(diǎn)，其中單循環(huán)(即連續(xù)分配)超過(guò)了兩個(gè)循環(huán)版本。(這使得神秘的答案成為可能。)

使用初始化數(shù)據(jù)的結(jié)果：

使用未初始化數(shù)據(jù)的結(jié)果(這是神秘測(cè)試的結(jié)果)：

這是一個(gè)很難解釋問(wèn)題：初始化數(shù)據(jù)，只分配一次，并被用于每一個(gè)向量大小不同的測(cè)試用例：

提案

每個(gè)與堆棧溢出有關(guān)的低級(jí)別性能問(wèn)題都應(yīng)該被要求為整個(gè)緩存的相關(guān)數(shù)據(jù)大小提供MFLOPS信息！這是浪費(fèi)每個(gè)人的時(shí)間去思考答案，特別是在沒(méi)有這些信息的情況下與其他人討論這些問(wèn)題。

反對(duì) 回復(fù) 2019-07-05

猛跑小豬

TA貢獻(xiàn)1858條經(jīng)驗(yàn) 獲得超8個(gè)贊

想象一下你在一臺(tái)機(jī)器上工作n是正確的值，因?yàn)樗荒芤淮卧趦?nèi)存中容納兩個(gè)數(shù)組，但是通過(guò)磁盤緩存可用的總內(nèi)存仍然足以容納所有四個(gè)數(shù)組。

假設(shè)有一個(gè)簡(jiǎn)單的LIFO緩存策略，以下代碼：

for(int j=0;j<n;j++){
    a[j] += b[j];}for(int j=0;j<n;j++){
    c[j] += d[j];}

會(huì)首先引起a和b加載到RAM中，然后完全在RAM中工作。當(dāng)?shù)诙€(gè)循環(huán)開(kāi)始時(shí)，c和d然后從磁盤加載到RAM中并對(duì)其進(jìn)行操作。

另一個(gè)循環(huán)

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];}

將分出兩個(gè)數(shù)組，并在另外兩個(gè)數(shù)組中分頁(yè)。每次繞圈..這顯然是多慢點(diǎn)。

您可能沒(méi)有在測(cè)試中看到磁盤緩存，但是您可能看到了其他形式的緩存的副作用。

這里似乎有點(diǎn)混亂/誤解，所以我會(huì)嘗試用一個(gè)例子來(lái)解釋一下。

說(shuō)n = 2我們用的是字節(jié)。在我的場(chǎng)景中，我們有內(nèi)存只有4字節(jié)我們剩下的內(nèi)存要慢得多(比如100倍的訪問(wèn)時(shí)間)。

假設(shè)一個(gè)相當(dāng)愚蠢的緩存策略如果字節(jié)不在緩存中，則將其放在緩存中，并在緩存中獲取以下字節(jié)您將得到這樣的場(chǎng)景：

帶著

for(int j=0;j<n;j++){
 a[j] += b[j];}for(int j=0;j<n;j++){
 c[j] += d[j];}

高速緩存a[0]和a[1]然后b[0]和b[1]并設(shè)定a[0] = a[0] + b[0]在緩存中-緩存中現(xiàn)在有四個(gè)字節(jié)，a[0], a[1]和b[0], b[1]..費(fèi)用=100+100。
集
a[1] = a[1] + b[1]
在緩存中。費(fèi)用=1+1。
重復(fù)
c
和
d.
總費(fèi)用=(100 + 100 + 1 + 1) * 2 = 404

帶著

for(int j=0;j<n;j++){
 a[j] += b[j];
 c[j] += d[j];}

高速緩存a[0]和a[1]然后b[0]和b[1]并設(shè)定a[0] = a[0] + b[0]在緩存中-緩存中現(xiàn)在有四個(gè)字節(jié)，a[0], a[1]和b[0], b[1]..費(fèi)用=100+100。
彈出
a[0], a[1], b[0], b[1]
從緩存和緩存
c[0]
和
c[1]
然后
d[0]
和
d[1]
并設(shè)定
c[0] = c[0] + d[0]
在緩存中。費(fèi)用=100+100。
我懷疑你開(kāi)始看到我要去哪里了。
總費(fèi)用=
(100 + 100 + 100 + 100) * 2 = 800