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

Starlight237

2019-02-15 21:04:26

Personal

Part0

ppt版本
常数优化有效性测试
参考文献：论程序底层优化的一些方法和技巧
注：此文件已经被我下载并上传，如果想要pdf文件但是下载不了道客巴巴文档可以私信找我要下载链接和密码。

Part1 常数优化前置概念

如何测量函数的耗时

根据前文，我们有必要评估函数的耗时，从而进行有效的优化。
使用头文件ctime或time.h中的clock()函数，此函数返回当前的总运行时间。
样例代码：

#include<ctime>
int tmp=clock();
function();
int _time=clock()-tmp;

这段代码运行后，_time变量就表示函数function()的运行时间。其单位为：ms（毫秒）
为了保证测量精确度，因为对于耗时较小的函数_time可能会为0，所以我们应该多次运行该函数取它们的总时间并求平均值。这种方法与测量纸的厚度的方法是一样的。用for循环实现。

一些基本的语句的耗时

整数加减：1（个时钟周期，下同）
整数位运算：1
整数乘法：2
整数除法：21
浮点加减：3
浮点除法：35
浮点开根：60
指针加法：1

各类型比较：

int运算是最快的。unsigned无符号数做除法比有符号数快。
float比任何整数运算更慢，double比float慢，long double最慢。
注意：实测int比char和short具有更快的速度。

Part2 常数优化方法

运算优化

正如Part01所说，不同的数据类型以及它们的各运算速度是不一样的。

3.1.1 一般情况的运算优化

1.优化除法/取模运算。例：将a/b==c/d化为a*d==c*b，事实上，这对于整数来说也能够保持精度。另外,unsigned无符号数比有符号数能够更快地完成除法运算。而对于取模，可以将其优化为：
inline int MOD(int x){return x<Mod?x:x%Mod;}
而对于某些题目，仅需要对答案取模。这类题目要边运算边取模的目的一般是防止溢出。
故我们甚至可以写成这样：
inline int MOD(int x){return x<=0x3f3f3f3f?x:x%Mod;}
如果是乘法，我们相应地可以写成：
inline int MOD(int x){return x<=45000?x:x%Mod;}
总之，这个范围要保证结果在计算时不会有溢出的风险。但采用了这种方式后，最后输出时一定要取模。
对于负数取模的优化：
inline int MODF(int x){x=MOD(x);return x<0?x+MOD:x;}

2.减少浮点除法

由于浮点运算满足运算定律，优化的余地很大。除了整数的那些方法外，还有很多技巧。
举两个骆爷pdf里的例子：

a/b+c/d化为(a*d+b*c)/(b*d)
int x=a/b,y=c/d,z=e/f;化为：
int t=b*d*f;
int x=a*d*f/t,y=c*b*f/t,z=e*b*d/t;

诸如此类。

·3.优化浮点运算

例如，要求保留2位小数，可以扩大10000倍然后用int/long long代替。或者左移14位（2^14=16384），然后输出的时候乘以2^(-14)≈0.00006103515625再保留两位小数即可。

3.1.2 特殊情况下的运算优化

注：位运算的优先级低于+-*/

1.乘除2的整数幂
x*(2^k)=x<<k   x/(2^k)=x>>k
2.乘除常数的优化
x*10=(x<<1)+(x<<3)注：实测x+(x<<2)<<1会更慢
x*13=x+(x+(x<<1)<<2)
x*14=(x<<1)+(x+(x<<1)<<2)
x*17=(x<<4)+x
x*63=(x<<6)-x
3.对2^k取模优化
x%(1<<k)=x&(1<<k)-1 正确性留给读者思考
例如x%2=x&1,x%8=x&7,x%16=x&15
4.对两个long long相乘取模（来自骆爷pdf）：
inline long long mul_mod(long long a,long long b,long long Mod){
    long long d=(long long)floor(a*(double)b/Mod+0.5),ret=a*b-d*Mod;
    return ret<0?ret+Mod:ret;
}

3.2 内存优化

内容较多，如有需要请移步C++卡常数之内存优化

3.3 分支优化

分支语句判断会影响CPU的流水线运行模式，消耗多余时间。
三目和短路运算符可以优化它。
例

if(maxn<x)maxn=x;化为maxn=maxn<x?x:maxn;或maxn<x&&(maxn=x);
if(a==b)work();化为a==b&&(work(),0);

另外，请将最可能的情况放置在if中而不是else中，并且尽量让自己的分支语句合理一些，不具有太大的不确定性。
为啥？
因为编译器会进行分支预测，这样做能够配合编译器做这个优化。
单独一个if时不会对效率造成太大影响，但ifelse的开销较大。三目主要的作用是优化ifelse语句。
例如void func(){if(...)return ;else {...}}是不良好的习惯。没有必要的else语句应该略去，否则一方面影响效率，一方面使代码不够美观。

3.4 循环展开与多路并行

由于展开能够消除分支以及一些管理归纳变量的代码，因此可以减少一些分支开销。一些情况下，循环展开甚至能够促使CPU并发。
注：展开过度会使循环体无法放入跟踪缓存（TC），造成负优化！

多路并行能取消上下文关联性，从而有机会使CPU并发。同样地，不可以过度并行。它一般是与循环展开配合使用的。

一个例子：

inline int sum(int a[],int len){
    register int *p=a,*q=a+len,s0=0,s1=0,s2=0,s3=0;
    #define F(x) s##x+=*(p+x)
    while(p+3<=q)F(0),F(1),F(2),F(3),p+=4;
    while(p<=q)s0+=*p++;
    return s0+s1+s2+s3;
}

这是一个求数组和的函数。这里使用了循环展开+四路并行。
WC2017T2就使用过这种优化方法。

3.5 读写优化

介绍两个函数：

size_t fread(void *buffer,size_t size,size_t count,FILE *stream)
size_t fwrite(const void *buffer,size_t size,size_t count,FILE *stream)
fread读，fwrite写。buffer为读写数组，size为每次读写的字节数，count为读写的总字节数，stream为流函数。

快速读写模板：

static char in[10000000],out[10000000],ch[20],*p=in,*q=out,*t=ch;
inline int read(){
    register int x=0;
    while(*p<48)++p;
    while(*p>47)x=(x+(x<<2)<<1)+(*p++^48);
    return x;
}
inline void write(int x){
    if(!x)*q++=48;
    else {
        while(x)*t++=x%10+48,x/=10;
        while(t!=ch)*q++=*--t;
    }
}//注意：如果读入量很大（比如超过了10000000字节），请使用下面的模板。

static char in[10000000],*p,*pp,out[10000000],*q=out,ch[20],*t=ch;//读写大小自行调整。
#define getch p==pp&&(pp=(p=in)+fread(in,1,10000000,stdin),p==pp)?EOF:*p++;
inline int read(){
    register int x=0;register char ch;
    while((ch=getch)<48);
    while(ch>47)x=(x+(x<<2)<<1)+(ch^48),ch=getch();
    return x;
}
inline void write(int x){
    if(!x)*q++=48;
    else {
        while(x)*t++=x%10+48,x/=10;
        while(t!=ch)*q++=*--t;
    }
}
int main(){pp=(p=in)+fread(in,1,10000000,stdin);......fwrite(out,1,q-out,stdout);}

另外一个功能齐全但是常数较大的版本请参见博客：https://www.luogu.org/blog/Howershine950644/post-mu-ban-zhen-zheng-di-du-xie-you-hua
请读者自行优化其常数。

注意因为fread的参数太大也会降低速度。因此在文件读写的情况下可以这样：

freopen(filename,”r”,stdin);
FILE* fp=fopen(filename,”r”);fseek(fp,0L,SEEK_END);
fread(in,1,ftell(fp),stdin);

3.6 STL容器优化

如果能手写尽量手写，如果不能手写则优化其内存分配。

众所周知，STL的默认分配器是allocator<T>，这是会动态分配内存的，我们可以开一个足够大的内存池，自定义myalloc类来优化内存分配的消耗。 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;

实测：对于list，在我的电脑上甚至比不加优化的list快10倍以上。

3.7 其他

例如：逗号运算符比分号运算符快，for(register int i=1;i<=n;++i)...比while(n--)...慢，因为少了i的变量枚举。

另外感谢@ywr8 补充：for(;n;--n)比while(n--)快。