🐍

BeartypeのRuntime型チェックのオーバーヘッドを見てみる

に公開
Python 3
tech

結論

  • たらい回し関数の場合5倍以上遅くなりオーバーヘッドは顕著
  • ただし一回当たりのチェックは短めなので関数の実行時間に応じてRuntime型チェックするかは選んだほうが良い

概要

  • BeartypeでRuntime型チェックできるけど実行速度どうなの？と思った
  • 関数呼び出し毎にデコレータから型チェックが走るので関数呼び出しコストが増えているはず
    • 関数呼び出しコストを最大化するため、たらい回し関数で検証
  • BeartypeによるRuntime型チェックありなしバージョンのたらい回し関数を作成して実行速度を比較してみた

実験内容

  1. たらい回し関数を作成
    • 数式・実装コードは下記に記載
      • メモ化のような高速化施策はしない
    • beartypeデコレータをつけることでRuntimeの型チェックが有効化される
      • xなどのアノテーションにfloatのような異なる型付けを行うとAssertionが発生
\begin{align*} Tarai(x, y, z) = \{ \\ &x: (x \leq y) \\ &Tarai(Tarai(x - 1, y, z), Tarai(y - 1, z, x), Tarai(z - 1, x, y)):(otherwise) \\ \} \end{align*} 
@beartype
def tarai_bear(x: int, y: int, z: int) -> int:
    global CALL_BEAR
    CALL_BEAR += 1
    if x <= y:
        return y
    else:
        return tarai_bear(
            tarai_bear(x - 1, y, z),
            tarai_bear(y - 1, z, x),
            tarai_bear(z - 1, x, y),
        )
  • 20回ずつ測定して処理時間を比較
  • Taraiへの入力は Tarai(12, 6, 0)で固定 (12604861回たらい回し関数が呼び出される)
  • 平均・標準偏差・関数呼び出し1回あたりの処理時間差を出力
検証コード
from beartype import beartype
import time
import numpy as np

CALL_BEAR = 0
CALL = 0


@beartype
def tarai_bear(x: int, y: int, z: int) -> int:
    global CALL_BEAR
    CALL_BEAR += 1
    if x <= y:
        return y
    else:
        return tarai_bear(
            tarai_bear(x - 1, y, z),
            tarai_bear(y - 1, z, x),
            tarai_bear(z - 1, x, y),
        )


def tarai(x: int, y: int, z: int) -> int:
    global CALL
    CALL += 1
    if x <= y:
        return y
    else:
        return tarai(
            tarai(x - 1, y, z),
            tarai(y - 1, z, x),
            tarai(z - 1, x, y),
        )


def measure_bear():
    start = time.perf_counter_ns()
    result = tarai_bear(12, 6, 0)
    end = time.perf_counter_ns()
    # print((end - start) * 1e-9)
    assert result == 12
    return end - start


def measure():
    start = time.perf_counter_ns()
    result = tarai(12, 6, 0)
    end = time.perf_counter_ns()
    assert result == 12
    return end - start


if __name__ == "__main__":
    n_check = 20
    ret_bear = np.array([measure_bear() for _ in range(20)])
    ret = np.array([measure() for _ in range(20)])

    mean_bear = np.mean(ret_bear) * 1e-9
    mean = np.mean(ret) * 1e-9
    assert CALL_BEAR == CALL

    print(f"Mean Execution time: w/ beartype: {mean_bear} s, w/o beartype: {mean} s")
    print(
        f"Standard Deviation: w/ beartype: {np.std(ret_bear * 1e-9)} s, w/o beartype: {np.std(ret * 1e-9)} s"
    )
    print("Overhead beartype:", mean_bear / mean)
    print(
        f"Beartype Overhead Per Function Call: {(np.sum(ret_bear) - np.sum(ret)) / CALL} ns"
    )

実験結果

  • beartypeが無効な場合と比較して6倍近く低速化している
  • 一方で1回あたりのbeartypeのチェックのコストは高々nsオーダーであることもわかる
    • 関数自体の処理が軽いケースではbeartypeの型チェックによるオーバーヘッドの影響が大きくなる
Mean Execution time: w/ beartype: 5.0738939289500005 s, w/o beartype: 0.858479332 s
Standard Deviation: w/ beartype: 0.20081855470630736 s, w/o beartype: 0.02991053195752637 s
Overhead beartype: 5.9103274124600595
Beartype Overhead Per Function Call: 334.42769396267045 ns
Beartype 平均実行時間 (s) 標準偏差 実行時間増加量
なし 0.858 0.029 x1(基準)
あり 5.074 0.200 x5.91

感想

  • nsオーダーで型チェックができるなら支払うべきコストな気がする
  • 速度を追求するならBeartypeの型チェックを無効化する機能も欲しいかも
    • 一応python -O main.pyでassertを完全に無効化すればほぼ同等になる

次の検証

  • 関数呼び出しコストの影響の小さいプログラムでの検証 (TODO)
  • JaxTypingを使って機械学習モデルをruntime型チェックしてみる (TODO)
  • 型チェックコストの大きいクラスを作ってみる (TODO)

Discussion