OI中C++的常数优化详解
Starlight237
2019-02-15 21:04:26
## Part0
[ppt版本](https://pan.wps.cn/l/sjsf3ug)
[常数优化有效性测试](https://www.luogu.org/paste/86286z05)
参考文献：[论程序底层优化的一些方法和技巧](http://www.doc88.com/p-1197280421746.html)
注：此文件已经被我下载并上传，如果想要pdf文件但是下载不了道客巴巴文档可以私信找我要下载链接和密码。
## Part1 常数优化前置概念
### 如何测量函数的耗时
根据前文，我们有必要评估函数的耗时，从而进行有效的优化。
使用头文件$ctime$或$time.h$中的clock()函数，此函数返回当前的总运行时间。
样例代码：
```cpp
#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里的例子：
```cpp
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 特殊情况下的运算优化
注：位运算的优先级低于+-*/
```cpp
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++卡常数之内存优化](https://www.luogu.org/blog/Howershine950644/c-ka-chang-shuo-zhi-nei-cun-you-hua)
3.3 分支优化
分支语句判断会影响CPU的流水线运行模式，消耗多余时间。
三目和短路运算符可以优化它。
例
```cpp
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并发。同样地，不可以过度并行。它一般是与循环展开配合使用的。
一个例子：
```cpp
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为流函数。
快速读写模板：
```cpp
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的参数太大也会降低速度。因此在文件读写的情况下可以这样：
```cpp
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的定义如下。
```cpp
#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容器：
例：
```cpp
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--)快。
## 本文完结
## Thank you for your reading
## 觉得不错请点个赞奥！