PowerShellスクリプトが遅い原因の知識マップ(知識グラフ)
PowerShellの配列は固定長のため$array += $itemは毎回全要素をコピーし、文字列の+=も不変な文字列を毎回作り直すため、どちらも件数の2乗に比例して遅くなる。この2乗の劣化はList[T]・foreach文の出力集約・StringBuilderや-joinで避けられ、二重ループでの突合はハッシュテーブル化で線形探索の比較回数を大きく減らせる、費用対効果の最も高い改善である。Get-Contentの読み方の使い分けや遅延列挙、Get-ChildItemの-Filterによる絞り込み、Format系コマンドレットを途中に挟まないことも効果があり、これらの効果はMeasure-Commandで検証する。並列化はアルゴリズムそのものを直してから最後に検討すべき手段で、計算量がO(n^2)のまま並列化しても効果は限られる。
配列の+=によるコピー
PowerShellの配列が固定長であるために、要素追加のたびに新しい配列を作って全要素をコピーする書き方。
配列への追加
ハッシュテーブルによる突合
二重ループの中でWhere-Objectなどによる全件走査を行う突合を、索引(ハッシュテーブル)を1度だけ作りキーで引く形に置き換える高速化手法。
件数の2乗に比例する速度劣化
配列や文字列の+=など、毎回全体をコピーする操作を繰り返すことで、処理時間が件数の2乗に比例して悪化する現象。
O(n^2)の劣化
文字列の+=による再生成
文字列が不変(immutable)であるために、連結のたびに新しい文字列インスタンスを生成する書き方。
List[T](System.Collections.Generic.List)
要素の追加が定数時間で行える.NETの可変長コレクション型で、配列の+=の代わりに.Add()で要素を足す。
foreach文
メモリ上のコレクションを1件ずつ処理する制御構文で、1件あたりのオーバーヘッドがパイプラインより小さく、ループ全体の出力をそのまま変数に集約できる。
StringBuilder / -join
不変な文字列の+=連結を避け、可変バッファでの組み立て(StringBuilder)や配列の一括結合(-join)によって文字列連結を高速化する手段。
二重ループの線形探索による突合
内側のループで毎回Where-Objectなどによる全件走査を行う突合方法で、比較回数が受注件数×マスター件数のように積になる。
Where-Objectによる全件走査
遅延列挙
巨大な入力を全件メモリに読み込まず1件ずつ列挙する仕組みで、[System.IO.File]::ReadLinesなどが該当し、foreach文と組み合わせるとメモリを使わずに処理できる。
Get-Content
ファイルを読み込むコマンドレットで、既定では改行区切りで1行ずつオブジェクトとして返し、-Rawで一括読み込み、-ReadCountでまとめ読みができる。
ファイルの行読み込み
Measure-Command
スクリプトブロックやコマンドの実行時間を計測してTimeSpanを返すコマンドレットで、測定対象の出力自体は破棄され結果に含まれない。
実行時間の計測
Get-ChildItemの-Filter
Get-ChildItemのプロバイダーがオブジェクト取得時に適用する絞り込みパラメーターで、取得後にWhere-Objectで捨てるより効率的とされる。
プロバイダー側の絞り込み
Format-Table/Format-List
PowerShellの結果を画面表示用に整形するコマンドレットで、通すと結果が元のオブジェクトではなく表示用のフォーマット情報に変わる。
Format系コマンドレット
後続パイプラインの破壊
Format系コマンドレットを出力の途中に挟むことで、後続のコマンドが受け取るオブジェクトが表示用のフォーマットオブジェクトに変わってしまい処理が壊れること。
Format系による後続処理の破壊
Write-Progress
コマンドの進行状況をホストの進捗表示として出すコマンドレットで、リダイレクト可能なデータストリームではなく、ログには残せない。
進捗表示
進捗更新の描画コスト
ループのたびにWrite-Progressで進捗を更新する描画コストで、更新頻度が高いと処理時間そのものより重くなることがある。
Write-Progressの描画負荷
ForEach-Object -Parallel
PowerShell 7.0で追加された、入力の各要素を別のランスペースで並列実行するパラメーターセット。
並列パラメーターセット
取得後にWhere-Objectで捨てる絞り込み
Get-ChildItemなどでいったん全件取得してからWhere-Objectで不要な項目を捨てる非効率な絞り込み方法。
1行ごとのオブジェクト生成コスト
Get-Contentが既定で1行ずつオブジェクトを生成することによるコストで、巨大ファイルを読み込む際に支配的になる。
Get-Contentの行オブジェクト化コスト
n件を+=で追加すると発生する要素コピーの総数はn(n-1)/2になり、件数の2乗に比例して遅くなる
文字列は不変なので$s += "line"は毎回新しい文字列を作り、配列の+=と同じ理由で件数の2乗に比例して遅くなる
List[T]の.Add()は定数時間の追加であるため、件数が増えても2乗の劣化を避けられる
foreach文の出力をそのまま変数へ集約する書き方(PowerShellらしい書き方)も配列の+=を避けられる
StringBuilderの可変バッファでの組み立てや-joinによる一括結合は、文字列版の2乗の劣化を避けられる
索引を1度だけ作りキーで引く形にすることで、二重ループの全件比較を件数にほぼ比例する回数まで減らせる
巨大なファイルをメモリに載せずforeach文で処理するには、ReadLinesのような遅延列挙のIEnumerableを渡す必要がある。丸かっこ内でコマンドの実行結果を評価すると全件がメモリに載る
読み込み方式(既定・-Raw・-ReadCount)ごとの速度差はMeasure-Commandで確認できる
-Filterの有無による速度差はMeasure-Commandで確認できる
突合の高速化効果はMeasure-Commandで二重ループ版と比較して確認できる
配列の+=とList[T]の速度差はMeasure-Commandで比較できる。ただし出力は破棄され表示コストは含まれない点に注意する
Format系コマンドレットが生成するフォーマットオブジェクトをパイプラインの途中に挟むと、後続の処理が壊れる
ループのたびに進捗を更新すると、描画コストが処理時間そのものを上回ることがある
突合のハッシュ化などアルゴリズムの改善を先に行ってから、並列化を検討すべきである
配列操作の改善などアルゴリズムの修正を先に行ってから、並列化を検討すべきである
計算量がO(n^2)のまま並列化しても、コア数の分しか速くならず効果は限定的である
-Filterで取得時に絞り込むことで、全件取得してからWhere-Objectで捨てる非効率な方法を避けられる
Get-Contentは既定で1行ずつオブジェクトを生成するため、巨大ファイルではこのコストが支配的になる
[System.IO.File]::ReadLinesのような逐次列挙は、1行ごとのオブジェクト生成コストを回避できる
Format系コマンドレットを挟むことによる処理コストもMeasure-Commandで確認できる
進捗更新の描画コストもMeasure-Commandで比較できる