P.S. 感謝@ComeIntoPower 提供了寶貴的修改意見。

OI中C++的常數(shù)優(yōu)化詳解

Part1 寄存器與cache

內(nèi)存的訪問是非常慢的，除了內(nèi)存，還有寄存器(register)、高速緩存cache，它們的訪問速度比內(nèi)存更快。

電腦的存儲分級可以用一個非常形象的栗子來說明： 
我們可以以經(jīng)典的閱讀書籍為例。我在讀的書，捧在手里（寄存器），我最近頻繁閱讀的書，放在書桌上（緩存），隨時取來讀。當然書桌上只能放有限幾本書。我更多的書在書架上（內(nèi)存）。如果書架上沒有的書，就去圖書館（磁盤）。我要讀的書如果手里沒有，那么去書桌上找，如果書桌上沒有，去書架上找，如果書架上沒有去圖書館去找?？梢詫?yīng)寄存器沒有，則從緩存中取，緩存中沒有，則從內(nèi)存中取到緩存，如果內(nèi)存中沒有，則先從磁盤讀入內(nèi)存，再讀入緩存，再讀入寄存器。

這是一張有兩級cache的計算機的存儲結(jié)構(gòu)圖。

寄存器具有最高的訪問速度，在變量前加關(guān)鍵詞register即將其加入寄存器。但如圖，寄存器的空間是有限的，不應(yīng)該濫用register，應(yīng)該僅在訪問最頻繁的幾個變量（如循環(huán)變量）前加register。

cache即高速緩存，一般分為3級（有些電腦為兩級），訪問速度逐級遞減。訪問變量時，CPU會優(yōu)先在cache而不是內(nèi)存中查找，如果cache中不存在此變量，則會進入內(nèi)存查找，這稱為cache miss。如圖，內(nèi)存訪問的開銷是巨大的，所以cache miss是一個重要的常數(shù)問題。

那么如何減少cache miss？

對于cache miss優(yōu)化，有如下幾點：

盡量讓某個數(shù)組的大小能夠卡進cache

與register一樣，cache的大小同樣有限。一些過大的內(nèi)存是不可以進入cache的。

基數(shù)排序時，以256為基數(shù)會比256*256更快。因為256大小的四個數(shù)組可以輕松進入cache。

詳見 洛谷題庫 WC2017挑戰(zhàn) Subtask1

保證時空局部性

什么是時空局部性？

時間局部性：當一個變量被使用時，它會在短時間內(nèi)再次被使用。 
空間局部性：當一個變量被使用時，它的內(nèi)存附近的變量會再次被使用。

保證這兩樣?xùn)|西的良好有益于減少cache miss。

怎樣優(yōu)化空間局部性？

• 將一些關(guān)系密切，例如經(jīng)常連著使用的變量盡量定義在一起，或用結(jié)構(gòu)體封裝起來。

• 適當調(diào)整變量定義順序

• 保證內(nèi)存連續(xù)訪問。例如：Floyd和矩陣乘法的程序中，將第三層循環(huán)作為第一層會大大提高速度。

怎樣優(yōu)化時間局部性？

• 盡量使用局部變量。因為堆棧的數(shù)據(jù)訪問十分頻繁。

指令緩存

同樣是空間局部性的原理，兩個相互關(guān)聯(lián)（例如調(diào)用對方）的函數(shù)應(yīng)該定義得足夠靠近，這能使它們有機會同時被加載到指令cache中。

cache的生活應(yīng)用：DevC++編譯程序后第一遍運行很慢，這是因為編譯后的程序沒有進入緩存。運行一次后，相關(guān)指令進入cache，就會提高運行速度。同樣地，對程序進行多次測速求平均時，如果程序訪問到了一些大數(shù)組，且它們之前沒有進入cache，則應(yīng)該忽略掉第一次運行，取i=2到n次的一段進行平均。

總結(jié)：cache優(yōu)化的原則：緊湊有關(guān)聯(lián)的代碼，分離無關(guān)聯(lián)的部分。

摘自駱爺pdf的一句話：“這也是編寫優(yōu)美代碼的原則?！?/p>

Part2 指針優(yōu)化數(shù)組連續(xù)訪問

指針用法：

這樣能夠大幅度提高速度。為啥呢？ 
a[i]本質(zhì)上是*(a+i)，64位平臺上是long long相加，比指針的前自加運算慢得多。 
注：初始化和數(shù)組復(fù)制方面，memset和memcpy比指針具有更高的速度，因為它們實際上調(diào)用了rep movsq指令，這比一般的mov指令快很多。

對于高維數(shù)組，例如  ，則a[i][j][k]的訪問相對而言十分慢。我們可以將它降成一維數(shù)組，a[i?h?w+j?w+k]代替，從而更快地訪問。另外也可以利用代數(shù)方法減少乘法次數(shù)，將其化為a[(i?h+j)?w+k]。更高維的數(shù)組也可以用這種方法優(yōu)化。

更多內(nèi)容請參考：
http:///articles/2012/06/c_c_tip_how_loop_through_multi_dimensional_arrays_quickly

Part3 內(nèi)聯(lián)函數(shù)、遞歸、遞推與堆棧開銷

inline函數(shù)能夠提高效率，因為它能夠減少堆棧開銷、減少傳參耗時。

#define宏函數(shù)與inline函數(shù)具有相同速度和效果，但會在函數(shù)體中反復(fù)計算參數(shù)，這當參數(shù)是一個式子時是很不利的。請讀者根據(jù)具體情況自行選擇。 
例：#define sq(x) ((x)*(x))//平方函數(shù)

同樣的道理，遞推比遞歸更優(yōu)秀。它減少了堆棧開銷，會更快速，同時避免了爆棧的危險。 
同樣地，手動bfs比dfs更為高效，且內(nèi)存開銷也更小，尤其是多次dfs一棵樹時。

Part4 優(yōu)化STL的動態(tài)分配內(nèi)存

一些STL的速度瓶頸即std::allocator對內(nèi)存的動態(tài)分配，這對于push_back等操作不利。

我們可以手寫這個struct，用足夠大小的內(nèi)存池來代替動態(tài)分配內(nèi)存。這里我們用派生于std::allocator的myalloc結(jié)構(gòu)體來代替它：

#include<bits/stdc++.h>
using namespace std;
#define reg register
static char space[10000000],*sp=space;
template<typename T>
struct myalloc:allocator<T>{
    myalloc(){}
    template<typename T2>
    myalloc(const myalloc<T2> &a){}
    template<typename T2>
    myalloc<T>& operator=(const myalloc<T2> &a){return *this;}
    template<typename T2>
    struct rebind{typedef myalloc<T2> other;};
    inline T* allocate(size_t n){
        T *result=(T*)sp;sp+=n*sizeof(T);
        return result;
    }
    inline void deallocate(T* p,size_t n){}
};

完成后，即可這樣定義STL容器：

實測表明，這確實能夠優(yōu)化STL相當一大部分的常數(shù)。

由于為了競賽中方便打，該模板沒有編寫內(nèi)存釋放函數(shù)（網(wǎng)上的模板十分冗長），因此，當內(nèi)存過大時不要用此模板，太大會RE，不太大也可能變慢。

如果平時想要使用這一類的優(yōu)化，請參考這個十分詳細的內(nèi)存池教程：https://blog.csdn.net/u010183728/article/details/81531392