この記事は競プロ Advent Calendar 2023 の 17 日目の記事として書かれました。¹

Qiita全国学生対抗戦 Advent Calendar 2023 なるものもあるらしいので、ついでにそちらにも紐づけています。²

はじめに

Verification³、してますか。私はしています。

ライブラリが充実してくると、それに要する手間もばかになりません。

競プロer御用達の oj-verify も、結果をキャッシュしたりして高速化する工夫はなされていますが、それでも多くのファイルが依存しているヘッダ⁴に修正を加えた場合などにはかなりの時間がかかってしまいます。これは嬉しくないです。⁵

そうですね、並列化ですね。
並列化しましょう。

想定している読者

ライブラリ盆栽系競技プログラマの皆様
oj-verify を GitHub Actions 上で動かそうとしたが、公式のドキュメント通りに操作しても謎のエラーで行き詰ってしまった人⁶
並列処理を眺めてムフフしたい人⁷
自分のライブラリが AC Libray に依存しているが、そのコピーを自分のリポジトリに置きたくない人

想定されたい筆者

学生⁸ (業プロ未経験⁹)

GitHub Actions も、これが作りたいがためにお勉強(ドキュメント漁り)をしました。
なので「もっといい書き方があるよ！」みたいなことはたくさんあると思います。コメント等で教えてください。

この記事のゴール

こういうものを作ります：

ライブラリの verification を GitHub Actions 上で並列実行して、テストの時短を目指します。

ゼロから実装するのは大変なので、今回は online-judge-tools/verification-helper (oj-verify) を内部的に呼び出すことにしました。
互換性が保たれるので、かえって嬉しいかもしれません。

この記事で提示している多くのソースコードは、verify 対象のライブラリが C++ で記述されている ことを前提として書かれています。
C++ 以外の言語との互換性が失われる箇所については別途対応方法を簡単に記載しますが、基本的に対応例等を示すことはありません。ご了承ください。

Public リポジトリ での使用が前提です。
課金額を最小化するような調整はしていません。
無料で使える環境でのご利用を推奨します。

GitHub Actions のランナーは ubuntu-22.04 のみ を扱います。
ubuntu-20.04 は動作するかもしれませんが、macos- 系や windows- 系のランナーで動かしたい人は頑張ってください。
普段 WSL とかを使っている人は気にしなくて大丈夫だと思います。

前提知識

基本的には以下のことが分かれば十分です：

Git の基本的な操作

ただし GitHub Actions やシェルについて深くは解説しません。
やってることを理解したりしたい人は次のことも分かる¹⁰と嬉しいかもです：

GitHub Actions の仕様について
Linux のシェルについて

本題

サンプルを用意しました。
ステップごとに該当するコミットへのリンクを示すので、適宜参考にしてください。

ところで、完成品だけが欲しい人は上述のサンプルをパクってくださればよろしいかと思います。

0. 準備

ライブラリをローカルのみに保存している人は適当にリポジトリを作成して push しておいてください。

oj-verify がローカルで動作することを確認しておくのがいいと思います。¹¹
あとでもう一度述べますが、ここを読んでコンパイラのオプションの設定もしてあげてください。

ここまでのサンプル

0.0. `oj-verify` を GitHub Actions 上で動かす

筆者はまずここで沼りました。
oj-verify 側のドキュメントの整備が追いついていないのか、書いてある通りにしても動かないので、まずそれを修正します。

0.0.0. ドキュメントに従う

ここのリンク先の「verify を自動でしてくれるように設定するには」を読んで設定してください。
何も起こらなければ正常です。(2023/12/16 現在)

ドキュメントのリンク先にある「競プロライブラリの GitHub のレポジトリの URL」というのは https://github.com/{{user-id}}/{{repository-name}}/ までの部分を指していると思われます。
末尾に tree/{{branch-name}} や .git などが付随していると 404 が出たりするので、そうなってしまった人は確認してください。

ここまでのサンプル

0.0.1. `verify.yml` を修正する

./.github/workflows/ 下にあります。

0.0.1.0. 不必要な依存関係のインストールを省く

required only if.... とのコメントが付いている step を削除しましょう。¹²

verify.yml

-    # required only if you want to verify Java code
-    - name: Install dependencies (Java)
-      uses: actions/setup-java@v3
-      with:
-        distribution: temurin
-        java-version: '11'
- 
     #(他も同様)

0.0.1.1. `oj-verify` を正しくインストールする

0.0.1.1.0. インストールコマンドを修正する

verify.yml

     - name: Install dependencies
-      run: pip3 install -U git+https://github.com/${{ github.repository }}.git@master
+      run: pip3 install -U online-judge-verify-helper

GitHub Actions の github.repository context はそのワークフローが置かれているリポジトリを指しますが、恐らく意図されているのは oj-verify のあるリポジトリです。¹³

0.0.1.1.1. Python のバージョンを指定する

verify.yml

     - name: Set up Python
       uses: actions/setup-python@v4
+      with:
+        python-version: 3.12.0

なくても動きますが、ずっと警告が表示され続けるので適当なバージョンを指定あげてしてください。

0.0.1.2. `actions/checkout@v3` に `fetch-depth: 0` を渡す

重要です。

verify.yml

     steps:
     - uses: actions/checkout@v3
+      with:
+        fetch-depth: 0

actions/checkout の更新により v2 以降で必要になりました。¹⁴

0.0.1.3 `on.push.branches` を正しく指定する

verify.yml

 on:
   push:
     branches:
-    - master
+    - {{your-default-baranch-name}}
   pull_request:

{{your-default-baranch-name}} は自分のリポジトリの default branch の名前¹⁵で置換してください。

default branch が master の人は何もしなくていいです。

ここまでやると、default branch への push や pull request があった際に自動的に verify workflow がトリガされるようになります。

0.0.2. コンパイラのオプションを設定する

ここの「C++ の設定」にしたがって、正しいコンパイラとオプションを指定してあげてください。
はじめにやった人はしなくて大丈夫です。

ここまでのサンプル

0.0.3. 権限を正しく設定する

0.0.3.0. Workflow permissions を修正する

Settubgs > Actions > General > Actions permissions > Workflow permissions
と進み、Read and write permissions を指定し、保存します。¹⁶

0.0.3.1. `GH_PAT` secret を設定する

ここの「ドキュメントが自動生成されるように設定するには」に従ってください。

一部のリンクが切れているようです。

公式ドキュメント等を参考にしてください:

ここまでの操作を全て行うと、恐らく oj-verify が正しく動くはずです。¹⁷
適当に empty commit を打ったりして動作確認をしてください。

自身のライブラリやテストが AC Libray に依存している人は、verify job 自体は失敗するはずです。これはステップ 0.1. で修正します。

0.0.4. GitHub Pages のデプロイ先を設定する

問題がなければ gh-pages というブランチが新たに生成されているはずです。
これを GitHub Pages のデプロイ元に設定します。

Settings > Pages > Build and deployment > Branch から、gh-pages のルートを選択して保存してください。¹⁸

pages build and deployment という workflow が走れば成功です。

正しく実行が終了すると、自動生成されたドキュメントへリンクがこの workflow の詳細の deploy job の欄に表示されるはずです。アクセスしてみましょう。

ここまでで oj-verify を GitHub Actions 上で利用する準備は整いました。

AC Library に依存していないかつ速度面で困っていない方はここでおしまいです。
お疲れ様でした。

ここまでのサンプル

0.1. テスト時に `AC Library` を自動で clone してもらう

色々な人のライブラリを見ていると、ルートに atcoder/ を置いているものをしばしば見かけます。
ライセンス上は全く問題ないとはいえ追従もしづらいので、できればしたくないですよね。

ということで workflows 実行時に、勝手に clone してもらうようにしてみましょう。

0.1.0. 競合を解消する

checkout が競合するので、それを解消します。

0.1.0.0. checkout するディレクトリを変更する

自分のリポジトリが ${{ github.workspace }}/main/¹⁹ 以下に clone されるようになります。

verify.yml

     - uses: actions/checkout@v3
       with:
+        path: main
         fetch-depth: 0

0.1.0.1. テストを走らせるディレクトリを追従する

ライブラリが main/ 以下にあるので、当然 oj-verify もそこで実行します。

verify.yml

     - name: Run tests
+      working-directory: main
       env:
         GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
         YUKICODER_TOKEN: ${{ secrets.YUKICODER_TOKEN }}
         GH_PAT: ${{ secrets.GH_PAT }}
       run: oj-verify all

0.1.1. AC Library を Clone する

0.1.1.0. clone step を追加する

Run tests step より前に、以下の step を追記します。

verify.yml

    - name: Clone AC-Library
      uses: actions/checkout@v3
      with:
        repository: atcoder/ac-library
        path: ac-library
        sparse-checkout: atcoder

0.1.1.1. コンパイラに AC Library の所在を明かす

Run test step へ渡す環境変数に CPLUS_INCLUDE_PATH を追加します。²⁰

verify.yml

     - name: Run tests
       env:
+        CPLUS_INCLUDE_PATH: ${{ github.workspace }}/ac-library
         ITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
         YUKICODER_TOKEN: ${{ secrets.YUKICODER_TOKEN }}
         GH_PAT: ${{ secrets.GH_PAT }}
       run: oj-verify all

これで、AC Library の自動 clone も完了です。お疲れ様でした。

ここまでのサンプル

1. 並列化

ここから先は分量が格段に増えるので、GitHub 経由で差分を示します。

1.0. job の並列化

こちらは matrix strategy というものを利用することで比較的簡単に実装できます。

とはいえ差分はそれなりに多いです。

差分：

各テストファイルの実行 job は、ファイルの辞書順インデクスを並列数で割ったあまりによって割り当てています。²¹

並列数は jobs.verify.strategy.matrix.id から適当に調整してください。
20 は Free プランにおける job の最大並列数です。

簡単な解説

oj-verify は .verify-helper/timestamps.remote.json に最終テスト時刻²²のタイムスタンプをキャッシュしています。

各 job で異なる箇所が変更されるため、正しくタイムスタンプを更新するためにはそれらを統合する必要があります。

workflow artifacts という便利な仕組みがあるので、ここではそれを用いることで各 job によるタイムスタンプの変更を保存しています。
統合は、post-verify job にて jq を用いて簡単に行っています。

ここまでのサンプル

1.1 プロセスの並列化

せっかくなので各 job 内のテストも並列化します。
これは job の並列化より少々大変そうです。²³

差分：

run-test.sh は新しく作成してください。

とりあえず並列数は $(nproc) にしています。²⁴

同じ問題に対するテストが job の並列数 (今回は 20) より多いと失敗します。
oj-verify が問題ごとにプログラムの実行ファイルをスレッド間で共有するためです。²⁵

run-test.sh L30, L40 の ::notice:: は必要に応じて変更してください。
うるさい場合は削除してもいいと思います。

簡単な解説

xargs を使います。

いかがでしたか？

タイムスタンプの書き換えを oj-verify ではなく workflow 側で取り持っています。(スレッド間で競合するので。)

また、Library Checker の問題に対するテストでは、初回に限り yosupo06/library-checker-problems を clone / pull するらしいので、若干強引ですが https://judge.yosupo.jp/problem/aplusb に対して oj d を叩くことで Git の競合を防いでいます。²⁶

2. テストケースをキャッシュする

GitHub Actions 上で cache を手軽に扱える cache action というものがあるらしいです。
せっかくなので利用しましょう。

差分：

ほぼ uses: actions/cache@v3 を書くだけですね。

ここでは一旦、verify/**/*.test.cpp にマッチするファイルたちと各 job に割り当たっているテストたちとによるハッシュをキャッシュの key に指定しています。
ここは適宜調整してください。²⁷

verify.yml

    - name: Cache judge data
      if: ${{ !cancelled() && github.ref_name == github.event.repository.default_branch }}
      id: cache-judge
      uses: actions/cache@v3
      with:
        path: |
          ~/.cache/online-judge-tools/library-checker-problems/
          main/.verify-helper/cache/
        key: verify-${{ hashFiles('main/verify/**/*.test.cpp', 'main/.verify-helper/targets.txt') }}

ここまでのサンプル

3. もう少しだけ使いやすく

on に workflow_dispatch を付与²⁸したり、concurrency を設定したりすると使いやすい気がします。

workflow 自体も大きくなってしまったので、ファイルを分割しました。

各 job に割り当てるテスト数を $(nproc) に制限したりもしています。(その代わりに job 数を増やすようにしています。)
最大並列数 (20) を超えると待機する job が発生しますが、筆者の環境ではこちらの方が合計の実行時間は若干短かったです。

その他の細かい修正点は差分をご覧ください。というかお好みでどうぞ。

差分：

リポジトリ環境変数に RUNNER_IMAGE を設定してください。
値は ubuntu-latest か ubuntu-22.04 で動くと思います。²⁹

これで終わりです。お疲れ様でした。

ここまでのサンプル

4. 改善案

沢山ある気がします。

テスト済み問題は割り当て時に弾く
実行時間をキャシュして、いい感じに分配する
#define PROBLEM を解析してキャッシュの容量を最小化する
etc.

気が向いたら個人的に修正をしたりする可能性もあります。³⁰

筆者のライブラリを置いておきます。
ここで何かやっているかもしれません：

おわりに

ここまでくるとゼロから実装した方が速いかもという気もしてきます。³¹

GitHub Actions のいいお勉強にはなりました。
ついでに Lint とか走らせてもいいかもです。

皆様におかれましては、快適なライブラリ盆栽ライフをお過ごしいただければと存じます。

参考文献

実は初投稿です、読みづらいかもしれません。赦してください。
記事の内容は表記に関するフィードバックをお待ちしております。 ↩
特にダメという文言は見当たりませんでしたが、もし見落としていたら教えてください。 ↩
verify とか verification とか呼んでいるのは大体競プロerな気がします。
業プロだとテストとか言いそうですが、筆者は実務経験が無いのでわかりません。詳しい人教えてください。 ↩
筆者の場合は internal/type_traits.hpp などがあります。その手のヤツです。 ↩
後述しますが、oj-verify は内部的に再利用します。互換性も保たれます。 ↩
私のことです。 ↩
私です。 ↩
厳密には生徒が正しいかもしれません。 ↩
やさしくしてください。 ↩
筆者は分かってません。 ↩
基本的には公式ドキュメントの記載通りで大丈夫なはずです。 ↩
先述した通り、この記事は C++ のみを動かす前提です。ほかの言語でも使いたい人は、その言語にあたるものを残しておいてください。 ↩
動くことが確認できたあとは online-judge-verify-helper の代わりにその時点での適当な commit をインストールするように書き換えると、oj-verify の更新が原因で急に壊れたりする心配がなくて安心かもです。 ↩
これを指定しないと先頭の commit だけが取られます。 ↩
現在は大抵の人が main だと思います。 ↩
権限を job 単位で指定する方法もあります。 ↩
動かなかったら教えてください。 ↩
元々そうなっている人はそのままでいいです。 ↩
${{ github.workspace }} ↩
他の言語でもこのように指定する方法があるのかはわからないです。 ↩
もっといい方法があるかもしれません。教えてください。 ↩
remote の場合は、正確には「依存するファイルの最終 commit 時刻」です ↩
これは主に oj-verify が thread-safe でないためです。(それはそう。) ↩
Linux 仮想マシンでは 4 っぽいです。でも結局コア数は 2 なので大して変わらない気がします。 ↩
マルチスレッドでの実行は想定されていないので当然です。 ↩
もっといい方法があるかもしれません。 ↩
何もなければこのままで大丈夫だと思います。 ↩
こういう使い方もできるようになります。いちいち empty commit を打ったりしなくていいので楽ですね。 ↩
後者がよさそう？ ↩
この記事に加筆する世界線も無くはないです。 ↩
速くないかもしれません。 ↩

【競プロ】ライブラリの verify を GitHub Actions で並列に走らせたい (oj-verify)

目次

はじめに

想定している読者

想定されたい筆者

この記事のゴール

前提知識

本題

0. 準備

0.0. `oj-verify` を GitHub Actions 上で動かす

0.0.0. ドキュメントに従う

0.0.1. `verify.yml` を修正する

0.0.1.0. 不必要な依存関係のインストールを省く

0.0.1.1. `oj-verify` を正しくインストールする

0.0.1.1.0. インストールコマンドを修正する

0.0.1.1.1. Python のバージョンを指定する

0.0.1.2. `actions/checkout@v3` に `fetch-depth: 0` を渡す

0.0.1.3 `on.push.branches` を正しく指定する

0.0.2. コンパイラのオプションを設定する

0.0.3. 権限を正しく設定する

0.0.3.0. Workflow permissions を修正する

0.0.3.1. `GH_PAT` secret を設定する

0.0.4. GitHub Pages のデプロイ先を設定する

0.1. テスト時に `AC Library` を自動で clone してもらう

0.1.0. 競合を解消する

0.1.0.0. checkout するディレクトリを変更する

0.1.0.1. テストを走らせるディレクトリを追従する

0.1.1. AC Library を Clone する

0.1.1.0. clone step を追加する

0.1.1.1. コンパイラに AC Library の所在を明かす

1. 並列化

1.0. job の並列化

簡単な解説

1.1 プロセスの並列化

簡単な解説

2. テストケースをキャッシュする

3. もう少しだけ使いやすく

4. 改善案

おわりに

参考文献

【競プロ】ライブラリの verify を GitHub Actions で並列に走らせたい (oj-verify)

目次

はじめに

想定している読者

想定されたい筆者

この記事のゴール

前提知識

本題

0. 準備

0.0. oj-verify を GitHub Actions 上で動かす

0.0.0. ドキュメントに従う

0.0.1. verify.yml を修正する

0.0.1.0. 不必要な依存関係のインストールを省く

0.0.1.1. oj-verify を正しくインストールする

0.0.1.1.0. インストールコマンドを修正する

0.0.1.1.1. Python のバージョンを指定する

0.0.1.2. actions/checkout@v3 に fetch-depth: 0 を渡す

0.0.1.3 on.push.branches を正しく指定する

0.0.2. コンパイラのオプションを設定する

0.0.3. 権限を正しく設定する

0.0.3.0. Workflow permissions を修正する

0.0.3.1. GH_PAT secret を設定する

0.0.4. GitHub Pages のデプロイ先を設定する

0.1. テスト時に AC Library を自動で clone してもらう

0.1.0. 競合を解消する

0.1.0.0. checkout するディレクトリを変更する

0.1.0.1. テストを走らせるディレクトリを追従する

0.1.1. AC Library を Clone する

0.1.1.0. clone step を追加する

0.1.1.1. コンパイラに AC Library の所在を明かす

1. 並列化

1.0. job の並列化

簡単な解説

1.1 プロセスの並列化

簡単な解説

2. テストケースをキャッシュする

3. もう少しだけ使いやすく

4. 改善案

おわりに

参考文献

0.0. `oj-verify` を GitHub Actions 上で動かす

0.0.1. `verify.yml` を修正する

0.0.1.1. `oj-verify` を正しくインストールする

0.0.1.2. `actions/checkout@v3` に `fetch-depth: 0` を渡す

0.0.1.3 `on.push.branches` を正しく指定する

0.0.3.1. `GH_PAT` secret を設定する

0.1. テスト時に `AC Library` を自動で clone してもらう