【洛谷日报#164】C 卡常数之内存优化

P.S. 感谢@ComeIntoPower 提供了宝贵的修改意见。

OI中C++的常数优化详解

Part1 寄存器与cache

内存的访问是非常慢的，除了内存，还有寄存器(register)、高速缓存cache，它们的访问速度比内存更快。

电脑的存储分级可以用一个非常形象的栗子来说明： 
我们可以以经典的阅读书籍为例。我在读的书，捧在手里（寄存器），我最近频繁阅读的书，放在书桌上（缓存），随时取来读。当然书桌上只能放有限几本书。我更多的书在书架上（内存）。如果书架上没有的书，就去图书馆（磁盘）。我要读的书如果手里没有，那么去书桌上找，如果书桌上没有，去书架上找，如果书架上没有去图书馆去找。可以对应寄存器没有，则从缓存中取，缓存中没有，则从内存中取到缓存，如果内存中没有，则先从磁盘读入内存，再读入缓存，再读入寄存器。

这是一张有两级cache的计算机的存储结构图。

寄存器具有最高的访问速度，在变量前加关键词register即将其加入寄存器。但如图，寄存器的空间是有限的，不应该滥用register，应该仅在访问最频繁的几个变量（如循环变量）前加register。

cache即高速缓存，一般分为3级（有些电脑为两级），访问速度逐级递减。访问变量时，CPU会优先在cache而不是内存中查找，如果cache中不存在此变量，则会进入内存查找，这称为cache miss。如图，内存访问的开销是巨大的，所以cache miss是一个重要的常数问题。

那么如何减少cache miss？

对于cache miss优化，有如下几点：

尽量让某个数组的大小能够卡进cache

与register一样，cache的大小同样有限。一些过大的内存是不可以进入cache的。

基数排序时，以256为基数会比256*256更快。因为256大小的四个数组可以轻松进入cache。

详见 洛谷题库 WC2017挑战 Subtask1

保证时空局部性

什么是时空局部性？

时间局部性：当一个变量被使用时，它会在短时间内再次被使用。 
空间局部性：当一个变量被使用时，它的内存附近的变量会再次被使用。

保证这两样东西的良好有益于减少cache miss。

怎样优化空间局部性？

• 将一些关系密切，例如经常连着使用的变量尽量定义在一起，或用结构体封装起来。

• 适当调整变量定义顺序

• 保证内存连续访问。例如：Floyd和矩阵乘法的程序中，将第三层循环作为第一层会大大提高速度。

怎样优化时间局部性？

• 尽量使用局部变量。因为堆栈的数据访问十分频繁。

指令缓存

同样是空间局部性的原理，两个相互关联（例如调用对方）的函数应该定义得足够靠近，这能使它们有机会同时被加载到指令cache中。

cache的生活应用：DevC++编译程序后第一遍运行很慢，这是因为编译后的程序没有进入缓存。运行一次后，相关指令进入cache，就会提高运行速度。同样地，对程序进行多次测速求平均时，如果程序访问到了一些大数组，且它们之前没有进入cache，则应该忽略掉第一次运行，取i=2到n次的一段进行平均。

总结：cache优化的原则：紧凑有关联的代码，分离无关联的部分。

摘自骆爷pdf的一句话：“这也是编写优美代码的原则。”

Part2 指针优化数组连续访问

指针用法：

for(register int i=1;i<=n;++i)work(a[i]);
应化为for(register int *S=a,*E=a+n;S!=E;)work(*++S);


这样能够大幅度提高速度。为啥呢？ 
a[i]本质上是*(a+i)，64位平台上是long long相加，比指针的前自加运算慢得多。 
注：初始化和数组复制方面，memset和memcpy比指针具有更高的速度，因为它们实际上调用了rep movsq指令，这比一般的mov指令快很多。

对于高维数组，例如  ，则a[i][j][k]的访问相对而言十分慢。我们可以将它降成一维数组，a[i∗h∗w+j∗w+k]代替，从而更快地访问。另外也可以利用代数方法减少乘法次数，将其化为a[(i∗h+j)∗w+k]。更高维的数组也可以用这种方法优化。

更多内容请参考：
http:///articles/2012/06/c_c_tip_how_loop_through_multi_dimensional_arrays_quickly

Part3 内联函数、递归、递推与堆栈开销

inline函数能够提高效率，因为它能够减少堆栈开销、减少传参耗时。

#define宏函数与inline函数具有相同速度和效果，但会在函数体中反复计算参数，这当参数是一个式子时是很不利的。请读者根据具体情况自行选择。 
例：#define sq(x) ((x)*(x))//平方函数

同样的道理，递推比递归更优秀。它减少了堆栈开销，会更快速，同时避免了爆栈的危险。 
同样地，手动bfs比dfs更为高效，且内存开销也更小，尤其是多次dfs一棵树时。

Part4 优化STL的动态分配内存

一些STL的速度瓶颈即std::allocator对内存的动态分配，这对于push_back等操作不利。

我们可以手写这个struct，用足够大小的内存池来代替动态分配内存。这里我们用派生于std::allocator的myalloc结构体来代替它：

#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容器：

list<int,myalloc<int> > L;vector<double,myalloc<double> > vec;


实测表明，这确实能够优化STL相当一大部分的常数。

由于为了竞赛中方便打，该模板没有编写内存释放函数（网上的模板十分冗长），因此，当内存过大时不要用此模板，太大会RE，不太大也可能变慢。

如果平时想要使用这一类的优化，请参考这个十分详细的内存池教程：https://blog.csdn.net/u010183728/article/details/81531392