シェルスクリプトを最大34倍に高速化、並列化の難問を解決した技術を解説：実行時に並列化するJITコンパイラを採用

マサチューセッツ工科大学は、同大学の研究者などが参加するオープンソースプロジェクト「PaSh」の成果を発表した。PaShはUNIXのシェルスクリプトを自動的に並列化し、高速化するシステムだ。

[＠IT]

　マサチューセッツ工科大学（MIT）は2022年6月7日（米国時間）、同大学の研究者などが参加するオープンソースプロジェクト「PaSh」の成果を紹介した。PaShはUNIXのシェルスクリプトを自動的に並列化し、高速化するシステムだ。2022年5月にリリースされたPaSh v0.8が最新版となる。

　システムのシェルインタープリタに変更を加えることなく利用できることがPaShの特徴だ。既存のシェルに追加し、PaShの使用をシェルスクリプトに指示するだけで、シェルスクリプトを並列化することが可能だ。

　UNIXのシェルは約50年前に開発が始まり、現在も広く使われているプログラミング環境だ。しかし、シェルスクリプトの正確で自動的な並列化は、研究者が長年取り組んできた難題として残っている。

　最近のシェルスクリプト並列化システムは、スクリプトを前もって並列化することで、ほぼ自動的に高速化する。だが、こうした静的な並列化は、シェルスクリプトに広く見られる動的な動作（変数の展開、コマンドの置換など）によって妨げられ、多くの場合、シェルやファイルシステムの現在の状態に関する推論が必要になる。

高速化と正確性に優れるPaSh

　そこでPaShプロジェクトは、シェルスクリプトの実行時に評価と並列化を進めるジャストインタイム（JIT）シェルスクリプトコンパイラである「PaSh-JIT」を開発した。

　PaShチームは古典的なプログラムから最新のプログラムまで、数百のシェルスクリプトでPaShをテストしたが、これらは1つも壊れなかった。PaShはシェルスクリプトの実行速度を、並列化されていない場合と比べて平均で6倍、最大で34倍近く高速化できた。

　また、他の手法では並列化できなかったシェルスクリプトの実行速度向上にも成功した。

　MITコンピュータサイエンス・人工知能研究所（CSAIL）の研究員で、PaSh-JITに関する論文のシニアオーサーを務めたニコス・バシラキス氏は、次のように述べている。「われわれのシステムは、こうした完全で正確な変換を初めて実現した。シェルスクリプトはデータサイエンティストや生物学者、エンジニア、経済学者など、非常に多くの人が幅広い分野で使っている。彼らはPaShにより、誤った結果を得るのを恐れることなく、シェルスクリプトを自動的に高速化できる」

　PaShプロジェクトはLinux Foundationでホストされており、MITやライス大学、スティーブンス技術研究所、ペンシルベニア大学などのサポートを受けている。

開発したJITコンパイラの3つの特徴

　JIT並列化ではシステムの状態に関する実行時情報を収集するものの、元のスクリプトの動作を変更してはならず、オーバーヘッドを最小に保つ必要がある。

PaSh-JITの仕組み　PaSh-JITはシェルスクリプトにJITエンジンの呼び出しを挿入する。JITエンジンは、実行時にプログラムの断片をコンパイルサーバに渡す（出典：Practically Correct, Just-in-Time Shell Script Parallelization）

　PaSh-JITは次のような3つの特徴を持っているという。「動的なインターポジションフレームワーク」「ステートフルな並列化コンパイルサーバ」「可換性を考慮した最適化」だ。

・動的なインターポジションフレームワーク

　JIT解析・最適化サブシステムが、スクリプトの実行中に安全で効果的な並列化を実現し、シェルスクリプトの動的な動作の課題に対応する。

　PaSh-JITは前処理として、与えられた入力スクリプトのうち、最適化できる可能性のあるプログラム領域に、並列化オプティマイザ（JITエンジン）の呼び出しを挿入する。その後、ユーザーのシェルインタープリタを呼び出し、変換済みのスクリプトを実行する。

　JITエンジンは実行時にオンザフライで呼び出され、プログラムの各断片が実行される直前に、並列化コンパイラを呼び出す。その際、シェルとファイルシステムの状態は既に解決済みだ。

・ステートフルな並列化コンパイルサーバ

　PaSh-JITはスクリプトの断片をコンパイルするために、実行時に、持続的に稼働する並列化サーバに問い合わせを行う。このモデルは、JITを呼び出すたびに起動コストがかかることを避けるため、実行時の効率を高め、（1）独立した領域の並列実行、（2）コンパイルと実行のパイプライン化、を目的とした追加の実行時最適化を実現する。また、シェル実行の一時停止と再開を透過的に行うことを可能にする。

・可換性を考慮した最適化

　入力に対して可換なコマンドを対象とした追加のコンパイル最適化を行う。さらに、そうしたコマンドを含むスクリプトの実行時性能を向上させる、並列化変換と実行時プリミティブも導入している。

　また、PaShのJIT並列化では、高速化されたプログラムが正確な結果を返すことが保証されている。PaShは、並列化できないプログラムコンポーネント（まだ実行されていないコンポーネントに依存している可能性がある）に到達すると、元のシェル（シェルバージョン）を実行し、エラーを回避する。

　2022年7月に開催される「OSDI '22」（16th USENIX Symposium on Operating Systems Design and Implementation）でPaSh-JIT」に関する論文のプレゼンテーションを予定している。