Valeの不変リージョン借用、初のプロトタイプ

 (verdagon.dev)
2 ポイント 投稿者 GN⁺ 2023-07-13 | 1件のコメント | WhatsAppで共有
  • Valeのリージョン借用プロトタイプが初めてコンパイルに成功し、世代参照とリージョンを組み合わせたメモリ安全アプローチを実際のプログラムで検証できるようになった
  • 開発者はC/C++に近い方法でコードを書き、必要な箇所にだけpureとリージョン借用を適用して世代チェックのオーバーヘッドを減らせる
  • 初のzero-check Valeプログラムは、ローグライクのレベル生成向けのCellular Automataサンプルで、生成されたアセンブリはunsafe_with_boundsモードとほぼ同等の水準まで近づいた
  • ベンチマークでは、safe_fastestはunsafe_with_boundsに対して観測可能なslowdownがなく、unsafe_no_boundsは両モードより1.18 ± 0.01倍速かった
  • まだC/Rustとの直接比較ではなく、LLVM最適化ノイズ、プロトタイプの完成度、inline data未対応のため、Vale専用のpre-optimizerとリージョン機能の整理が残っている

世代参照とリージョン借用の組み合わせ

  • Valeのメモリ安全アプローチは、reference counting、トレース型garbage collection、borrow checkingを使わない方向を目指している
  • 基本構造は、開発者がCやC++に近い方法でプログラムを書き、Valeのgenerational referencesがメモリ安全性を維持するというもの
  • その後、pureとregion borrowingを適用すると、世代チェックのオーバーヘッドの大半を取り除ける
  • linear styleまで加えれば、Valeコードで世代チェックをzeroまで下げられると見ている
  • リージョン借用は完全にopt-inなので、まずは気軽に書き、最適化が必要な部分にだけ後から追加できる
  • 同じプログラム内でも、一部はJavaのように柔軟に、一部はRustのように高速に、またはその中間を選べる構造を志向している

プロトタイプ作成に必要だった作業

  • ここ数年、コンパイラ基盤を構築しながら、リージョンベースの借用システムとgenerational referencesを同時にサポートできるよう作業してきた
  • 借用システム自体が複雑なうえ、既存のテンプレートより強力なfull genericsが必要だった
  • リージョンと世代参照が自然に連携して動作するには、新しいコンパイラ段階も必要だった
    • 内部的には、リージョンは「pure height」の整数に縮約される
    • リージョンgeneric parameterは負数、基本リージョンは0、各pure blockは増加する正数で表現される
  • 数か月前にリージョンプロトタイプが完成し、まだ粗い部分はあるものの、初めて何かを正常にコンパイルできた
  • その結果、初のzero-check Valeプログラムが作られた
    • --print_mem_overhead trueコンパイラフラグで、プログラム内の世代チェック数を数えられる

初のzero-checkプログラムとアセンブリ比較

  • 初のプログラムは、ローグライクゲームのレベルを生成するCellular Automataサンプルだった
  • コンパイラコードの小さなミスでも、生成アセンブリに余分な命令が入り、最終プログラムに人為的なオーバーヘッドを生む可能性がある
  • 問題を追跡するため、生成アセンブリをValeのunsafeモードと継続的に比較した
    • unsafe_no_bounds: Cに似て、すべてのメモリ安全保護を無効化し、generational referencesの代わりにraw pointerを使う
    • unsafe_with_bounds: Rustのように、配列アクセスにbounds checkingを追加する
  • 数か月にわたって差分を追跡した結果、生成アセンブリはunsafe_with_boundsモードとほぼ同一になった
  • 予想された唯一の違いは、各allocationの先頭にpseudo-random generation numberを入れる点で、実際の世代チェックでは読み取られなかった
    • 内部的には高速性を保つため、単調増加レジスタを使っている
    • isolatesまたはunique referencesが追加されれば、この違いを取り除ける

ベンチマーク結果と測定条件

  • ベンチマークの要約は以下のとおり
Summary
  './build_unsafe_no_bounds/main' ran
    1.18 ± 0.01 times faster than './build_unsafe_with_bounds/main'
    1.18 ± 0.01 times faster than './build_safe_fastest/main'
  • Valeのnormal modeであるsafe_fastestは、bounds checkingのみのモードと比べてslowdownを示さない
  • この測定では、このアプローチに観測可能なオーバーヘッドはない
  • 直接試すには、regions branchをビルドし、benchmarking scriptsを確認し、discord serverで質問できる
  • 測定条件には明確な制約がある
    • CやRustのような言語と直接比較したベンチマークではない
    • そうしたコンパイラには長年にわたる別個の最適化があり、実験変数を曖昧にする可能性がある
    • メモリ安全アプローチの違いを分離するため、unsafe_no_bounds、unsafe_with_boundsと比較した
    • 測定環境は、Ubuntu 22.04を実行するRazer Blade 15" 2018、512GB SSDだった
    • 測定ツールはhyperfineで、cset shield内で実行された

大きなプログラムで見えた最適化ノイズ

  • より大きなプログラムでは、optimizer noiseがかなり観察された
    • benchmark noiseとは異なり、測定設定は± 0.01のように非常に一貫した実行時間を示した
    • ある領域の小さな変更が、測定値を一方向に揺らすことがあった
  • generation numberのサイズを変えたとき、一貫してnegative overheadである1.13 ± 0.01が出た事例もあった
    • プログラムにgeneration numberは多くなかったため、奇妙な結果だった
    • register allocationの変化が、意味上の違いから来る性能差を上回った可能性がある
  • より大きなプログラムである小さなローグライクゲームでは、optimizerがif文内部の同一の2つのbranchをマージできず、他の明白な最適化も見逃した
  • 読み取られないintegerの存在がどのような影響を与えるかは定かではなく、LLVMのバグである可能性もある
  • この結果は、RustのMIRに似たVale専用のpre-optimizerが必要になり得ることを示唆している
    • LLVMはCをより念頭に置いて設計されている
    • LLVMがgenerational referencesを、意図的に解放済みメモリへアクセスするパターンとして捉えれば、undefined behaviorとして扱う可能性があると見ている

適用可能性と次の作業

  • 世代参照とリージョンは、組み合わせることで非常に高速なメモリ安全アプローチを作れる
  • このアプローチが適している可能性のあるソフトウェア領域には、次の条件がある
    • tracing garbage collectionより予測可能なlatencyを求める
    • reference countingより優れた性能とcache friendlinessを求める
    • borrow checkingより簡単にprototypeとiterationを行いたい
  • ValeがCやC++と正面から比較される前に、残っている作業がある
    • LLVM optimizerがgenerationとimmutabilityを推論する際に問題があるため、Vale専用pre-optimizerが必要
    • Valeは現在、すべてのstructをheapに置く暫定策の代わりに、inline dataをサポートする必要がある
    • 上記ベンチマークはstructを使っていなかったため、inline data未対応はこの結果には影響しない
    • リージョン機能はまだprototype段階なので、粗い部分を整え、技術的負債を減らしたうえでmain branchにマージする必要がある
  • マージ後は、標準ライブラリがリージョンを使うようにして、ユーザーのmain program codeがリージョンを直接使わなくてもメリットを得られるようにする計画
  • 現在の測定は、zero-checkプログラムが可能であり、期待した速度に到達できることを示している

関連記事

1件のコメント

 
GN⁺ 2023-07-13
Hacker Newsのコメント

  • Valeをダウンロードして試してみたが、valecコンパイラを最初に引数なしで実行すると、いきなり"(panic)"と表示されるのは印象が悪かった
    panicはかなり強い表現で、通常のエラー処理の場面では避けるべきだと思う。プログラムがパニックを起こしたというのは、制御不能な状況のように感じられて後味がよくない
    次にコマンドライン引数のヘルプを見ようとしたが、現状では実質的になく、hello.vlにWebサイトのHello Worldの例を保存してvalec hello.vlを実行するとUnknown subcommandが出た
    そこでvalec build hello.vlを実行したところ、Unrecognized input: hello.vlの後に再び(panic)が出て、valec helpも役に立たず、結局あきらめた。これをどう使えばいいのかわからない

    • 申し訳ない。ヘルプファイルがもう正しく表示されなくなっているようだ。ダウンロードに含まれているvalec-help-build.txtを直接catしてみれば、探している内容が説明されているはず
      コンパイラは今かなり粗削りな状態だ。8月から5月まではリージョン(region)のプロトタイピングに100%集中していて、今遭遇しているのはその過程で積み上がった技術的負債だ。ヘルプシステムの統合テストがないこともその一つ
      この1〜2か月、その負債を返済してきたが、まだ0.2リリース時の水準には戻れていない。さらに助けが必要なら知らせてほしいし、Discordサーバーに来れば助けられる人がたくさんいる
    • Valeはまだ実質的に研究開発段階なのではないかと思う。特定ブランチの特定コミットだけが動くと期待するくらいで、誰でもコンパイラを入手して何か作れる段階だとは言いがたい
      ただREADMEはこの点を明確に示しておらず、“Try Vale”となっているので曖昧だ。それでも現状は研究開発/概念実証に近く見える
    • これはバグというよりユーザーインターフェースの問題に近い。実験的なものなら、実際のバグについてもある程度は大目に見てもいいと思う
      ユーザーインターフェースやバグという観点で見ても、40年物のC++を35年物のgdbでデバッグする体験は、どんな実験言語にも十分張り合える。たとえばfuncname()::staticvarnameの表示は奇妙なインターフェースで、半分くらいは失敗する。C++のビルドシステムに至っては言うまでもない
      実験的な技術なら、概念を批判することはできても、粗いユーザーインターフェースはある程度受け入れられると思う
    • GitHubのREADMEにコンパイラの使い方が書かれている
      https://github.com/ValeLang/Vale#building-a-vale-program
    • まだアルファ段階のソフトウェアなら、おおむね予想どおりの姿だ

  • トレーシングGCよりレイテンシが予測しやすく、参照カウントより性能とキャッシュ親和性が高く、borrow checkerよりプロトタイピングや反復作業がしやすいというなら、好奇心を超えて関心が湧いてくる
    RSSフィードも購読し始めた: https://verdagon.dev/rss.xml

    • ついにAOTコンパイル言語で、「たまにメモリバグが出ることにしよう」に行き着かない新しいアイデアが出てきた

  • Valeにはスポンサーがもっと必要だ
    https://github.com/sponsors/ValeLang
    この記事がトップページに載っている間に、プロジェクトが月3,000ドルの目標を達成できるよう手助けしたい
    Evanがこれを本業として取り組めるよう支援したい。自分もスポンサーだ。高速で安全、それでいてプロトタイピングが楽しい言語には支援する価値がある

    • GitHub SponsorsとPatreonでの支援は、収益配分がどう違うのか気になる

  • 「Vale専用の事前最適化器、RustのCraneliftに似たもの」というのは、おそらくMIR、つまり中間レベル中間表現のことを指しているのだと思う。関連して良いブログ記事がある: https://blog.rust-lang.org/2016/04/19/MIR.html
    Craneliftは主にJITに焦点を当てたコンパイラバックエンドだが、理論上はLLVMの代わりにもなりうる。代替バックエンドの作業も進んでいるが制約がある: https://github.com/bjorn3/rustc_codegen_cranelift

    • その通りだと思う。CraneliftはWebAssembly向けのRust最適化器と見なせる

  • 大半のコードではメモリ管理を気にせずに済みつつ、ホットなコードパスだけをゼロコスト抽象化で最適化できる選択肢を与えるアプローチは、両方の長所を兼ね備えているように聞こえる
    利便性のために安全性ではなく性能だけを引き換えにする条件なら、なおさらそう思う

    • C++しか使わないが、メモリ管理はまったく心配していない
      共有所有権は悪い概念だから、スマートポインタも使わない
      メモリ管理の問題はたいてい些細なものだと思う

  • 世代参照(generational references)の文脈で 安全だ とは何を意味するのか、ずっと気になっている。
    正しく理解しているなら、use-after-free と double-free を防ぐという意味なのだろうか？ そうだとすると、予想した世代と実際の世代が一致しないとき、メモリアクセスでプログラムが依然として失敗する可能性がある。
    その点では、参照カウント、トレーシングGC、借用検査より安全性が低く見える。

    • double-free は Vale の単一所有権、つまり C++ の意味での単一所有権によって防がれ、世代参照は use-after-free を安全に検出できるようにしている。
      参照を通じて解放済みメモリにアクセスしようとすると、予測可能かつ安全にセグメンテーションフォルトやアサーション失敗になるはずだ。今後は仮想アドレス空間の再マッピングという改善が入れば、セグメンテーションフォルトもなくせるのではと期待している。
    • ダングリングポインタで任意のメモリを読み書きできてしまう代わりに、セグメンテーションフォルトになるという意味で安全だということ。
      ただし 世代インデックス であれば、実際にアクセスを試みる前にランタイムでアクセスが有効かどうか確認できるはずでもある。Vale で可能なのかは分からない。
    • GC、借用検査、参照カウントよりは安全性が低い。それでも malloc/free よりは安全で、ほかの利点もある。
    • 私も気になっている。これがどうやって use-after-free と double-free を防ぐのか分からない。
      check 関数は割り当ての世代番号を必要とするので、割り当てにアクセスする。つまり、参照がその割り当てにアクセスできるか確認するために、まずその割り当てにアクセスしなければならないということだ。
      もちろん、その割り当てがすでに解放されていれば、その割り当てと世代番号にアクセスすること自体が未定義動作なので、機能しない。
      あまりにも明白に見えるので、自分が何か大きな点を見落としているのか、それともここで言う「メモリ安全性」がまったく別の意味なのか分からない。
    • 本人が限定的に定義した「安全」より安全性が低いかと言われれば、たぶんそうかもしれない。

  • Vale は V のような言語ではない。V は https://mawfig.github.io/2022/06/18/v-lang-in-2022.html で非常に批判的なレビューを受けていたが、名前が似ているので Vale のことだと勘違いして覚えていた。
    同じ勘違いをした人がいるかもしれないので書いておく。

    • その「非常に批判的なレビュー」は、1年前に修正された小さなバグの一覧にすぎない。
      記事の内容はもはや関連性がないのに、そのまま残っているし、そのブログの唯一の記事でもある。
    • その「批判的レビュー」は、反対派やトロールが繰り返し使う古いスパムに近いように見える。言語のアルファ版に対する「レビュー」、実質的には攻撃的な文章で、それ以外の価値はなさそうだ。
      今は 2023 年で、V もベータ版 (0.4) だ。しかもその記事の作者は使い捨ての GitHub アカウントを使ってレビュー/攻撃を投稿し、物議を醸したあと姿を消した。
      そのブログにある唯一の記事も V 攻撃の記事だけで、ほかのレビューはない。実質的な内容があった部分はすでに修正されている[1]。
      mawfig.github を検索すれば、HN で繰り返し貼られ、たいてい中傷目的で使われていたことも分かる。
      [1]: https://github.com/vlang/v/issues/14803
      [1]: https://github.com/vlang/v/issues/14787
      [1]: https://github.com/vlang/v/issues/14786

  • Evan のマイルストーン達成おめでとう。プログラミング言語設計やコンパイラの経験はないが、Vale の記事を読むのを楽しんでいる。

    • 私も似た感じだが、名前は別のほうがよかったと思う。
      今や Evan の Vale と Adobe Software Technology Lab の Val があって、関連資料を検索するのがかなり難しくなりそうだ。
      https://www.val-lang.dev
    • 私も、たいていの場合は記事を理解するための背景知識がないが、それでも興味深い。
    • 私も記事は素晴らしいと思うし、Vale の未来に期待している。

  • 「Vale は高速だ。Vale は LLVM で AOT コンパイルされ、静的型付けを使い、速度と柔軟性を備えたメモリ安全性のために新しい 世代参照 技法を使っており、まもなくリージョン借用検査を導入してさらに高速になるだろう」
    https://vale.dev/

  • 5年間続いている2人の議論を立ち聞きしている気分だ。
    ここで何が起きているのか説明してくれる人はいる？ 記事が難解すぎる。