「指令集」常用指令集优化技巧

指令集是什么

指令集 是存储在CPU内部,对CPU运算进行指导和 优化 的硬程序

常用指令集有 MMX, SSE, SSE2, SSE3, SSSSE3, SSE4.1, SSE4.2, AVX, AVX2

由于博主不会汇编, 本文只介绍被封装好的指令集及用于操作指令集的函数

指令集能用来干什么

优化程序运行速度(其实就是卡常), 并没有什么用处, 因为大部分算法竞赛 禁止 使用以下划线开头的函数, 指令集通常是以 __ 开头的....

不要在算法竞赛(特指某竞赛)中使用指令集 / 内嵌汇编

指令集有许多优秀的函数, 可以通过一条语句对指令集进行操作

指令集详(lue)解

指令集可以被 片面地 理解为分块, 通过提供的函数可以统一对这些指令集进行操作

前备

使用指令集首先要使用预编译命令, 比如

1
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

除此之外, 还要加入

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

因为 Intrinsics 是对 MMXSSE 等指令集的指令的一种封装,以函数的形式提供,使得程序员更容易编写和使用这些高级指令,在编译的时候,这些函数会被内联为汇编,不会产生函数调用的开销

定义

扯了那么多, 先来讲一下如何定义指令集

  • __m64 64 整数 指令集(MMX
  • __m128 128 单精度 指令集(SSE
  • __m128d 128 双精度 指令集(SSE2
  • __m128i 128 整数 指令集(SSE2
  • __m256 256 单精度 指令集(AVX
  • __m256d 256 双精度 指令集(AVX
  • __m256i 256 整数 指令集(AVX

这些数据类型与寄存器的对应关系:

64 MM 寄存器(MM0 ~ MM7):__m64

128 SSE 寄存器(XMM0 ~ XMM15):__m128__m128d__m128i

256 AVX 寄存器(YMM0 ~ YMM15):__m256__m256d__m256i

下面都是以 256 AVX 指令集为例子

基础函数

下面是关于上面的一些函数

赋值

对于 __m256i 256 位的, 也就是 32 个字节, 所以可以放 4 long long int 8 int 16 short 32 个字节 (char)

赋值有自带的函数, 下面是函数原型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 字节(char)
__m256i _mm256_set_epi8 (char e31, char e30, char e29, char e28, char e27, char e26, char e25, char e24, char e23, char e22, char e21, char e20, char e19, char e18, char e17, char e16, char e15, char e14, char e13, char e12, char e11, char e10, char e9, char e8, char e7, char e6, char e5, char e4, char e3, char e2, char e1, char e0)

// short
__m256i _mm256_set_epi16 (short e15, short e14, short e13, short e12, short e11, short e10, short e9, short e8, short e7, short e6, short e5, short e4, short e3, short e2, short e1, short e0)

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

// long long int
__m256i _mm256_set_epi64x (long long e3, long long e2, long long e1, long long e0)

// __int128
__m256i _mm256_set_m128i (__m128i hi, __m128i lo)

注意! 对于指令集存储的数字是 倒序

除此之外, 指令集由函数资瓷全部赋值为一个数, 下面是两个例子, 其他的仿照上面就好啦

1
2
__m256i _mm256_set1_epi64x (long long a)
__m256i _mm256_set1_epi32 (int a)

运算

下面只给出 __int32(int) 和 __int64(long long) 的实例

判断两指令集是否相等

1
2
__m256i _mm256_cmpeq_epi32 (__m256i a, __m256i b)
__m256i _mm256_cmpeq_epi64 (__m256i a, __m256i b)

返回一个指令集, 对于第 i 位, 若 a_i=a_b , 则值为 0xFFFFFFFFFFFFFFFF 否则就是 0

判断两指令集的大小

1
2
__m256i _mm256_cmpgt_epi32 (__m256i a, __m256i b)
__m256i _mm256_cmpgt_epi64 (__m256i a, __m256i b)

返回一个指令集, 对于第 i 位, 若 a_i>a_b , 则值为 0xFFFFFFFFFFFFFFFF 否则就是 0

位运算合辑

1
2
3
4
5
6
7
8
// 按位与
__m256i _mm256_and_si256 (__m256i a, __m256i b)

// 按位或
__m256i _mm256_or_si256 (__m256i a, __m256i b)

// 按位异或
__m256i _mm256_xor_si256 (__m256i a, __m256i b)

开根

1
2
__m256d _mm256_sqrt_pd (__m256d a)
__m256 _mm256_sqrt_ps (__m256 a)

这个只资瓷 单精度双精度 的指令集(不是废话吗

上/下取整

1
2
3
4
5
6
7
// 向下取整
__m256d _mm256_floor_pd (__m256d a)
__m256 _mm256_floor_ps (__m256 a)

// 向上取整
__m256d _mm256_ceil_pd (__m256d a)
__m256 _mm256_ceil_ps (__m256 a)

有了小数和整数, 也就有了取整

更多指令集, 可以看 这里

实例

#1

下面是一个读入一个序列, 对序列中的每个数开根的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>

const int MAXN = 100010;

int n;
int a[MAXN];
float ans[MAXN];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) ans[i] = sqrt(a[i]);
for (int i = 1; i <= n; i++) printf("%f ", ans[i]);
return 0;
}

可以使用指令集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>

#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

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

const int MAXN = 100010;

int n;
__m256 t[MAXN / 8];
float *a = (float *)&t;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%f", a + i);
int siz = n / 8;
for (int i = 0; i <= siz; i++) t[i] = _mm256_sqrt_ps(t[i]);
for (int i = 1; i <= n; i++) printf("%f ", a[i]);
return 0;
}

#2

区间开根 区间求和

大概是我实现丑了, 只能做 float 范围内的(?)

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cmath>

#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

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

const int MAXN = 100000;

int n, m;
__m256 a[MAXN >> 3];
float t[9];

inline void modify(int l, int r) {
while (((l - 1) & 7) && l <= r)
((float*)(a + (l >> 3) + 1))[(l & 7) - 1] =
floor(sqrt(((float*)(a + (l >> 3) + 1))[(l & 7) - 1])),
++l;
if (l == r + 1) return;
while ((r & 7) && l <= r)
((float*)(a + (r >> 3) + 1))[(r & 7) - 1] =
floor(sqrt(((float*)(a + (r >> 3) + 1))[(r & 7) - 1])),
--r;
if (l == r + 1) return;
l = (l >> 3) + 1, r >>= 3;
while (l <= r) a[l] = _mm256_floor_ps(_mm256_sqrt_ps(a[l])), ++l;
}

inline long long query(int l, int r) {
if (r < l) l ^= r ^= l ^= r;
long long ans = 0;
while (((l - 1) & 7) && l <= r)
ans += floor(((float*)(a + (l >> 3) + 1))[(l & 7) - 1]), ++l;
if (l == r + 1) return ans;
while ((r & 7) && l <= r)
ans += floor(((float*)(a + (r >> 3) + 1))[(r & 7) - 1]), --r;
if (l == r + 1) return ans;
l = (l >> 3) + 1, r >>= 3;
__m256 s = _mm256_set_ps(0, 0, 0, 0, 0, 0, 0, 0);
while (l <= r) s = _mm256_add_ps(a[l], s), ++l;
for (int i = 0; i < 8; ++i) ans += floor(((float*)&s)[i]);
return ans;
}

int main() {
scanf("%d", &n);
int num = n >> 3;
for (int i = 1; i <= num; ++i) {
for (int j = 1; j <= 8; ++j) scanf("%f", t + j);
a[i] = _mm256_set_ps(t[8], t[7], t[6], t[5], t[4], t[3], t[2], t[1]);
}
for (int i = 1; i <= (n & 7); ++i) scanf("%f", t + i);
a[++num] = _mm256_set_ps(t[8], t[7], t[6], t[5], t[4], t[3], t[2], t[1]);
scanf("%d", &m);
int opt, p, q;
while (m--) {
scanf("%d%d%d", &opt, &p, &q);
if (!opt)
modify(p, q);
else
printf("%lld\n", (long long)floor(query(p, q)));
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!