計算機和軟體專業的同學在本科期間都有一門必修課：國內大多數叫《資料結構》，國外大多叫《演算法導論》，非常重要，分為兩部分：資料結構——array、list、stack、queue、tree、set、graph等，和演算法——增刪改查、排序等等，
這是狹義上的資料結構和演算法，實際軟體開發中，只要涉及到復雜的功能時，往往會涉及書本之外的資料結構和演算法的問題，對于大型軟體工程來說，尤其是游戲引擎這種對性能要求近乎苛刻的系統，演算法尤為重要，
但是，我們在大學里學習《資料結構》這門課時，并不知道的一點是，這些資料結構和演算法都是在計算機的“鴻蒙時代”設計出來的，計算和資料讀取的性能接近，但是如果運行在當今的硬體上，可能使用map不見得比無腦遍歷連續陣列的方式更快，甚至同樣的演算法在不同的硬體架構下也會得出截然相反的結果，忽視了硬體特性的資料結構和演算法，高性能就是鏡中花，水中月，遺憾的是大學里老師不會告訴我們這些，以至于作業了很多年的程式員，甚至是很多引擎程式員都不知道，依然生搬硬套教科書上的做法，難免貽笑大方，
寒霜引擎做過一件“毀三觀”的事：不用四叉樹、八叉樹、BSP、BVH、Portal等來管理場景，而是無腦遍歷所有場景物體，竟然更快，見《Culling The Battlefield》，
那么這是為什么呢？其實這是近代計算機硬體的發展趨勢導致的，我們先來看一下近些年來硬體的發展軌跡，見下圖（不要糾結現在馬上就2021年了，而圖中的資料只到2010年），圖中顯示了計算性能大幅提升，而帶寬卻發展緩慢，
為了提升性能，當前PC上的CPU都是金字塔式的三級cache：越靠近CPU，cache大小越小，速度越高，執行命令訪問資料時，先從cache line開始查找，沒有的話就依次向遠離CPU的方向訪問各級cache，一直到主存盤器，甚至是去磁盤或者外部存盤設備上訪問資料，這樣，如果資料組織的跟演算法的訪問順序很接近，那么就能大幅減少Cache miss，從而大幅提升性能，那可能有人要問，干嘛不給CPU一大塊速度非常高的cache呢？很簡單，就是成本太高了，
所以，如果你寫的代碼性能低，可能往往不是你的指令太多，而是資料排布的不合理，造成了大量的cache miss，
針對這種硬體現狀，就誕生了一種新的程式設計思想——面向資料編程（Data-oriented design），簡稱DOD，傳統的面向物件設計是以功能為核心的，而DOD是以資料處理為核心的（程式的根本目的不就是處理資料嗎），核心思想就是將需要處理的相關資料都緊密排布在物理存盤器上，一次性處理一組物件的某個操作，而不是隨意訪問分散在物理記憶體上的各種資料，另外需要注意的是，程式本身也是資料，執行前也需要加載到CPU去執行，一次性處理所有的資料就不存在反復加載程式了，DOD的資料組織形式最典型的一種就是將AOS（Array of Structures）改成SOA（Structure of Arrays），分別見下圖（出自https://en.wikipedia.org/wiki/AoS_and_SoA），
DOD也不是什么新技術了，Ogre 2.0多年前就開始研發了，計劃從面向物件改成面向資料設計，見《OGRE.2.0.pdf》，2013-2015年在自研《盤古引擎》時也開始使用包括DOD這樣的cache友好的設計思想，下面羅列這期間遇到過的一些相關案例，
資料壓縮是最常見的一種cache友好的方案，例如，我們紋理壓縮、頂點屬性壓縮，甚至是延遲著色里的GBuffer也能瘋狂壓縮（CryEngine曾經將GBuffer壓縮到了3張RT），
記憶體池和物件池是為了解決記憶體碎片，但是也利于性能提升，
將Ogre里的八叉樹改成Cache友好的四叉樹，性能提升很多，
使用面向資料設計去重構粒子系統，大幅減少cache miss，
SSAO采樣數量一定的情況下，隨著采樣核的增大，耗時也會增大，為啥？就是因為GPU上的cache大小也是有限的，采樣范圍大了就增加了cache miss，還有，渲染SSAO時用了一個4x4的隨機紋理，在螢屏上反復平鋪以增加采樣方向的隨機性，也實踐了資料訪問的連續性，下圖分別為隨機紋理、中間結果和最終過濾的結果，
模型里的頂點在編輯器里需要排序，以有效利用VS處理時的cache，
Stl庫里的很多容器（containers）的第二個模板引數默認都是內置的模板類template <class _Ty> class allocator，一般來說，內置的分配器就足夠了，但是對于3D實時引擎這種對性能要求近乎苛刻的系統，自己設計一個就可以根據實際的應用場景來合理排布容器元素，
曾幫一家公司優化過一個演算法，里面需要遍歷一個二維陣列，修改下訪問的主序就能得到截然不同的性能，
之前做分布式紋理壓縮時深入研究過pvr這種外部壓縮格式，內部壓縮格式有PVRTC2和PVRTC4，發現它們的紋素排列方式很詭異，并不是像其它壓縮格式那樣簡單地從從上到下、從左到右，而是之字形排布的，推斷為的也是cache友好，須知GPU里的顯存也是有cache的，我們shader里進行一次采樣，其實硬體就是將一大塊都從顯存里傳輸到cache里了，除了CPU上有“cache友好”這一說法，GPU上也是有的，
最近兩年Unity也搞出了ECS，其實就是新瓶裝舊酒，底層依然是DOD的設計思想，當然不可否認的是Unity一貫的優勢——易用性做的真的很好，盡管各種引擎內部都支持DOD的設計，但是能將這個技術暴露出給用戶使用的，獨此一家，
所以說資料的組織形式比演算法更重要：演算法是由需求決定的，資料要按照演算法去排布，
當然，DOD也有缺點，會破壞封裝性，增加了維護成本，那么怎么來決定是用OOD還是DOD呢？我的結論是，將你代碼里的1%-10%的代碼熱點使用DOD，其它地方使用OOD，“將性能優化到極致”是我的口頭禪，但是也不會不明白“過猶不及”的道理，世界上絕大部分選擇本就是妥協的結果，
那么回到原來的問題，大學學習《資料結構和演算法》就沒有用處了？絕不是的，首先是通過這門課來深入理解軟體運行的原理，另外，還能鍛煉邏輯思維能力，當然還有很多都可以鍛煉邏輯思維能力，比如那個輟學搞寫作的韓寒曾說過，靠學習數學來練習邏輯思維能力就是扯淡，他認為寫作更能鍛煉這個能力，
那么學習《資料結構和演算法》還有什么額外的用處呢？肯定也是有的，保不準哪一天等你已經作業了十幾年以后，還有極個別公司面試時會拿這個來難為你，這時你就不用再消耗寶貴的時間去翻書了，
最近很忙，隨便寫點吧，寫到哪算哪，參考的很多案例都是很多年前的，難免記憶出現錯位，也懶得去查筆記驗證了，出現錯誤請求讀者斧正，另外很多地方跳躍性較強，也難免燈下黑，老引擎程式員可能都碰到過類似問題，看后會心一笑，新入行的看懵的話也不負責解釋，以后作業中慢慢去品吧，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241322.html
標籤：其他
下一篇：計網計算題