OI常数优化之从入门到进阶

这里是上一篇「玄学」常数优化的一些技巧的进阶篇

什么输入输出优化 && 循环展开之类的在前一篇文章中介绍过了,本文介绍一些更加实用的

本文仅供参考,由读者引发的一切后果,任何责任由读者自行承担。后果包括但不限于:

  • OJ 上一些题目爆零(CE)
  • NOIP / NOI禁赛三年(
  • 优化后变慢

优化快读

我们知道,getchar是逐字符读取的,在cstdio中,有一个fread函数,能整段读取,比getchar还快,并且支持freopen(完美兼容)和fopen(需要把下面的所有stdin改成你的文件指针)

函数原型:

1
size_t fread(void *buffer,size_t size,size_t count,FILE *stream);

作用:从stream中读取count个大小为size个字节的数据,放到数组buffer中,返回成功了多少个大小为为size个字节的数据。

新的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline char nc() {
static char buf[1000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

//#define nc getchar
inline void read(int &sum) {
char ch = nc();
int tf = 0;
sum = 0;
while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();
tf = ((ch == '-') && (ch = nc()));
while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();
(tf) && (sum =- sum);
}

但要注意,由于这种方法是整段读取的,这也造就了它两个巨大的Bug:

  1. 不能用键盘输入。数据还没输入,程序怎么整段读取。如果你需要在电脑上用键盘输入调试,请把第5行的注释取消。
  2. 不能和scanfgetchar等其他读入方法混合使用。因为fread是整段读取的,也就是说所有数据都被读取了,其他函数根本读取不到任何东西(只能从你的读取大小后面开始读),因此,所有类型的变量读入都必须自己写,上面的read函数只支持int类型。

下面是测试,摘自LibreOJ,单位为毫秒(n=3×106)(n=3\times 10^6)


读入方法编译器[0,21)[0,2^1)[0,23)[0,2^3)[0,215)[0,2^{15})[0,231)[0,2^{31})[0,263)[0,2^{63})
freadG++ 5.4.0 (−O2)1313131339397070111111
getcharG++ 5.4.0 (−O2)58587373137137243243423423
cin(关闭同步)G++ 5.4.0 (−O2)161161147147205205270270394394
scanfG++ 5.4.0 (−O2)182182175175256256368368574574
cinG++ 5.4.0 (−O2)4424424294297067061039103916831683

没错,你没有看错,fread以压倒性的优势碾压了其他所有方法,而关闭同步的cinscanf快,并且读long long的时候比getchar还要快,关于为什么不使用位运算的问题下一章会说


下面的内容某些OI比赛不支持。慎用!

其实还可以更快,Linuxsys/mman.h中存在函数mmapscanf底层实现时调用的就是mmap函数,其作用是把文件映射进内存,这里仅仅给出代码,有兴趣的同学可以自行查阅有关资料

代码就不改了(其实是懒

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<sys/mman.h>

namespace Inputs{
char* s;
int a[24];
io(){s=(char*)mmap(NULL,1 << 26 ,PROT_READ,MAP_PRIVATE,fileno(stdin),0);}
void scan(char* u){
while(*s<48)
++s;
while(*s>32)
*u++=*s++;
*u=0;
}
int scan(){
int Hibiki=0,v=1;
while(*s<48)
v=*s++^45?1:-1;
while(*s>32)
Hibiki=Hibiki*10+*s++-48;
return Hibiki*v;
}
}

有人喜欢用isdigit宏,但这个宏在本机测试上的确更慢了,这个宏的效率还有待研究


输出优化

这里就略了,使用sprintf就可以了


位运算

在很多时候,我们会听到很多有关位运算的追捧,像”位运算的常数很小,比加减法还要快。”这是真的吗?

左移和右移的天上地下

下面有两段代码:

1
2
3
4
5
6
7
8
9
#include<cstdio>

int x = 5;

int main(int argc, char *const argv[]) {
x <<= 1;
printf ("%d", x);
return 0;
}
1
2
3
4
5
6
7
8
9
#include<cstdio>

int x = 5;

int main(int argc, char *const argv[]) {
x *= 2;
printf ("%d",x);
return 0;
}

它们理论上是等价的,但g++翻译成汇编后呢? 两段代码的汇编代码是一样的!下面是x <<= 1x *= 2被翻译后的代码

1
addl    %eax, %eax1

它等价于a = a + a。是不是被打脸了,响不响,痛不痛,红不红,痒不痒……好吧,从上面的例子可以看出,某些时候自作聪明的优化并没有任何用

那乘以 44 呢?翻译后的代码还是一样的

1
sall    $2, %eax1

上面的代码等价于x <<= 2。现在死心了吧。

或许你还执着于x *= 10。这次翻译后的汇编代码终于不一样了,下面是x *= 10的汇编代码(O2优化)

1
2
leal    (%eax,%eax,4), %eax
addl %eax, %eax

只有两条指令

1
2
x = x + x * 4 //别看是加法和乘法,却是一条指令完成。
x = x + x //加法还不容易吗

那些喜欢用x = (x << 3) + (x << 1)的人请自重。

那是不是说位运算一无所用呢?并不是,在除法方面有不少用处。 右移的汇编代码

1
2
3
4
movl    _x, %eax
sarl %eax
movl %eax, _x
movl _x, %eax

除以2的代码

1
2
3
4
5
6
7
movl    _x, %eax
movl %eax, %edx //(del)
shrl $31, %edx //(del)
addl %edx, %eax //(del)
sarl %eax
movl %eax, _x
movl _x, %eax

整整多了三行。

但这种情况仅限于有符号的整数,因为有符号的整数的右移和除法不是同一个东西,编译器还需要修正一下。 如果用的是unsigned类型,那汇编代码又一样了


ModAnd的战争

下面是x % 2的代码(−O2)

1
2
3
4
5
6
7
8
9
movl    _x, %eax
movl $LC0, (%esp)
movl %eax, %edx //(del)
shrl $31, %edx //(del)
addl %edx, %eax //(del)
andl $1, %eax
subl %edx, %eax //(del)
movl %eax, 4(%esp)
movl %eax, _x

x & 1呢?少了44条语句(−O2)

1
2
3
4
5
movl    _x, %eax
movl $LC0, (%esp)
andl $1, %eax
movl %eax, 4(%esp)
movl %eax, _x

Xortemp的故事

相信大家在学交换两个变量的值的时候一定会先学习所谓的“三变量交换法”,然后就被异或取代了。 下面是异或(a ^= b ^= a ^= b)的汇编

1
2
3
4
5
6
7
8
movl    _b, %edx
movl _a, %eax
xorl %edx, %eax
xorl %eax, %edx
xorl %edx, %eax
movl %eax, _a
xorl %eax, %eax
movl %edx, _b

movl指令和xorl指令各44条。 那三变量交换法(int t = a;a = b,b = t;)呢?

1
2
3
4
5
movl    _a, %eax
movl _b, %edx
movl %eax, _b
xorl %eax, %eax
movl %edx, _a

从此,temp再没有异或。


神奇的”位运算技巧”

网上有很多奇奇怪怪的方法,例如取绝对值(n ^ (n >> 31)) - (n >> 31),取两个数的最大值b & ((a - b) >> 31) | a & ( ~(a - b) >> 31),取两个数的最小值a & ((a - b) >> 31) | b & ( ~(a-b) >> 31 )

喜欢用上面代码的人难道没有自己亲自数一数上面有多少条位运算的指令吗?

但凡事没有绝对,还是有一些优秀的例子的:

取最后一个11和后面的00 : lowbit(x) = (x & ( -x ))

判断一个数是不是22的幂n > 0 ? ( n & (n - 1)) == 0 : false


Xor和网络流的故事

还记得网络流的反向弧?通常某些人喜欢在结构体中新建一个变量来表示这条边的反向弧编号。但这样不免有些浪费,因为在插入新边的时候,我们一般会把两条互为反向弧的边相邻插入,有一个有趣的性质可以完美地解决这个问题:(2 * x) ^ 1 = 2 * x + 1, (2 * x + 1) ^ 1 = 2 * x也就是说,我们可以用异或节省下一个空间

那在汇编中呢?异或本来就是逻辑运算,一条指令xorl $1, _x搞定,但如果用另一个变量呢?编译器需要对变量进行初始化,还多了一条指令


条件语句

相信条件语句会在程序中经常出现,而且也是不可避免的,谁知道,这么死板的事情还可以再优化。


if?:的故事

在那个夜黑风高的白天。。。 if遇到了?:,然后两人吵了很久很久,然而并分不出上下,没错,?:运算符并不一定比if更快。为什么?它们的汇编长得一模一样,除了了唯一的不同:文件名(汇编第一行会带有文件名)(不论开没开O2)。

1
2
正在比较文件 if.s 和 3.s
FC: 找不到差异

那网上的“?:运算符比if快”是个什么鬼? 是它们没写清楚,是“?:运算符比if-else快”。

有什么区别吗?你需要先弄清楚if的工作原理。

if就像一个铁路分叉道口,在CPU底层这种通讯及其不好的地方,在火车开近之前,鬼知道火车要往哪边开,那怎么办?

猜!

  • 如果猜对了,它直接通过,继续前行。
  • 如果猜错了,车头将停止,倒回去,你将铁轨扳至反方向,火车重新启动,驶过道口。

如果是第一种情况,那很好办,那第二种呢?时间就这么浪过去了,假如你非常不走运,那你的程序就会卡在停止-回滚-热启动的过程中。

上面猜的过程就是分支预测

虽然是猜,但编译器也不是随便乱猜,那怎么猜呢?答案是分析之前的运行记录。假设之前很多次都是true,那这次就猜true,如果最近连续很多次都是false,那这次就猜false

但这一切都要看你的CPU是不是某CPU了(好像从哪里听过?),如果你遇到了一个神经CPU,那岂不是很GG?因此,一般把容易成立的条件写在前面判断,把不容易成立的条件放在else那里。

但是?:消除了分支预测,因此在布尔表达式的结果近似随机的时候?:更快,否则就是if更快啦。


下面的内容某些OI比赛不支持。慎用!

gccgcc存在内置函数:__builtin_expect(!!(x), tf)

tftrue时表示x非常可能为true,反之同理

用法:if(__builtin_expect(!!(x), tf))


switchif-else的故事

下面有两段代码,你觉得那段更快呢?

1
2
3
4
5
if (x == 1)      x++;
else if (x == 2) x *= 2;
else if (x == 3) x /= 3;
else if (x == 4) x >>= 1;
else if (x == 5) x = 1;

1
2
3
4
5
6
7
8
9
10
11
12
switch (x) {
case 1:
x++; break;
case 2:
x *= 2; break;
case 3:
x /= 3; break;
case 4:
x >>= 1; break;
case 5:
x = 1;
}

显然地,下面的代码更快,因为上面的代码需要逐条判断,而下面的代码直接跳转

那是不是所有switch都比if快呢?凡事没有绝对,当switch遇到default的时候,整个程序的效率就会大打折扣,因为它又回到了if的无脑判断模式。再比如,当if用来判断区间的时候就比switch快,if只需要做三次逻辑运算(两条判断,一条逻辑与),而switch呢?我就呵呵一笑


短路的故事

此短路非彼短路,它指的是一种运算符的特性。 我们常用的逻辑运算符,例如&&||都是短路运算符。什么意思呢?比如在运算A&&B时,如果发现A已经为false,就不会再计算B

现在你能解释第一章中留下的问题了吗?

(tf)&&(sum=-sum);tftrue的时候,会执行后面的sum=-sum,如果tffalse,则不会执行后面的sum=-sum。 等价于如下语句:

1
if (tf) sum =- sum;

tf=((ch=='-')&&(ch=getchar()));ch='-'时,会执行后面的ch=getchar(),因为getchar一般不会等于 00(如果不放心可以写成tf=((ch=='-')&&((ch=getchar()),true))),因此tf的结果等于true。当ch!='-'时,不会执行后面的ch=getchar()tf的值为false。等价于如下语句:

1
2
3
4
if ( ch == '-' ) {
tf = true;
ch = getchar();
}

总结一下:

  • if(A) B; \rightarrow (A)&&(B)
  • if(A) B; else C; \rightarrow A&&(B,1)||C

为什么?详情参见下一小节。

如果短路运算符只能改写if语句,那这里就不会浪费这么多篇幅来介绍这个东西。事实上,这个东西比我们想象得有用得多。看下面两段代码:

1
2
3
double t = rand();
if (t / RAND_MAX < 0.2 && t != 0)
printf ("%d", t);
1
2
3
double t = rand();
if (t != 0 && t / RAND_MAX < 0.2)
printf ("%d", t);

你认为那一份代码会更快?好像没什么区别对吧。但对于CPU来说很有区别。第一段代码中的t/RAND_MAX<0.2true的概率约为 20%20\%,但t!=0true的概率约为1RAND_MAX1\over RAND\_MAX,明显小于20%20\%

因此,如果把计算一个不含逻辑运算符布尔表达式的计算次数设为 11 次,设计算了 XX 次,则对于第 11 段代码,XX 的数学期望为 656\over 5 次,但对于第二段代码,XX 的数学期望为 ,远远大于第一段代码。

总结一下, - 遇到A&&B时,优先把可能为false的表达式放在前面。 - 遇到A||B时,优先把可能为true的表达式放在前面。

布尔表达式和逗号运算符的故事

为什么要专门设置这么一小节呢? 因为很多人喜欢用if(x==true),直接用if(x)就好了。还有x==false!x,它们也是等价的。

现在,请另一位大佬隆重登场:逗号运算符。

若干条语句可以通过逗号运算符合并成一条语句。 例如t=a;a=b;b=t;可以写成t=a,a=b,b=t;有什么用吗?它的返回值。

1
int x=(1,5,4,2,6,3,9);

猜一猜,上面的语句执行完后x的值是多少? 答案是 99

没错,逗号运算符的返回值就是最后一个的值。

现在可以解释上一小结留下总结了吧。

A&&(B,1)||CAtrue时会执行(B,1),返回值为true,因此A&&(B,1)的返回值为true,因此不会执行C,当Afalse时,不会执行(B,1),且A&&(B,1)的值为false,因此会执行C


这次就先写到这里吧quq

打算出再一个从进阶到入土quq(咕咕

坚持原创技术分享,您的支持将鼓励我继续创作!