SML#のプログラムにMassiveThreadsのオプションを付けるとパフォーマンスが低下する

SML# には最初からユーザレベルの細粒度スレッドライブラリ MassiveThreads のラッパーが提供されています。
Myth ストラクチャを使ってプログラムを書き、環境変数 MYTH_NUM_WORKERS で仕様コア数を指定するようです。
> 11.2 MassiveThreadsを用いた細粒度スレッドプログラミング‣ Chapter 11 SML#の拡張機能:マルチスレッドプログラミング ‣ Part II チュートリアル ‣ プログラミング言語SML#解説

この環境変数を通常のシングルスレッド向けの AObenchSML で設定みたところ、パフォーマンスが 60% ほど低下しました。

$ time ./aobench-smlsharp aobench-smlsharp.ppm

real 0m11.233s
user 0m9.969s
sys 0m1.417s

$ time MYTH_NUM_WORKERS=0 ./aobench-smlsharp aobench-smlsharp.ppm

real 0m18.210s
user 1m10.984s
sys 0m2.163s

4コアの環境で実行しています。user(CPU時間)ではちょうど 18.210s * 4 ≒ 1m10.984s ですね。
ランタイムの何かが無駄に同期しているんでしょうか? 謎です。

並列ML: MaPLe で AObench を高速化

POPL2020 で新しい並列ML(MaPLe)(略称: MPL)の提案がありました。
正確に言うと言語の提案じゃ無くて、「並列プログラムの性質を表す(良い)性質 Disentanglement Property を提案したので、その良さ(= 並列プログラムの実行効率)を示すための処理系を作って公開しました」というモノ。


(珍しいことに)あっさり手元で動いたので AObench-SML に追加してベンチマークを取ってみました。
ただしこの処理系の持つ並列プリミティブは正しく使わないとクラッシュするので実用するものではありません*1


AObench はピクセル毎に並列化しやすく、ループ毎に配列の互いに異なる領域に書き込むアルゴリズムなのでMPL(というかDisentanglement)の役立つ形の処理にかなりよくマッチしています(多分)。

ベンチマーク結果

実際のベンチマーク結果を以下に示します。

処理系 real user sys
gcc 0m0.732s 0m0.718s 0m0.012s
mlton 0m1.589s 0m1.579s 0m0.008s
mpl 0m0.398s 0m1.523s 0m0.016s

MPLについてはユーザがプロセス数を指定する必要があるため、以下のようにコア数と同じ procs 4 を指定しています。
(後ろの 4 は後述する並列粒度指定。実験的に求めた値。)

./aobench-mpl @mpl procs 4 set-affinity -- aobench-mpl.ppm 4

この処理系は MLton を拡張して実装されているので並列化しない場合は素の MLton と同じパフォーマンスが出ます。
今回はちょうど(プロセス数と同じ)4倍速になってますね。

変更箇所

主な変更箇所を解説します。

まず以下の部分。
ライン毎のループを ForkJoin.parfor に換えています。粒度とループ範囲を与えるだけで並列化完了です。
この粒度は上で示したコマンドライン引数から渡される 4 で、この範囲(つまり f n .. f (n+3) を実行する範囲)では各スレッド内でシーケンシャル実行されます。
ここで渡す関数が並列実行されます。

<       for {begin=0, limit=h, step=succ} (fn y=>
---
>       ForkJoin.parfor grain (0, h) (fn y =>
>         let val drand48 = mk_rand (48271 + y) in

for から parfor への変更だけだと乱数生成の部分がスレッド間で共有されてしまい速度が出ませんでした*2
そのため以下のようにクロージャを作る関数を定義し直して使用するようにしました。

<   local
<     val rand = Random.rand (48271, Option.getOpt (Int.maxInt, 1073741823))
<   in
<   fun drand48 () = Random.randReal rand
<   end
---
>   fun mk_rand seed =
>     let
>       val rand = Random.rand (seed, Option.getOpt (Int.maxInt, 1073741823))
>     in
>       fn () => Random.randReal rand
>     end

まとめ

  • 簡単に速くなったのでそこそこ感動しました
    • 動くはずのモノが動くとやる気が出る
  • スレッド間で共有している ref (今回の場合 rand の中身) があっても遅くなるだけで動くのが良かった

*1:今回の提案にはその自動検査は含まれていない

*2:MLtonと比べて25%程度の高速化

nfq_bind_pf の使い方

Linux にはネットワークフィルタリング機能と、そのラッパーライブラリである libnetfilter-queue があります。
そのライブラリの提供するAPIである nfq_bind_pfnfq_unbind_pfuint16_t pf を要求します。
これに何を渡せばいいのかよく判らなかったという話。

  • サンプルコード では AF_INET を使うように書いてある。
  • nfq_bind_pf のコメントでは PF_INET(など) を使えと書いてある。
  • どっちを使っても動いてる(ように見える)

どっちを使えばいいのか?というか AF_INETPF_INET って何だっけ?


PF_INETとAF_INETの微妙な違い によると:

  • PF_ はプロトコルファミリー、AF_ はアドレスファミリーを表す
  • BSDソケットの設計ではプロトコルファミリーとアドレスファミリーは独立している
  • 現状のインターネットではIPv4/v6とそれらの唯一のアドレッシング方法しか無い(から独立に指定出来るうれしみは無い)

(適当な)結論

  • PFプロトコルファミリーを表す
  • AF はアドレスファミリーを表す
  • 実装は同じ値なのでどっちでも動く(PF_INETAF_INET2)
  • ドキュメントには bind a nfqueue handler to a given protocol family と書いてあるので PF_* を指定するべき
  • サンプルコード書いた人が怪しい

リンク

GitHub Actions で Github Pages を更新する方法

github actions でビルドした内容で github pages で公開しているサイトを更新する方法をメモ。

環境+要件

  • github 上のパブリックリポジトリである
  • gh-pages ブランチを github pages として公開したい
  • gh-pages ブランチの中身を一部だけ差し替えたい(各リリースの内容をまとめて公開したい)
  • master への push の時のみ公開するページを更新したい

案1: github-push-action

github token を使って簡単に git push してくれる action。簡単に使えるし単機能でよいが、以下の理由で今回は使えなかった。

So while you can push to the `gh-pages` branch using the `GITHUB_TOKEN`, it won't spawn a GitHub Pages build.
You'll need to create a personal access token and supply it to your GitHub Action as a secret.

https://github.community/t5/GitHub-Actions/Github-action-not-triggering-gh-pages-upon-push/m-p/26869/highlight/true#M301

↑のスレッドの内容(でかつ私の環境で再現した事項)をまとめると、
GitHub Actions から `GITHUB_TOKEN` で push するとパブリックリポジトリGitHub Pages のビルドが動かない

案2: actions-gh-pages

案1 の引用先で薦められてた github pages 専用 action。
なにやらいろいろ出来るようだけどブランチ全体のコンテンツを上書きしてしまうので使えなかった。

採用案

自力で personal access token を使って push すればよい。

..
jobs:
  ..
  publish:
    name: publish to github pages
    runs-on: ubuntu-18.04
    needs: build     # ビルドの後に実行
    # master への push の時のみ動作
    if: github.event_name == 'push' && github.ref == 'refs/heads/master'
    steps:
      - uses: actions/checkout@v1
        with:
          ref: gh-pages
          fetch-depth: 1
      - uses: actions/download-artifact@v1
        with:
          name: artifact
      - name: Commit artifact
        run: |
          git config user.email "admin@example.com"
          git config user.name "Github Action Bot"
          git add .    # artifact を追加(実際はコンテンツの一部を上書き)
          if ! (git diff --quiet && git diff --staged --quiet); then
            git commit -m "Add: changes ($GITHUB_SHA)"    # ハッシュをメモってコミット
          fi
      - name: Push to gh-pages branch
        env:
          PERSONAL_TOKEN: ${{ secrets.PERSONAL_TOKEN }}    # personal access token を使う
          PUBLISH_BRANCH: gh-pages
        run: |
          git push https://<githubユーザ>:${PERSONAL_TOKEN}@github.com/<githubユーザ>/<リポジトリ>

Github Actions を勉強した

今後覚えざるを得なさそうだったのでリポジトリを作ったついでに Github Actions を勉強して使ってみました。
勘や常識(を出来るだけ)無しに公式ドキュメントに書いてある内容のみで理解することを目標にしましたが、ちょっとつらかった。

とりあえずビルドは動かせるようになったしあまり深入りしないようにしよう。。。

coqdocを使った

coqdocを初めて使ってみました。

はじめは company-coq のスタイルに合わせて見出しとか書いてましたが、なんとなく気が向いたので公式(documenting-coq-files-with-coqdoc )の方を確認してみたのでした。

目的はcoqスクリプトの(主にコメントの)整形スタイルを妥当なモノに統一することなので出力はどうでもいいんですが、…デフォルトはあまりかっこよくないですね :p

今のところ単一ファイルなのでコマンドは:

$ coqdoc --utf8 hoge.v

これだけ。

静的コード解析の会#9

(会場と日程を変更しました) #静的コード解析の会 第9回 - connpass に行ってきました。今回も何らかの発表は出来ず。
どこかで宣伝したらしく、前回から人数が大幅に増えて14~5人くらいの参加者でした。

参加者の傾向としては:

  • なぜかIsabelle使いが多い。
  • モデル検査勢が(人数的に)優勢。
  • 他は各々の好みでいろいろ。

といった感じでした。