1. May I have 1 bit ? 下面兩段代碼，哪一個占用空間更少，那個速度更快？思考10秒再繼續往下看:) 復制代碼 //v1 struct BitBool { bool b0 :1; bool b1 :1; bool b2 :1; } BitBool bb; bb.b1 = true; //v2 struct NormalBool { bool b0; bool b1; bool b2; } NormalBool nb; nb.b1 = true; 復制代碼 第一種通常被認為是優化的版本，甚至UE3裡都有很多類似代碼，但實際上卻在兩方面都不占優，why？原因是現代大部分cpu都沒有指令能直接訪問1bit數據，而 bb.b1 = true 相當於 bb.b1 |= (1<<xxxx); 相應匯編代碼可能為(實際匯編根據編譯器可能會不同): shl cl,2 xor cl,al and cl,4 xor al,cl 而 nb.b1 = true;只需要 mov BYTE PTR [rcx+2], dl 當考慮空間優化時一般只考慮到了數據占用空間，而沒有考慮代碼所占用的內存。因此雖然sizeof(BitBool)==1==8bit (默認8bit對齊的系統)，但訪問b1的指令所占空間卻需要8~11byte！ 考慮到訪問成員的代碼通常會成為內聯函數，因此BitBool所占空間為 1 + 11 * n ，n為代碼中需要訪問數據的次數！ 而NormalBool雖然需要3byte，但其訪問代碼只需要3byte機器碼，所占空間為3 + 3 * n。因此無論在性能還是空間性，NormalBool均更好！ 2 Cache missing is killer!!! 把一個隨機數列依次插入list和vector，保持兩個新數列從小到大排序：7,5,2,7,9,3 ===> 2,3,5,7,7,9 ，下面是代碼，對於不同的數據量n，哪一種方法更好？ 復制代碼 std::list<int> myList; std::vector<int> myVec; //create a random number array const int size = 50000; std::array<int, size> myArr; for(int i = 0; i < size; i++) { myArr[i] = rand() % 2000; } //pre-allocate memory myVec.reserve(size); myList.resize(size,65535); //fill vector for(int i = 0; i < size; i++) { int value = myArr[i]; auto it = myVec.begin(); for(; it != myVec.end(); it++) { if(*it > value) { it = myVec.insert(it, value); break; } } if(it == myVec.end()) myVec.push_back(value); } //fill list for(int i = 0; i < size; i++) { int value = myArr[i]; auto it = myList.begin(); for(; it != myList.end(); it++) { if(*it > value) { it = myList.insert(it, value); break; } } if(it == myList.end()) myList.push_back(value); } 復制代碼 兩段代碼幾乎相同從算法分析的角度看，頻繁插入操作是vector的災難，但實際測試結論是無論size為多大，vector總是比list快，並且size越大，差距越明顯,在我的機器上當size=50k時快了近10倍！！why？首先list需要占用更多內存，其次vector總是保證元素位於連續的內存，這是最重要的！Cache missing導致的性能損失甚至比復制元素還嚴重。對現代CPU來說，運算速度已經非常快，一次cache missing就會浪費n個cpu周期，合理組織數據，讓cpu減少等待時間是現代cpu非常重要的優化手段。 注意，上面的演示代碼只是為了展示cache missing的重要性，並不是完成這個任務的最優方法，另外實際情況下對於復雜類型來說，隨著復制代價的提高，vector未必就能總勝出了:)。 3. False Sharing（cache-line ping-ponging） 大部分程序員都聽說過cache missing，但知道false sharing的就不那麼多了。為了討論false sharing，首先要介紹cache line. 就像CPU不能讀取1bit一樣，cpu訪問cache時通常也會多讀取一些額外數據，同時讀取的這一段數據就稱為一條cache line。每一級cache都由n條cache line組成，對於intel i級的cpu來說cache line大小為64byte。假設cpu需要訪問變量v時， v地址附近的數據都被讀入cache中。對於單核的世界來說，一切都很好，但對於多核心下的多線程設計來說，問題就來了，假設v被加載到了第一個核的cache中，此時另一個核心需要訪問臨近v的變量v1怎麼辦？ 如果都是只讀操作，那麼每個核心可以各保存一份cache line v的副本，不會有沖突。但如果線程1需要修改v，線程2需要修改v2怎麼辦呢，顯然會導致不同核心的cache line狀態不一致。為了解決這個問題，整個cache line都要被來回重新加載。比如：線程1從主內存加載cache line v，修改v，把整個cache line回寫到主內存，線程2再重復這個過程修改v1，這種情況就稱為false sharing，顯然如果在並行運行的核心代碼中出現這種的情況，性能是非常糟糕的，而這樣的代碼通常又不太容易發現 下面是wiki上false sharing的一個例子: 復制代碼 struct foo { int x; int y; }; static struct foo f; int sum_a(void) { int s = 0; for (int i = 0; i < 1000000; ++i) s += f.x; return s; } void inc_b(void) { int i; for (i = 0; i < 1000000; ++i) ++f.y; } 復制代碼 假設sum_a和inc_b兩個函數同事運行在不同核心的不同線程上，f的所有成員都在同一條cache line，inc_b在不聽修改內存中的值，因此導致false sharing。 在做性能優化前，一定要先profile，profile，profile！！！很多情況下，問題所在的位置和程序員所預期的都不一樣，盲目修改代碼甚至有可能降低程序性能！！！ ps：最悲劇的情況就是沒有任何可靠的profile工具，還必須做性能優化，我目前的情況就是這樣，怎一個慘字了得.... more refereence： Modern C++: What You Need to Know Native Code Performance on Modern CPUs: A Changing Landscape Native Code Performance and Memory: The Elephant in the CPU
