【学术】对于代码常系数影响因素的考察——以快读为例

引子——快读

inline int read()
{
    char ch;int x=0;
    while((ch=getchar())<33);
    for(;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
    return x;
}

这段代码已经经过了一定程度的优化。比如为人熟知的 inline 关键字、使用 <33 判断空字符、压行等等。

但是,怎么知道它的具体优化效果呢?在这里,我们使用汇编的方式。

实验过程中的一些细节

  • 使用的编译器是 MinGW-w64 g++ 8.1.0;
  • 使用 C++11 标准;
  • 生成汇编代码的命令是 g++ -S test.cpp -o test.s

正文开始

首先,我们知道一些流传甚广的说法,接下来一一进行验证

我们用于测试的代码如下:

#include <cstdio>
inline int read()
{
    char ch;int x=0;
    while((ch=getchar())<33);
    for(;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
    return x;
}
int main()
{
    read();
    return 0;
}

1. 位运算 & 与逻辑运算 &&

这两者在布尔运算中运算结果完全等效,但是时间有差距。按照我们的一般认识,位运算是更快的。

但是,使用汇编验证后,得到的结果是:使用 && 时,汇编码长为 \(73\) 行;使用 & 时,汇编码长为 \(76\) 行!也就是说,&&& 速度上有微妙的差距。

那么,其它逻辑运算与位运算是否有类似的结果呢?

省略实验步骤,我得到的结论是:

  • ||| 完全等价;
  • !^1 要快许多。

2. inline 关键字

我们使用原本的测试代码进行实验,对比有无 inline 的汇编行数 (控制变量法)

结果令人意想不到:有 inline 时,汇编码长为 \(73\) 行;而无 inline 时,汇编码长为 \(70\) 行! 也就是说,inline 不一定可以优化常数


3. x=x*10+ch-'0' 的其它写法

想必你已经记住了不更改测试代码的情况下汇编有 \(73\) 行。

现在,我们把 x=x*10+ch-'0' 改为 x*=10,x+=ch-'0',看看汇编的变化。汇编代码变为了 \(69\) 行

但是经试验,将 x+=ch-'0' 再次拆开不会有任何变化。

其它与快读无关的更多研究


4. i++++i

曾有人说,++i 相比 i++ 有玄学优化,并给出了一堆理由。事实是否如此呢?

使用如下的测试代码:

int main()
{
    for(int i=1;i<=100;i++);
    return 0;
}

汇编结果很精简,只有 \(30\) 行。将其中的 i++ 改为 ++i 后,然而,结果长度并没有变化。所以说,在一般的循环语句中,i++++i 完全等价

但是有一些例外的情况。我们将代码添加一点东西:

int main()
{
    for(int i=1,j;i<=100;j=i++);
    return 0;
}

多了一条赋值语句。此时,汇编行数为 \(33\)。将其中的 i++ 改为 ++i 后,行数变为了 \(32\) 行。

虽然语义不等价,但这也说明了,在出现赋值的情况时,++ii++ 少一条汇编。


(仍会持续更新)

总结

所以,卡常要拒绝迷信,相信科学!

上一篇:hdu7107 GCD on Sequence


下一篇:P3842 [TJOI2007]线段