avx 是一组并行计算的指令
最多可支持 8 个 long long 同时计算,并且洛谷支持使用,可以用来抢最优解或者卡常。
需要比较新的 CPU,CCF 估计不支持。
1. 头文件
#include <immintrin.h>
2. 基本类型
__m256i
是 256 位容器,__m512i
是 512 位容器。
可以使用 loadu
或者 set
这个加载到容器,storeu
存回内存中(见下文)。
3. 计算
除了除法、取模以外,大部分运算都可以加速。(浮点运算似乎支持除法,但是也不推荐使用,速度很慢)
部分函数名格式:_mm
+ 位数(256/512) + _
+ ((可选)mask_
/maskz_
/空
)+ 运算类型(add/sub/mul/div/cmp/min/max 等) + _
+ 数字类型(epi8/epi16/epi32/epi64/epu8/epu16/epu32/epu64/pd/ps/ph)
mask
表示掩码,详见文档。pd=double,ps=float,ph=16位浮点数
比如 _mm512_add_epi64
,_mm512_sub_epi32
,_mm256_mask_add_epi32
。可以将速度提高好几倍。不一定所有组合都有,请以官方文档为准。
4. 例题
这种东西竟然还有例题
[WC2017] 挑战
任务一:基数排序,不细说
我个人认为基数排序用 avx 没有太大的提升空间
(我似乎找到了关于寻址的函数 _mm512_i32gather_epi32
_mm512_i32scatter_epi32
,但是没有实际测试过)
任务二:
对于字符串处理,avx 基本无敌,因为可以将速度提高 64 倍,从而碾压标程。
这里列出了一些需要用到的函数:
_mm512_loadu_si512
加载 512 位数据
_mm512_set1_epi8
用一个 8 位数据填充整个 512 位寄存器,相当于 memset
_mm512_cmpeq_epu8_mask
比较 512 位数据,返回 64 位掩码
_mm_popcnt_u64
或 __builtin_popcountll
统计 64 位整数内 1 的个数
核心代码如下:
1 | j=0; |
任务三:
用 _mm512_add_epi32
优化 dp 转移,速度 * 16,应该能过。
洛谷:【模板】线段树 1
可以用 avx 快速计算区间加和区间和,由于值域都是 long long,只能提高 8 倍速,相对前一题,比较极限。
5. 文档
官方文档:https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html
翻译后文档:https://avx.fanplus.top