• Golang
  • 23 Sep 2017

    Go のジェネリクス

    Docs: https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/edit?pli=1#heading=h.vuko0u3txoew

    概要

    ジェネリクスとその問題の心臓は以下になります. (generic より)
    
    1. (C 方式) 放置. プログラマーを遅くさせる. しかし言語に複雑性を追加しない.
    
    2. (C++ 方式) コンパイル時特殊化もしくはマクロ拡張. コンパイルを遅くする. 大量のコードを生成し, それらは冗長であり, 複製されたコピーを排除する良いリンカを必要とする. 独立した特殊化は効率的かもしれないが, プログラム全体としては命令キャッシュを貧しく使うことになり苦しめられる. template の使用を削除したことで text segment がメガバイトから 10 キロバイトに縮小した単純なライブラリについて聞いたことがあります.
    
    3. (Java 方式) 全てを暗黙的にしまう. 実行を遅くする. C プログラマが書いた実装や C++ コンパイラが生成した実装と比較すると, Java コードはより小さいですが, 暗黙的なボクシングとアンボクシングのために空間計算量や時間計算量の面で効率が下がります. byte のベクトルは 1 byte あたり 1 バイトよりも大きな空間を使用します. ボクシングとアンボクシングを隠そうとすると, 型システムも複雑になる可能性があります. 一方で, 命令キャッシュをより良く使えるかも知れず, バイトのベクトルは別々に書き込むことが出来ます.
    
    ジェネリクスのジレンマとは: プログラマを遅くしたいか, コンパイラを遅くさせバイナリを肥大化させたいか, 実行速度を遅くさせたいか.
    

    一部分だけ雑に訳すとこのような感じ. バイトのベクトル? とかよくわかってないけれど…も, 概ねの雰囲気は分かった気になった.

    C++ 方式は最悪種類の数だけ生やす事になるので, 上に書いたようにバイナリの肥大化とかキャッシュが有効に使えなくなったり, みたいな問題があり Java 方式はバイナリの肥大化は招かないものの, いわゆる int とかのプリミティブ型のジェネリックな関数を呼び出した時にボクシングしたりして遅くなりますよねという話.

    上のドキュメントに書いてあったけど最近少しばかり話題の Rust は C++ 方式らしい. なるほど.

    バイナリの肥大化の問題は書き手の問題になるとは思うけれど, そもそも言語がそれを許さないようにする (自由度が低いようにする) 方が, 言語としては開発者に優しいのでそういう方針ならば, そのままいけばいいと思う.

    https://days2011.scala-lang.org/sites/days2011/files/ws3-1-Hundt.pdf

    ちょっと昔に golang と多言語を比較する論文を読んだことがあり, 上のリンクはそれで, 内容は大体忘れてしまったけれど たしか書き手を選ぶが C++ が最高の結果であり, golang は実行速度とかバイナリサイズが大きくて色々負けていて, これから改善していきたい, みたいな話だったような気がする. 今は結構人気が出てきたけれどもジェネリクスの追加を C++ 方式のようにバイナリの肥大化を招きかねないようなアプローチですることは無いだろうし, 実行速度が落ちるようなアプローチでも無いだろうなという気はする.