數(shù)據(jù)布局

數(shù)據(jù)重組

程序的核心循環(huán)中常常存在多個(gè)數(shù)組之間的運(yùn)算，而這些數(shù)組在內(nèi)存中并不是連續(xù)存放的，會導(dǎo)致程序的訪存局部性較差。此時(shí)可以使用數(shù)組重組的方式將多個(gè)數(shù)組合并成為結(jié)構(gòu)體數(shù)組，該結(jié)構(gòu)體的屬性域?yàn)橹亟M前各數(shù)組的元素，從而提高程序訪問數(shù)據(jù)的局部性。

原始代碼：

優(yōu)化后代碼：

數(shù)據(jù)轉(zhuǎn)置

當(dāng)循環(huán)訪問數(shù)組中元素時(shí)，若最內(nèi)層循環(huán)對數(shù)組的索引方式與內(nèi)存中的存放方式不同，會導(dǎo)致數(shù)據(jù)的訪問不連續(xù)，無法充分利用程序的空間局部性。針對這一問題，可以使用數(shù)組轉(zhuǎn)置的方法對數(shù)組的數(shù)據(jù)布局進(jìn)行變換，使得內(nèi)層循環(huán)對數(shù)組的訪問連續(xù)。

原始代碼：

優(yōu)化后代碼：

結(jié)構(gòu)屬性域調(diào)整

程序中訪問結(jié)構(gòu)體變量時(shí)，常被訪問的可能是少量的屬性域，如果改變這些結(jié)構(gòu)的定義，使經(jīng)常被訪問的屬性域組織在一起，能夠有效地提高結(jié)構(gòu)定義變量的空間局部性。示例如下。

原始代碼：

優(yōu)化后代碼：

屬性域調(diào)整后改善了內(nèi)存中數(shù)據(jù)的連續(xù)性。經(jīng)過測試，進(jìn)行100000次循環(huán)迭代，結(jié)構(gòu)屬性域調(diào)整前耗時(shí)494us，調(diào)整后耗時(shí)395us。優(yōu)化人員在編寫程序時(shí)合理的運(yùn)用此類技巧，可以使得程序的運(yùn)行情況更好。

結(jié)構(gòu)體拆分

除了結(jié)構(gòu)體屬性域調(diào)整能夠改進(jìn)數(shù)據(jù)的局部性，結(jié)構(gòu)體拆分也能改進(jìn)數(shù)據(jù)的局部性。上節(jié)列舉的示例經(jīng)過結(jié)構(gòu)體屬性域調(diào)整后，雖然同一次迭代內(nèi)x維的時(shí)間t_x、速度v_x和位移d_x在內(nèi)存中存放連續(xù)，但是相鄰的迭代間P[i]和P[i+1]的數(shù)據(jù)在內(nèi)存中還是不連續(xù)的，此時(shí)可以利用結(jié)構(gòu)體拆分的方法進(jìn)行改寫。

將結(jié)構(gòu)體拆分成三個(gè)結(jié)構(gòu)體后，以motion_x為例，數(shù)據(jù)在內(nèi)存中的布局如圖示

繼續(xù)以上述結(jié)構(gòu)拆分的代碼段定義的motion_x結(jié)構(gòu)體為例，經(jīng)過結(jié)構(gòu)拆分之后相鄰的迭代間P[i]和p[i+1]的數(shù)據(jù)已經(jīng)連續(xù)，但t_x、v_x、d_x相鄰迭代的數(shù)據(jù)在內(nèi)存中依然不是連續(xù)的。此時(shí)可以使用結(jié)構(gòu)體數(shù)組轉(zhuǎn)為數(shù)組結(jié)構(gòu)體的方法，將不連續(xù)的數(shù)據(jù)存放在數(shù)組結(jié)構(gòu)體中，改進(jìn)程序的數(shù)據(jù)布局情況。

將結(jié)構(gòu)體數(shù)組轉(zhuǎn)換為數(shù)組結(jié)構(gòu)體后，數(shù)據(jù)t_x、v_x和d_x相鄰迭代的數(shù)據(jù)在內(nèi)存中連續(xù)存放，如圖所示。

總結(jié)

訪存性能優(yōu)化是程序性能優(yōu)化中重要的組成部分。這部分內(nèi)容從計(jì)算機(jī)多層次存儲結(jié)構(gòu)的基本概念出發(fā)，按照離處理器從近至遠(yuǎn)的順序介紹了一些如何更好地利用多層次存儲結(jié)構(gòu)的程序優(yōu)化方法，并說明了如何在編寫程序時(shí)改善數(shù)據(jù)局部性，以提高程序的訪存性能。