回答編集履歴
3
計測結果を追加等
answer
CHANGED
|
@@ -8,11 +8,19 @@
|
|
|
8
8
|
参考: [SIMDの組み込み関数のことはじめ - koturnの日記](http://koturn.hatenablog.com/entry/2016/07/18/090000)
|
|
9
9
|
コンパイラによって注意点がありますが、それさえ注意していれば大丈夫です。上のコードの実行環境はWSL上のUbuntuです。AVX2に対応したCPUで試して見てください。その他、リトルエンディアンが前提など、環境依存が多々ありますので、ご注意ください。
|
|
10
10
|
|
|
11
|
-
手元での結果では速い順で
|
|
11
|
+
手元での結果では速い順で(単位は秒)
|
|
12
12
|
|
|
13
|
+
```
|
|
14
|
+
prep_avx2 5.64 (user 5.40, system 0.18)
|
|
13
|
-
|
|
15
|
+
shift_ll 6.22 (user 6.04, system 0.17)
|
|
16
|
+
prep_ll 6.53 (user 6.39, system 0.14)
|
|
17
|
+
prep_int 7.83 (user 7.64, system 0.18)
|
|
18
|
+
shift_int 8.85 (user 8.71, system 0.14)
|
|
19
|
+
prep_char 14.75 (user 14.46, system 0.20)
|
|
20
|
+
shift_char 21.48 (user 21.15, system 0.28)
|
|
21
|
+
```
|
|
14
22
|
|
|
15
|
-
という感じでした。AVX2の256bitとlong longではそれほど差が出
|
|
23
|
+
という感じでした。AVX2の256bitとlong longではそれほど差が出ていないのは、AVX2には_m265iをそのままシフトする関数がない(64bit整数4つそろぞれシフトならある)ため、面倒だったので、uint64_tで作って、そのままキャストしているところだと思います。ここを四つ同時にシフトしてうまくするように書き直せばもう少し速くなると思います。
|
|
16
24
|
|
|
17
25
|
なお、long longではprepとshfitが逆転しました。mallocを64回も呼び出すこと自体が重いのかも知れません。一気に巨大なメモリ領域を確保などの工夫をすれば、速くなる可能性はあります。
|
|
18
26
|
|
2
誤字の修正
answer
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
[ビット列検索 | gist](https://gist.github.com/raccy/3ccc6f1a2ca7ca60ef7c85e17875ecbd)
|
|
4
4
|
|
|
5
|
-
shiftは愚直に毎回シフトするもの、prepはあらかじめシフト済みのsearchとmaskを用意しておくものです。avx2がついているのだけ、AVX2で__m256i(256bit整数)を使っています。同じようにSSEで128bit、AVX-512で512bitも作れると思います
|
|
5
|
+
shiftは愚直に毎回シフトするもの、prepはあらかじめシフト済みのsearchとmaskを用意しておくものです。avx2がついているのだけ、AVX2で__m256i(256bit整数)を使っています。同じようにSSEで128bit、AVX-512で512bitも作れると思います、たぶん。
|
|
6
6
|
|
|
7
7
|
SIMDはアセンブラを使わなくても可能です。
|
|
8
8
|
参考: [SIMDの組み込み関数のことはじめ - koturnの日記](http://koturn.hatenablog.com/entry/2016/07/18/090000)
|
1
結果の一部が間違っていた。
answer
CHANGED
|
@@ -10,7 +10,7 @@
|
|
|
10
10
|
|
|
11
11
|
手元での結果では速い順で。
|
|
12
12
|
|
|
13
|
-
prep_avx2 > shift_ll >
|
|
13
|
+
prep_avx2 > shift_ll > prep_ll >>> prep_int > shift_int >>> prep_char >>> shift_char
|
|
14
14
|
|
|
15
15
|
という感じでした。AVX2の256bitとlong longではそれほど差が出ません。AVX2には_m265iをそのままシフトする関数がない(64bit整数4つそろぞれシフトならある)ため、面倒だったので、long longで作って、そのままキャストしています。ここを四つ同時にシフトしてうまくするように書き直せばもう少し速くなると思います。
|
|
16
16
|
|