测来测去7：筛法求素数Loop Unrolling性能优化实例

Posted on 本文总阅读量次

筛法求素数

最近拿到一段筛法求素数的代码，希望能够在不改变原有算法的基础上提高性能。

关于筛法求素数的算法，网络上有很多介绍。算法之间的效率存在差异，但我们的重点不在这里，而是如何在不改动现有算法的前提下提升性能。

关于不同筛法算法可以参见这里，这段程序里使用的是埃拉托斯特尼筛法。

核心代码段：

1
2
3
4
5
6
7
8
9
10
11
12
13
count = 0; 
for (i=2; i <= 8192; i++) {
    flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
    if (flags[i]) {
               /* remove all multiples of prime: i */
	for (k=i+i; k <= 8192; k+=i) {
	    flags[k] = 0;
	}
	count++;
    }
}

完整代码在：

wget https://raw.githubusercontent.com/llvm-mirror/test-suite/master/SingleSource/Benchmarks/Shootout/sieve.c

其实是LLVM编译器的性能测试代码。

测试环境

1
2
3
4
5
CPU: Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz
Hyper-thread:OFF
Power-governor: Performance
GCC: 4.8.5 20150623 (Red Hat 4.8.5-28) (GCC)
GCC option: -O3

诊断

先运行一下原有代码看看时间：

1
2
3
4
5
6
7
gcc sieve.c -O3 -o sieve
time -p ./sieve

Count: 1028
real 3.34
user 3.34
sys 0.00

简单想象一下代码流程：

  • 处理的数据是8K Byte(char flags[])，相对于32K的L1缓存不算什么数据量，所以数据缓存似乎问题不大
  • 生成的二进制文件也不大，指令缓存也没太大压力
  • 前端这边处理的主要是带分支的循环，内层循环就算还好吧…但外层循环中有个if分支判断
  • 涉及到这个判断，因为素数的出现/分布没太大规律，所以对CPU来说，这个分支判断结果相当于是随机的，有可能会影响前端流水线的性能

然后用我们之前介绍的Top-down方法和toplev工具看看实际测试的情况：

./toplev.py -v --no-desc -l1 /root/perfcontest/sieve

1
2
3
4
5
6
7
8
9
Using level 1.
# 3.4-full on Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz
perf stat -x\; --no-merge -e '{cpu/event=0xc2,umask=0x2/,cpu/event=0xe,umask=0x1/,cpu/event=0xd,umask=0x3,cmask=1/,cpu/event=0x9c,umask=0x1/,cycles}' /root/perfcontest/sieve
Count: 1028
FE             Frontend_Bound:          38.45 +-     0.00 % Slots       <==
BAD            Bad_Speculation:         16.45 +-     0.00 % Slots      
BE             Backend_Bound:            8.92 +-     0.00 % Slots below
RET            Retiring:                36.19 +-     0.00 % Slots below
               MUX:                    100.00 +-     0.00 %

基本上可以看到是前端Bound了，同时分支预测里出现了比较多的Bad_Speculation。

优化

OK，先用个简单的方法处理一下分支：

结合业务的话，素数越到后面分布是越稀松的，所以外层循环中的那个判断应该大部分时间是false。所以，先套个likely/unlikely。

1
2
3
4
5
6
#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

...
	    if (unlikely(flags[i])) {
...

编译之后看一下时间：

1
2
3
4
5
time -p ./sieve
Count: 1028
real 3.08
user 3.08
sys 0.00

有些许提升，不过不太明显。如果此时再用toplev测试一下，可以发现分支预测的改善并不可观。

那么如何改善分支预测呢？最好的办法就是不要有分支；或者，如果完全没有不可能的话，就让分支出现规律性；如果这样也不行的话，就减少分支；如果减少也不可能的话，就搞大乱序并发。

对于我们这个算法来说，判断每个数字的标志位并做后续的置位是算法的要求。提升规律性的话，也没有什么特别好的办法（至少我没想出来）， 那就只能用最后一种办法了…

把循环展开，提升流水线并行性。

展开16级还不算那么激进吧…同时内层循环也可以适当展开…

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
for (i=2; i <= 8191; i = i + 16) {
    if (unlikely(flags[i])) {
	    for (k=i+i; k <= 4096; k+=(7 * i)) {
	        flags[k] = 0;
	        flags[k + i] = 0;
	        flags[k + (2 * i)] = 0;
	        flags[k + (3 * i)] = 0;
	        flags[k + (4 * i)] = 0;
	        flags[k + (5 * i)] = 0;
	        flags[k + (6 * i)] = 0;
	    }
	count0++;
    }
    if (unlikely(flags[i + 1])) {
	    for (k=i+i + 2; k <= 8191; k+=(i + 1)) {
	        flags[k] = 0;
	    }
	count1++;
    }
    if (unlikely(flags[i + 2])) {
	    for (k=i+i + 4; k <= 8191; k+=(i + 2)) {
	        flags[k] = 0;
	    }
	count2++;
    }
    if (unlikely(flags[i + 3])) {
	    for (k=i+i + 6; k <= 8191; k+=(i + 3)) {
	        flags[k] = 0;
	    }
	count3++;
    }
    if (unlikely(flags[i + 4])) {
	    for (k=i+i+8; k <= 8191; k+=(i + 4)) {
	        flags[k] = 0;
	    }
	count4++;
    }
    if (unlikely(flags[i + 5])) {
	    for (k=i+i + 10; k <= 8191; k+=(i + 5)) {
	        flags[k] = 0;
	    }
	count5++;
    }
    if (unlikely(flags[i + 6])) {
	    for (k=i+i + 12; k <= 8191; k+=(i + 6)) {
	        flags[k] = 0;
	    }
	count6++;
    }
    if (unlikely(flags[i + 7])) {
	    for (k=i+i + 14; k <= 8191; k+=(i + 7)) {
	        flags[k] = 0;
	    }
	count7++;
    }
    if (unlikely(flags[i + 8])) {
	    for (k=i+i+16; k <= 8191; k+=(i + 8)) {
	        flags[k] = 0;
	    }
	count8++;
    }
    if (unlikely(flags[i + 9])) {
	    for (k=i+i + 18; k <= 8191; k+=(i + 9)) {
	        flags[k] = 0;
	    }
	count9++;
    }
    if (unlikely(flags[i + 10])) {
	    for (k=i+i + 20; k <= 8191; k+=(i + 10)) {
	        flags[k] = 0;
	    }
	count10++;
    }
    if (unlikely(flags[i + 11])) {
	    for (k=i+i + 22; k <= 8191; k+=(i + 11)) {
	        flags[k] = 0;
	    }
	count11++;
    }
    if (unlikely(flags[i + 12])) {
	    for (k=i+i+24; k <= 8191; k+=(i + 12)) {
	        flags[k] = 0;
	    }
	count12++;
    }
    if (unlikely(flags[i + 13])) {
	    for (k=i+i + 26; k <= 8191; k+=(i + 13)) {
	        flags[k] = 0;
	    }
	count13++;
    }
    if (unlikely(flags[i + 14])) {
	    for (k=i+i + 28; k <= 8191; k+=(i + 14)) {
	        flags[k] = 0;
	    }
	count14++;
    }
    if (unlikely(flags[i + 15])) {
	    for (k=i+i + 30; k <= 8191; k+=(i + 15)) {
	        flags[k] = 0;
	    }
	count15++;
    }
}
   }
   printf("Count: %d\n", count0 + count1 + count2 + \
                         count3 + count4 + count5 + \
                         count6 + count7 + count8 + \
                         count9 + count10 + count11 + \
                         count12 + count13 + count14 + \
                         count15);

先直接刷一下时间：

1
2
3
4
5
time -p ./sieve
Count: 1028
real 1.56
user 1.56
sys 0.00

提升了120%

再用toplev看一下：

1
2
3
4
5
6
7
8
9
10
./toplev.py -v --no-desc  -l1 /root/perfcontest/sieve
Using level 1.
# 3.4-full on Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz
perf stat -x\; --no-merge -e '{cpu/event=0xc2,umask=0x2/,cpu/event=0xe,umask=0x1/,cpu/event=0xd,umask=0x3,cmask=1/,cpu/event=0x9c,umask=0x1/,cycles}' /root/perfcontest/opt1
Count: 1028
FE             Frontend_Bound:          11.60 +-     0.00 % Slots below
BAD            Bad_Speculation:          3.30 +-     0.00 % Slots below
BE             Backend_Bound:            8.43 +-     0.00 % Slots below
RET            Retiring:                76.68 +-     0.00 % Slots       <==
               MUX:                    100.00 +-     0.00 %

瓶颈已经不在分支预测上了。

用perf stat看一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[root@server-P1 perfcontest]# perf stat ./sieve
Count: 1028

 Performance counter stats for './opt1':

       2334.081187      task-clock (msec)         #    1.000 CPUs utilized          
                 7      context-switches          #    0.003 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               141      page-faults               #    0.060 K/sec                  
     5,355,895,762      cycles                    #    2.295 GHz                    
    19,038,809,322      instructions              #    3.55  insn per cycle         
     4,209,500,410      branches                  # 1803.494 M/sec                  
        10,114,763      branch-misses             #    0.24% of all branches        

       2.334590616 seconds time elapsed

branch-misses占比很小，同时IPC也在3.55，已经接近理论最大值(4)。

后续

仅仅调了一个小时，应该还有继续优化的空间，比如利用PGO和SIMD指令。这个留在后续尝试。

test
© 2020 DecodeZ All Rights Reserved. 本站访客数人次 本站总访问量次
Theme by hiero