當(dāng)前位置：首頁(yè) > 公眾號(hào)精選 > CPP開(kāi)發(fā)者

這篇 CPU Cache，估計(jì)也沒(méi)人看

時(shí)間：2021-12-08 17:02:20
關(guān)鍵字： CPU    CACHE    BSP    內(nèi)存   
手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]↓推薦關(guān)注↓無(wú)論你寫什么樣的代碼都會(huì)交給CPU來(lái)執(zhí)行，所以，如果你想寫出性能比較高的代碼，這篇文章中提到的技術(shù)還是值得認(rèn)真學(xué)習(xí)的。另外，千萬(wàn)別覺(jué)得這些東西沒(méi)用，這些東西非常有用，十多年前就是這些知識(shí)在性能調(diào)優(yōu)上幫了我的很多大忙，從而跟很多人拉開(kāi)了差距……基礎(chǔ)知識(shí)首先，我們都知道現(xiàn)...


無(wú)論你寫什么樣的代碼都會(huì)交給 CPU 來(lái)執(zhí)行，所以，如果你想寫出性能比較高的代碼，這篇文章中提到的技術(shù)還是值得認(rèn)真學(xué)習(xí)的。另外，千萬(wàn)別覺(jué)得這些東西沒(méi)用，這些東西非常有用，十多年前就是這些知識(shí)在性能調(diào)優(yōu)上幫了我的很多大忙，從而跟很多人拉開(kāi)了差距……


基礎(chǔ)知識(shí)

首先，我們都知道現(xiàn)在的 CPU 多核技術(shù)，都會(huì)有幾級(jí)緩存，老的 CPU 會(huì)有兩級(jí)內(nèi)存（L1 和 L2），新的CPU會(huì)有三級(jí)內(nèi)存（L1，L2，L3 ），如下圖所示：


其中：


  • L1 緩存分成兩種，一種是指令緩存，一種是數(shù)據(jù)緩存。L2 緩存和 L3 緩存不分指令和數(shù)據(jù)。
  • L1 和 L2 緩存在每一個(gè) CPU 核中，L3 則是所有 CPU 核心共享的內(nèi)存。
  • L1、L2、L3 的越離CPU近就越小，速度也越快，越離 CPU 遠(yuǎn)，速度也越慢。
再往后面就是內(nèi)存，內(nèi)存的后面就是硬盤。我們來(lái)看一些他們的速度：


  • L1 的存取速度：4 個(gè)CPU時(shí)鐘周期
  • L2 的存取速度：11 個(gè)CPU時(shí)鐘周期
  • L3 的存取速度：39 個(gè)CPU時(shí)鐘周期
  • RAM內(nèi)存的存取速度 ：107 個(gè)CPU時(shí)鐘周期
我們可以看到，L1 的速度是 RAM 的 27 倍，但是 L1/L2 的大小基本上也就是 KB 級(jí)別的，L3 會(huì)是 MB 級(jí)別的。例如：Intel Core i7-8700K ，是一個(gè) 6 核的 CPU，每核上的 L1 是 64KB（數(shù)據(jù)和指令各 32KB），L2 是 256K，L3 有 2MB（我的蘋果電腦是 Intel Core i9-8950HK，和Core i7-8700K 的Cache大小一樣）。


我們的數(shù)據(jù)就從內(nèi)存向上，先到 L3，再到 L2，再到 L1，最后到寄存器進(jìn)行 CPU 計(jì)算。為什么會(huì)設(shè)計(jì)成三層？這里有下面幾個(gè)方面的考慮：


  • 一個(gè)方面是物理速度，如果要更大的容量就需要更多的晶體管，除了芯片的體積會(huì)變大，更重要的是大量的晶體管會(huì)導(dǎo)致速度下降，因?yàn)樵L問(wèn)速度和要訪問(wèn)的晶體管所在的位置成反比，也就是當(dāng)信號(hào)路徑變長(zhǎng)時(shí)，通信速度會(huì)變慢。這部分是物理問(wèn)題。
  • 另外一個(gè)問(wèn)題是，多核技術(shù)中，數(shù)據(jù)的狀態(tài)需要在多個(gè)CPU中進(jìn)行同步，并且，我們可以看到，cache 和RAM 的速度差距太大，所以，多級(jí)不同尺寸的緩存有利于提高整體的性能。
這個(gè)世界永遠(yuǎn)是平衡的，一面變得有多光鮮，另一面也會(huì)變得有多黑暗。建立這么多級(jí)的緩存，一定就會(huì)引入其它的問(wèn)題，這里有兩個(gè)比較重要的問(wèn)題，


  • 一個(gè)是比較簡(jiǎn)單的緩存的命中率的問(wèn)題。
  • 另一個(gè)是比較復(fù)雜的緩存更新的一致性問(wèn)題。
尤其是第二個(gè)問(wèn)題，在多核技術(shù)下，這就很像分布式的系統(tǒng)了，要對(duì)多個(gè)地方進(jìn)行更新。


緩存的命中

在說(shuō)明這兩個(gè)問(wèn)題之前。我們需要要解一個(gè)術(shù)語(yǔ) Cache Line。緩存基本上來(lái)說(shuō)就是把后面的數(shù)據(jù)加載到離自己近的地方，對(duì)于 CPU 來(lái)說(shuō)，它是不會(huì)一個(gè)字節(jié)一個(gè)字節(jié)的加載的，因?yàn)檫@非常沒(méi)有效率，一般來(lái)說(shuō)都是要一塊一塊的加載的，對(duì)于這樣的一塊一塊的數(shù)據(jù)單位，術(shù)語(yǔ)叫 Cache Line，


一般來(lái)說(shuō)，一個(gè)主流的 CPU 的 Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes），64 Bytes也就是 16 個(gè) 32 位的整型，這就是 CPU 從內(nèi)存中撈數(shù)據(jù)上來(lái)的最小數(shù)據(jù)單位。


比如：Cache Line是最小單位（64Bytes），所以先把 Cache 分布多個(gè) Cache Line，比如：L1 有 32KB，那么，32KB/64B = 512 個(gè) Cache Line。


一方面，緩存需要把內(nèi)存里的數(shù)據(jù)放到放進(jìn)來(lái)，英文叫 CPU Associativity。Cache 的數(shù)據(jù)放置的策略決定了內(nèi)存中的數(shù)據(jù)塊會(huì)拷貝到 CPU Cache 中的哪個(gè)位置上，因?yàn)?Cache 的大小遠(yuǎn)遠(yuǎn)小于內(nèi)存，所以，需要有一種地址關(guān)聯(lián)的算法，能夠讓內(nèi)存中的數(shù)據(jù)可以被映射到 Cache 中來(lái)。這個(gè)有點(diǎn)像內(nèi)存地址從邏輯地址向物理地址映射的方法，但不完全一樣。


基本上來(lái)說(shuō)，我們會(huì)有如下的一些方法。


  • 一種方法是，任何一個(gè)內(nèi)存地址的數(shù)據(jù)可以被緩存在任何一個(gè) Cache Line 里，這種方法是最靈活的，但是，如果我們要知道一個(gè)內(nèi)存是否存在于 Cache 中，我們就需要進(jìn)行 O(n) 復(fù)雜度的 Cache 遍歷，這是很沒(méi)有效率的。
  • 另一種方法，為了降低緩存搜索算法，我們需要使用像Hash Table這樣的數(shù)據(jù)結(jié)構(gòu)，最簡(jiǎn)單的hash table就是做求模運(yùn)算，比如：我們的 L1 Cache 有 512 個(gè) Cache Line，那么，公式：（內(nèi)存地址 mod 512）* 64就可以直接找到所在的Cache地址的偏移了。但是，這樣的方式需要我們的程序?qū)?nèi)存地址的訪問(wèn)要非常地平均，不然沖突就會(huì)非常嚴(yán)重。這成了一種非常理想的情況了。
  • 為了避免上述的兩種方案的問(wèn)題，于是就要容忍一定的hash沖突，也就出現(xiàn)了 N-Way 關(guān)聯(lián)。也就是把連續(xù)的N 個(gè) Cache Line 綁成一組，然后，先把找到相關(guān)的組，然后再在這個(gè)組內(nèi)找到相關(guān)的 Cache Line。這叫 Set Associativity。如下圖所示。
對(duì)于 N-Way 組關(guān)聯(lián)，可能有點(diǎn)不好理解，這里個(gè)例子，并多說(shuō)一些細(xì)節(jié)（不然后面的代碼你會(huì)不能理解），Intel 大多數(shù)處理器的 L1 Cache 都是 32KB，8-Way 組相聯(lián)，Cache Line 是 64 Bytes。這意味著，


  • 32KB的可以分成，32KB / 64 = 512 條 Cache Line。
  • 因?yàn)橛? Way，于是會(huì)每一Way 有 512 / 8 = 64 條 Cache Line。
  • 于是每一路就有 64 x 64 = 4096 Byts 的內(nèi)存。
為了方便索引內(nèi)存地址，


  • Tag：每條 Cache Line 前都會(huì)有一個(gè)獨(dú)立分配的 24 bits來(lái)存的 tag，其就是內(nèi)存地址的前24bits
  • Index：內(nèi)存地址后續(xù)的 6 個(gè) bits 則是在這一 Way 的是Cache Line 索引，2^6 = 64 剛好可以索引64條Cache Line
  • Offset：再往后的 6bits 用于表示在 Cache Line 里的偏移量
如下圖所示：（圖片來(lái)自《Cache: a place for concealment and safekeeping》）


當(dāng)拿到一個(gè)內(nèi)存地址的時(shí)候，先拿出中間的 6bits 來(lái)，找到是哪組。


然后，在這一個(gè) 8 組的 cache line 中，再進(jìn)行 O(n) n=8 的遍歷，主是要匹配前 24bits 的 tag。如果匹配中了，就算命中，如果沒(méi)有匹配到，那就是 cache miss，如果是讀操作，就需要進(jìn)向后面的緩存進(jìn)行訪問(wèn)了。


L2/L3 同樣是這樣的算法。而淘汰算法有兩種，一種是隨機(jī)一種是 LRU?，F(xiàn)在一般都是以 LRU 的算法（通過(guò)增加一個(gè)訪問(wèn)計(jì)數(shù)器來(lái)實(shí)現(xiàn)）


這也意味著：


  • L1 Cache 可映射 36bits 的內(nèi)存地址，一共 2^36 = 64GB 的內(nèi)存
  • 當(dāng) CPU 要訪問(wèn)一個(gè)內(nèi)存的時(shí)候，通過(guò)這個(gè)內(nèi)存中間的 6bits 定位是哪個(gè) set，通過(guò)前 24bits 定位相應(yīng)的Cache Line。
  • 就像一個(gè) hash Table 的數(shù)據(jù)結(jié)構(gòu)一樣，先是 O(1)的索引，然后進(jìn)入沖突搜索。
  • 因?yàn)橹虚g的 6bits 決定了一個(gè)同一個(gè) set，所以，對(duì)于一段連續(xù)的內(nèi)存來(lái)說(shuō)，每隔 4096 的內(nèi)存會(huì)被放在同一個(gè)組內(nèi)，導(dǎo)致緩存沖突。
此外，當(dāng)有數(shù)據(jù)沒(méi)有命中緩存的時(shí)候，CPU 就會(huì)以最小為 Cache Line 的單元向內(nèi)存更新數(shù)據(jù)。當(dāng)然，CPU 并不一定只是更新 64Bytes，因?yàn)樵L問(wèn)主存實(shí)在是太慢了，所以，一般都會(huì)多更新一些。好的 CPU 會(huì)有一些預(yù)測(cè)的技術(shù)，如果找到一種 pattern 的話，就會(huì)預(yù)先加載更多的內(nèi)存，包括指令也可以預(yù)加載。


這叫 Prefetching 技術(shù) （參看，Wikipedia 的 Cache Prefetching 和 紐約州立大學(xué)的 Memory Prefetching）。比如，你在for-loop訪問(wèn)一個(gè)連續(xù)的數(shù)組，你的步長(zhǎng)是一個(gè)固定的數(shù)，內(nèi)存就可以做到prefetching。（注：指令也是以預(yù)加載的方式執(zhí)行）


了解這些細(xì)節(jié)，會(huì)有利于我們知道在什么情況下有可以導(dǎo)致緩存的失效。


緩存的一致性

對(duì)于主流的 CPU 來(lái)說(shuō)，緩存的寫操作基本上是兩種策略，


  • 一種是 Write Back，寫操作只要在 cache 上，然后再 flush 到內(nèi)存上。
  • 一種是 Write Through，寫操作同時(shí)寫到 cache 和內(nèi)存上。
為了提高寫的性能，一般來(lái)說(shuō)，主流的 CPU（如：Intel Core i7/i9）采用的是 Write Back 的策略，因?yàn)橹苯訉憙?nèi)存實(shí)在是太慢了。


好了，現(xiàn)在問(wèn)題來(lái)了，如果有一個(gè)數(shù)據(jù) x 在 CPU 第 0 核的緩存上被更新了，那么其它 CPU 核上對(duì)于這個(gè)數(shù)據(jù) x 的值也要被更新，這就是緩存一致性的問(wèn)題。（當(dāng)然，對(duì)于我們上層的程序我們不用關(guān)心 CPU 多個(gè)核的緩存是怎么同步的，這對(duì)上層的代碼來(lái)說(shuō)都是透明的）


一般來(lái)說(shuō)，在 CPU 硬件上，會(huì)有兩種方法來(lái)解決這個(gè)問(wèn)題。


  • Directory 協(xié)議。這種方法的典型實(shí)現(xiàn)是要設(shè)計(jì)一個(gè)集中式控制器，它是主存儲(chǔ)器控制器的一部分。其中有一個(gè)目錄存儲(chǔ)在主存儲(chǔ)器中，其中包含有關(guān)各種本地緩存內(nèi)容的全局狀態(tài)信息。當(dāng)單個(gè) CPU Cache 發(fā)出讀寫請(qǐng)求時(shí)，這個(gè)集中式控制器會(huì)檢查并發(fā)出必要的命令，以在主存和 CPU Cache之間或在 CPU Cache自身之間進(jìn)行數(shù)據(jù)同步和傳輸。
  • Snoopy 協(xié)議。這種協(xié)議更像是一種數(shù)據(jù)通知的總線型的技術(shù)。CPU Cache 通過(guò)這個(gè)協(xié)議可以識(shí)別其它Cache上的數(shù)據(jù)狀態(tài)。如果有數(shù)據(jù)共享的話，可以通過(guò)廣播機(jī)制將共享數(shù)據(jù)的狀態(tài)通知給其它 CPU Cache。這個(gè)協(xié)議要求每個(gè) CPU Cache 都可以窺探數(shù)據(jù)事件的通知并做出相應(yīng)的反應(yīng)。如下圖所示，有一個(gè) Snoopy Bus 的總線。


因?yàn)?Directory 協(xié)議是一個(gè)中心式的，會(huì)有性能瓶頸，而且會(huì)增加整體設(shè)計(jì)的復(fù)雜度。而 Snoopy 協(xié)議更像是微服務(wù) 消息通訊，所以，現(xiàn)在基本都是使用 Snoopy 的總線的設(shè)計(jì)。


這里，我想多寫一些細(xì)節(jié)，因?yàn)檫@種微觀的東西，讓人不自然地就會(huì)跟分布式系統(tǒng)關(guān)聯(lián)起來(lái)，在分布式系統(tǒng)中我們一般用 Paxos/Raft 這樣的分布式一致性的算法。


而在 CPU 的微觀世界里，則不必使用這樣的算法，原因是因?yàn)?CPU 的多個(gè)核的硬件不必考慮網(wǎng)絡(luò)會(huì)斷會(huì)延遲的問(wèn)題。所以，CPU 的多核心緩存間的同步的核心就是要管理好數(shù)據(jù)的狀態(tài)就好了。


這里介紹幾個(gè)狀態(tài)協(xié)議，先從最簡(jiǎn)單的開(kāi)始，MESI 協(xié)議，這個(gè)協(xié)議跟那個(gè)著名的足球運(yùn)動(dòng)員梅西沒(méi)什么關(guān)系，其主要表示緩存數(shù)據(jù)有四個(gè)狀態(tài)：Modified（已修改）, Exclusive（獨(dú)占的）,Shared（共享的），Invalid（無(wú)效的）。


這些狀態(tài)的狀態(tài)機(jī)如下所示（有點(diǎn)復(fù)雜，你可以先不看，這個(gè)圖就是想告訴你狀態(tài)控制有多復(fù)雜）：


下面是個(gè)示例（如果你想看一下動(dòng)畫演示的話，這里有一個(gè)網(wǎng)頁(yè)（MESI Interactive Animations），你可以進(jìn)行交互操作，這個(gè)動(dòng)畫演示中使用的 Write Through 算法）：


當(dāng)前操作 CPU0 CPU1 Memory 說(shuō)明
1) CPU0 read(x) x=1 (E)
x=1 只有一個(gè)CPU有 x 變量， 所以，狀態(tài)是 Exclusive
2) CPU1 read(x) x=1 (S) x=1(S) x=1 有兩個(gè)CPU都讀取 x 變量， 所以狀態(tài)變成 Shared
3) CPU0 write(x,9) x=9 (M) x=1(I) x=1 變量改變，在CPU0中狀態(tài) 變成 Modified，在CPU1中 狀態(tài)變成 Invalid
4) 變量 x 寫回內(nèi)存 x=9 (M) X=1(I) x=9 目前的狀態(tài)不變
5) CPU1 read(x) x=9 (S) x=9(S) x=9 變量同步到所有的Cache中， 狀態(tài)回到Shared
MESI 這種協(xié)議在數(shù)據(jù)更新后，會(huì)標(biāo)記其它共享的 CPU 緩存的數(shù)據(jù)拷貝為 Invalid 狀態(tài)，然后當(dāng)其它 CPU 再次read 的時(shí)候，就會(huì)出現(xiàn) cache miss 的問(wèn)題，此時(shí)再?gòu)膬?nèi)存中更新數(shù)據(jù)。從內(nèi)存中更新數(shù)據(jù)意味著 20 倍速度的降低。


我們能不能直接從我隔壁的 CPU 緩存中更新？是的，這就可以增加很多速度了，但是狀態(tài)控制也就變麻煩了。還需要多來(lái)一個(gè)狀態(tài)：Owner(宿主)，用于標(biāo)記，我是更新數(shù)據(jù)的源。于是，出現(xiàn)了 MOESI 協(xié)議


MOESI 協(xié)議的狀態(tài)機(jī)和演示示例我就不貼了（有興趣可以上Berkeley上看看相關(guān)的課件），我們只需要理解MOESI協(xié)議允許 CPU Cache 間同步數(shù)據(jù)，于是也降低了對(duì)內(nèi)存的操作，性能是非常大的提升，但是控制邏輯也非常復(fù)雜。


順便說(shuō)一下，與 MOESI 協(xié)議類似的一個(gè)協(xié)議是 MESIF，其中的 F 是 Forward，同樣是把更新過(guò)的數(shù)據(jù)轉(zhuǎn)發(fā)給別的 CPU Cache 但是，MOESI 中的 Owner 狀態(tài) 和MESIF 中的 Forward 狀態(tài)有一個(gè)非常大的不一樣—— Owner 狀態(tài)下的數(shù)據(jù)是 dirty 的，還沒(méi)有寫回內(nèi)存，F(xiàn)orward 狀態(tài)下的數(shù)據(jù)是 clean的，可以丟棄而不用另行通知。


需要說(shuō)明的是，AMD 用 MOESI，Intel 用 MESIF。所以，F(xiàn) 狀態(tài)主要是針對(duì) CPU L3 Cache 設(shè)計(jì)的（前面我們說(shuō)過(guò)，L3 是所有 CPU 核心共享的）。（相關(guān)的比較可以參看StackOverlow上這個(gè)問(wèn)題的答案）


程序性能

了解了我們上面的這些東西后，我們來(lái)看一下對(duì)于程序的影響。


示例一

首先，假設(shè)我們有一個(gè)64M長(zhǎng)的數(shù)組，設(shè)想一下下面的兩個(gè)循環(huán)：


const int LEN = 64*1024*1024;
int *arr = new int[LEN];

for (int i = 0; i < LEN; i = 2) arr[i] *= i;

for (int i = 0; i < LEN; i = 8) arr[i] *= i;
按我們的想法來(lái)看，第二個(gè)循環(huán)要比第一個(gè)循環(huán)少4倍的計(jì)算量，其應(yīng)該也是要快4倍的。但實(shí)際跑下來(lái)并不是，在我的機(jī)器上，第一個(gè)循環(huán)需要 127 毫秒，第二個(gè)循環(huán)則需要 121 毫秒，相差無(wú)幾。


這里最主要的原因就是 Cache Line，因?yàn)?CPU 會(huì)以一個(gè) Cache Line 64Bytes 最小時(shí)單位加載，也就是 16 個(gè) 32bits 的整型，所以，無(wú)論你步長(zhǎng)是 2 還是 8，都差不多。而后面的乘法其實(shí)是不耗 CPU 時(shí)間的。


示例二

我們?cè)賮?lái)看一個(gè)與緩存命中率有關(guān)的代碼，我們以一定的步長(zhǎng)increment來(lái)訪問(wèn)一個(gè)連續(xù)的數(shù)組。


for (int i = 0; i < 10000000; i ) {
for (int j = 0; j < size; j = increment) {
memory[j]  = j;
}
}
我們測(cè)試一下，在下表中， 表頭是步長(zhǎng)，也就是每次跳多少個(gè)整數(shù)，而縱向是這個(gè)數(shù)組可以跳幾次（你可以理解為要幾條 Cache Line），于是表中的任何一項(xiàng)代表了這個(gè)數(shù)組有多少，而且步長(zhǎng)是多少。


比如：橫軸是 512，縱軸是4，意思是，這個(gè)數(shù)組有 4*512 = 2048個(gè)長(zhǎng)度，訪問(wèn)時(shí)按512步長(zhǎng)訪問(wèn)，也就是訪問(wèn)其中的這幾項(xiàng)：[0, 512, 1024, 1536]這四項(xiàng)。


表中同的項(xiàng)是，是循環(huán) 1000 萬(wàn)次的時(shí)間，單位是“微秒”（除以1000后是毫秒）


| count |   1    |   16  |  512  | 1024  |
------------------------------------------
|     1 |  17539 | 16726 | 15143 | 14477 |
|     2 |  15420 | 14648 | 13552 | 13343 |
|     3 |  14716 | 14463 | 15086 | 17509 |
|     4 |  18976 | 18829 | 18961 | 21645 |
|     5 |  23693 | 23436 | 74349 | 29796 |
|     6 |  23264 | 23707 | 27005 | 44103 |
|     7 |  28574 | 28979 | 33169 | 58759 |
|     8 |  33155 | 34405 | 39339 | 65182 |
|     9 |  37088 | 37788 | 49863 |156745 |
|    10 |  41543 | 42103 | 58533 |215278 |
|    11 |  47638 | 50329 | 66620 |335603 |
|    12 |  49759 | 51228 | 75087 |305075 |
|    13 |  53938 | 53924 | 77790 |366879 |
|    14 |  58422 | 59565 | 90501 |466368 |
|    15 |  62161 | 64129 | 90814 |525780 |
|    16 |  67061 | 66663 | 98734 |440558 |
|    17 |  71132 | 69753 |171203 |506631 |
|    18 |  74102 | 73130 |293947 |550920 |
我們可以看到，從 [9，1024]以后，時(shí)間顯著上升。包括 [17，512]和 [18,512]也顯著上升。這是因?yàn)?，我機(jī)器的 L1 Cache 是 32KB, 8 Way 的，前面說(shuō)過(guò)，8 Way 的有 64 組，每組 8 個(gè) Cache Line，當(dāng) for-loop步長(zhǎng)超過(guò) 1024 個(gè)整型，也就是正好 4096 Bytes 時(shí)，也就是導(dǎo)致內(nèi)存地址的變化是變化在高位的 24bits 上，


而低位的1 2bits 變化不大，尤其是中間6bits沒(méi)有變化，導(dǎo)致全部命中同一組 set，導(dǎo)致大量的 cache 沖突，導(dǎo)致性能下降，時(shí)間上升。而 [16, 512]也是一樣的，其中的幾步開(kāi)始導(dǎo)致L1 Cache開(kāi)始沖突失效。


示例三

接下來(lái)，我們?cè)賮?lái)看個(gè)示例。下面是一個(gè)二維數(shù)組的兩種遍歷方式，一個(gè)逐行遍歷，一個(gè)是逐列遍歷，這兩種方式在理論上來(lái)說(shuō)，尋址和計(jì)算量都是一樣的，執(zhí)行時(shí)間應(yīng)該也是一樣的。


const int row = 1024;
const int col = 512
int matrix[row][col];

//逐行遍歷
int sum_row=0;
for(int _r=0; _r for(int _c=0; _c sum_row  = matrix[_r][_c];
}
}

//逐列遍歷
int sum_col=0;
for(int _c=0; _c for(int _r=0; _r sum_col  = matrix[_r][_c];
}
}
然而，并不是，在我的機(jī)器上，得到下面的結(jié)果。


  • 逐行遍歷：0.081ms
  • 逐列遍歷：1.069ms
執(zhí)行時(shí)間有十幾倍的差距。其中的原因，就是逐列遍歷對(duì)于 CPU Cache 的運(yùn)作方式并不友好，所以，付出巨大的代價(jià)。


示例四

接下來(lái)，我們來(lái)看一下多核下的性能問(wèn)題，參看如下的代碼。兩個(gè)線程在操作一個(gè)數(shù)組的兩個(gè)不同的元素（無(wú)需加鎖），線程循環(huán)1000萬(wàn)次，做加法操作。在下面的代碼中，我高亮了一行，就是p2指針，要么是p[1]，或是 p[30]，理論上來(lái)說(shuō)，無(wú)論訪問(wèn)哪兩個(gè)數(shù)組元素，都應(yīng)該是一樣的執(zhí)行時(shí)間。


void fn (int* data) {
for(int i = 0; i < 10*1024*1024; i)
*data  = rand();
}

int p[32];

int *p1 = 
本站聲明： 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布，目的在于傳遞更多信息，并不代表本站贊同其觀點(diǎn)，本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者，如若文章內(nèi)容侵犯您的權(quán)益，請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息，不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司，隨著阿維塔和賽力斯的入局，華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字： 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國(guó)汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V，這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具，可用于創(chuàng)建軟件定義汽車。 SODA V工具的開(kāi)發(fā)耗時(shí)1.5...

關(guān)鍵字： 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來(lái)越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行，同時(shí)企業(yè)卻面臨越來(lái)越多業(yè)務(wù)中斷的風(fēng)險(xiǎn)，如企業(yè)系統(tǒng)復(fù)雜性的增加，頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性，提升韌性，成...

關(guān)鍵字： 亞馬遜 解密 控制平面 BSP

8月30日消息，據(jù)媒體報(bào)道，騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字： 騰訊 編碼器 CPU

8月28日消息，今天上午，2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開(kāi)幕式在貴陽(yáng)舉行，華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字： 華為 12nm EDA 半導(dǎo)體

8月28日消息，在2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上，華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱，數(shù)字世界的話語(yǔ)權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字： 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn)： 有效應(yīng)對(duì)環(huán)境變化，經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措，毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著，戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng)，提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略，塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字： 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日，由中央廣播電視總臺(tái)與中國(guó)電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字： VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上，軟通動(dòng)力信息技術(shù)（集團(tuán)）股份有限公司（以下簡(jiǎn)稱"軟通動(dòng)力"）與長(zhǎng)三角投資（上海）有限...

關(guān)鍵字： BSP 信息技術(shù)
關(guān)閉