D.Horiyama's output

JavaScript関数型プログラミング Ch.7 関数型コードの最適化

JavaScript勉強メモ関数型プログラミング
  • [https://book.impress.co.jp/books/1115101137:embed:cite]

まえがき

  • パフォーマンスの話

  • 命令型よりも効率が悪い、ということはない

    • メモリは食うことがある

    • 個別の関数は速くならない

      • 関数呼び出しが増える分オーバヘッドで遅くなる
    • が、関数呼び出しの重複を避け、本当に必要になるまで呼び出しを遅延することで実行速度を高める

関数実行の中身を調べる

スタックフレームの内訳はおよそ以下:

executionContextData = {
    scopeChain,     // 
    variableObject, // 関数の引数、arguments、局所変数、関数等への参照保持
    this            // 関数オブジェクトへの参照
}

  • 関数呼び出しのたびに関数コンテキストが積まれる

    • いわゆるスタックフレーム

    • 空フレームは約48バイト

      • 「約」って何だ…？

  • scopeChain

    • 識別子の探索に使われるオブジェクトのリスト

      • 大昔のwith文とかで書き換えられるやつ

    • var変数のスコープ

      • レキシカル
    • クロージャのからくり

  • variableObject

    • 局所変数1つごとに8バイト増

  • this

    • callとかapplyとかで指定するやつ
    • nullだとGlobal Object

  • ルール

    • JSはシングルスレッド
    • 唯一のグローバルコンテキストが存在する

    • 関数コンテキストの個数は無制限

      • 言語仕様上は、か
      • ブラウザによる制限はある

    • 関数呼び出しは実行コンテキストを新たに作成する

      • 再帰呼び出しでもそう

再帰コードの問題点

  • スタックフレーム積むのでメモリ食う

    • カリー化とかもそう
  • 柔軟性、再利用性、正確性とのトレードオフである

  • 適宜map, filter, reduceなど使え

    • 再帰にならない

  • ES6ではTCO: tail call optimization (末尾呼び出し最適化)がある

    • 再帰コードを書いてもループに最適化される

遅延評価を使用して実行を遅らせる

  • FPにおける高速化の肝1

alternation関数コンビネータ(OR)により不要な計算を避ける

  • 短絡評価みたいな話

ショートカットフュージョンを利用する

  • 参照透過性により、数学的に同値変形できる例
compose(map(f), map(g))
map(compose(f, g))
compose(filter(p1), filter(p2))
filter(x => p1(x) && p2(x))

  • Lodash等の関数型ライブラリが、上記のような最適化を行える場合がある

    • 計算の中間結果を保持する内部データ構造の数が減る
    • 結果、省メモリになる

“必要に応じて呼び出す”戦略を実現する

  • メモ化の話

メモ化を理解する

  • 参照透過性により、引数から評価結果が完全に予測可能

    • 引数 => 評価結果 の辞書をキャッシュする

計算が集中する関数をメモ化する

  • 計算がめっちゃ減る
  • Function.prototype.memoizeとか作ると便利だけど、他の関数型ライブラリとバッティングするからやめたほうがいいかも
  • 何にせよ、メモ化機構は一元化すべき

カリー化とメモ化を利用する

  • アリティが1以外だとメモ化は難しい

  • カリー化を使おう

    • アリティが1な関数の入れ子

メモ化を最大限に利用するために分解を行う

  • 問題を分解して、メモ化可能な小さい関数にせよ

メモ化を再帰呼び出しに適用する

  • 階乗の例
  • 【補】フィボナッチ数の計算とかでも有名ですね
  • スタックフレームを積み外ししなくて済む

再帰と末尾呼び出し最適化(TCO)

const factorial = (n, current = 1) => 
    (n === 0) ? current
              : factorial(n - 1, n * current);
  • 再帰ステップが最後にあると、命令型のループと同じ速度で実行できる
  • ES6に追加されたコンパイラの拡張仕様

非末尾再帰の動作

factorial(4)
  4 * factorial(3)
    4 * 3 * factorial(2)
      4 * 3 * 2 * factorial(1)
        4 * 3 * 2 * 1 * factorial(0)
          4 * 3 * 2 * 1 * 1
        4 * 3 * 2 * 1
      4 * 3 * 2
    4 * 6
  return 24

末尾再帰の動作

factorial(4)
  factorial(3, 4)
  factorial(2, 12)
  factorial(1, 24)
  factorial(0, 24)
  return 24

  • スタックの利用が効率化

    • n個のフレームを巻き戻す必要がなくなる

非末尾再帰を末尾再帰に変換する

  • 引数を使って結果をaccumulateする

    • デフォルト引数を使うとすっきり

コラム

  • トランポリンとサンク
  • 本書の範囲外