卡常小记

EP1. 512x512 矩阵乘法 B3615

tag：SIMD，fma，cache

思路主要来源于 algorithmica。

首先矩阵乘法这个东西很适合 SIMD。先启动一下指令集：record1,491ms

这里使用了一个 GCC 扩展，即 typedef double vec __attribute__ ((vector_size(32))) 可以生成一个 $4$ 个 double 打包的类型 vec，基本兼容正常数组的语法，底层实现是 __m256d。

此外，矩阵乘法的核心操作是 $x\gets x + y\cdot z$，这个可以用 fma 压到一行指令，当然也有对应的指令集操作。

这个东西并不是那么 Cache-friendly。所以我们考虑分块计算，假设我们要求出 C[x,x+h][y,y+w] 这一个较小的子矩阵答案，我们需要 fetch $(h+w)\cdot n$ 个位置，而我们原先的做法相当于算一个位置就 fetch 了 $2\cdot n$ 个位置。

取 $h=6,w=8$，平均一个位置 fetch 了 $\frac{h+w}{hw}$ 行，效率大约提升了 $6.8$ 倍！

当然实现出来没有理论上那么优秀，因为有别的瓶颈。

这个东西其实对 Cache 还是不太友好，考虑更加激进一点，我们每次只用 A,B 的一小块来更新 C，这样数组中一小部分高频访问，可以减少 Cache-miss。

当然可以调整参数！

这个东西差不多到头了，我们发现 lg 的评测机支持 avx512f 也就是同时压 $8$ 个 double，启动一下！

感觉应该还有优化空间，但卡不动了。

做法还是比较清晰的：对 $k$ 根号分治：

小于 $\sqrt V$ 的只有根号个 $k$，枚举 $k$ 随便拿个啥 DS 维护一下即可；
大于 $\sqrt V$ 的话，$\lfloor \frac{a_i}{k} \rfloor$ 只有根号种，考虑枚举这个商，把一个询问拆成根号个，假设当前商为 $q$，则询问的答案即为 $q\cdot k$ 在区间 $[l,r]$ 的非严格后继。

区间非严格后继可以扫描线，这样就变成了 $O(n)$ 次修改，$O(q \sqrt V)$ 次询问的 $\text{rmq}$ 问题。后者可以直接上带修 ST 表。~~好了我们做完了。~~

下面是常数优化 Hints：