「卡常」关于卡常代码 & 优化的讨论与思考

本文来通过实际代码来讨论一下一些卡常 / 优化

也是继 OI常数优化之从入门到进阶 之后的又一篇卡常文章

编译器: x86-64 GCC 4.8.4 (CCF钦定)

编译选项: -std=c++98 -O1 -lm (毕竟 NOIP 不能吸氧 (O2)


关于位运算

你用的位运算真的快吗

关于左移与右移

关于 x << 1x * 2 的讨论

我们在写线段树 / 普通代码, 要将一个数变成它的二倍的时候, 我们有两种写法:

1
2
3
4
5
// 1
x = x << 1;

// 2
x = x * 2;

我们来看一看编译过后的汇编代码:

// 1:

1
2
3
movl    (%rdi), %eax
addl %eax, %eax
movl %eax, (%rdi)

// 2:

1
2
3
movl    (%rdi), %eax
addl %eax, %eax
movl %eax, (%rdi)

这段汇编是什么意思呢, 就是将 xx 赋值为 x+xx + x, 达到了 x=x×2x = x \times 2 的效果

所以说对于 x << 1x * 2 都是一样的

在线段树上, 通常访问一个点的左儿子的时候, 会要执行 root = root * 2 + 1 , 有些人会写 root = root << 1 | 1 , 这样其实也是一样的:

1
2
3
4
5
// 1
x = x << 1 | 1;

// 2
x = x * 2 + 1;

汇编代码:

// 1:

1
2
3
movl    (%rdi), %eax
leal 1(%rax,%rax), %eax
movl %eax, (%rdi)

// 2:

1
2
3
movl    (%rdi), %eax
leal 1(%rax,%rax), %eax
movl %eax, (%rdi)

这也是一样的, 所以说不用担心不用位运算线段树常数大了 2333

x >> 1x / 2

我们同样做出测试

1
2
3
4
5
// 1
n = n >> 1;

// 2
n = n / 2;

汇编代码:

// 1

1
2
3
movl    (%rdi), %eax
sarl %eax
movl %eax, (%rdi)

// 2

1
2
3
4
5
6
movl    (%rdi), %eax
movl %eax, %edx
shrl $31, %edx
addl %edx, %eax
sarl %eax
movl %eax, (%rdi)

对比

1
2
3
4
5
6
         movl    (%rdi), %eax
+ movl %eax, %edx
+ shrl $31, %edx
+ addl %edx, %eax
sarl %eax
movl %eax, (%rdi)

由于 c++ 的一些机制, 显然 / 2 相对慢一些

所以说在写整数二分的时候, >> 1 总是比 / 2

关于快读 (x = x * 10)x = (x >> 1 + x >> 3)

实验

1
2
3
4
5
// 1
x = x * 10;

// 2
x = (x << 1) + (x << 3);

汇编:

// 1:

1
2
3
4
movl    (%rdi), %eax
leal (%rax,%rax,4), %eax
addl %eax, %eax
movl %eax, (%rdi)

// 2:

1
2
3
4
movl    (%rdi), %eax
leal 0(,%rax,8), %edx
leal (%rdx,%rax,2), %eax
movl %eax, (%rdi)

显然直接看汇编是没用什么用的, 我们来实际跑一下

loj #7 Input Test

-(x << 1) + (x << 3)x * 10
fread()228228 ms , 124124 KiB & Submission232232 ms , 252252 KiB & Submission
getchar()11581158 ms , 252252 KiB & Submission11211121 ms , 252252 KiB & Submission

评测鸭

1用时内存链接
x * 1010.9110.91 us2424 KBSubmission 6769
(x << 1) + (x << 3)10.8210.82 us2424 KBSubmission 6768
2用时内存链接
x * 1010.510.5 us2424 KBSubmission 6776
(x << 1) + (x << 3)11.0411.04 us2424 KBSubmission 6777

实际上, 在大部分情况下, 没有经过严禁证明的, x * 10(x << 1) + (x << 3) 的速度是没有什么太大的区别的 (防杠精专属 QAQ)

所以说这个好像并没有什么太大的优化


关于 memset 的初值

1
2
3
void qwq(int *ans) {
memset((void *)ans, -1, sizeof ans);
}

这个是一个简单的将 ans 数组清空为 1-1 的函数, 我们将其转为汇编:

1
2
3
qwq(int*):
movq $-1, (%rdi)
ret

也没有什么问题, 但是我们如果尝试把数组清空为 11 为发生什么呢?

如果在本地跑一跑, 会出现 1684300916843009 这个数组

我们尝试转成汇编

1
2
3
void qwq(int *ans) {
memset((void *)ans, 1, sizeof ans);
}

汇编

1
2
3
4
qwq(int*):
movabsq $72340172838076673, %rax
movq %rax, (%rdi)
ret

7234017283807667372340172838076673 这个数是啥啊?

如果你手算 / python 一下, 你会发现:

72340172838076673 mod 2147483648=1684300972340172838076673 \text{ mod } 2147483648 = 16843009

所以说对于 memset, 是不能进行 memset 去初始化任意数的


其他位运算技巧

x & 1x % 2

直接上代码

1
2
3
4
5
// 1
if (x & 1) x++;

// 2
if (x % 2) x++;

汇编

// 1:

1
2
3
4
5
movl    (%rdi), %eax
testb $1, %al
je .L1
addl $1, %eax
movl %eax, (%rdi)

// 2:

1
2
3
4
5
movl    (%rdi), %eax
testb $1, %al
je .L1
addl $1, %eax
movl %eax, (%rdi)

x & 1x % 2 的汇编代码其实是相同的, 所以说在判断奇数偶数的时候 x & 1x % 2 是一样的


x ^= y ^= x ^= y 与三变量交换法

代码

1
2
3
4
5
6
7
8
9
void qwq (int &x, int &y) {
x ^= y ^= x ^= y;
}

void qaq (int &x, int &y) {
int p = x;
x = y;
y = p;
}

汇编:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
qwq(int&, int&):
movl (%rdi), %eax
xorl (%rsi), %eax
movl %eax, (%rdi)
xorl (%rsi), %eax
movl %eax, (%rsi)
xorl %eax, (%rdi)
ret
qaq(int&, int&):
movl (%rdi), %eax
movl (%rsi), %edx
movl %edx, (%rdi)
movl %eax, (%rsi)
ret

x ^= y ^= x ^= y 要进行三次 xorl 操作和三次 movl 操作, 自然比不上四次 movl


关于其他优化技巧

if - else !

if-else 取 max 和三目运算符取 max

程序

1
2
3
4
5
6
7
8
int qwq (int x, int y) {
return x > y ? x : y;
}

int qaq (int x, int y) {
if (x > y) return x;
else return y;
}

汇编

1
2
3
4
5
6
7
8
9
10
qwq(int, int):
cmpl %esi, %edi
movl %esi, %eax
cmovge %edi, %eax
ret
qaq(int, int):
cmpl %esi, %edi
movl %esi, %eax
cmovge %edi, %eax
ret

并没有什么差异, 就算有什么条件检测, 但是对于单个的 max 还是没有必要的


if-elseswitch

1
2
3
4
5
6
7
8
// 1
void qwq (int &x) {
if (x == 1) x++;
else if (x == 2) x += 2;
else if (x == 3) x += 3;
else if (x == 4) x += 4;
else if (x == 5) x += 5;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 2
void qwq (int &x) {
switch (x) {
case 1:
x += 1; break;
case 2:
x += 2; break;
case 3:
x += 3; break;
case 4:
x += 4; break;
case 5:
x += 5;
}
}

// 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
qwq(int&):
movl (%rdi), %eax
cmpl $1, %eax
jne .L2
movl $2, (%rdi)
ret
.L2:
cmpl $2, %eax
jne .L4
movl $4, (%rdi)
ret
.L4:
cmpl $3, %eax
jne .L5
movl $6, (%rdi)
ret
.L5:
cmpl $4, %eax
jne .L6
movl $8, (%rdi)
ret
.L6:
cmpl $5, %eax
jne .L1
movl $10, (%rdi)
.L1:
rep ret

// 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
qwq(int&):
cmpl $5, (%rdi)
ja .L1
movl (%rdi), %eax
jmp *.L4(,%rax,8)
.L4:
.quad .L1
.quad .L3
.quad .L5
.quad .L6
.quad .L7
.quad .L8
.L3:
movl $2, (%rdi)
ret
.L5:
movl $4, (%rdi)
ret
.L6:
movl $6, (%rdi)
ret
.L7:
movl $8, (%rdi)
ret
.L8:
movl $10, (%rdi)
.L1:
rep ret

显然地可以看到,直接 if ,是无脑判断,而使用 switch 语句,则是真正的跳转

关于除法

我们看到一个程序:

1
2
3
void qwq(int &ans) {
ans = ans / 3;
}

将其转成汇编

1
2
3
4
5
6
7
8
9
qwq(int&):
movl (%rdi), %ecx
movl $1431655766, %edx
movl %ecx, %eax
imull %edx
sarl $31, %ecx
subl %ecx, %edx
movl %edx, (%rdi)
ret

这个 14316557661431655766 是啥啊, 为什么我会出来这个大质数, 我有没有输入

计算好的同学会发现, 14316557663=42949672981431655766 * 3 = 4294967298(232)(2^{32}) 难倒这个是巧合吗?

我们先来了解一下除法原理

除法原理

我们来分析一下编译器除法原理

除以 22 的整数次幂

这个比较好搞吧 (

汇编

比如我们要对 xx 除以 2p2^p

1
2
3
4
5
6
7
8
qwq(int&):
movl (%rdi), %eax
leal <x1>(%rax), %edx
testl %eax, %eax
cmovns %eax, %edx
sarl $<x2>, %edx
movl %edx, (%rdi)
ret

< x1 > 就是 2p12^p-1

< x2 > 就是 pp

除以 22 的非整数次幂

这个比较难弄了 /dk

我们需要使用一些数学方法来去优化

注意到

xpx×2np×2n=x×2np×12n{x\over p}\rightarrow x\times {2^n\over p\times 2^n} = x \times {2^n \over p} \times {1 \over 2^n}

nn 通常取 width of type

编译器预处理了出来 2np2^n\over p, 再按照除以 22 的整数次幂就可以了

所以说 14316557663=42949672981431655766 * 3 = 4294967298(232)(2^{32}) 并非是巧合

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