8.1節(jié)中，我們看到了各種劃分方法；并且在8.2節(jié)，了解了對(duì)性能影響的各種因素。如何在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，使用這些信息提高多線(xiàn)程代碼的性能？這里的問(wèn)題與第6、7章中的問(wèn)題不同，之前是關(guān)于如何設(shè)計(jì)能夠安全、并發(fā)訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。在8.2節(jié)中，單線(xiàn)程中使用的數(shù)據(jù)布局就會(huì)對(duì)性能產(chǎn)生巨大沖擊(即使數(shù)據(jù)并未與其他線(xiàn)程進(jìn)行共享)。
關(guān)鍵的是，當(dāng)為多線(xiàn)程性能而設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，需要考慮競(jìng)爭(zhēng)(contention)，偽共享(false sharing)和數(shù)據(jù)距離(data proximity)。這三個(gè)因素對(duì)于性能都有著重大的影響，并且你通?？梢愿纳频氖菙?shù)據(jù)布局，或者將賦予其他線(xiàn)程的數(shù)據(jù)元素進(jìn)行修改。首先，讓我們來(lái)看一個(gè)輕松方案：線(xiàn)程間劃分?jǐn)?shù)組元素。
假設(shè)你有一些偏數(shù)學(xué)計(jì)算任務(wù)，比如，需要將兩個(gè)很大的矩陣進(jìn)行相乘。對(duì)于矩陣相乘來(lái)說(shuō)，將第一個(gè)矩陣中的首行每個(gè)元素和第二個(gè)矩陣中首列每個(gè)元素相乘后，再相加，從而產(chǎn)生新矩陣中左上角的第一個(gè)元素。然后，第二行和第一列，產(chǎn)生新矩陣第一列上的第二個(gè)結(jié)果，第二行和第二列，產(chǎn)生新矩陣中第二列的第一個(gè)結(jié)果，以此類(lèi)推。如圖8.3所示，高亮展示的就是在新矩陣中第二行-第三列中的元素產(chǎn)生的過(guò)程。
http://wiki.jikexueyuan.com/project/cplusplus-concurrency-action/images/chapter8/8-3.png" alt="" />
圖8.3 矩陣相乘
現(xiàn)在，讓我們假設(shè)兩個(gè)矩陣都有上千行和上千列，為了使用多線(xiàn)程來(lái)優(yōu)化矩陣乘法。通常，非稀疏矩陣可以用一個(gè)大數(shù)組來(lái)代表，也就是第二行的元素緊隨著第一行的，以此類(lèi)推。為了完成矩陣乘法，這里就需要三個(gè)大數(shù)組。為了優(yōu)化性能，你需要仔細(xì)考慮數(shù)據(jù)訪(fǎng)問(wèn)的模式，特別是向第三個(gè)數(shù)組中寫(xiě)入的方式。
線(xiàn)程間劃分工作是有很多種方式的。假設(shè)矩陣的行或列數(shù)量大于處理器的數(shù)量，可以讓每個(gè)線(xiàn)程計(jì)算出結(jié)果矩陣列上的元素，或是行上的元素，亦或計(jì)算一個(gè)子矩陣。
回顧一下8.2.3和8.2.4節(jié)，對(duì)于一個(gè)數(shù)組來(lái)說(shuō)，訪(fǎng)問(wèn)連續(xù)的元素是最好的方式，因?yàn)檫@將會(huì)減少緩存的使用，并且降低偽共享的概率。如果要讓每個(gè)線(xiàn)程處理幾行，線(xiàn)程需要讀取第一個(gè)矩陣中的每一個(gè)元素，并且讀取第二個(gè)矩陣上的相關(guān)行上的數(shù)據(jù)，不過(guò)這里只需要對(duì)列的值進(jìn)行寫(xiě)入。給定的兩個(gè)矩陣是以行連續(xù)的方式存儲(chǔ)，這就意味著當(dāng)你訪(fǎng)問(wèn)第一個(gè)矩陣的第一行的前N個(gè)元素，然后是第二行的前N個(gè)元素，以此類(lèi)推(N是列的數(shù)量)。其他線(xiàn)程會(huì)訪(fǎng)問(wèn)每行的的其他元素；很明顯的，應(yīng)該訪(fǎng)問(wèn)相鄰的列，所以從行上讀取的N個(gè)元素也是連續(xù)的，這將最大程度的降低偽共享的幾率。當(dāng)然，如果空間已經(jīng)被N個(gè)元素所占有，且N個(gè)元素也就是每個(gè)緩存行上具體的存儲(chǔ)元素?cái)?shù)量，就會(huì)讓偽共享的情況消失，因?yàn)榫€(xiàn)程將會(huì)對(duì)獨(dú)立緩存行上的數(shù)據(jù)進(jìn)行操作。
另一方面，當(dāng)每個(gè)線(xiàn)程處理一組行，就需要讀取第二個(gè)矩陣上的每一個(gè)數(shù)據(jù)，還要讀取第一個(gè)矩陣中的相關(guān)行上的值，不過(guò)這里只需要對(duì)行上的值進(jìn)行寫(xiě)入。因?yàn)榫仃囀且孕羞B續(xù)的方式存儲(chǔ)，那么現(xiàn)在可以以N行的方式訪(fǎng)問(wèn)所有的元素。如果再次選擇相鄰行，這就意味著線(xiàn)程現(xiàn)在只能寫(xiě)入N行，這里就有不能被其他線(xiàn)程所訪(fǎng)問(wèn)的連續(xù)內(nèi)存塊。那么讓線(xiàn)程對(duì)每組列進(jìn)行處理就是一個(gè)改進(jìn)，因?yàn)閭喂蚕碇豢赡苡性谝粋€(gè)內(nèi)存塊的最后幾個(gè)元素和下一個(gè)元素的開(kāi)始幾個(gè)上發(fā)生，不過(guò)具體的時(shí)間還要根據(jù)目標(biāo)架構(gòu)來(lái)決定。
第三個(gè)選擇——將矩陣分成小矩陣塊？這可以看作先對(duì)列進(jìn)行劃分，再對(duì)行進(jìn)行劃分。因此，劃分列的時(shí)候，同樣有偽共享的問(wèn)題存在。如果你可以選擇內(nèi)存塊所擁有行的數(shù)量，就可以有效的避免偽共享；將大矩陣劃分為小塊，對(duì)于讀取來(lái)說(shuō)是有好處的：就不再需要讀取整個(gè)源矩陣了。這里，只需要讀取目標(biāo)矩形里面相關(guān)行列的值就可以了。具體的來(lái)看，考慮1,000行和1,000列的兩個(gè)矩陣相乘。就會(huì)有1百萬(wàn)個(gè)元素。如果有100個(gè)處理器，這樣就可以每次處理10行的數(shù)據(jù)，也就是10,000個(gè)元素。不過(guò)，為了計(jì)算著10,000個(gè)元素，就需要對(duì)第二個(gè)矩陣中的全部?jī)?nèi)容進(jìn)行訪(fǎng)問(wèn)(1百萬(wàn)個(gè)元素)，再加上10,000個(gè)相關(guān)行(第一個(gè)矩陣)上的元素，大概就要訪(fǎng)問(wèn)1,010,000個(gè)元素。另外，硬件能處理100x100的數(shù)據(jù)塊(總共10,000個(gè)元素)，這就需要對(duì)第一個(gè)矩陣中的100行進(jìn)行訪(fǎng)問(wèn)(100x1,000=100,000個(gè)元素)，還有第二個(gè)矩陣中的100列(另外100,000個(gè))。這才只有200,000個(gè)元素，就需要五輪讀取才能完成。如果這里讀取的元素少一些，緩存缺失的情況就會(huì)少一些，對(duì)于性能來(lái)說(shuō)就好一些。
因此，將矩陣分成小塊或正方形的塊，要比使用單線(xiàn)程來(lái)處理少量的列好的多。當(dāng)然，可以根據(jù)源矩陣的大小和處理器的數(shù)量，在運(yùn)行時(shí)對(duì)塊的大小進(jìn)行調(diào)整。和之前一樣，當(dāng)性能是很重要的指標(biāo)，就需要對(duì)目標(biāo)架構(gòu)上的各項(xiàng)指標(biāo)進(jìn)行測(cè)量。
如果不做矩陣乘法，該如何對(duì)上面提到的方案進(jìn)行應(yīng)用呢？同樣的原理可以應(yīng)用于任何情況，這種情況就是有很大的數(shù)據(jù)塊需要在線(xiàn)程間進(jìn)行劃分；仔細(xì)觀(guān)察所有數(shù)據(jù)訪(fǎng)問(wèn)的各個(gè)方面，以及確定性能問(wèn)題產(chǎn)生的原因。各種領(lǐng)域中，出現(xiàn)問(wèn)題的情況都很相似：改變劃分方式就能夠提高性能，而不需要對(duì)基本算法進(jìn)行任何修改。
OK，我們已經(jīng)了解了訪(fǎng)問(wèn)數(shù)組是如何對(duì)性能產(chǎn)生影響的。那么其他類(lèi)型的數(shù)據(jù)結(jié)構(gòu)呢？
根本上講，同樣的考慮適用于想要優(yōu)化數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)訪(fǎng)問(wèn)模式，就像優(yōu)化對(duì)數(shù)組的訪(fǎng)問(wèn)：
嘗試調(diào)整數(shù)據(jù)在線(xiàn)程間的分布，就能讓同一線(xiàn)程中的數(shù)據(jù)緊密聯(lián)系在一起。
嘗試減少線(xiàn)程上所需的數(shù)據(jù)量。
當(dāng)然，應(yīng)用于其他數(shù)據(jù)結(jié)構(gòu)上會(huì)比較麻煩。例如，對(duì)二叉樹(shù)劃分就要比其他結(jié)構(gòu)困難，有用與沒(méi)用要取決于樹(shù)的平衡性，以及需要?jiǎng)澐值墓?jié)點(diǎn)數(shù)量。同樣，樹(shù)的的屬性決定了其節(jié)點(diǎn)會(huì)動(dòng)態(tài)的進(jìn)行分配，并且在不同的地方進(jìn)行釋放。
現(xiàn)在，節(jié)點(diǎn)在不同的地方釋放倒不是一個(gè)嚴(yán)重的問(wèn)題，不過(guò)這就意味著處理器需要在緩存中存儲(chǔ)很多東西，這實(shí)際上是有好處的。當(dāng)多線(xiàn)程需要旋轉(zhuǎn)樹(shù)的時(shí)候，就需要對(duì)樹(shù)中的所有節(jié)點(diǎn)進(jìn)行訪(fǎng)問(wèn)，不過(guò)當(dāng)樹(shù)中的節(jié)點(diǎn)只包括指向?qū)嶋H值的指針時(shí)，處理器只能從主存中對(duì)數(shù)據(jù)進(jìn)行加載。如果數(shù)據(jù)正在被訪(fǎng)問(wèn)線(xiàn)程所修改，這就能避免節(jié)點(diǎn)數(shù)據(jù)，以及樹(shù)數(shù)據(jù)結(jié)構(gòu)間的偽共享。
這里就和用一個(gè)互斥量來(lái)保護(hù)數(shù)據(jù)類(lèi)似了。假設(shè)你有一個(gè)簡(jiǎn)單的類(lèi)，包含一些數(shù)據(jù)項(xiàng)和一個(gè)用于保護(hù)數(shù)據(jù)的互斥量(在多線(xiàn)程環(huán)境下)。如果互斥量和數(shù)據(jù)項(xiàng)在內(nèi)存中很接近，對(duì)與一個(gè)需要獲取互斥量的線(xiàn)程來(lái)說(shuō)是很理想的情況；需要的數(shù)據(jù)可能早已存入處理器的緩存中了，因?yàn)樵谥盀榱藢?duì)互斥量進(jìn)行修改，已經(jīng)加載了需要的數(shù)據(jù)。不過(guò)，這還有一個(gè)缺點(diǎn)：當(dāng)其他線(xiàn)程嘗試鎖住互斥量時(shí)(第一個(gè)線(xiàn)程還沒(méi)有是釋放)，線(xiàn)程就能對(duì)對(duì)應(yīng)的數(shù)據(jù)項(xiàng)進(jìn)行訪(fǎng)問(wèn)?；コ怄i是當(dāng)做一個(gè)“讀-改-寫(xiě)”原子操作實(shí)現(xiàn)的，對(duì)于相同位置的操作都需要先獲取互斥量，如果互斥量已鎖，那就會(huì)調(diào)用系統(tǒng)內(nèi)核。這種“讀-改-寫(xiě)”操作，可能會(huì)讓數(shù)據(jù)存儲(chǔ)在緩存中，讓線(xiàn)程獲取的互斥量變得毫無(wú)作用。從目前互斥量的發(fā)展來(lái)看，這并不是個(gè)問(wèn)題;線(xiàn)程不會(huì)直到互斥量解鎖，才接觸互斥量。不過(guò)，當(dāng)互斥量共享同一緩存行時(shí)，其中存儲(chǔ)的是線(xiàn)程已使用的數(shù)據(jù)，這時(shí)擁有互斥量的線(xiàn)程將會(huì)遭受到性能打擊，因?yàn)槠渌€(xiàn)程也在嘗試鎖住互斥量。
一種測(cè)試偽共享問(wèn)題的方法是：對(duì)大量的數(shù)據(jù)塊填充數(shù)據(jù)，讓不同線(xiàn)程并發(fā)的進(jìn)行訪(fǎng)問(wèn)。比如，你可以使用：
struct protected_data
{
std::mutex m;
char padding[65536]; // 65536字節(jié)已經(jīng)超過(guò)一個(gè)緩存行的數(shù)量級(jí)
my_data data_to_protect;
};用來(lái)測(cè)試互斥量競(jìng)爭(zhēng)或
struct my_data
{
data_item1 d1;
data_item2 d2;
char padding[65536];
};
my_data some_array[256];用來(lái)測(cè)試數(shù)組數(shù)據(jù)中的偽共享。如果這樣能夠提高性能，你就能知道偽共享在這里的確存在。
當(dāng)然，在設(shè)計(jì)并發(fā)的時(shí)候有更多的數(shù)據(jù)訪(fǎng)問(wèn)模式需要考慮，現(xiàn)在讓我們一起來(lái)看一些附加的注意事項(xiàng)。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多