M_sea

指令集学习笔记
昨天查了一发 $\mathrm{\color{black}{s}\color{red}{my}}$ 的水表,发现他...
扫描右侧二维码阅读全文
25
2019/06

指令集学习笔记

昨天查了一发 $\mathrm{\color{black}{s}\color{red}{my}}$ 的水表,发现他切了某道 Ynoi 题。

然后我点开了代码,发现我完全看不懂。于是问了一下 $\mathrm{\color{black}{s}\color{red}{my}}$ ,发现是指令集。

然后就学了一下,并稍微写了一下总结。

环境

不要在正式比赛中使用指令集

  • LOJ:不超过 AVX 。
  • 洛谷:支持 AVX2,有时支持 AVX-512 。
  • UOJ:比较特殊,在开头加上这段代码,然后就什么都能用了。
#define __AVX__ 1
#define __AVX2__ 1
#define __SSE__ 1
#define __SSE2__ 1
#define __SSE2_MATH__ 1
#define __SSE3__ 1
#define __SSE4_1__ 1
#define __SSE4_2__ 1
#define __SSE_MATH__ 1
#define __SSSE3__ 1

作用

可以对连续的内存空间批量处理。

可以看做每多少个字节分成一块,块内可以 $O(1)$ 处理。

对于 $\mathrm{int}$ 来说就相当于带了 $\frac{1}{8}$ 的常数。于是就可以 $n^2$ 过百万了(雾

详解

前置工作

首先你需要告诉编译器你需要使用指令集:

#pragma GCC target("avx,avx2")

这里只写了两个指令集,如果需要更多直接加在引号里就好了。

然后你需要引用两个头文件:

#include <immintrin.h>
#include <emmintrin.h>

这两个头文件是 C++ 把指令集封装成了函数,这样就可以不在代码里写汇编了。

变量

_m256i_m256_m256d 三种,分别存 long longfloatdouble

当然 long longint 也是可以的。

函数

可以在这里查需要的函数。

列几条典型的:

__m256i _mm256_set_epi32 (int e7, int e6, int e5, int e4, int e3, int e2, int e1, int e0)

把 $8$ 个 $32$ 位整数打包成一个指令集。

__m256i _mm256_set_epi64x (__int64 e3, __int64 e2, __int64 e1, __int64 e0)

把 $4$ 个 $64$ 位整数打包成一个指令集。

__m256i _mm256_add_epi32 (__m256i a, __m256i b)

返回两个指令集相加的结果。

__m256i _mm256_and_si256 (__m256i a, __m256i b)

返回两个指令集按位与的结果。

__m256i _mm256_cmpgt_epi32 (__m256i a, __m256i b)

如果 a 的某一位大于 b 的某一位,那么返回值中该位为 $\mathrm{0xffffffff}$ ,否则为 $0$ 。

__m256i _mm256_cmpeq_epi32 (__m256i a, __m256i b)

如果 a 的某一位等于 b 的某一位,那么返回值中该位为 $\mathrm{0xffffffff}$ ,否则为 $0$ 。

访问

直接用指针就行了。

a=_mm256_set_epi32(1,2,3,4,5,6,7,8);
int *b=(int *)&a;

那么 b={8,7,6,5,4,3,2,1}

注意事项

用的是 $x$ 位的指令集,就一定要 $x$ 位对齐,不然会 $\mathrm{RE}$ 。

例题:[Ynoi2018]五彩斑斓的世界

如何正确地暴力切题

这道题有两种操作:区间把大于 $x$ 的数减去 $x$ ,区间查询 $x$ 的出现次数。

暴力非常好写,我们只要用指令集优化暴力就好了。

时间复杂度 $O(\frac{nm}{8})$ ,加上一些优化可以过。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2")
#include <immintrin.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
using int_t=long long int;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,a[N];

inline void modify(int* l,int* r,int x) {
    __m256i add=_mm256_set_epi32(x,x,x,x,x,x,x,x);
    while (int_t(l)%32&&l<=r) {
        if (*l>x) *l-=x;
        ++l;
    }
    while (l+7<=r) {
        __m256i p=*(__m256i*)l;
        *(__m256i*)l=_mm256_add_epi32(p,_mm256_mullo_epi32(_mm256_cmpgt_epi32(p,add),add));
        l+=8;
    }
    while (l<=r) {
        if (*l>x) *l-=x;
        ++l;
    }
}

inline int query(int* l,int* r,int x) {
    int res=0;
    __m256i sum=_mm256_setzero_si256();
    __m256i o=_mm256_set_epi32(x,x,x,x,x,x,x,x);
    while (int_t(l)%32&&l<=r) {
        if (*l==x) ++res;
        ++l;
    }
    while (l+7<=r) {
        sum=_mm256_sub_epi32(sum,_mm256_cmpeq_epi32(*(__m256i*)l,o));
        l+=8;
    }
    while (l<=r) {
        if (*l==x) ++res;
        ++l;
    }
    int* ar=(int*)&sum;
    for (re int i=0;i<8;++i) res+=ar[i];
    return res;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=m;++i) {
        int op=read(),l=read(),r=read(),x=read();
        if (op==1) modify(a+l,a+r,x);
        else printf("%d\n",query(a+l,a+r,x));
    }
    return 0;
}

参考资料

最后修改:2019 年 06 月 25 日 08 : 30 PM

1 条评论

  1. xgzc

    Orz M_sea

发表评论