静的リンク・動的リンク・動的ローディングの違い

今日のネタはリンカの仕事について。低レイヤな話としてありがちだが、いかんせんバイナリを入力にバイナリを出力する処理なので直感的に理解しづらい。ってことで調べながらメモる。

リンカ(linker)とは何か

リンカ とは、コンパイルされたファイル(オブジェクトファイル)同士をつないで実行可能なファイルを作るプログラムである。ほとんどの場合、ソースコードはファイルごとにコンパイルされ、ファイルごとにオブジェクトファイルが生成される。他方、プログラム中で外部ファイルで定義されたシンボル(変数名や関数名など)を参照する場合がある。たとえばライブラリ中に定義された関数を呼び出す場合などである。リンカの役割は、このようなファイル内を見ただけでは正体不明のシンボルと外部ファイルに含まれる定義を紐付けることである。

リンカには静的リンクと動的リンクの2種類がある。以下にそれぞれについてざっくりまとめる。

静的リンク

静的リンクは、正体不明のシンボルを定義しているすべてのオブジェクトファイルを、動かしたいオブジェクトファイルの中に静的にコピーするようなやり方である。後述する動的リンクと違い、コンパイル時にすべてのリンク作業を完了できるため、実行時にリンク関連のエラーが起こることがない。一方、あらゆる依存先のファイルを1つのオブジェクトファイルに詰め込むので、ファイルサイズが大きくなる傾向がある。

個人的なイメージとしては、Docker みたいなコンテナにすべての依存関係を封じ込めてしまう発想と似ていると思う。ホストのシステム全体で見ると同じ依存関係があちこちに出てきて冗長であるが、実行時にコケないという性質はかなり重宝される。ストレージの容量が飛躍的に増えた現代では静的リンクがベターな選択肢になることも多いと思われる。

ここからは静的リンクによって実行ファイルを作る実験をしてみる。C 言語でやってもつまらないので C++ と Rust の組み合わせでやってみる。ホストマシンは Ubuntu 20.04.4。

まずはライブラリ側のコードとして適当な C++ のプログラムを定義する。引き算をする minus 関数を定義しているだけである。このファイルを hello.cpp と名付ける。

extern "C" {
    int minus(int a, int b);
}

int minus(int a, int b) {
    return a - b;
}

そしてこのファイルをライブラリとしてコンパイルする。まずは 拡張子.o のオブジェクトファイルを作って、拡張子 .aアーカイブファイルに追加する。静的リンクを使うときはアーカイブとしてまとめるのが一般的なやり方である。アーカイブ名を `libxxx.a" のようにするのは守るべき命名規則である。

$ g++ -c -o hello.o -static hello.cpp
$ ar rv libhello.a hello.o

次にこのライブラリを呼び出す Rust プログラムを以下のように定義する。リンク時に minus という関数が正体不明なので、このファイル単体では実行できない。

extern "C" {
    fn minus(a: i64, b: i64) -> i64;
}

fn main() {
    unsafe {
        println!("100-3 = {}", minus(100, 3));
    }
}

cargo を使って Rust プロジェクトをコンパイルする。このとき以下のようなビルドスクリプト build.rs を記述してやる。

fn main() {
    println!(r"cargo:rustc-link-search=native=/(省略)/clang_lib");
    println!(r"cargo:rustc-link-lib=static=hello");
}

1つ目の命令では、正体不明のライブラリがあったら clang_lib ディレクトリを探しに行けばよいことを教えている。ちなみに /lib/usr/lib はデフォルトで検索対象になっている。(man ld とかすればデフォルトのディレクトリを確認できる。)2つ目の命令でリンク方法が 静的(static)であることを教えている。

そして、プロジェクトをビルドし、その成果物であるプログラムを実行する。ちゃんとライブラリ側の minus 関数を呼び出して 100-3 を計算できたことが分かる。

$ cargo build
   Compiling invoke_c v0.1.0 (/(省略)/invoke_c)
    Finished dev [unoptimized + debuginfo] target(s) in 0.88s
$ target/debug/invoke_c 
100-3 = 97

静的リンクを実行して得られたオブジェクトファイルを覗いてみる。

$ readelf -s target/debug/invoke_c | grep minus
// Num:    Value          Size Type    Bind   Vis      Ndx Name
   572: 0000000000008025    22 FUNC    GLOBAL DEFAULT   14 minus

この結果から、オブジェクトファイルが持っているシンボルテーブルに含まれている minus というシンボルはオフセットが 0x8025 のアドレスに定義があることが分かる。

以上、静的リンクでした。

動的リンク

静的リンクとは対照的に、動的リンクではプログラムの実行開始直後にリンク処理が行われる。コンパイル時にはリンクは行われず、正体不明のシンボルはプログラムが実行されるまで正体不明のままである。ちなみに、この動的なリンク処理はオペレーティング・システムが担う役割である。

実行時に適切なライブラリが見つからないと実行時エラーが起きてしまう。一方で、ライブラリのコードを埋め込むわけではないので、複数のプログラムから利用されるライブラリが存在する場合はストレージ容量の節約になる。この利点が大きいので Linux では基本的に動的リンクが利用される。

ここからは先ほどと同様にして動的リンクの実験をしてみる。

まずは共有オブジェクト(shared object)としてライブラリのコードをコンパイルする。結果として拡張子 .so のファイルが得られる。

$ g++ -shared -o libhello.so hello.cpp 

cargo のビルドスクリプトは以下のようにする。dylib= によって動的リンクを行うことを示している。また、hello を指定することで実行時には libhello.so というライブラリが必要であることを示している。

fn main() {
    println!(r"cargo:rustc-link-search=native=/(省略)/clang_lib");
    println!(r"cargo:rustc-link-lib=dylib=hello");
}

そしてプロジェクトをビルドする。

$ cargo build
   Compiling invoke_c v0.1.0 (/(省略)/invoke_c)
    Finished dev [unoptimized + debuginfo] target(s) in 0.46s

まずは何も考えずにビルド成果物を実行してみる。

$ target/debug/invoke_c 
target/debug/invoke_c: error while loading shared libraries: 
libhello.so: cannot open shared object file: No such file or directory

このエラーメッセージは libhello.so という共有ライブラリが見つからないと言っている。この共有ライブラリがコンパイル時に指定されたんだから実行時に必要なはずだけど、それが見つからない状況である。ちなみに以下で libhello.so が必要であることは確認できる。

$ readelf -a target/debug/invoke_c | grep libhello.so
 0x0000000000000001 (NEEDED)             Shared library: [libhello.so]

この問題を解決する方法として、動的リンクによってライブラリを検索する場所を環境変数 LD_LIBRARY_PATH の値として設定すればよい。結果として以下のコマンドで実行に成功する。

$ LD_LIBRARY_PATH=/(省略)/clang_lib/ target/debug/invoke_c
100-3 = 97

ついでに生成されたオブジェクトファイルのシンボルテーブルを見てみる。

$ readelf -a target/debug/invoke_c | grep minus
// Num:    Value          Size Type    Bind   Vis      Ndx Name
   571: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND minus

以下の結果により minus というシンボルが未定義(UNDefined)であり、アドレスも適当な値として 0 で埋められていることが分かる。

また以下のコマンドの結果より、オペレーティング・システムがこのバイナリファイルを読んだときに動的にリンク処理を行うための情報が格納されていることが分かる。

$ readelf -a target/debug/invoke_c | grep ld-linux
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [ld-linux-x86-64.so.2]

インタプリタとして ld-linux-x86-64.so.2 が必要らしい。リンカなしでは生きてゆけない。

これで動的リンクについてはおしまい。

動的ローディング

最後に、動的リンクと混同されがちな 動的ローディング について説明する。ローディングとはオブジェクトファイルをメモリ上に載せる操作である。この時点でリンクとは別物である。

特に、動的リンクはオペレーティング・システムの仕事であるのに対して、動的ローディングはアプリケーションの仕事である。アプリが好きなタイミングで外部のオブジェクトファイルをメモリに載せて実行するような操作である。動的リンクはプログラム実行開始直後に行われるのに対し、動的ローディングは任意のタイミングで実行される可能性がある。

今日はもう眠いのでやりたくないが、動的ローディングの実験もしてみる。先ほど作った共有ライブラリを Python プログラムから呼び出す。

Python ファイルは以下の通りである。 これを main.py と名付ける。

import ctypes

libhello = ctypes.CDLL("/(省略)/libhello.so")
print("100-3 =", libhello.minus(100, 3))

ここでは CDLL という API によって動的ローディングを行っている。これは裏では dlopen などの API を呼び出している。そのソースコードこのあたり だと思われる。(ちなみに dlopen はシステムコールではなく共有ライブラリが提供する API である。最終的には mmap などのシステムコールが呼ばれる。)

プログラムを実行してみるとプログラムを動的にロードできていることが分かる。

$ python3 main.py 
100-3 = 97

めでたし。

PyTorch の推論時のオーバヘッドを調べてみた

論文投稿が終わって解放感がスゴい。勢いあまって PyTorch の推論の高速化について実験したのでその結果をここにまとめる。もちろん機械学習は勉強中なので手探りで実験しながら調べている感じである。アホみたいなことをしている可能性がある。

悩ましい(と思っている)ところ

ニューラルネットワーク用のライブラリといえば今は PyTorch やら TensofFlow やらが主流なんだろうけど、どちらも Python 向けに作られている。Python と聞くと遅いイメージがあるが、Python から API を叩くと裏では C++カリカリにチューニングされたプログラムが動いているので学習は効率的に行われる。別に不満はない。一方で推論時は、モデルに入力を食わせて出力が欲しいだけなのに、推論のたびに Python から C++ を呼び出すみたいなことが起こる。自分の機械学習の用途からすると1回の探索につき学習済みモデルを100万回くらい呼び出したいこともある。そうなると、言語をまたいでプログラムを実行するオーバヘッドが膨らみすぎるのである。処理の高速化のために機械学習を使いたいのに、機械学習を使うと実行時間が膨れ上がってしまう。これをどうにかしたい。そこでオーバヘッドを含む推論の高速化の方法を調べながら比較実験してみた。

適当なモデルを作る

まずは今回の実験用に適当なニューラルネットワークを定義する。以下のようにしてみた。

class MyNN(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.a = nn.Linear(2, 8)
        self.b = nn.Linear(8, 8)
        self.c = nn.Linear(8, 1)

    def forward(self, x):
        x = nn.ReLU()(self.a(x))
        x = nn.ReLU()(self.b(x))
        x = self.c(x)
        return x

隠れ層が1つだけのニューラルネットワークを定義している。そして適当に入力を用意して学習させてみる。PyTorch でよく見る感じの、確率的勾配法によって重みを調整する流れである。最後に、学習したパラメータを保存している。

(省略)
model.train()
for _ in range(n_epochs):
    for x, y in zip(X, Y):
        optimizer.zero_grad()
        predicted = model(x)
        loss = loss_fn(predicted, y)
        loss.backward()
        optimizer.step()

torch.save(model.state_dict(), "model_py.pt")

コード全体は Gist に置いた。本記事のコードはすべて同じ Gist のページに置いている。今回は  f(x_1, x_2) = | x_1| + x_2 という関数を近似してみた。どんなパラメータであっても推論速度に差は出ないのでどうでもよいのだが。

Python でロードして呼び出す場合

ここからは推論にかかる時間を計測する。まずはおそらく推論時のもっとも素朴なやり方であるモデルをロードするやり方をやってみる。以下ではモデルをロードした上で100万回の推論を行っている。

size = 1_000_000
input_values = list(map(
    lambda _: [random.uniform(-10, 10),
               random.uniform(-10, 10)],
    range(size)))
X = torch.tensor(input_values)

model = MyNN()
model.eval()
model.load_state_dict(torch.load("model.pt"))

import time
start = time.time()
for x in X:
    model(x)
print(time.timeit() - start)

実行時間は 124 秒だった。これは遅い。日が暮れる。

Python で TorchScprit を呼び出す

次にやってみるのは TorchScript というテクノロジーである。モデルを Python の実行環境に依存しない形で保存したりロードしたりできるらしい。Python に非依存である代わりに TorchScript 言語専用のインタプリタが存在しているようなので、ある意味新たな言語を仲介してモデルにアクセスできるようになっていると思ったらよさそう。仕組みはよく分かっていないが JavaC++ からも TorchScript を叩きやすいらしい。もしかして Java から TorchScript を利用する場合は JVM 上で動く TorchScript のインタプリタが存在している?よく分からんが、まずは Python から使ってみよう。

TorchScript のチュートリアル を見ながら進める。モデルを TorchScript の形式で保存するのは簡単で、以下のようにモデルを保存する部分だけ書き換えればよい。

example = torch.tensor([random.uniform(-10, 10), random.uniform(-10, 10)])
traced_script_module = torch.jit.trace(model, example)
traced_script_module.save("../model_torchscript.pt")

モデルに適当な入力を食わせる tracing という方法でやってみた。どうやら TorchScript として保存するためには Python インタプリタを動かしてみることに意味があるらしい。動的解析みたいに見えるが、おそらくモデルの保存は安全に行われると思う。謎テクノロジーだ。

そして TorchScript をロードして100万回推論を実行してみた。

model = torch.jit.load("../model_torchscript.pt")
start = time.time()
for x in X:
    _ = model(x)
print(time.time() - start)

実行時間は 54 秒だった。同じ Python でもオーソドックスなモデルの保存方法より推論時の性能が向上することが分かった。なにか最適化が走っているのだと思われる。Python でモデルを保存するときは TorchScript でやるのが今後の主流になるのかな。

Java で TorchScript を呼び出す

TorchScript として保存したモデルは他のプログラミング言語から呼び出すのが簡単らしい。ってことで次は Java からモデルをロードして推論を実行してみた。このソースコード を参考に実装した。

実装した Java コードは以下である。

Module mod = Module.load("../../model_torchscript.pt");
 int size = 1000000;
(中略)
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
    Tensor inputs = Tensor.fromBlob(
            data[i],
            new long[]{2} // shape
    );
    mod.forward(IValue.from(inputs));
}
long elapsed = (System.currentTimeMillis() - start);
System.out.println(elapsed);

実行時間は 35 秒であった。わりと速い。

以下、Java から PyTorch を動かすためのメモ:

まず、Java プロジェクトの pom.xml に以下を追加した。これで Pytorch を動かすための Java API が叩けるようになる。

    <dependencies>
        <dependency>
            <groupId>org.pytorch</groupId>
            <artifactId>pytorch_java_only</artifactId>
            <version>1.11</version>
        </dependency>
    </dependencies>

また、裏で動く Pytorch として ここの指示 の通りに LibTroch (version 1.11.0) をダウンロードしてきて Java の実行時の VM 引数に -Djava.library.path=/(省略)/libtorch/lib を指定した。

C++ から TorchScript を呼び出す

同様に、C++ から TorchScript を呼び出してみる。

model = torch::jit::load(argv[1]);
int size = 1000000;
(中略)
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
for (size_t i = 0; i < size; i++) {
    int64_t shape[] = {2};
    std::vector<torch::jit::IValue> inputs{torch::from_blob(data[i], shape)};
    model.forward(inputs);
}
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "[ms]" << std::endl;

実行時間は 44 秒であった。Java より速いかと思ったら意外とそんなことはなかった。なぜだろう。

C++ API からモデルを呼び出す

いろいろ調べたところ、TorchScript すら遅いと感じる場合は PyTorch の C++ API を使うとよいらしい。PyTorch の裏側で実行される LibTorch というライブラリを直接叩けるようだ。TorchScript みたいにインタプリタを挟むのではなく、C++ のピュアなデータ構造として表現されたニューラルネットワークを使って推論を実行できるってことだろう。

今回は学習から C++ API を使ってやる必要がある。このチュートリアル を見ながらやってみた。コードは以下のような感じである。

int main()
{
    (中略)
    for (size_t epoch = 1; epoch <= n_epochs; epoch++) {
        for (size_t i = 0; i < size / batch_size; i++) {
            torch::Tensor x = X[i];
            torch::Tensor y = Y[i];
            optimizer.zero_grad();
            torch::Tensor predicted = model->forward(x).reshape({batch_size});
            torch::Tensor loss = torch::mse_loss(predicted, y);
            loss.backward();
            optimizer.step();
        }
    }
    torch::save(model, "../model_cpp.pt");
}

基本的には Python から PyTorch を使う時と同じような流れで C++ でプログラムが組めるようになっている。

そして例によって100万回推論を実行してみる。

int main()
{
    c10::InferenceMode guard(true);
    auto model = std::make_shared<MyNN>();
    torch::load(model, "../model_cpp.pt");
    (中略)
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    for (size_t i = 0; i < size; i++) {
        model->forward(input_values[i]);
    }
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "[ms]" << std::endl;
}

実行時間は 9 秒であった。めっちゃ速い。これだ。

まとめ

各設定で推論を100万回実行したときの実行時間を以下にまとめる。

設定 実行時間
Python 124 秒
TorchScript from Python 54 秒
TorchScript from Java 35 秒
TorchScript from C++ 44 秒
C++ API 9 秒

推論時のオーバヘッドを減らせる C++ API が最強だけど、Java から TorchScript を呼び出すくらいでも悪くないケースも多いかもしれない。Rust から C++ API を叩けるラッパーとかもあるっぽいので、そのあたりを触ってみたい。C++ よりは Rust でプログラム書きたいので。

github.com

おしまい。

【読書メモ】Linuxで動かしながら学ぶTCP/IPネットワーク入門

定期的にやってくる「特に勉強したいこともないしネットワークのことでも勉強するか」ってシーズンが来た。ネットワークの考え方とか前よりは分かってきたが、実際のところどういう仕組みなのかピンと来ない。ってことで今回は書籍「Linuxで動かしながら学ぶTCP/IPネットワーク入門」を買って動かしながらやってみたメモ。

書籍については、この著者が書いたはてなブログの記事を参照のこと。

blog.amedama.jp

第一章 はじめに

この本では Network Namespace なる技術を使ってネットワークを構築してゆくらしい。普段から Ubuntu ユーザなので環境構築で特に困りそうなことはない。

第二章 TCP/IP とは

この章ではプロトコルの階層構造とか ping コマンドのような基本的な事項について書かれている。さすがにこのあたりはだいたい知っている。ping は裏で ICMP(Internet Control Message Protocol)プロトコルの echo request/reply が使われているらしい、へー。traceroute コマンドの動作原理についても書かれている。IP ヘッダのフィールドである TTL(Time to Live)がルータを通過するごとにデクリメントされる性質を利用しているらしい。なるほど。ルータはルーティングの情報をルーティングテーブルで管理する。宛先の IP アドレスに応じて via(ネクストホップのルータ)や dev(デバイス)が指定される。ふむふむ。

第三章 Network Namespace

この章では network namespace を使いながらルーティングを設定する。手を動かしながらやってみるとルータを介した ping が動くようになる。ネットワークインターフェイス(veth)ごとに名前や IP アドレスを設定する。network namespace ごとにルーティングテーブルを設定する。

今回の場合は、ルーティングテーブルを設定するときに「宛先がどんな IP アドレスのときにどこに転送する」ことを人間が教えてあげる。ルーティングテーブルは局所的なルールを定義するものだが、それを定義する人はネットワークの全体を把握しないといけない。インターネットを構成するルータではそれが難しいので、動的にルーティングを制御する仕組みとして BGP(Border Gateway Protocol)が存在する。なるほど。

第四章 イーサネット

この章はデータリンク層イーサネットについて書かれている。IP のパケットは複数のフレームを経由して目的の IP アドレスまで運ばれる。イーサネットではフレームを運ぶ先は MAC アドレスによって与えられる。IP アドレスから MAC アドレスは ARP(Address Resolution Protocol)プロトコルを用いて解決される。

前の章の IP のルーティングの話と総合して IP による通信の仕組みを整理してみる。まず、目的地点の IP アドレスが与えられる。ルーティングテーブルを参照することで、目的地点の IP アドレスから次に送信すべき IP アドレスを特定する。そして ARP によって、次に送信する IP アドレスから MAC アドレスを特定する。MAC アドレスが分かったのでイーサネットの仕組みでフレームを送信できる。このように、次の IP アドレスの特定と MAC アドレスの特定を繰り返すことで目的地までバケツリレー的にパケットが運ばれる。

後半は、ブリッジを使うことで複数のネットワーク機器を接続できることが書かれている。network namespace を使う場合はブリッジ用のネットワークスペースを作り、そこに type bridge のネットワークインターフェイスを追加する。それを mater とするリンクを追加してゆけばよい。

第五章 トランスポート層プロトコル

この章ではトランスポート層プロトコルとして UDPTCP を触ってみる。この章に至るまでネットワーク層データリンク層と下ってきたが、ここでトランスポート層まで上る。ネットワーク層までのプロトコルでは、どのパケットがどのアプリケーションのためのものか判別できないという課題があった。これに対してトランスポート層プロトコルでは、パケットにポートの情報を持たせることでどのアプリケーションに向けたものであるかを明示する。

UDP ではポートを指定してパケットを送信できる。これは nc コマンドを使って実験できる。nc コマンドは CTF(capture the flag)をやったときに使ったことがある。サーバ側のポート番号は上位のプロトコルによってだいたい固定で、クライアント側のポート番号はランダムに払い出されることが多い。

TCP では UDP とは違ってパケットの損失の検知や順序を保つことができる。よりリッチな機能を提供するといえる。通信の開始時にスリーウェイハンドシェイクを行う。TCP は信頼性が高いのでより上位の HTTP とか SMTP プロトコルでは前提となっている。

第六章 アプリケーション層のプロトコル

この章ではアプリケーション層の HTTP, DNS, DHCP について書かれている。これまでの章の内容を理解していれば、これらのプロトコルTCP/IP を活用したものであることがよく分かる。

第七章 NAT

この章は NAPT について書かれている。NAPT は、プライベート IP からグローバル IP とトランスポート層のポート番号のペアへ変換する技術である。もちろん一対一対応しているので逆方向に変換もできる。実際にはパケットの書き換えを行っている。NAPT って教科書とかに書いてあるので知識として知っていたが、パケットの書き換えをしているイメージはなかった。言われてみればそりゃそうだ。

前半はソースとなる IP アドレスを書き換える Source NAT について実験できる。今までとの違いは iptables にルールを追加する部分にある。具体的には、対象となる IP アドレスの範囲に対して MASQUERADE(マスカレード)を指定する。「マスカレード」って仮面舞踏会って意味なんだよな。なんとオシャレなネーミング。ちなみに iptables は network space ごとに存在している。

後半は Destination NAT について書かれている。いわゆる「ポートを解放する」ことである。サーバとしてリクエストを受け付けるときにグローバル IP アドレスが埋められたパケットがやってくるので、それをプライベート IP アドレスに変換する処理である。これは iptables で DNAT を指定することで実現される。

第八章 ソケットプログラミング

いよいよ最後の章である。といってもソケットを使ったプログラミングをする話なので、ソフトウェア屋さんである自分にとっては API 叩いてるだけに見える。ただし、ソケットを使ったプログラミングは TCP とか UDP のようなトランスポート層プロトコルに従った通信を実現するものであることは意識したい。HTTP とかのアプリケーション層の話はいったん忘れても問題ない。もし HTTP に代わる天才的なアプリケーション層のプロトコルを思いついたら、この章に書いてあるみたいな感じでソケットプログラミングをやってみよう。他方、TCP でも UDP でもないトランスポート層プロトコルを思いついたら、必ずしもソケットを活用できるわけではない。もっと低レイヤな部分から作ろう。

全体的な所感

一言で言うとめっちゃ良い本であった。分かりやすい。読者に TCP/IP のエッセンスを理解させたいという気合いが感じられた。これまでのネットワークの書籍って独りよがりなものが多いというか、事実を述べるだけになっているものが多い印象がある。ネットワーク屋さんは仕様や仕組みを深く理解してこそ力を発揮できるというのはよく理解できるので、そのあたりについて細かく書かれた書籍が重宝されるのは分かる。ただ、初学者がまず理解すべきなのはプロトコルの階層構造の意義とか、階層構造の概念が現実世界でどのように実装されているのかとか、各レイヤーでどういう情報が加わって何を達成できるようになるのかとかだと思う。この書籍はこういうエッセンシャルな部分を無駄なく教えてくれている。

積率母関数の覚え方

統計で出てくる積率母関数って覚えてもすぐに忘れますよね。印象づけて覚えるためにマクローリン展開との関連性をメモる。

覚えたいこと

確率変数 X積率母関数 M_X(t) は以下である。

M_X(t) = E [ e^{tX} ]

この関数を使うと以下のようにして n 次のモーメント E [ X^n ] を計算できる。

E [ X^n ] = \left.\frac{d^n M_X}{dt^n}\right|_{t=0}

印象付けて覚えよう

指数関数  e^xマクローリン展開 は以下である。

e^x = 1 + x + \frac{x^2}{2!}+ \frac{x^3}{3!} + \dots

xtX に置き換えると以下となる。

e^{tX} = 1 + tX + \frac{(tX)^2}{2!}+ \frac{(tX)^3}{3!} + \dots

期待値 E は線形性があるので以下が成り立つ。

E[e^{tX}] = E[1] + E[tX] + E[\frac{(tX)^2}{2!}] + E[\frac{(tX)^3}{3!}] + \dots

定数倍を期待値の外に出すと以下となる。

E[e^{tX}] = E[1] + t E[X] + \frac{t^2}{2!} E[X^2] + \frac{t^3}{3!} E[X^3] + \dots

これが積率母関数 M_X(t) である。

両辺を微分してゆくと以下のようになる。

M_X(t) = E[1] + t E[X] + \frac{t^2}{2!} E[X^2] + \frac{t^3}{3!} E[X^3] + \dots\\
\frac{dM_X}{dt} = E[X] + t E[X^2] + \frac{t^2}{2!} E[X^3] + \frac{t^3}{3!} E[X^4] + \dots\\
\frac{d^2 M_X}{dt^2} = E[X^2] + t E[X^3] + \frac{t^2}{2!} E[X^4] + \frac{t^3}{3!} E[X^5] + \dots\\
\frac{d^n M_X}{dt^n} = E[X^n]  + t E[X^{n+1}] + \dots

このように n 回微分して  t=0 を代入すると右辺は n 次のモーメント  E [ X^n ] だけが残る。

めでたし。

f:id:t-keita:20220224020807p:plain:w0

【読書メモ】Googleのソフトウェアエンジニアリング16, 18章

前回 に続き GoogleSWE 本を読んでメモる。

書籍は以下である。

www.oreilly.co.jp

今回は以下の2つの章を読む。

  • 16章 バージョンコントロールとブランチ管理
  • 18章 ビルドシステムとビルド哲学

16章 バージョンコントロールとブランチ管理

16.1 バージョンコントロールとは何か

内容: バージョンコントロールシステムはさまざまな理由から重要である。
所感: バージョン管理の重要さはよく分かっているので感想は特にない。むしろ無かったら即死する。

内容: バージョンコントロールシステム(Version Control System, VCS)には中央集権的 VCS と分散 VCS がある。中央集権的 VCS(Centralized VCS) は単一の中央リポジトリーがあるモデルである。Subversion がその代表例である。一方で、分散 VCS (Distributed VCS)は中央リポジトリーについての制約が強制されないモデルである。Git がその代表例である。ちなみに Google では分散 VCS を内製してものを使っている。
所感: Google では Git っぽいものを内製しているらしい。知らなかった。Google保有するくらいの巨大なコードベースを中央集権的に管理するとなると Git では力不足らしい。

内容: 中央集権的 VCS ではトランクにコミットされたものが信頼できる現在のバージョン、つまり Source of Truth である。一方で、分散 VCS の概念には Source of Truth は存在しない。しかし実際は、特定のリポジトリーの特定のブランチを Source of Truth として宣言することがややこしさを回避することために重要である。
所感: 分散的な環境において「ここを見れば最新」が明確であることの重要性について。普通の開発だったらプロジェクトごとにルールが決められるだけの話であって特に課題になることはなさそう。Google のコードベースは巨大で多様なので Source of Truth の明示が重要なんだろう。

16.2 ブランチ管理

内容: 進行中の作業(work in progress)はブランチに似ている。
所感: ここの主張がよく分からなかった。あえてブランチを作らなくても VCS がブランチ管理相当のことをやってくれるので、ブランチは特別(崇高)なものじゃないよって言ってる?

内容: 開発(dev)ブランチは特定の機能開発用のブランチであり、トランクの安定性向上を目的として作成される。しかし、dev ブランチは理にかなっていないので、トランクだけを使うトランクベース開発(trunk-based development)にすべき。安定性の問題は CI によってテストをたくさんすれば解決できる。dev ブランチを後でまとめてマージするより楽。
所感: ここは一般的なブランチの使い方を否定する内容になっている。確かに、ブランチを切るとマージ作業がややこしくなるイメージはある。なるほどなぁ。ちなみにリリースブランチはトランクから cherry-pick するだけのものなのであまり害はないらしい。

16.3 Googleでのバージョンコントロール

内容: Google ではほぼすべてのプロジェクトを単一のリポジトリで管理する "モノリポ" を採用している。リポジトリ内の依存関係において、選択すべきバージョンは1つしか存在してはならないという原則がある。選択の余地を作らないことがスケーリングには重要である。
所感: Source of Truth の話と同じことを言っていると理解した。しかし常に最新版へ依存しないといけないってけっこう辛くないか。バージョンを固定したくなりそう。たとえばライブラリの API の呼び出し方が変わったときは、それに合わせてクライアント側の呼び出し部分を変える必要があるってことよな。こういうのは例外的に dev ブランチでもよいってことなんだろうが、本当に例外的なんだろうか。

16.4 モノリポ

内容: Google ではモノリポを採用している。利点は、あらゆるプロジェクトの最新版が常に見えていることやリポジトリを探す手間が小さいことである。一方で、必ずしもそれがどの環境にとっても最適とはいえない。重要なことは選択の機会を無くすことである。最近は Git サブモジュールなど、モノリポを模倣するようなメカニズムがある。
所感: Git submodule って知らなかった。依存するリポジトリをプロジェクトのディレクトリ配下で管理できるらしい。

18章 ビルドシステムとビルド哲学

18.1 ビルドシステムの目的

内容: ビルドとはソースコードを実行可能なバイナリへ変換する行為である。速さと正しさが求められる。ビルドシステムはテストなど自動化の文脈でも有用である。
所感: ビルドシステムの大切さは理解できているつもりなのでまぁそうだよなぁという内容。

18.2 ビルドシステムがないと何が起こるか

内容: コンパイラだけだと依存関係の解決ができない。ビルド用にシェルスクリプトを書いてもスケールしない。
所感: ビルドスクリプトを叩くときは90%くらいコケる気持ちで臨むのでよく分かる。

18.3 現代的ビルドシステム

内容: シェルスクリプトや Ant、Maven などはタスクベースのビルドスクリプトと呼ばれ、任意のタスクを実行できるのが特徴である。それゆえ(安全側に倒す必要があるため)ビルドの並列化が難しい。また、変更したコードのバイナリへの影響を追跡できずインクリメンタルビルドを実現することも難しい。
所感: 個人的には Maven を使うことが多いが大して使いにくいと感じたことはなかった。もっと大規模なシステムをビルドしたり、他人が作ったビルドスクリプトをメンテナンスしたら不便さが分かるのかもしれん。

内容: 上記の課題に対してアーティファクトベースのビルドシステムが有効である。Google で使用している Blaze がその例である。エンジニアはビルドのために what を指定するだけで how は指定しない。エンジニアは限られた命令セットしか使えないが、それがビルドシステムの効率化に寄与している。
所感: アーティファクトベースのビルドシステムを関数型プログラミングに例えているのが分かりやすい。端的に言うと referential transparency(副作用がなく状態を持たない性質)が保たれる操作の組み合わせによってビルドを構成することで、並列計算も値の再利用もできるという感じ。dynamnic programming とかメモ化とかそういう計算。なるほど。ちなみにこっちの方式のデメリットってあるんだっけ?

内容: ビルドの時の依存関係を外部からダウンロードする場合はセキュリティ面での考慮を要する。Bazel では、ダウンロードした外部ファイルのハッシュ値を管理することでバージョンが勝手に変わるのを検知する。新たなバージョンを受け入れる場合はレビューで承認される必要がある。
所感: URL だけでは依存関係を一意に管理しきれないという話だな。なるほど。

内容: 以下の図はリモートキャッシュを用いた分散ビルドの方式である。中央にビルドの出力がキャッシュされている。各ユーザがビルドを実行したとき、すでに欲しいものがキャッシュに存在すればダウンロードしてくる。存在しなければ自らビルドする。

f:id:t-keita:20220127232047p:plain:w600

所感: 共有キャッシュが機能するのはアーティファクトベースのビルドシステムを採用しているからだと理解した。同じ素材からは常に同じ料理が作られるのがポイント。

内容: 続いて以下の図はリモート実行による分散ビルド方式である。中央のビルドマスターがビルドタスクを受け付け、実際のビルド処理はワーカーに投げる。もちろんキャッシュも利用する。

f:id:t-keita:20220127232753p:plain:w600

所感: こちらはアーティファクトベースのビルドシステムの並列可能性がポイント。一般的な master/slave 方式の分散処理だと思う。最近は master と slave って言わないほうがいんだっけ。

内容: そして Google の分散ビルドシステムは以下のような仕組みである。キャッシュをダウンロードしたり、新たなビルドタスクをリモートに投げれるようになっている。

f:id:t-keita:20220127233305p:plain:w600

所感: 結局のところ、ビルドの計算リソースや成果物を会社単位でシェアしているのでモノリポでも上手く運用できているんだな。このくらいの仕組みならオープンソースでも再現できるらしい。本当か。とはいえビルドができて分散処理ができてキャッシュを管理できたらいいのか。

18.4 モジュールと依存関係を扱う

内容: ビルドのターゲットの単位は好きに決めることができる。小さな単位でターゲットを定義していくことが推奨である。各ターゲットの可視性は適切に絞ろう。
所感: ビルドするにあたり考えたこともない課題感だが言ってることは理解できる。Dockerfile から Docker イメージをビルドするときに RUN を細かく分けるか、コマンドを && で連結して1つの RUN にするかみたいな話だな。再計算とストレージのトレードオフ

内容: Blaze では、推移的に依存しているライブラリを直接呼び出すのを禁止している。その分、依存関係の記述量が増えるデメリットがあるが、保守性の向上によるメリットの方が大きいことが経験的に分かっている。
所感: pandas を使いたいときに pandas を依存関係に追加しても numpy は自動的に追加されないみたいな話。Python だったらけっこう面倒くさそうだが、Java とかだったらあまり嫌なケースを思いつかない。

内容: 外部への依存関係の管理には単一バージョンルールが適用される。つまり、外部ライブラリのバージョンを全体として統一する。ダイヤモンド依存関係を回避するのが目的である。一方で、既存のバージョンとの整合性を保つためには推移的な依存関係は自動でダウンロードするわけにはいかない。すべての依存関係のバージョンを明示的に管理する必要がある。
所感: これはかなりスゴイ話。推移的な依存関係って膨大な数になるので、すべての整合性が取れる組み合わせが存在するのかすら疑問。Python の依存関係とかヤバそう。適当に pip を叩きまくるだけで環境が壊れるんだぞ。

全体的な所感

まず、16章「バージョンコントロールとブランチ管理」がすごく読みづらかった。翻訳の問題かと思って英語版を見てみたがそれも読みづらい。3人の著者がいるので章によって読みやすさが違うのか。

今回読んだ2章ともに運用が非効率化する原因を徹底的に潰し、それによって生じる課題はマシンパワーや自動化の仕組みで解決するって感じだな。Source of Truth が不明になることを徹底的に潰すため、モノリポかつトランクベースで開発をしている。これには膨大なコミットを捌く VCS が必要である。そしてビルドがカオスになるのを避けるためアーティファクトベースのビルドシステムを使い、おまけに分散ビルドを実現しているって感じ。

ちなみにモノリポにおけるマイクロサービスってどう開発されるのか気になった。自チームのサービスの API を更新する場合、通信相手のサービス内の呼び出し箇所も一緒に修正してあげるのかな。

必要条件と十分条件の覚え方

必要条件と十分条件ってどっちがどっち向きか分からなくなりますよね。

めっちゃシンプルな覚え方を高校生の時に編み出したので紹介します。

p は q であるための...

 p \rightarrow q

のように 矢印が成り立てば 十分 条件

 p \leftarrow q

のように 矢印が成り立てば 必要 条件

ところでみなさん、右利きですか?左利きですか?

はい、右利きですよね。生活するうえで、

手さえあればだいたいのことは 十分 ですね

ただし、たまには

手も 必要 ですね

おしまい。

matplotlib でフォントを埋め込む方法

matplotlib とかその派生の seaborn で作った図(PDF)を論文に貼りたいが、その図にフォントが埋め込まれないときの対処メモ。焦らず、まずは心を落ち着けよう。

症状

PDF ファイルのフォントの埋め込み状況を確認すると Type3 フォントが埋め込まれてない。フォント名としては DejaVuSans とか。ヤバイ、カメラレディの提出に間に合わない。

対処方法1

matplotlib で図を生成するとき、Type3 フォントではなくTrueType フォントを使うように指定する。

具体的には、図を描画する前に以下の命令を実行する。

matplotlib.rc('pdf', fonttype=42)

これでフォントが埋め込まれた。以下で確認できる。

$ pdffonts demo.pdf 
name                                 type              encoding         emb sub uni object ID
------------------------------------ ----------------- ---------------- --- --- --- ---------
DejaVuSans                           CID TrueType      Identity-H       yes no  yes     24  0
DejaVuSans-Bold                      CID TrueType      Identity-H       yes no  yes     15  0

何をやっているか?

使用した matplotlib.rc 関数の API は以下にある。

matplotlib.org

PDF の設定についてはこのあたりに書かれている。

### PDF backend params
#pdf.compression:    6  # integer from 0 to 9
                        # 0 disables compression (good for debugging)
#pdf.fonttype:       3  # Output Type 3 (Type3) or Type 42 (TrueType)
#pdf.use14corefonts: False
#pdf.inheritcolor:   False

デフォルトが Type3 フォントで、42 にすると TrueType フォントが使われるということらしい。なぜか TrueType にするとフォントが埋め込まれる。ラッキー。

対処方法2

上記の方法はサブセット埋め込み(sub)になっていないのでファイルサイズが大きい。

そんなときは以下のように pgf バックエンドで描画するとよい(ただし実行には LaTeX 環境の構築が必要)。

plt.savefig("demo.pdf", backend="pgf")

フォント名が変わったけど必要な文字だけサブセット埋め込みになっているのでいい感じ。

$ pdffonts demo.pdf 
name                                 type              encoding         emb sub uni object ID
------------------------------------ ----------------- ---------------- --- --- --- ---------
EJSLOC+DejaVuSans                    CID TrueType      Identity-H       yes yes yes      7  0

何をやっているか?

PDF の描画を pgf というバックエンドにより行っている。LaTeX の処理系を使っている。詳細は以下にある。

matplotlib.org

おしまい。

■ 参考