プログラム側の性能チューニングの中でも汎用的であり、どの言語・分野でも費用対効果が高そうな原則およびサンプルを紹介しています。
結論
以下の3つの原則を意識して、プログラムの性能チューニングおよび開発を行いましょう。
-
原則1. 計算量を小さくする
- 多重ループを改善する
- アルゴリズムを改善する
-
原則2. 高コスト処理をバッチ化する
- SQL, REST API, 外部コマンドをまとめる
- システムコール (ex. read, write)をまとめる
-
原則3. 高コストなものを再利用する
- TCP、HTTP、DB等のコネクションを再利用する
- 外部サーバからの問い合わせ結果を再利用する
- 確保したメモリ、オブジェクト、スレッド等を再利用する
なおシステムのアーキテクチャ、ハードウェア構成などのチューニング・最適化はこの記事の対象外です。(原則2,3の考え方は応用できますが、そこまでは踏み込みません)
背景
色々なシステム開発に携わっていると、設計や開発の中で性能を意識する人というのは意外と少ないように感じます。開発対象の目的や性能要件を考慮すれば明らかに後々の性能検証等で大きな問題となりそうな箇所であっても、何事もなく開発が進められたりします。
もちろん「中途半端な最適化は悪だから、後で必要な時にチューニングするべき」という格言は正しいです。しかしこの格言は設計やコーディングをしている時点である程度の性能ボトルネックについての仮説や予測を立てることも暗黙の内に期待されているのではないでしょうか?だからこそ「チューニングが必要そうなところはメソッド化やモジュール化して、後でチューニングしやすいようにしよう」という文言も添えられていることが多いのと考えています。
この事実を理解せずに性能ボトルネックについての仮説や予測を立てずにコーディングやユニットテスト等の作業を進めてしまい、いざシステムテストを実施すると致命的な性能ボトルネックが発生して右往左往してしまうのを目の当たりすることは珍しくありません。「後で必要な時に性能チューニングすれば良い」と言うのは結構ですが、そのために必要な指針(仮説や予測の立て方)、知識、スキル等を持たなければ机上の空論でしかありません。問題対応をただ単純に先延ばししているのと何ら変わりはありません。
NOTE:
Intel DPDK(ネットワークのパケットを超高速に処理するための開発キット)みたいものを開発するのであれば、当然より高度な最適化のための知識やスキルを総動員する必要があります (ex. 並列化、CPU等のAffinity、キャッシュヒット、キャッシュライン、CPUアーキテクチャ、コンパイラのオプション、ハードウェアオフロード等)。しかしこのような特殊な分野でない限りは、最優先すべき最適化は他にあります。
紹介する性能チューニングの特徴
本記事では性能チューニングの中でも以下の特徴を持った原則、および代表的なテクニックのサンプルを紹介します。
- プログラム側の修正で実現できる
- 特定のプログラミング言語やライブラリに依存しない
プログラミング言語、アーキテクチャ、ハードウェア等に特化したより専門的で高度な最適化も数多く存在しますが、まずはより汎用的な原則を押さえておくべきです。
NOTE:
コンパイラの最適化オプション、Linuxカーネル等のパラメータチューニング等に物凄く精通しているのに、本記事で扱っているような基本的な性能チューニングを一切知らない/適用できない人をたまに見かけます。
そういう人は自分自身の得意分野の性能チューニングで問題の解決を試みるため、性能ボトルネック次第では極めて効果の薄い性能チューニングを施しがちになります。周りがあまり詳しくない技術者の場合「これだけやっても駄目だから仕方ない」と誤解を蔓延させるオマケ付きです。
性能チューニングの原則
ここでは私自身が最も大事と考える3つの原則を紹介します。重要度は状況に応じて変わりますが、基本的に上から順番に原則を適用することをお勧めします。
- 原則1. 計算量を小さくする
- 原則2. 高コスト処理をバッチ化する
- 原則3. 高コストなものを再利用する
NOTE: 他にも加えたいところですが、あまり多すぎると実践しづらいので3つに留めています。
原則1. 計算量を小さくする
性能チューニングで最も大事なものの一つが、プログラム処理の計算量を小さくすることです。
計算量、O記法などを知らない場合は、以下の記事などを参考にしてください。
[初心者向け] プログラムの計算量を求める方法
計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜
情報系やコンピュータサイエンスを専攻している人には常識レベルの話なのですが、たとえ知っていても実践できている人は残念ながら意外と少ないです。プログラムを書いてる時でも、DB向けのSQLを書いてる時などでも計算量は常に頭の片隅で意識しておく習慣をつけておきましょう。
NOTE: ちなみにDBのSQLの場合、その時点のDBのテーブルのレコード数、統計情報などによってオプティマイザが内部実行計画を変更する可能性があるためややこしいです。このため当初は計算量がO(N)で動作していたSQLが、例えばDB統計情報の精度不足によってO(N^2)になることもあります。
大まかな基準としては計算量がO(N)以上なら「性能の阻害要因になるかも」と警戒し、O(N^2)以上の場合は「性能の阻害要因に絶対になる」くらいの意識で確認することがお勧めです。
- ループ処理
- 再帰処理
- データ構造と操作 (追加、更新、削除、参照など)
- その他 各種アルゴリズム
- SQL (ex. サブクエリ、Join/Scanなどの実行計画)
判断基準の目安例
- 計算量がO(N^2)以上、処理要素数N=数千~数万以上
- 計算量がO(N)以上、処理要素N=数十~数百以上、各要素の処理が高コスト処理に相当
- 高コスト処理については原則2を参照
補足: 計算量の係数
例えば計算回数を3*n
の式で求められる場合、計算量はO(N)となります。係数である3は無視していいわけですね。
しかしプログラムの性能を考える場合はこの係数は意識することも大事です。例えば10*n
の計算回数で処理時間が10秒だった場合、係数の部分を1にできれば処理時間を1秒に改善できます。もちろん開発対象の要件等にはよりますが、この係数部分の改善が極めて重要となるケースは十分にあることは想像できると思います。
後述する原則2, 原則3も、この係数部分を小さくすることに利用できます。
原則2. 高コスト処理をバッチ化する
プログラムが行う処理、要求される性能(ex. 処理時間)を考慮した場合、要求される性能を満たすために大きな阻害になる高コスト処理が存在することがあります。このような高コスト処理が何度も実行されるのは致命傷となる可能性が高いため、まとめて実行(バッチ化)することを検討しましょう。
高コスト処理と判断するかどうかはケースバイケースになります。しかし以下のような処理は「要求される性能を満たすための阻害要因となる高コスト処理」になる可能性が高いため、高コスト処理の候補として意識することをお勧めします。
- 外部コマンド実行
- プロセス生成コストが高い
- サーバへのリクエスト(REST API, SQL, RPC, etc...)
- サーバ間通信のコストが高い
- リクエストあたりの処理時間が長い、あるいは長い可能性がある
- システムコール
- I/O処理、ユーザ空間とカーネル空間の切り替えコストが高い
- 前述した2つ高コスト処理に比べればインパクトは小さめ
- 未知のライブラリ
- どのような処理をしてるかを理解するまではコストが高い可能性が残る
先ほども述べたように阻害要因になる可能性が高くても、状況によっては問題ない場合もあります。例えばある処理の支配項である「SQLのINSERT (1回あたり1msかかる)」が実行される場合のパターンを3つ考えてみます。
- 3秒以内に行う必要がある処理の中で、SQLのINSERTを高々10回しか行わない
-
1ms * 10 = 10ms
のため、性能ボトルネックになる可能性は極めて低いため問題なし
-
- 3秒以内に行う必要がある処理の中で、SQLのINSERTが1万回行われる
-
1ms * 10000 = 10s
のため、致命的な性能ボトルネックになるため問題あり
-
- 60秒以内に行う必要がある処理の中で、SQLのINSERTが1万回行われる
-
1ms * 10000 = 10s
のため、性能ボトルネックになる可能性は極めて低いため問題なし
-
上記の3つのパターンを見ればわかるように、性能要件と処理要素数などに応じて阻害要因になるかどうかは変わります。このためここで重要なのは、阻害要因になる可能性があるもの(高コスト処理の候補)に対して大まかな概算を行い、実際に問題がありそうかどうかをざくっと見極めることです。問題がないと断定できなければ、その部分は要確認ポイントとして当たりを付けます。
高コスト処理を特定することができた場合、あとはその部分をバッチ化する方法を検討することになります。一般的に上で述べたような高コスト処理は何らかの形でまとめて実行する手段が用意されており、まとめて実行した場合に処理時間が大幅に短縮できる場合が多いです。そのような手段がない場合は、まとめて実行する手段を呼び出し先に実装してもらう必要があるかもしれません。
NOTE:
Python, Ruby等のスクリプト言語は、C/C++/Java等のコンパイル型言語と比べてステップ単位の処理が何倍~何十倍も遅いです(JavaScriptについてはV8エンジンの目覚ましい進化などにより、やや事情が異なります)。
このため処理内容と性能要件によっては、ステップ単位の処理そのものが高コスト処理として顕在化する可能性があります。このような場合はできるだけ「C言語等で高速処理されるように実装された標準関数、ライブラリ」を活用してまとめて処理するようにしましょう。例えばPythonであれば巨大な配列の生成や処理については極力Numpy等のライブラリに任せるといった具合です。
判断基準の目安例
- 数十~数百以上の外部コマンドを実行している
- 外部コマンドの処理時間が長い場合、さらに注意が必要
- 数百~数千以上のHTTPリクエスト、SQLなどを送信している
- 送信先がインターネット上などの場合、さらに注意が必要
- 数千~数万以上のシステムコールを実行している
- 1秒間に数千~数万リクエストを処理したり、大量データを処理したりする場合などは要注意
- μs, ns単位の処理時間を意識する場合、さらに注意が必要
原則3. 高コストなものを再利用する
例えばプログラムの処理を行う際には、スレッドや各種コネクション(ex. HTTP, SQL)を活用して実装することも多いと思います。これらを頻繁に利用する場合、毎回新しく作成して破棄するのは思いのほか大きなコストになります。このように**高コストかつ使用頻度が高いもの
については、再利用できるのであれば再利用するための仕組みを検討**しましょう
もちろん高コストなものというのは、プログラムの目的や性能要件などによって大きく異なります。これは原則2と同様です。例えばHTTPリクエストを10分に一回しか送信しない場合はHTTPコネクションを再利用するメリットは小さいですが、1秒に数十~数百回送信する場合はHTTPコネクションを再利用するメリットは大きいといった具合です。プログラムの用途や性能要件によっては、毎回メモリを使う度に律儀にmallocで確保してfreeで解放すること自体が大きなコストとなる場合もあり、このような場合にはmallocしたメモリ領域自体を再利用する仕組みを導入するメリットも大きいです。
代表的な再利用対象を以下に示します。
- HTTP, DB等のコネクション
- コネクションプールを活用して再利用する
- 例えばJDBC(JavaのDB API)ではTomcat JDBC Poolを活用する
- スレッド
- スレッドプールを活用して再利用する
- 例えばJavaではExecutorServiceを活用する
- サーバの問い合わせ結果
- HTTPレスポンスをキャッシュする
- DNSレスポンスを一定期間キャッシュする
- ライブラリ等にキャッシュ機構が備わっている場合、これを活用する
判断基準の目安例
- 1秒間に数十~数百以上のスレッドの生成破棄を行っている
- コネクションプールやセッションを意識せずにHTTP、SQL等を大量に発行している
- 使用している言語やライブラリによっては生成破棄が繰り返されてる可能性がある
原則を適用する流れ
最適化の原則を当てはめるのは以下の作業を行うときです。
- 実装を行う時
- 既存の実装に対してチューニングを行う時
コーディングを行う時に以下のチェックを行います。該当する原則がある場合は、後々最適化を施す必要がある箇所となり得ます。
- 各原則に該当するかどうか当たりを付ける
- 当たりを付けた箇所には以下の対応を行う
- TODOコメント、ログ埋め込み
- プログラムを動作させて性能ログを取得する
- 性能ログをもとに処理時間を確認し、確認結果から性能チューニングが実際に必要か判断する
ちなみに当たりを付ける範囲が細かいほど手間がかかるため、「これとこれが怪しい」くらいの範囲をまとめてしまっても構いません。実際にその範囲が性能の阻害要因になったタイミングで範囲を細分化して問題箇所を特定するのも一つの手です。
該当箇所には以下のような対応をしましょう。各該当箇所を何も考えずに最適化しても効果が薄く部分最適化にしかならない可能性があるため、後々の最適化を行うための準備だけに留めます。
- 処理時間を測定できるように性能関連ログを埋め込む
- TODOコメントで重要な最適化候補であることを明記する
チューニングのサンプル
ここでは各原則を実現するためのサンプルをいくつか紹介します。
ソースコードは基本的にPython3.6を前提に記述しています。
NOTE: 測定結果の比較等はその都度環境(ex. OS, Host/VM/WSL)が異なるため、参考情報程度に留めてください。
原則1. 計算量を小さくする
多重ループにHashMap/Set等を活用する
あるコレクションから別のコレクションを検索するような処理では多重ループを使うことが多いです。しかし多重ループは計算量がO(N^2)、O(N^3)と大きくなるため、処理要素数が多くなると一気に性能ボトルネックとして顕在化します。
このような時には一方のコレクションからHashMapやSetを作成し、これを検索に活用することによって例えば計算量をO(N^2)からO(N)等に減らすことができます。コレクションの要素数分だけ新しいHashMap/Setを作成するコストが勿体ないと思うかもしれませんが、以下のテーブルの処理要素数を見ればそのコストは極めて小さいものだと分かります。
要素数 | O(N)×2 | O(N^2) |
---|---|---|
10 | 20 | 100 |
100 | 200 | 10,000 |
10,000 | 20,000 | 100,000,000 |
まず二重ループ処理になっている例を示します。(実行時間の測定等の処理は割愛)
all_files = list(range(1, 100000))
target_files = list(range(50000, 60000))
matched_files = []
# 計算量がO(N^2) -> BAD
for f in all_files:
if f in target_files:
matched_files.append(f)
print(len(matched_files)
ここで注意してもらいたいのがfor文の中にあるif f in target_files:
の箇所です。この部分はループではないため処理が1回で終わっているように見えますが「リストのtarget_filesに要素sが含まれているか」を確認するために、合致する要素を見つけるまで平均でN/2の要素チェックの処理が行われることになります。Javaにおけるコレクション操作メソッドのcontains()
等も同様です。このためプログラム文法上は多重ループになっていなくても、実際の処理では多重ループ相当の処理になっている場合があります。
次にListからSetを作成して二重ループを改善した例を示します。(実行時間の測定等の処理は割愛)
NUM = 1000000
nums = list(range(1, NUM))
# TUNING: set関数によりListからSetを作成
# NOTE: //で割り算しているのは整数を保持するため
expected_nums = set(range(1, NUM//2))
matched_nums = []
# 計算量がO(N)に改善 -> GOOD
start = time.time()
for f in nums:
if f in expected_nums:
matched_nums.append(f)
print(len(matched_nums)
ループ処理の部分の比較結果を以下に示します。
計算量 | 実行時間 |
---|---|
O(N^2) | 8,228 ms |
O(N) | 4 ms |
処理要素数N=10万件の場合、計算量をO(N)に改善することで約2000倍高速化できました。
このように処理対象のレコード数が数万以上の場合は、このような簡単なループ処理でも大きな改善効果があります。
原則2. 高コスト処理をバッチ化する
外部コマンド大量実行をまとめる
プログラムの中で外部コマンドを実行する場合、その実行する回数が多いほどパフォーマンスが低下します。これは外部コマンド実行がプロセス生成などを伴うコストの高い処理だからです。
ここでは「/etc配下の全ファイルの総バイトサイズを表示する」ことを目的にしたプログラムを例として取り上げます。wcコマンドを--bytes
オプションを指定することにより指定したファイルのバイトサイズを出力することができます。
NOTE:
ちなみにPythonを含む大半の汎用プログラミング言語では、ファイルのバイト数を取得するための標準関数等が用意されています。このためwcコマンドなんて使う必要はありません。このためこの例では「どうしても外部コマンドであるwcコマンドが必要」という前提で読み進めてください。
import pathlib
from subprocess import check_output
cwp = pathlib.Path("/etc")
files = [f for f in cwp.glob("**/*") if f.is_file()]
total_byte = 0
for f in files:
# 各ファイルに対してwcコマンドを実行 -> 極めて非効率
result = check_output(["wc", "--byte", str(f)])
size, file_path = result.split()
total_byte += int(size)
print("file num:", len(files))
print("total byte:", total_byte)
結果は本節の最後に掲載していますが、ファイル毎にwcコマンドを実行しているため、対象ファイル数が数百~数千以上になると処理に数秒~数十秒以上かかるようになります。このため、wcコマンドの実行回数をできるだけ減らす工夫が必要となります。幸いwcコマンドは一回のコマンド実行で複数のファイルを指定することができます。このためwcコマンド実行回数をファイル数分から1回にバッチ化できます。
バッチ処理化した例を以下に示します。(実行時間の測定等の処理は割愛)
NOTE: 例にあるwcコマンド結果のパース処理はかなり雑かつ手抜きです。真似しないでください。
import pathlib
from subprocess import check_output
cwp = pathlib.Path("/etc")
files = [f for f in cwp.glob("**/*") if f.is_file()]
# wcコマンドに全ファイルを引数として渡してバッチ処理化
args = [str(f) for f in files]
# NOTE: Pythonでは*でargsのリストを引数として展開できる
result = check_output(["wc", "--byte", *args])
total_byte = int(str(result).split(r"\n")[-2].split()[0])
print("file num:", len(files))
print("total byte:", total_byte)
コマンド処理のバッチ化 | 実行時間 |
---|---|
なし | 12,600 ms |
あり | 338 ms |
同じwcコマンドを--bytes
オプション付きで使用しているにも関わらず、バッチ処理化することにより処理時間を約1/40に短縮することができました。
このようなバッチ処理を何らかの形で提供しているUnix/Linuxコマンド、各種ライブラリ(ex. SQL, HTTP, I/O)はそこそこ存在します。性能面で問題がある場合は積極的に活用しましょう。
ちなみに外部コマンドのバッチ処理化をより突き詰めたい人は、以下の記事あたりが参考になります。タイトルには「シェルスクリプト」とありますが、基本的に外部コマンドを如何に効率良く活用するかに関する記事です。
シェルスクリプトを何万倍も遅くしないためには —— ループせずフィルタしよう
続: シェルスクリプトを何万倍も遅くしないためには —— やはりパイプは速いし解りやすい
I/O処理にバッファを使用する (=システムコール回数を減らす)
性能要求が高い状況化では、ファイルの読み書き、ネットワークの送受信などのI/O処理周りのシステムコールは大きなボトルネックになりがちです。このためシステムコールを減らすためにI/O処理のバッファリングが重要となります。
NOTE: 重要なのは「システムコール回数を減らすために何ができるか?」であり、その有効な手段としてI/Oバッファリングを活用しているということです。
例えばファイルの読み書きの場合であれば、それぞれの言語によって適切なバッファリングのアプローチを取ります。
- Javaの場合:BufferedReader, BufferedWriter等を使用する。
- C言語の場合:fwrite, fread関数等を使用する。
- Pythonの場合:open時にバッファリングがデフォルトで有効。
Pythonの例を以下に示します。なおPythonの場合はデフォルトでI/Oバッファが有効となっているため、あえて無効にすることでその効果を確認してみます。(実行時間の測定等の処理は割愛)
# buffering=0を指定した場合はI/Oバッファが無効となる
f = open("file.txt", "wb", buffering=0)
s = b"single line"
for i in range(500000):
f.write(s)
f.close()
以下の比較結果でも、I/Oバッファを有効にすると約10倍のwrite処理の性能改善があったことが分かります。
バッファ有無 | 実行時間 |
---|---|
なし | 2,223 ms |
あり | 245 ms |
for, whileループを使わない (スクリプト型言語)
Python, Ruby, Perl等のスクリプト型言語はその動作の仕組み上、C言語やJava等のようにネイティブコードとして実行されるプログラミング言語と比較すると処理速度が非常に遅いです。特に単純な演算、ループ処理などは数十倍~数百倍くらい遅くなるケースも珍しくありません。
スクリプト言語であっても処理性能が重要になってくるような場面では、ループ処理に相当する部分を以下の手法で委譲してしまいましょう。
- 組み込み関数、言語機能を使用する
- Pythonのリスト内包表現
- map, filter, apply等の関数 (C/C++言語で実装されたものが望ましい)
- C言語等で実装されたライブラリ、モジュールを使用する
NOTE: 少し分かりづらいかもしれませんが、「スクリプト型言語のループ処理を、C言語実装にバッチ処理させている」ということから原則2に関連する手法の一つです。こういう発想をできるようにするのも大切なので日頃から意識したいものです。
例としてPythonで数値リストの総和の処理をループ処理で行った場合と、sum関数で行った場合を比較してみます。(実行時間の測定等の処理は割愛)
nums = range(50000000)
# ループ処理の場合
total = 0
for n in nums:
total += n
# sum関数の場合
total = sum(nums)
比較結果を以下に示しています。約5倍くらい高速になっています。
計算方法 | 実行時間 |
---|---|
ループ処理 | 3,339 ms |
sum関数 | 612 ms |
sum関数はC言語で実装されているため高速に処理しています。join関数やmap関数などもC言語で実装されているため、うまく活用することでPython側のループ処理を回避して高速化することができます。
原則3. 高コストのものを再利用する
適切な文字列結合を選択する
プログラミング言語によっては、複数の文字列を結合して一つの文字列を作る文字列結合処理は非常にコストがかかります。
Python, Javaの場合は文字列結合のたびに新しい文字列オブジェクトが生成されるため非常に無駄が多いです。このためJavaであればStringBuilder、Pythonの場合はjoin()を活用したテクニック等を使うようにしましょう。詳細については以下の記事が参考になります。
【Java】文字列結合の速度比較
Pythonの処理速度を上げる方法 その2: 大量の文字列連結には、join()を使う
ちなみにJava7になってからs = "hello" + "s" + "!!"
のような1行の文字列結合に限り自動的にStringBuilderを使うように最適化してくれるようになっていますが、ループ外の変数に対する文字列結合処理にはこの最適化は適用されませんので注意しましょう。
同じコネクションを再利用する
HTTP等のリクエストを送信する際にHTTPライブラリを使うと、ライブラリによっては1リクエスト毎にコネクションを生成&破棄します。例えばPythonのrequetsライブラリのrequests.get()はこのパターンに該当します。
1秒に数十~数百リクエストを送信する場合は、必ずHTTP1.1以降のPersistent Connectionで同じコネクションを使いまわすようにしましょう。
PythonのrequestsライブラリでSessionを活用した場合とそうでない場合を比較してみます。(実行時間の測定等の処理は割愛)
import requests
NUM = 3000
url = 'http://localhost:8080/'
# Sessionなしの場合
def without_session():
for i in range(NUM):
response = requests.get(URL)
if response.status_code != 200:
raise Exception("Error")
# Sessionありの場合
def with_session():
with requests.Session() as ses:
for i in range(NUM):
response = ses.get(URL)
if response.status_code != 200:
raise Exception("Error")
without_session()
with_session()
比較結果を以下に示しています。同一ホスト内(Local)にWebサーバがある場合は約1.2倍、インターネット(Internet)にWebサーバがある場合は約2倍高速化しています。サーバへの接続コストが高い条件下ほど効果が大きくなることが分かりますね。
計算量 | 実行時間 |
---|---|
Internet + Sessionなし | 7,000 ms |
Internet + Sessionあり | 3.769 ms |
Local + Sessionなし | 6,606 ms |
Local + Sessionあり | 5.538 ms |
その他
原則とか直接関連しない性能チューニングのトピックです。
DEBUGログ出力時に処理を発生させない
DEBUGログで固定文字列以外を使っている場合、仮にログレベルでDEBUGログを出力しないように設定していても引数を渡す部分は計算されるため処理コストがかかります。特に1秒に数千、数万回実行されるような箇所にこのようなDEBUGログがあると性能インパクトは非常に大きくなります。
計算を伴うDEBUGログ出力を入れる場合、必ずログレベルチェックのif文を組み合わせて、DEBUGログ出力を行わないログレベルの時には計算処理が発生しないようにしましょう。
l = [1, 2, 3, 4, 5]
# BAD:
# ログレベルに関わらず、リストの総和計算と文字列結合を実施
logging.debug("Sum=" + sum(l))
# GOOD:
if logging.isdebug():
# DEBUGレベルの場合は一切実施されない
logging.debug("Sum=" + sum(l))
# GOOD: 固定文字列の場合は計算が発生しないためOK
logging.debug("Entered the function A")
NOTE: 遅延評価されるプログラミング言語の場合はこの限りではありません。