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

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

Part1 寄存器與cache

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

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

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

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

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

那么如何減少cache miss？

對(duì)于cache miss優(yōu)化，有如下幾點(diǎn)：

盡量讓某個(gè)數(shù)組的大小能夠卡進(jìn)cache

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

基數(shù)排序時(shí)，以256為基數(shù)會(huì)比256*256更快。因?yàn)?56大小的四個(gè)數(shù)組可以輕松進(jìn)入cache。

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

保證時(shí)空局部性

什么是時(shí)空局部性？

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

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

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

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

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

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

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

• 盡量使用局部變量。因?yàn)槎褩５臄?shù)據(jù)訪問十分頻繁。

指令緩存

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

cache的生活應(yīng)用：DevC++編譯程序后第一遍運(yùn)行很慢，這是因?yàn)榫幾g后的程序沒有進(jìn)入緩存。運(yùn)行一次后，相關(guān)指令進(jìn)入cache，就會(huì)提高運(yùn)行速度。同樣地，對(duì)程序進(jìn)行多次測(cè)速求平均時(shí)，如果程序訪問到了一些大數(shù)組，且它們之前沒有進(jìn)入cache，則應(yīng)該忽略掉第一次運(yùn)行，取i=2到n次的一段進(jì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位平臺(tái)上是long long相加，比指針的前自加運(yùn)算慢得多。 
注：初始化和數(shù)組復(fù)制方面，memset和memcpy比指針具有更高的速度，因?yàn)樗鼈儗?shí)際上調(diào)用了rep movsq指令，這比一般的mov指令快很多。

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

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

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

inline函數(shù)能夠提高效率，因?yàn)樗軌驕p少堆棧開銷、減少傳參耗時(shí)。

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

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

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

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

我們可以手寫這個(gè)struct，用足夠大小的內(nèi)存池來代替動(dòng)態(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容器：

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

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

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