コード最適化(高速化)の基礎

プログラミング入門 プログラミング

いまさらだけどホットエントリ経由．

  • プログラミングを始めたばかりで高速化の大枠が全くわからず意味不明なことをしていた在学時、こんな資料があったら良かったのになあ、と思って書いたもの。

内容をまとめるとこんな感じ．

  • id:vanbraam ここまでCPU-intensiveな処理が通常のプログラムでは殆どない.本稿の言に従えば"律速段階"はそこじゃない事が多い;MathJax+math/tex->MathMLでこれだけの数式が書けるのを知る事ができたのは大きな収穫
  • id:kmaebashi 『つまり、Pythonはコードを一行ずつ機械語(010011011...）に変換（コンパイル）して動作します。』呪いのように何度も出てくる間違いだ…／結局、速くなったのは、ライブラリ使ったから、ですよね。アルゴリズム重要?

これに関連して，自分なりに，いろいろとテキトーに書き連ねてみる．テキトーなのであとで加筆変更する可能性大．


ていうか，本当に何も知らない初心者だったら，まずはCode Complete 第二版の25章,26章を読め．話はそれからだ．*1

必用かどうか検討する．

パフォーマンス改善する前に，まず最初に「高速化する意味はあるか？」を検討してみよう．

  • 何回くらい使う？：仮に1回に10時間かかるプログラムでも，一回しか使わないなら，何時間もかけて高速化するメリットはない．
  • どのくらい高速化する？：たとえばExcel方眼紙を整形するスクリプトを書いたとして，一回の実行に数分かかるとしても，使うのが年に一回の納品の時のみだというなら，高速化するメリットはない
  • そもそも可能なのか？：普通に計算すると自分が死ぬまで動かし続けても終わらないような問題もある．
  • ほっときゃ早くなるんじゃね？：CPUが早くなったりVMやライブラリのバージョンアップを待てば，自分が努力しなくても早くなることもある．
  • id:thesecret3 積分のようなものは、時間とともにハード・ソフト両方の性能が向上するので、pythonで1回書いて30年ぐらい熟成すれば100万倍ぐらいにはなりそうな。

普通はこの段階の検討はすんでることが多いが，念のため確認しておこう．

最もお手軽な方法

仮に必用だとしたら，真っ先にすべきことは，速度を金で買うことだ．

金で買えるならそれが一番早くて安いことが多い．技術力も不要だ．

  • 早いハードに買い替える：新しくて早いCPUに載せ替える，メモリやHDDを造設する．HDDをSSDに換装する，ブロードバンド回線を引く，など．
  • 商用のソフトウエアやライブラリを購入する．
  • スパコンやクラウドコンピューティングを利用する．（レンタルする．）

オープンソースなどで公開されてるツールやライブラリを使うというのも，これの亜種と言えるだろう．


小手先のチューニングが有効な場合もある．

  • コンパイラやVMの最適化オプションを変更してみる
  • 新しいバージョンのコンパイラやVMを使ってみる．
  • DBにインデックスをはる．DBのバージョンを新しくする．

それでもだめなら，技術を駆使して高速化する．

金ではどうにもならない場合には，手作業で高速化するしかない．*2

  • よほどの場合を除いてミクロな最適化は，コンパイラ／VM任せにする

プログラミング作法 (アスキードワンゴ)

プログラミング作法 (アスキードワンゴ)

  • 7章 性能

基本的なことのはず．知らない人は必見だけど，ベテランなら知ってることばかり．

【電子合本版】Code Complete 第2版　完全なプログラミングを目指して

【電子合本版】Code Complete 第2版　完全なプログラミングを目指して

25章と26章に基本的な高速化テクニックに関する説明がある．良くも悪くも教科書的に良くまとまっている．

ある意味で基本的すぎるのでコンピュータサイエンスを学んだ人なら知ってることも多いが，大学でCSを学んでなくて基礎が欠けてる人は一通り目を通しておいた方がいいと思う．

  • 25章 コードチューニング戦略
    • 25.2.4 コンパイラによる最適化
    • 25.3.1 非効率の一般的な原因
  • 26章 コードチューニングテクニック

良い最適化コンパイラを使用すると，全体で約40％以上コードが早くなる可能性がある．「第26章 コードチューニングテクニック」で紹介するテクニックの多くは，約15〜30％の改善しか見込まれないものだ．すっきりとしたコードを書いて，後はコンパイラに任せてみるのも一案である．

コードをチューニングすることは，コンパイラの種類，バージョン，ライブラリのバージョンなどを変更するたびに，最適化を再プロファイリングするという契約書にサインしたことを意味する．再プロファイリングを行わないと，コンパイラやライブラリの1つのバージョンではパフォーマンスを改善する最適化が，ビルド環境を変えた途端にパフォーマンスを低下させるという結果になるかもしれない．

Jacksonの最適化の法則

  • 法則1：最適化しない
  • 法則2：まだ最適化しない ー 完全に明白で最適化を使用しない解決策が見つかるまでは（上級者向け）

コンパイラが生成したアセンブラコードを詳しく調べ，せっかくの最適化が何の意味もなかったことを知って，筆者はひどく落ち込んでしまった．配列の要素を順番に取り出す必要に迫られたのは，筆者が初めてではなかったらしい．コンパイラの最適化で既に配列アクセスをポインタに変換していたのである．1つだけ言えることは，パフォーマンスを測定せずに思い付く程度の最適化は，コードを読みにくくするだけである，ということだ．

パフォーマンスのボトルネックをデータ無しで予測したり分析したりできるプログラマなど存在したためしがない．それがどうなっているのかをいくら考えてみたところで，全く別の何かであることを知って，驚くのがオチである．

それに対して，ここでの変更は「アンチリファクタリング」と呼んだ方がよいかもしれない．これらの変更は「内部構造を改善する」どころか，パフォーマンスの改善と引き換えに内部構造を改悪する．これは仕方のないことだ．変更によって内部構造が悪くならなかったら，それらを最適化だとは考えないだろう．だから最適化を既定で使用し，それらを標準のコーディングプラクティスと考えるのである．*5

アルゴリズム周りの知識は必須．*6 下手なアルゴリズムで実装した物は適切に実装されたものより，何千倍も何億倍も遅くなることがある．*7

ここは応用分野ごとにことなるので，上に上げたような基礎知識だけではいかんともしがたい．

Javaパフォーマンス

Javaパフォーマンス

必用とあれば，各言語やプラットフォーム環境固有のテクニックも駆使するかもしれない．

その他もろもろのパフォーマンス本リスト．

普通に必用なのは，せいぜいここまで．




本当にハードに依存したレベルで最適化をするならば，アーキテクチャに関する知識も一通りはあった方がいいが，そこまで必用としないことも多い．*8いずれにせよ，もはや人間に理解できると思わない方が良いだろう．

コンピュータの構成と設計 第5版 上・下電子合本版

コンピュータの構成と設計 第5版 上・下電子合本版

http://ec.nikkeibp.co.jp/nsp/dl/09842/index.shtml

  • 3.8 高速化：半語並列性および行列の乗算
  • 4.12 高速化：命令レベル並列性を応用した行列の乗算
  • 5.14 高速化：キャッシュのブロック化を応用した行列の乗算
  • 6.12 高速化：複数のプロセッサを応用した行列の乗算
  • 6.2 並列処理プログラム作成の困難さ

ヘネシー＆パターソン　コンピュータアーキテクチャ　定量的アプローチ 第5版

ヘネシー＆パターソン　コンピュータアーキテクチャ　定量的アプローチ 第5版

  • 3.2 命令レベル並列性技術のためのコンパイラの基本．
  • 3.12 マルチスレッディング：単一プロセッサスループット改善のためのスレッドレベル並列性抽出
  • 4.5 ループレベル並列性の検出と増強

上記の例題では，7クロックサイクル当たり，ループの1つの繰り返しを終了し，1つの配列の要素をストアした．しかし，それら7クロックサイクルのうち，配列要素で行われる実際の演算はたった3つ（ロード，加算，ストア）である．残る4クロックサイクルはDADDUIとBNEというループのオーバーヘッドと，2クロックサイクルのストールである．これら4つのクロックサイクルを削減するためには，オーバーヘッドとなる命令数に比べてもっと多くの命令を実行する必用がある．

分岐とオーバーヘッドとなる命令数に比べて全体の命令数を増やす単純な方法が，ループアンローリング（Loop Unrolling）である．アンローリングは，ループの本体を単純に複数分回複製し，ループ終了のコードを調整する．
(3.2「命令レベル並列性技術のためのコンパイラの基本」 の「基本的なパイプラインスケジューリングとループアンローリング」より)

コンパイラの構成と最適化

コンパイラの構成と最適化

コンピューターアーキテクチャは全く知らなくても動くコードは書けるし，全てが関係あると言えばある．

あなたが初心者で上記の本が積ん読状態なら，このあたりを開いてみるのも良いだろう．


その感想は，きっと「うむ，わからん」だ．

しかもここで紹介されてるのは，最適化技術としては古いものだから，最新の最適化コンパイラやVMはもっと進歩してるだろう．一介のプログラマが，その挙動を予測できるなどとは夢にも思わないほうがいい．


参考になるので追記

元記事について．

実は、このプログラムはまた別のプログラムに組み込まれ、f(x)f(x) の中身を変えて色んな場面で何千回も使用されることになっています。

…いや、嘘ですが、このような状況は珍しくありません。

単なる設定だけど，この仮定はとても重要．これがなければ，苦労してこの部分を高速化する必要がない．ただしこの部分が本当にボトルネックになるかについては計測して確認する必要がある．

最初からある程度まとめて機械語にコンパイルしておくことは出来ないのでしょうか。

何度も繰り返し実行される部分だけでも予めコンパイルしてしまえば、繰り返しのたびにその行を逐次コンパイル、という作業がなくなって速くなるのではないでしょうか。

最適化の話も絡むので，話はそう簡単ではないらしい．

結果として、ソースコードを書く人間はハードウェアレベルの挙動を理解していることが求められる上、バーチャルマシンによる安全装置が無いため、ちょっとのミスで致命的なバグを起こしがちです。

この手の言語で圧倒的に最も有名なものはC言語でしょうが、ここではFortranというものを使用します。

うーん．．．．

アセンブラだったらその通りだと思うけど，C言語は仮にも高級言語だから．最適化コンパイラの挙動を予測するのは非常に困難．「最も低級な高級言語」の古いコンパイラでさえも，かなり高度な最適化をやっていた．

詳細については「コンピュータアーキテクチャ」とか見てもらえば分かるけど，これは既に人間が理解するのは不可能な領域に達してるでしょ．

gfortran -O3 simple.f -o simple

とコンパイルします。-O3 は最適化オプションです。

オプションの詳細はツール（コンパイラ）ごとに異なる．*9 高速化する場合は，コンパイラ オプションについてはマニュアルを読んで確認しておくべきだろう．*10

…というか、よほど優秀でない限り自分で書いてはいけないのです！

数値積分などという作業は、科学計算においてメジャー中のメジャーのような計算であり、そのための手法は研究し尽くされており、限界まで速度と精度を高めたプログラムが既に存在するのです。

ここは同意．むしろ最初に調査すべき事項の一つだな．

ただし、そのプログラムが自分の使っている言語で使用可能なのかというのは別の問題です。

むしろ先にライブラリを調査し，そのライブラリの言語を記述言語として採用できないか，検討しないだろうか？

中身が空のFortranプログラムを書いてみるとわかるのですが、外部プログラムの飛び出し（というかディスクI/O）というのは実はあまり早い作業ではありません。

粒度にもよるが，一般論としてコンテキストスイッチは重い処理．*11

その辺についてもCode Completeで一通りまとめられていた．（ 25.3.1 非効率の一般的な原因 ）

http://b.hatena.ne.jp/entry/qiita.com/Akai_Banana/items/48a35d2a40d1804d3b32

大きな間違いはないにせよ，全体に「うーん，そうかなあ．．．」と言いたくなる感じ．

  • id:ironies 凡人が思いつくものなんざどこかの天才が既に作ってるから、車輪の再発明してねえでそいつを探せってこったな。

最適化処理でさえも，とうの昔にコンパイラに組み込まれてる場合がある．

ついでに．いろいろメモ

2004年物だけど，コンパイラやVMのコード最適化のチュートリアルとしてはよくできてる．古いものだと理解した上で読むならお勧め．今だともっと進歩してるんだろう．

興味深いが，「月刊ジャバワールド 2000年 9月号」とすると，ちょっと古いか．「1. 最適化って？」あたりなら目を通しておいてもいいかも．

Visual Studio2017固有の高速化テクニック．なお高速化全般に言えることだが，これらはあくまでヒントでしかなく，実際に使用すべきかどうかはケースバイケース．

*1:

【電子合本版】Code Complete 第2版　完全なプログラミングを目指して

【電子合本版】Code Complete 第2版　完全なプログラミングを目指して

いいお値段するけど，Kindle版なら半額の時もあるから，そこを狙うべし．コレ書いてる今も，４０％ポイント還元だ．

*2:高速化を謳った技術書は，通常この段階のものをターゲットにしてる．

*3:一般にLight Weight Languageは重いのが多い．もとより高速化は視野に入ってない．

*4:共通部分式など一部のものはコンパイラでも最適化してくれるが，本質的には共通であったとしてもコード上は共通になってない場合は自動的に除去するのは不可能だろう．

*5:セミコロンを「だから」と略したせいで，訳が少し分かり難くなってると思う．
"This is true by definition. If the changes didn't degrade the internal structure, we wouldn't consider them to be optimizations; we would use them by default and consider them to be standard coding practice."
「これは定義からして当然だ．もしその変更が内部構造を改悪しないものならば，我々はそれらを『最適化』とは考えない．我々はそれらを『標準のコーディングプラクティス』と考え，デフォルトで使用するだろう．」

*6:http://d.hatena.ne.jp/JavaBlack/20151020/p2

*7:そんな難しい問題だと，初心者が実装したコードだと動くこと自体が奇蹟だろうけど．

*8:もはや「必用としないことの方が多い」かもしれない．

*9:最もメジャーなのは -O3 などだと思う．おそらくは "Optimize" のOだろう．数字は最適化レベルによって変わる．

*10:コンパイラオプションなんて常識だとも思うが，そういえば最近は統合環境に頼りすぎてて，コマンドラインを触ったことがない開発者もいるのかな？

*11:ここで「一般論として」と逃げを打ってるのに注意．パフォーマンスについて「一般論としてはこうだ」と傾向を把握するのは簡単だが，それが本当にこのプログラム内でも重いのか，どの程度重いのか，どのように書き換えたら改善されて，それはどのくらいの高速化に繋がるか，その高速化は将来にわたっても「高速化」であり逆効果にはならないのか等についてはケースバイケースで，遙かに難しい問題になる．