FHC 2023 Final 反省会会場 / 並列化研究

概要 / 言い訳タイム

FHC 2023 Finalの順位表を見ると、私がBをダウンロードだけして提出していないことがわかると思います。 そもそもカクタス(F)をシバけないとどうしようもないセットではあったのですが、それでもBを出していれば一応5位で入賞であり、このムーブは奇妙です。

これ

実際何が起きたのかというと、普通にTLEしました。AC率からもわかるように最悪ケースを作るのが難しい問題ではないのですが、$N \times M \le 1{,}000{,}000$に対して $N = M = 300$がほぼ最悪ケースだと勘違いしました。このコンテストは世界top25のコンテストです。

反省

そもそもこのミスはリカバリー可能なはずでした。FHCは手元実行なので、適当にケースごとに並列化すれば容易に高速化できるはずです。この準備はしようしようと思っていたのですが、面倒でやらなかったらやられてしまいました。

というわけで、この記事はFHC用に並列化環境を整備する話になります。

成果物

成果物をFHC 2023 Qual A1問題に適応したのがこちらになります。

qual-A1.cpp · GitHub

非ライブラリ部分は次のようになります。

using namespace std;

void solve(auto input_end, auto output) {
    int s, d, k;
    cin >> s >> d >> k;
    input_end();

    int buns = 2 * (s + d);
    int patties = s + 2 * d;

    output([&] {
        if (buns < k + 1 || patties < k) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
        cout << flush;
    });
};

int main() {
    int t;
    cin >> t;
    fhc_solve([&](auto i, auto o){ solve(i, o); }, t);
    return 0;
}

可能な限り、「いつものように普通にsolve関数を書いたら、勝手に並列化される」に近いものを目指しました。

  • input_end()を入力が終わった後に呼ばないといけない
  • output()にラムダを渡して、そこですべての出力を行わないといけない
  • outputの最後で必ずflushしないといけない
  • multi-threadを使っているので、グローバル変数を書き換えたりすると、何が起きるかわからない
  • 実行のたびに出力をファイルに全部保存して消してないので、出力が大きいとやばそう

などが残った制約です。代償としてライブラリ側はfreopenなどを乱用したコードになりました。

実行すると次のようになります

$ ./A1/main < A1/big.in > A1/big.out                    
Start FHC solver: tmp = "/tmp/output-14960984700273349145", parallel = 12
[#0] Start case: 1 / 79
[#0] End case: 1 (0 ms)
[#1] Start case: 2 / 79
[#1] End case: 2 (0 ms)
[#0] Start case: 3 / 79
[#0] End case: 3 (0 ms)
[#2] Start case: 4 / 79
[#2] End case: 4 (0 ms)
[#3] Start case: 5 / 79
[#10] Start case: 6 / 79
[#3] End case: 5 (0 ms)
[#1] Start case: 7 / 79
[#10] End case: 6 (0 ms)
[#5] Start case: 8 / 79
[#1] End case: 7 (0 ms)
:

私のPCは(論理)12コアなので、12並列でケースが実行されます。

Bに再挑戦

実際にBに再挑戦してみました、80s -> 28sなので、おおよそ3倍弱の高速化のようです。80sってそもそも間に合ってね？については、コンテスト中の6分間であわてて定数倍高速化した後のコードだからです(本当は一番最初のコードで試したかったのですが、上書きしていたため入手できませんでした…)。

旧
./B/main_single < B/test.in > B/test3.out  80.11s user 0.03s system 99% cpu 1:20.14 total

新
./B/main < B/test.in > B/test3.out  148.96s user 0.15s system 527% cpu 28.245 total

また、ログは次のような感じです。最大ケースのCase 31(N = M = 1000)に引っ張られていることがわかります。

:
[#4] End case: 98 (13 ms)
[#4] Start case: 99 / 100
[#4] End case: 99 (5 ms)
[#4] Start case: 100 / 100
[#4] End case: 100 (14 ms)
[#8] End case: 45 (1874 ms)
[#7] End case: 37 (11847 ms)
[#3] End case: 38 (11849 ms)
[#2] End case: 36 (11859 ms)
[#0] End case: 39 (11978 ms)
[#10] End case: 35 (12436 ms)
[#6] End case: 41 (12013 ms)
[#9] End case: 40 (12544 ms)
[#11] End case: 42 (12237 ms)
[#5] End case: 43 (11407 ms)
[#1] End case: 31 (28236 ms)
./B/main < B/test.in > B/test3.out  148.96s user 0.15s system 527% cpu 28.245 total

Eにも挑戦

また、結構実行時間がやばかったEに対してもやってみたところ…　MLEしました。

並列なしでメモリを4GBぐらい使うとんでもプログラムなので、12並列ならばさもありなんです。

3並列ならば、高速化が確認できました(155s -> 70s)。しかし、いざ本番でMLEで突然死、は困るので、この弱点の対応法は悩みどころです。48GB余裕なぐらいメモリ増設すればいいだけでは？ お安い対策としては、そもそもクラウドに巨大インタンスを借りてそこでやるなどが考えられます。ルール的にOKなのかは微妙ですが…

./E/main_single < ./E/big.in > ./E/big2.out  139.51s user 15.66s system 99% cpu 2:35.24 total
./E/main < ./E/big.in > ./E/big2.out  183.57s user 5.30s system 269% cpu 1:10.12 total

ログを確認したところ、一番時間のかかるケースは10s程度だったので、クラウド等にガチ強力インスタンス借りれば10s切れそうではある

[#0] End case: 15 (10019 ms)