卡常 FQA

位运算比加减法快？

答

否，and, xor, or 和加减法一样快，<<, >> 比加减法满，具体指令表如下：

instruction	operands	Latency	RThroughput
add, sub, and, xor, or	r, r/i	1	0.25
add, sub, and, xor, or	r, m		0.5
add, sub, and, xor, or	m, r/i	5	1
shr, shl, sar	r, i	1	0.5
shr, shl, sar	m, i		2
shr, shl, sar	r, cl	2	2
shr, shl, sar	m, cl		4

这里 cl 是指 rcx 的最低 8 位。

手写读入中 x = x * 10 + c - 48 改成 x = (x << 1) + (x << 3) + (c ^ 48) 更快吗？

答

x * 10 改成 (x << 1) + (x << 3) 是无效的，因为编译器的实现既没有乘法也没有位运算，而是用 lea，同理 x * 2 改成 x << 1 也是没有意义的。

x * 10:

1 2	lea eax, [eax + eax * 4] add eax, eax

c - 48 改成 c ^ 48 在 Coffee Lake 上是会变快的，造成速度差异的原因还是因为编译器用了 lea。

x = x * 10 + c - 48:

1 2	lea eax, [eax + eax * 4] lea eax, [ecx + eax * 2 - 48]

x = x * 10 + (c ^ 48):

1
2
3

lea eax, [eax + eax * 4]
xor ecx, 48
lea eax, [ecx + eax * 2]

等等，为什么后者更快，它不是多了一条指令吗？因为在 Coffee Lake 上有三个参数的 lea 要慢一些，它比 xor 加两个参数的 lea 还要慢，编译器生成三参数 lea 的原因可能是照顾 11 代及以后的处理器。指令表中 lea 的信息：

instruction	operands	Latency	RThroughput
lea	r16, […]	2-4	1
lea	r32/64, [<= 2 个参数]	1	0.5
lea	r32/64, [3 个参数]	3	1
lea	r32/64, [包含 rip 作为参数]		1

另外，这个 lea eax, [ecx + eax * 2 - 48] 很慢并不意味着 mov eax, DWORD PTE [ecx + eax * 2 - 48] 也慢，内存加载有专用的执行单元 AGU，它比 ALU 更快。

a ^= b ^= a ^= b 比 swap(a, b) 更快吗？

答

否，mov 指令不劣于 xor 指令，而且 mov r, r 比 xor r, r 更好。在语义上，编译器能够理解三赋值意味着交换，某些时候就不会真的交换，只是把之后用到变量的地方替换一下。

inline 与 register 加上更快吗？

答

register 没用，开了 O2 register 会被直接过滤掉。

inline 有用。内联函数的基本目的是去掉函数调用的开销，这一点编译器做得很好，该内联的都会自动内联，所以通常不需要自己加 inline。

当 inline 有其他目的的时候，就需要加 inline 了，通常有两种：

当实参传递进去的时候，会有一些好的性质。比如我定义了一个矩阵乘法函数 mul_mod(A, B, C, mod)，当我调用 mul_mod(a, b, c, 998244353) 时，如果内联的话就可以把所有取模运算都优化。

code

const int N = 100;

inline void mul_mod(int a[N][N], int b[N][N], int c[N][N], int mod) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            for (int j = 0; j < N; j++)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
}
void mul_mod_9(int a[N][N], int b[N][N], int c[N][N]) {
    mul_mod(a, b, c, 998244353);
}

递归层数是固定的，想把它完全展开来避免函数调用的开销。

有时 inline 还是不会内联，需要用 __attribute((always_inline)) inline 替代 inline 实现强制内联。

三目运算和 if 的速度有差别吗？

答

它们在语义上有一点细微的差别，所以可能导致编译结果不一样。

比如 if (x > 50) sum += x 和 sum += x > 50 ? x : 0 并不等价。sum += x > 50 ? x : 0 要翻译成 if 应该这样：

1
2
3

int temp = 0;
if (x > 50) temp = x;
sum += temp;

这会导致三目被编译成无分支的概率更大。

数组大小开 $2^k$ 会变慢吗？

答

有可能。如果访问的地址序列构成公差为 $2^k$ ( $k$ 很大) 的等差数列，那么就会导致缓存异常，二维数组大小开 $2^k$ 就可能会出现这种情况。
请参阅 Cache Associativity。