2021/02/15 - 2021/02/21 の振り返り
英語
達成回数: 6 (total 17)
内容: Duolingo
感想: Duolingo以外もなんかやったほうがよさそうだけど、何やろうか。
運動
達成回数: 5 (total 16)
内容: フィットネスバイク, リングフィット
感想: 少しずつ体力がついている感じする。筋肉がついている様子はない。
その他
達成回数: 5 (total 11)
内容: レガシーコードからの脱却と30日でできる! OS自作入門を読んだ。
感想:レガシーコードからの脱却ではレガシーコードを作らないためのプラクティスをいくつか学んだ。今読んだところまででもやれそうなことがいくつかあったので、実践していきたい。OS自作入門はOSよりもRustについて調べてる時間のほうが長かった。Rust難しい。
2021/02/08 - 2021/02/14 の振り返り
英語
達成回数: 4 (total 11)
内容: Duolingo
感想: すこし単語が聞き取れるようになった気がする。気がするだけかもしれない
運動
達成回数: 5 (total 11)
内容: フィットネスバイク, リングフィット
感想: リングフィットで威力が高い範囲攻撃スキルを手に入れてからそれを選択しがちだけどこれでいいのだろうか。ちゃんと負荷を与えられているとキツくて連続で選ぶの避けそうだし、もっと負荷をあげるべき？
その他
達成回数: 2 (total 6)
内容: レガシーコードからの脱却と30日でできる! OS自作入門を読んだ。
感想: 現在進行形でレガシーコードを作成している気がするので、脱却できるようにがんばって読み進めたい。OS自作入門は10日目の重ね合わせ処理のあたり。内容としては頑張って処理をサボろうというのが大部分な感じ。
2021/02/01 - 2021/02/07 の振り返り
英語
達成回数: 7
内容: Duolingo, ABCニュース英語
感想: ぼちぼち
運動
達成回数: 6
内容: フィットネスバイク, リングフィット
感想: 疲れた。ドラゴに二回やられた。つらい
その他
達成回数: 4
内容: テスト駆動開発と音声分離に関する本を少し読んだ。全然頭に入ってこない。本を読むの苦手すぎる
2020年の振り返りと2021年の目標
もう年が明けてから一ヶ月経とうとしていますが。
2020年の振り返り
2020年の目標
— runom (@runom) 2019年12月31日
・修論を書いて卒業する
・競プロで可能な限りコンテストに参加する
・Kaggleでソロメダルを取る
・ソフトウェア開発手法を身につける
・英語を学ぶ
・メンタルを安定させる
- 修論を書いて卒業する
もはや懐かしい。なんとか卒業できました。 - 競プロで可能な限りコンテストに参加する
全然出ていない。（AtCoderの参加回数数えてみたら17回だけだった。）練習しないからたまに参加してもレーティングが下がって、モチベも下がるみたいな状態が続いた。 - Kaggleでソロメダルを取る
そもそもまともに参加してすらいない。やる気が感じられませんね。 - ソフトウェア開発手法を身につける
会社の研修や業務で初歩的な部分は学んだけど、身についているかと言われると微妙。 - 英語を学ぶ
全然やっていない。流石にやばいと思って12月くらいから Duolingo というアプリを使い始めた。 - メンタルを安定させる
相変わらず躁鬱っぽく上がったり下がったりしている。大学の頃よりマシにはなったかもしれない。
全体的に達成できていない。技術とか語学に関しては、労働のせいで時間が…という言い訳もあるけど、モチベーションが足りていないのが根本的な原因だと思う。
まぁ環境が大きく変化するタイミングに流行病が合わさった大変な状況でなんだかんだ生活できたのは偉かった。
2021年の目標
最低限
- 1日30分英語に関する何かを行う
ちゃんとがんばろうとすると、趣味でも業務でも英語を読み書きする能力が必要になってくると感じたので。あと業務で必要になるかもしれないという事情もある。前述した Duolingo はもうすぐで2ヶ月継続になるのでこの調子で続けたい。あとは強度を上げるために時間を伸ばしたり他のこともできたらいい感じ。 - 1日30分運動する
流行病の影響で以前に増して家に引きこもるようになり、健康面の不安が大きくなってきたので。なぜか家にはリングフィットやフィットネスバイクといったものが眠っているので、これらを使ってがんばりたい。
この2つは本当は毎日やるべきなんだろうけど、どうしても無理な日はあると思うので、8割くらいの日数達成することを目標にする。残り334日なので267日達成できれば上出来で、200日は超えたいところ。
できれば
- 競プロ: 問題を1問解く, コンテストに参加する
コンテスト参加回数が20回以上 - データ分析コンペ: Discussionを1つ読む, Submitを1回する
最後まで追ったコンペが1つ以上 - 技術書: 30分読み進める
読み終えた本が5冊以上 - その他技術系の何か
何らかのアウトプットを出す。
こっちは時間と心に余裕があればという感じ。どれか1つやるのを100日以上達成したい。
がんばるぞ。
ClangでC++ Modulesを試したときのメモ
以下の記事を読んだので、試してみた。
使用した Clangのバージョンは以下の通り。
clang version 9.0.0 (https://git.llvm.org/git/clang.git 962a041dca1359c3c47cd8c242fa5d66028f666e)
まずはコードを用意。
// speech.cppm export module speech; export const char* get_phrase() { return "Hello, world!"; }
// main.cpp import speech; //import <iostream>; #include <iostream> int main() { std::cout << get_phrase() << '\n'; }
import <header>; はまだ対応していないみたいなので、普通にincludeした。コンパイルと実行。
$ clang++ -fmodules-ts --precompile speech.cppm $ clang++ -fmodules-ts -fprebuilt-module-path=. speech.pcm main.cpp $ ./a.out Hello, world!
動いた。-fprebuilt-module-pathはプリコンパイルされたモジュールファイルが置かれているディレクトリを指定。
プリコンパイル前のモジュールファイルの拡張子が .cppm でない場合は、以下のように -x c++-module を付ければよいらしい。
$ clang++ -fmodules-ts -x c++-module --precompile speech.cpp $ clang++ -fmodules-ts -fprebuilt-module-path=. speech.pcm main.cpp
また、プリコンパイルされたモジュールファイルの名前と、モジュール名が同じでない場合は -fmodule-file=[モジュール名]=[モジュールファイル]で指定すると通った。
$ clang++ -fmodules-ts --precompile speech_module.cppm $ clang++ -fmodules-ts -fprebuilt-module-path=. -fmodule-file=speech=speech_module.pcm speech_module.pcm main.cpp
上記の記事にあった Modules Paritions は動かなかった。(Modules TSには含まれていない？）
参考：
SIMD(AVX-512)を使って競プロの問題を解いてみる
この記事は Competitive Programming (2) Advent Calendar 2018 18日目の記事です。
定数倍高速化の方法としてSIMDを用いたものが存在します。SIMDを用いて競プロの問題を解いている例としては以下の記事がありました。
SIMDの命令セットにも色々種類があるようですが、今回はその中でもAVX-512を用いて競プロの問題を解いてみます。
AVX-512やそもそものSIMDについては以下の記事が参考になると思います。
SIMDプログラミング入門（AVX-512から始める編） - Qiita
※注意
・現時点でAVX-512を使えるコンテストサイトはないと思います(たぶん)。なので今回は手元の環境で実行してます。
・対象とした問題のテストケースが公開されていなかったので、自分で最大ケースを作って試してます。おそらく大丈夫だとは思うのですが、コードに誤りがあった場合は指摘してくださると嬉しいです。
問題(ABC106 D - AtCoder Express 2)
自明な解法
問題に書いてある通りのことをやればよいですね。こんな感じのコードになると思います。
#include <cstdio> using namespace std; int main() { const int m_max = 200000; const int q_max = 100000; int N, M, Q; scanf("%d%d%d", &N, &M, &Q); int L[m_max], R[m_max]; for (int i = 0; i < M; i++) { scanf("%d%d", &L[i], &R[i]); } int ans[q_max]; int p[q_max], q[q_max]; for (int i = 0; i < Q; i++) { scanf("%d%d", &p[i], &q[i]); } for (int i = 0; i < Q; i++) { ans[i] = 0; } for (int i = 0; i < Q; i++) { for (int j = 0; j < M; j++) { if (p[i] <= L[j] && R[j] <= q[i]) { ans[i]++; } } } for (int i = 0; i < Q; i++) { printf("%d\n", ans[i]); } }
これだと計算量は O(QM) で、QMが最大でになるのでちょっと厳しそうです。実際に実行してみましょう。
$ g++-7 -O3 -march=native AtCoderExpress2.cpp -o AtCoderExpress2 $ time ./AtCoderExpress2 < testcase.txt > output.txt real 1m5.404s user 1m5.388s sys 0m0.004s
TLは3秒なので、大幅にオーバーしてます。
SIMDで並列化
早速上記のコードを並列化してみます。二重forの外側と内側どちらを並列化するかですが、今回は内側のループを並列化することにします。（そっちを先に思いついたので。）
#include <cstdio> #include <cstdint> #include <immintrin.h> using namespace std; int main() { const int m_max = 200000; const int q_max = 100000; int N, M, Q; scanf("%d%d%d", &N, &M, &Q); alignas(64) int16_t L[m_max], R[m_max]; for (int i = 0; i < M; i++) { scanf("%hd%hd", &L[i], &R[i]); } int ans[q_max]; int16_t short p[q_max], q[q_max]; for (int i = 0; i < Q; i++) { scanf("%hd%hd", &p[i], &q[i]); } for (int i = 0; i < Q; i++) { ans[i] = 0; } const int M1 = M / 32 * 32; for (int i = 0; i < Q; i++) { const __m512i pp = _mm512_set1_epi16(p[i]); const __m512i qq = _mm512_set1_epi16(q[i]); for (int j = 0; j < M1; j += 32) { const __m512i LL = _mm512_load_si512(L + j); const __m512i RR = _mm512_load_si512(R + j); const __mmask32 cond1 = _mm512_cmple_epi16_mask(pp, LL); const __mmask32 cond2 = _mm512_cmple_epi16_mask(RR, qq); ans[i] += _mm_popcnt_u32(_kand_mask32(cond1, cond2)); } for (int j = M1; j < M; j++) { if (p[i] <= L[j] && R[j] <= q[i]) { ans[i]++; } } } for (int i = 0; i < Q; i++) { printf("%d\n", ans[i]); } }
$ g++-7 -O3 -march=native AtCoderExpress2AVX512.cpp -o AtCoderExpress2AVX512 $ time ./AtCoderExpress2AVX512 < testcase.txt > output_avx512.txt real 0m0.995s user 0m0.992s sys 0m0.000s $ diff output.txt output_avx512.txt $
めっちゃ速くなりましたね。1秒を切ることに成功しました。
まとめ
対象とした問題が単純だったというのはあるのですが、思ったよりも簡単にSIMDで高速化出来ました。問題がもっと複雑な場合でも高速化できるものはあると思うので、計算量を落とす方法は思いつかないけど定数倍高速化すれば通りそう、みたいな時は少し考えてみてもよいかもしれません。
今回使用したAVX-512の命令は単純なものだけでしたが、色々機能が追加されているらしいので、コンテストサイト(特にAtCoder)で使えるようになることを願いつつ終わりたいと思います。
オチ
実は元のコードとSIMDを用いたコードは処理が若干異なっています。後者の方に合わせるとコードは以下のようになります。ついでに変数の型も合わせました。
#include <cstdio> #include <cstdint> using namespace std; int main() { const int m_max = 200000; const int q_max = 100000; int N, M, Q; scanf("%d%d%d", &N, &M, &Q); int16_t L[m_max], R[m_max]; for (int i = 0; i < M; i++) { scanf("%hd%hd", &L[i], &R[i]); } int ans[q_max]; int16_t p[q_max], q[q_max]; for (int i = 0; i < Q; i++) { scanf("%hd%hd", &p[i], &q[i]); } for (int i = 0; i < Q; i++) { ans[i] = 0; } for (int i = 0; i < Q; i++) { for (int j = 0; j < M; j++) { ans[i] += (p[i] <= L[j] & R[j] <= q[i]); } } for (int i = 0; i < Q; i++) { printf("%d\n", ans[i]); } }
if文が消えて演算子が`&&` から `&`に変わりました。
この状態で実行してみます。
$ g++-7 -O3 -march=native AtCoderExpress2.cpp -o AtCoderExpress2 $ time ./AtCoderExpress2 < testcase.txt > output.txt real 0m1.085s user 0m1.080s sys 0m0.004s
SIMDを使ったのと同じくらいの実行時間になりました。これはどういうことかというと、条件分岐が消えたのも速くなった理由の一つではありそうですが、自動ベクトル化が効いたことが主な理由だと考えられます。コンパイラがコードを解析した結果、SIMDが使えると判断した際には（明示的に書かれていなくても）自動的に使うように最適化されることがあります。
実際にアセンブラを出力して確認してみると、AVX-512で使用されるzmmレジスタが使われていることなどから、AVX-512が使われている=SIMD命令が使われていることが確認できました。
AtCoderは128bitのSIMD幅の命令は使えるそうなので(AVX-512は512bit)単純に考えると4倍くらいの実行時間になって、それでもTL3秒に間に合いそうな気がしてきます。そのままだと通らなかったので適当にコードをいじって投げると通っちゃいました。
Submission #3820425 - AtCoder Beginner Contest 106
以上のことから、 SIMDを自分で明示的に書く前に、すでに自動ベクトル化がされていないか、されていない場合には自動ベクトル化を阻害するようなコードになっていないか等を確認するとよいかもしれません。
