iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

GPT-4 Technical Report

LLM

発表生放送

www.youtube.com

  • 単語の頭文字を指定して文章を書かせたり、rhyming poemを書かせる
  • GPT-4と会話するためのdiscordのbotをGPT-4に書かせ、エラーメッセージを貼り付けてデバッグさせ、そのままbotをnotebook上で動かして、デモ用のdiscordにデプロイする
  • そのdiscordで視聴者から送られてきた画像をGPT-4に解釈させる
  • 事前に用意したかなり雑なスケッチをHTML/javascriptに変換させる
  • 税制の文章をぶちこんで"TaxGPT"してもらう

すごいね

Technical Report

https://cdn.openai.com/papers/gpt-4.pdf

Adding Conditional Control to Text-to-Image Diffusion Models

拡散モデル 機械学習

arxiv.org

背景

巷で超人気のControlNetの論文。promptによる画像の制御はとても難しく、どちらかというと気に入るものが出てくるまでガチャをする（せざるを得ない）状況だったのが、この論文により、構図などを具体的に指定できるようになったので、AIアート生成界隈(?)ではかなり話題になっている。

一方、技術的には、実はそういったconditionを拡散モデルに入れること自体はとても自明で自然なんですよね。そんなに革命的ということはない。じゃあなんで今まで出来なかったかというと、現実的には、そういった学習に使えるデータ数が少なく、モデルのfinetuneでキレイな画像を生成する能力を破壊しちゃうのが課題だった。

（かなり俺の主観あり）

貢献

なんかいい感じにスムーズにfinetuneできそうな機構をくっつけてfinetuneしたら良かったっぽい。元のモデルの重みは固定しつつ、横にもう一個モデルをくっつけて、そいつを最初は重みゼロで少しずつそっちに移行するような感じでfinetuneするらしい。

感想

結構ヒューリスティクス的な印象も強いが、現実的に結構うまく行ってるので、逆に色々なところで使えるテクなのかもしれない。trainableな重みを最初ゼロにして横にくっつけるのは、ResNetでBNのgammaをゼロにするのを思い出しますね。

T2Adapterとかいう少しあとに出たやつが似たような感じでもっとすごいという噂もある。

Lecture 11: Prompting, Instruction Finetuning, and RLHF (CS224n)

LLM 機械学習

Stanfordの講義スライド。

内容

  • prompting
  • LLMに指示して色々させる
    • zero-shot learning
      • LLMくんに聞く
    • few-shot learning (= in-context learning)
      • LLMくんに聞く前に例示してあげる
    • chain-of-thought (CoT)
      • "Let's think step by step" って言ってあげると言われたとおり順々に考えてくれて答えが正確になる
      • モデルが滅茶デカにならないとこの現象（この指示を出したほうが正確になるということ）は起こらない。
  • instruction finetuning
  • RLHF
    • 人間がより望む回答をしてくれるよう、RLする。
    • 方策ベースのRLで点が高くなるように。ただし人間に点を直接つけさせると微妙なので、比較させる方がいいらしい。

歴史や実例を交えながら説明されてて良いなと思いました。

その他

P.33のこれがおもろかったｗ　diffusion modelにmasterpieceとかpixiv 10000とか言うと良いのは知ってたけど、それと全く同じやんけ。

備忘録を再開しようかな

備忘録を久々につけてみようかな。暫く空いたこの期間に忘れたくないような学びがなかったという訳ではなかったんだけど、どうしても気軽にアウトプットできない期間ではありましたね。趣旨は変わらず、主に自分のためのメモを書いていく予定。

特に今、LLMと拡散モデルにめっちゃ興味が有るので、その辺のことを書いていこうと思います。なるべく毎日。

JPEG を爆速でデコードできる OpenCV をビルドして Python から使う

深層学習の計算のボトルネックを GPU にできないことは、意外としょっちゅうである。結構よくあるのが、入力の読み込み・デコードがボトルネックになるパターンである。

JPEG データの場合、libturbojpeg というライブラリを使って読み込むと CPU 利用率がめっちゃ抑えられる。以下では、OpenCV を libturbojpeg を使うようにビルドして Python から叩く方法をまとめる。

ビルド

すっ飛ばしていきなり結論みたいになってますが、シェルスクリプトにまとめました。

install_opencv.sh · GitHub

libturbojpeg と OpenCV をビルドしてカレントディレクトリ下の .local ってディレクトリに配置します。Python は pyenv 使ってる想定で、今読み込まれてるバージョンを使ってビルドします。詳しくはスクリプト読んでちょ。

Python から読む

方法1: PYTHONPATH を通す

.local/lib/python3.6/site-packages/cv2.so を Python から読めるようにする必要があるので、 PYTHONPATH にこのディレクトリを追加する。

export PYTHONPATH=/ほげほげ/ぴよぴよ/lib/python3.6/site-packages :$PYTHONPATH

あとは import cv2 ってやって怒られなければ OK。cv2.imread が爆速になってるはず。

方法2: Python の中で syspath を追加する

プロジェクトごとに違うビルドをしたりしてると、上みたいな設定をグローバルに適用することに抵抗があることがある。その場合は、ややお行儀が悪い感じがするが、実行する Python スクリプトの最初に上と同じような設定をしてやれば良い。下の関数を最初に他の import よりも前に呼んでおく。

def add_local_lib_dir_to_syspath():
    import sys
    import os

    local_lib_dir_path = os.path.join(
        os.path.dirname(__file__),
        '.local',
        'lib/python{}.{}/site-packages'.format(sys.version_info[0], sys.version_info[1]))
    sys.path.append(local_lib_dir_path)

mp4をサクッと連結する

【ffmpeg】動画・音声を連結する concat の使い方 其の2 : ニコニコ動画研究所

mp4boxを使うのが楽だった。

MP4BoxをMacでテキトーに使う - 松久外吉のチラ裏

/Applications/GPAC.app/Contents/MacOS/MP4Box -force-cat -add AAA.MP4 -cat BBB.MP4 -cat CCC.MP4 ... -new "OUT.MP4"

PyTorch で開発中の JIT 機能

概要

https://github.com/pytorch/pytorch/tree/v0.4.0/torch/csrc/jit

PyTorch は NN 定義をコンパイルし Python のユーザーコードを通らずモデルを実行できる機能を開発中。実は開発は普通にオープンに GitHub で行われているし master にじゃんじゃん入っているので試せる。以下の 2 種類の両方が実装されつつある。

  • 実際に実行して作成された計算グラフを IR に変換する torch.jit.compile
  • Python のコードを制御構文も含めて直接 IR に変換する torch.jit.script

以下は PyTorch 0.4.0 で実行。

In [1]: import torch

In [2]: torch.__version__
Out[2]: '0.4.0'

torch.jit.compile

まずは試す

In [4]: @torch.jit.compile(nderivs=0)
   ...: def f(x):
   ...:     return x * 2.0 + 1.0
   ...:

In [5]: x = torch.rand(2, 3)

In [6]: f(x)
Out[6]:
tensor([[ 2.5645,  1.5038,  2.3040],
        [ 1.6422,  2.9829,  1.8165]])

In [7]: f(x)
clang: error: unsupported option '-fopenmp'
clang: error: unsupported option '-fopenmp'
warning: pytorch jit fuser failed to compile with openmp, trying without it...
Out[7]:
tensor([[ 2.5645,  1.5038,  2.3040],
        [ 1.6422,  2.9829,  1.8165]])

2 回目の実行であからさまにコンパイルされている。

速度の比較

In [29]: def g(x):
    ...:     return x + 1.0
    ...:

In [30]: def f_nojit(x):
    ...:     for _ in range(1000):
    ...:         x = g(x)
    ...:     return x
    ...:

In [31]: @torch.jit.compile(nderivs=0)
    ...: def f_jit(x):
    ...:     for _ in range(1000):
    ...:         x = g(x)
    ...:     return x
    ...:

In [32]: %timeit f_nojit(x)
1000 loops, best of 3: 1.74 ms per loop

In [33]: %timeit f_jit(x)
The slowest run took 14983.91 times longer than the fastest. This could mean that an intermediate result is being cached.
10 loops, best of 3: 10.8 µs per loop

In [34]: %timeit f_jit(x)
The slowest run took 7.04 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 11 µs per loop

Python の関数呼び出しは非常にオーバーヘッドが大きい。敢えて Python の関数呼び出しを行いまくる書き方をした関数を JIT 有りと JIT 無しで比較。100 倍近く高速になっている。Numba とかで再帰呼び出しで書いたフィボナッチとかをコンパイルしても大体 100 倍ぐらい速くなるので、ちょうどこんなもんだと思う。

IR を見る

In [35]: @torch.jit.compile(nderivs=0)
    ...: def f(x):
    ...:     for _ in range(5):
    ...:         x = x * x
    ...:     return x
    ...:

In [36]: f(x)
Out[36]:
tensor([[ 3.8660e-04,  6.9221e-20,  1.1373e-06],
        [ 1.6299e-16,  7.5940e-01,  3.5456e-13]])

In [37]: f(x)
Out[37]:
tensor([[ 3.8660e-04,  6.9221e-20,  1.1373e-06],
        [ 1.6299e-16,  7.5940e-01,  3.5456e-13]])

In [38]: f.graph_for(x)
Out[38]:
graph(%0 : Float(2, 3)) {
  %6 : Float(2, 3) = prim::FusionGroup_0(%0)
  return (%6);
}
with prim::FusionGroup_0 = graph(%8 : Float(2, 3)) {
  %9 : Float(2, 3) = aten::mul(%8, %8)
  %7 : Float(2, 3) = aten::mul(%9, %9)
  %5 : Float(2, 3) = aten::mul(%7, %7)
  %3 : Float(2, 3) = aten::mul(%5, %5)
  %1 : Float(2, 3) = aten::mul(%3, %3)
  return (%1);
}

トレースを取ってそこから IR を作るので、ループは展開されている。 graph_for という関数名からわかる通り、入力の shape に応じてコンパイルが行われており、IR の中で shape が決まっている。

逆伝搬の IR を見る

デコレータで何階微分をコンパイルするか指定させるインターフェースは非常に使いにくい。

In [44]: x.requires_grad = True

In [45]: @torch.jit.compile(nderivs=1)
    ...: def f(x):
    ...:     for _ in range(5):
    ...:         x = x * x
    ...:     return x
    ...:

In [46]: f(x).sum().backward()

In [47]: f(x).sum().backward()

In [48]: f.graph_for(x)
Out[48]:
graph(%0 : Float(2, 3)
      -------- stage 1 --------
      %6 : Float(2, 3!)) {
  %23 : Float(2, 3), %24 : Float(2, 3), %25 : Float(2, 3), %26 : Float(2, 3), %27 : Float(2, 3) = prim::FusionGroup_0(%0)
  ---------------- stage 1 ----------------
  %22 : Float(2, 3) = prim::FusionGroup_1(%0, %27, %26, %25, %6, %24)
  return (%23, %22);
}
with prim::FusionGroup_0 = graph(%8 : Float(2, 3)) {
  %9 : Float(2, 3) = aten::mul(%8, %8)
  %7 : Float(2, 3) = aten::mul(%9, %9)
  %5 : Float(2, 3) = aten::mul(%7, %7)
  %3 : Float(2, 3) = aten::mul(%5, %5)
  %1 : Float(2, 3) = aten::mul(%3, %3)
  return (%1, %3, %5, %7, %9);
}
with prim::FusionGroup_1 = graph(%4 : Float(2, 3)
      %11 : Float(2, 3)
      %18 : Float(2, 3)
      %25 : Float(2, 3)
      %31 : Float(2, 3!)
      %32 : Float(2, 3)) {
  %34 : Float(2, 3) = aten::mul(%31, %32)
  %33 : Float(2, 3) = aten::mul(%31, %32)
  %30 : Float(2, 3) = aten::add[alpha={1}](%33, %34)
  %27 : Float(2, 3) = aten::mul(%30, %25)
  %26 : Float(2, 3) = aten::mul(%30, %25)
  %23 : Float(2, 3) = aten::add[alpha={1}](%26, %27)
  %20 : Float(2, 3) = aten::mul(%23, %18)
  %19 : Float(2, 3) = aten::mul(%23, %18)
  %16 : Float(2, 3) = aten::add[alpha={1}](%19, %20)
  %13 : Float(2, 3) = aten::mul(%16, %11)
  %12 : Float(2, 3) = aten::mul(%16, %11)
  %9 : Float(2, 3) = aten::add[alpha={1}](%12, %13)
  %6 : Float(2, 3) = aten::mul(%9, %4)
  %5 : Float(2, 3) = aten::mul(%9, %4)
  %2 : Float(2, 3) = aten::add[alpha={1}](%5, %6)
  return (%2);
}

stage は何階微分かに相当する。 https://github.com/pytorch/pytorch/blob/master/torch/csrc/jit/ir.h#L175

forward だけでコンパイルした時は、stage 0 の return は 1 つだけだったのに対し、今回は stage 0 の return で一杯値を返している。これは、関数の返り値だけでなく、逆伝搬で必要になる情報を覚えておいてもらうために出力している。逆に、stage 0 でこれらが出てこないのは、ちゃんと生存解析的なことが行われているから？（要調査）

ちなみに：print とかは消滅する

In [52]: @torch.jit.compile(nderivs=0)
    ...: def f(x):
    ...:     for _ in range(3):
    ...:         x = x * x
    ...:         print('YOYO', x)
    ...:     return x
    ...:

In [53]: f(x)
YOYO tensor([[ 0.6119,  0.0635,  0.4251],
        [ 0.1031,  0.9829,  0.1667]])
YOYO tensor([[ 0.3745,  0.0040,  0.1807],
        [ 0.0106,  0.9662,  0.0278]])
YOYO tensor([[ 0.1402,  0.0000,  0.0327],
        [ 0.0001,  0.9335,  0.0008]])
Out[53]:
tensor([[ 0.1402,  0.0000,  0.0327],
        [ 0.0001,  0.9335,  0.0008]])

In [54]: f(x)
Out[54]:
tensor([[ 0.1402,  0.0000,  0.0327],
        [ 0.0001,  0.9335,  0.0008]])

トレースに print は出てこないので、コンパイルされた IR にも print は含まれず、コンパイル後は出力が行われなくなる。他にも、当然だが、内容によって分岐していたりループ回数が違ったりするコードをコンパイルすると正しく動作しなくなる。

torch.jit.script

試す＆速度計測

In [1]: import torch

In [2]: x = torch.rand(2, 3)

In [3]: def g(x):
   ...:     return x + 1.0
   ...:

In [4]: def f_nojit(x):
   ...:     for _ in range(1000):
   ...:         x = g(x)
   ...:     return x
   ...:

In [5]: f_jit2 = torch.jit.script(f_nojit)

In [6]: f_jit2(x)
Out[6]:
tensor([[ 1000.0438,  1000.9478,  1000.7737],
        [ 1000.9696,  1000.5553,  1000.5251]])

In [7]: %timeit f_jit2(x)
100 loops, best of 3: 13.4 ms per loop

上の f_nojit の 1 ms より、むしろ遅くなってる！？

何で遅いの？

In [8]: @torch.jit.compile(nderivs=0)
   ...: def f_jit(x):
   ...:     for _ in range(1000):
   ...:         x = g(x)
   ...:     return x
   ...:

In [10]: f_nojit
Out[10]: <function __main__.f_nojit>

In [11]: f_jit
Out[11]: <torch._C.CompiledFunction at 0x10facfa40>

In [12]: f_jit2
Out[12]: <torch._C.GraphExecutor at 0x10fd11f10>

torch.jit.compile をかけた関数は、 torch._C.CompiledFunction になり、コンパイルが行われる。一方、現状、 torch.jit.script で出てくるのは torch._C.GraphExecutor であり、IR をインタプリタ実行していると思われる。

IR を見てみる

In [13]: f_jit2.graph
Out[13]:
graph(%x : Dynamic) {
  %1 : Dynamic = prim::Constant[value={1000}]()
  %2 : Dynamic = prim::Constant[value={1}]()
  %7 : Dynamic = prim::Loop(%1, %2, %x)
    block0(%3 : Dynamic, %4 : Dynamic) {
      %5 : Dynamic = ^g()(%4)
      %6 : Dynamic = prim::Constant[value={1}]()
      -> (%6, %5)
    }
  return (%7);
}

torch.jit.compile で出てきた IR との違いが興味深い。

  • shape が決まっていない状態で変換されるので、shape のところが Dynamic になっている。
  • ループがループのまま IR で表現されている。

ちなみに：こっちだとなんと print できる

In [14]: def f(x):
    ...:     for _ in range(3):
    ...:         x = x * x
    ...:         print(x)
    ...:     return x
    ...:

In [15]: f2 = torch.jit.script(f)

In [16]: f2(x)
 0.0019  0.8982  0.5986
 0.9402  0.3084  0.2758
[ CPUFloatTensor{2,3} ]
 3.6755e-06  8.0684e-01  3.5828e-01
 8.8395e-01  9.5081e-02  7.6056e-02
[ CPUFloatTensor{2,3} ]
 1.3509e-11  6.5100e-01  1.2837e-01
 7.8137e-01  9.0403e-03  5.7845e-03
[ CPUFloatTensor{2,3} ]
Out[16]:
tensor([[ 1.3509e-11,  6.5100e-01,  1.2837e-01],
        [ 7.8137e-01,  9.0403e-03,  5.7845e-03]])

コンパイルした後も print が無視されない。

In [17]: f2.graph
Out[17]:
graph(%x : Dynamic) {
  %1 : Dynamic = prim::Constant[value={3}]()
  %2 : Dynamic = prim::Constant[value={1}]()
  %7 : Dynamic = prim::Loop(%1, %2, %x)
    block0(%3 : Dynamic, %4 : Dynamic) {
      %5 : Dynamic = aten::mul(%4, %4)
       = prim::Print(%5)
      %6 : Dynamic = prim::Constant[value={1}]()
      -> (%6, %5)
    }
  return (%7);
}

IR を見てみると、 prim::Print という命令が普通に emit されている。確かに、デバッグとかでみんな使いたいよね。

ソースコードなど

ソースコードを解説するのは大変なので省略。大まかな構成だけ。

Deep Mutual Learning (arxiv)

[1706.00384] Deep Mutual Learning

手法

  • distillationの進化系
  • 2つのネットワークを同時に学習させる
  • 通常通りのsupervised learning lossに加え、mimicry lossを使う
  • mimicry lossとは2つのネットワークの出力を似せたい（KLダイバージェンス）

実験結果

  • distillationよりも精度が上がる
  • 明確にteacher-studentではなく同じネットワークを2つ用いた場合でも精度が上がる
  • 同時に学習させるネットワークの数を2から増やしてみるともっと精度が上がる
  • 直感としては、教師にアンサンブルを使うと良くなる気がするが、実験してみるとそれよりも複数のネットワーク同士のmimic lossを使う方が良くなるらしい

ただし、小規模なデータでしか実験されていない。著者らも考察しているが、どちらかというとunderfitの場合の話ではなくoverfitの場合の話であるようだ。普通に学習させてもtrain accuracyが100%に行くようなデータを用いているため、regularizationとして働いているっぽい気がする。そうなると、underfitな小規模ニューラルネットワークのoptimization difficultyを改善しモデルのキャパシティの限界を上げるというようなdistillationの話とはちょっと違う気がする。

PyPI でバージョン番号を変えず内容を変える

PyPI では、アップロードしたファイルを消すことが出来ても、置き換えることはできない。従って、あるバージョンでアップロードしてしまった後、そこにミスが発覚した場合、再アップロードして置き換えることは不可能である。

www.reddit.com

・・・というのが常識で、例えば上の reddit での議論でも、できないのが仕様ということになっている。

しかし、実は、1度だけチャンスがある。パッケージ作成で使うアーカイブのフォーマットを変えると再アップロードできる。具体的な手順は以下。

  • PyPI の Web 上で、'Remove' ボタンを使って、再アップロードしたいバージョンを一度削除する。
  • フォーマットに zip を指定してパッケージを作成しアップロードする。
python setup.py sdist --formats zip upload

仕組みとしては、PyPI は重複判定を単純にファイルが存在するかで判定しているらしく、しかも ‘Remove’ をしてもファイルは残ったままになっている。そこで、zip を指定すると、ファイル名が被らないので再アップロードができる（デフォルトは tar.gz）。

ちなみに、ドキュメントを見ると、一見 zip, tar.gz のみならず色々な種類のアーカイブがサポートされているように見える・・・が、PyPI がサポートしているのは zip, tar.gz のみであり、他のフォーマットを使うと以下のようなエラーになる。複数回チャンスがあると誤解すると危険なので注意。

Upload failed (400): Invalid file extension.
error: Upload failed (400): Invalid file extension.

「GNU開発ツール」を読んだのでビルド工程をマニュアル操作で進めてみる

www.oversea-pub.com

書籍に従いつつ手を動かしてみた時のメモ書き。gcc のバージョンの違いに注意して進めて行きます。

$ gcc -dumpversion
4.8

プリプロセス

C 言語ソース (.c) → 前処理済み C 言語ソース (.i)

$ cat hello.c
#include <stdio.h>

int main() {
  printf("Hello world\n");
  return 0;
}

$ cpp hello.c > hello.i

$ head hello.i
# 1 "hello.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 1 "<command-line>" 2
# 1 "hello.c"
# 1 "/usr/include/stdio.h" 1 3 4
# 27 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/features.h" 1 3 4
# 374 "/usr/include/features.h" 3 4

$ tail hello.i

extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__ , __leaf__));
# 943 "/usr/include/stdio.h" 3 4

# 2 "hello.c" 2

int main() {
  printf("Hello world\n");
  return 0;
}

コンパイル

前処理済み C 言語ソースファイル (.i) → アセンブリ言語ソースファイル (.s)

$ `gcc -print-prog-name=cc1` hello.i
 main
Analyzing compilation unit
Performing interprocedural optimizations
 <*free_lang_data> <visibility> <early_local_cleanups> <*free_inline_summary> <whole-program>Assembling functions:
 main
Execution times (seconds)
 phase setup             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall    1094 kB (74%) ggc
 phase parsing           :   0.01 (100%) usr   0.00 ( 0%) sys   0.01 (33%) wall     329 kB (22%) ggc
 phase finalize          :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 (33%) wall       0 kB ( 0%) ggc
 preprocessing           :   0.01 (100%) usr   0.00 ( 0%) sys   0.01 (33%) wall      25 kB ( 2%) ggc
 TOTAL                 :   0.01             0.00             0.03               1472 kB

$ cat hello.s
        .file   "hello.i"
        .section        .rodata
.LC0:
        .string "Hello world"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movl    $.LC0, %edi
        call    puts
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4"
        .section        .note.GNU-stack,"",@progbits

アセンブル

アセンブリ言語ソースファイル → オブジェクトファイル

$ as -o hello.o hello.s

$ file hello.o
hello.o: ELF 64-bit LSB  relocatable, x86-64, version 1 (SYSV), not stripped

$ readelf -S hello.o
There are 13 section headers, starting at offset 0x130:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       0000000000000015  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  00000590
       0000000000000030  0000000000000018          11     1     8
  [ 3] .data             PROGBITS         0000000000000000  00000055
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .bss              NOBITS           0000000000000000  00000055
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .rodata           PROGBITS         0000000000000000  00000055
       000000000000000c  0000000000000000   A       0     0     1
  [ 6] .comment          PROGBITS         0000000000000000  00000061
       000000000000002c  0000000000000001  MS       0     0     1
  [ 7] .note.GNU-stack   PROGBITS         0000000000000000  0000008d
       0000000000000000  0000000000000000           0     0     1
  [ 8] .eh_frame         PROGBITS         0000000000000000  00000090
       0000000000000038  0000000000000000   A       0     0     8
  [ 9] .rela.eh_frame    RELA             0000000000000000  000005c0
       0000000000000018  0000000000000018          11     8     8
  [10] .shstrtab         STRTAB           0000000000000000  000000c8
       0000000000000061  0000000000000000           0     0     1
  [11] .symtab           SYMTAB           0000000000000000  00000470
       0000000000000108  0000000000000018          12     9     8
  [12] .strtab           STRTAB           0000000000000000  00000578
       0000000000000013  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), l (large)
  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

$ objdump -j .rodata -s hello.o

hello.o:     file format elf64-x86-64

Contents of section .rodata:
 0000 48656c6c 6f20776f 726c6400           Hello world.

$ objdump -d hello.o

hello.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <main>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   bf 00 00 00 00          mov    $0x0,%edi
   9:   e8 00 00 00 00          callq  e <main+0xe>
   e:   b8 00 00 00 00          mov    $0x0,%eax
  13:   5d                      pop    %rbp
  14:   c3                      retq

$ nm hello.o
0000000000000000 T main
                 U puts
  • nm の T は .text セクションに含まれてることを意味し、U は Undefined の略で外部参照。

静的リンク

$ gcc -print-file-name=libc.a
/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../x86_64-linux-gnu/libc.a

$ ar t `gcc -print-file-name=libc.a` | head
init-first.o
libc-start.o
sysdep.o
version.o
check_fds.o
libc-tls.o
elf-init.o
dso_handle.o
errno.o
init-arch.o

$ nm `gcc -print-file-name=libc.a` 2>/dev/null | grep -C 5 "T printf$"
                 U vfprintf

printf.o:
0000000000000000 T _IO_printf
0000000000000000 T __printf
0000000000000000 T printf
                 U stdout
                 U vfprintf

snprintf.o:
                 U _IO_vsnprintf
  • .a は ar コマンドで作成されたアーカイブファイルであり複数のオブジェクトファイルを連結したもの
$ ld -o hello_static `gcc -print-file-name=crt1.o` `gcc -print-file-name=crti.o` hello.o `gcc -print-file-name=libc.a` `gcc -print-file-name=libgcc_eh.a` `gcc -print-libgcc-file-name` `gcc -print-file-name=libc.a` `gcc -print-file-name=crtn.o`

$ ./hello_static
Hello world

$ ll hello_static
-rwxrwxr-x 1 872525 Jun  3 23:59 hello_static*

$ file hello_static
hello_static: ELF 64-bit LSB  executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.24, not stripped

動的リンク

$ file /lib/x86_64-linux-gnu/libc-2.19.so
/lib/x86_64-linux-gnu/libc-2.19.so: ELF 64-bit LSB  shared object, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), BuildID[sha1]=cf699a15caae64f50311fc4655b86dc39a479789, for GNU/Linux 2.6.24, stripped

$ nm /lib/x86_64-linux-gnu/libc-2.19.so
nm: /lib/x86_64-linux-gnu/libc-2.19.so: no symbols

$ readelf -s /lib/x86_64-linux-gnu/libc-2.19.so | grep " printf@@"
   596: 0000000000054340   161 FUNC    GLOBAL DEFAULT   12 printf@@GLIBC_2.2.5
  • strip コマンドで付加情報が削除されてる（= stripped) 場合、nm コマンドでは解析できない。
$ ld -o hello_dynamic `gcc -print-file-name=crt1.o` `gcc -print-file-name=crti.o` hello.o `gcc -print-libgcc-file-name` `gcc -print-file-name=crtn.o` -lc -dynamic-linker /lib64/ld-linux-x86-64.so.2

$ ./hello_dynamic
Hello world

$ ll hello_dynamic
-rwxrwxr-x 1 4907 Jun  4 00:06 hello_dynamic*

$ file hello_dynamic
hello_dynamic: ELF 64-bit LSB  executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, not stripped

$ readelf -l hello_dynamic

Elf file type is EXEC (Executable file)
Entry point 0x4003c0
There are 7 program headers, starting at offset 64

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  PHDR           0x0000000000000040 0x0000000000400040 0x0000000000400040
                 0x0000000000000188 0x0000000000000188  R E    8
  INTERP         0x00000000000001c8 0x00000000004001c8 0x00000000004001c8
                 0x000000000000001c 0x000000000000001c  R      1
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
  LOAD           0x0000000000000000 0x0000000000400000 0x0000000000400000
                 0x0000000000000580 0x0000000000000580  R E    200000
  LOAD           0x0000000000000580 0x0000000000600580 0x0000000000600580
                 0x00000000000001cc 0x00000000000001cc  RW     200000
  DYNAMIC        0x0000000000000580 0x0000000000600580 0x0000000000600580
                 0x0000000000000190 0x0000000000000190  RW     8
  NOTE           0x00000000000001e4 0x00000000004001e4 0x00000000004001e4
                 0x0000000000000020 0x0000000000000020  R      4
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     10

 Section to Segment mapping:
  Segment Sections...
   00
   01     .interp
   02     .interp .note.ABI-tag .hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .rela.plt .init .plt .text .fini .rodata .eh_frame
   03     .dynamic .got .got.plt .data
   04     .dynamic
   05     .note.ABI-tag
   06
  • 64 bit 環境なので ld-linux のファイル名が違った。
$ ls
a.out

$ ./a.out
bash: ./a.out: No such file or directory

$ ./b.out
bash: ./b.out: No such file or directory
  • ELF ローダが正しく指定されてないプログラムを起動しようとすると、ファイル自体は有るのにまるでファイルが無いかのようなメッセージが出るの、面白すぎる。

日々のデバッグに役立ちそうな情報

$ ldd /bin/pwd
        linux-vdso.so.1 =>  (0x00007ffd4b9e3000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f5376114000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f53764d9000)

$ LD_DEBUG=help /bin/pwd
Valid options for the LD_DEBUG environment variable are:

  libs        display library search paths
  reloc       display relocation processing
  files       display progress for input file
  symbols     display symbol table processing
  bindings    display information about symbol binding
  versions    display version dependencies
  scopes      display scope information
  all         all previous options combined
  statistics  display relocation statistics
  unused      determined unused DSOs
  help        display this help message and exit

To direct the debugging output into a file instead of standard output
a filename can be specified using the LD_DEBUG_OUTPUT environment variable.

$ LD_DEBUG=libs /bin/pwd
...

mypy のソースコードをちょっと読んだメモ

mypy は Python の型アノテーションを元に静的な型チェックを行うライブラリ。型推論を行い返り値の型などもチェックする。

起動からアルゴリズム部分に到達するまで

  • mypy コマンドは scripts/mypy が起動される
  • main.py の main
  • mypy.build.build が呼ばれる
  • dispatch メソッドが色々やってそう

全体の流れ

  • build.py の中にアルゴリズムや設計思想がテキストで説明してある
  • dispatch は ① load_graph(source) して ② process_graph(graph) する

load_graph

  • Graph とは str->State の dict
  • State は 1 つのモジュールに対応
  • エッジは基本的に import に対応
  • 空の graph からスタートし、BFS して依存関係を全列挙する
  • State はファイル名を与えられていながら依存性を出したりしてるので中でパースしてそう
  • State の self.tree が構文木っぽい
  • mypy.fastparse.parse がパースを担当する
  • 最初に Python 公式の typed-ast を使ってパースする https://github.com/python/typed_ast
  • それを ASTConverter という輩が mypy 独自の AST にコンバートする
  • 変換後の AST は nodes.py

process_graph

  • State を依存関係で SCC に分解し末尾から順に処理していく
  • fresh: キャッシュが既に有り処理不要
  • stale: キャッシュが古いので解析が必要
  • process_stale_scc の中で SCC 内部の解析が行われるようだ

process_stale_scc

  • Semantic Analysis
    • semantic_analysis
    • semantic_analysis_pass_three
    • semanal.pyの冒頭に説明がある
  • Type Check
    • type_check_first_pass
    • type_check_second_passを更新がなくなるまで繰り返す
    • checker.py

なんとなく何をしてるかは説明でわかったけど、具体的な処理を追うのは TODO。Any 型等の噂の見どころ（？）に到達したい。

感想

  • 循環 import を何とかするための工夫がかなり多い
  • 解析を高速化するためにファイルに対するキャッシュを作るらしく、そのキャッシュがあるか無いかとか、あっても後々の解析のために読まないといけないのかとか、その辺の場合分けのコードが多い

Numba のコードをちょっと読んだメモ

Numba は LLVM を使って Python のコードを JIT するライブラリ。

ちゃんと速い。https://gist.github.com/iwiwi/9228787711a353e115ffcdee21f1a882

@jit からコンパイル部分に到達するまで

  • @jit → decorators._jit → dispatcher というものが返される
  • 適当に動かした例では、dispatcher は registry.CPUDispatcher のようだ
  • こいつにはほぼ全く実装がない
  • 基底クラスは dispatcher.Dispatcher
  • その基底クラスは _DispatcherBase
  • その基底クラスは _dispatcher.Dispatcher で C extension 内
  • __call__ 時に JIT してると思うけど、__call__ は _dispatcher.Dispatcher のものが呼ばれているようだ
  • _dispatcher.c 内の関数 Dispatcher_call に相当
    1. 呼び出された Python 関数の引数の型を確認しコンパイルできるか等調べる
    2. コンパイルする時は関数 compile_and_invoke を呼ぶ
    3. compile_and_invoke は self._compile_for_args を呼ぶ
  • （後で調べる①：どこで返り値の型を推定した？ → 分かった：返り値の型はここでは推定する必要がなく引数の型だけで良い）
  • （後で調べる②：なんで C extension に入ってるんだろう？ → 速度のためだろうか・・・？）
  • _compile_for_args は _DispatcherBase で定義されており、self.compile を呼ぶ
  • compile は Dispatcher で定義されており、キャッシュ等を調べたあと self._compiler.compile を呼ぶ
  • 適当に動かした例では、_compiler は _FunctionCompiler のようだ
  • _FunctionCompiler.compile は compiler.py 内の compile_extra を呼ぶ
  • compiler.compile_extra は compiler.Pipeline.complile_extra を呼ぶ
  • （見逃してなければ Python の関数はまだ Python の関数オブジェクトそのまま来てる）
  • compiler.Pipeline.complile_extra この辺が重要そう。
  • こいつは Python 関数オブジェクトをバイトコード化し、それをコンパイルする
  • ここから呼び出される _compile_core を見るとコンパイルのプロセスが書かれている

コンパイルのパイプライン

以下は nopython モードでのコンパイルのパイプライン

  1. Python bytecode を取り出す
  2. Python bytecode を Numba IR に変換
  3. Numba IR の後処理をする
  4. 型を推定・アノテートする
  5. LLVM IR を生成・コンパイル

1. Python bytecode を取り出す

  • bytecode.py 内の get_code_object で、関数.__code__ で取り出す

2. Python bytecode を Numba IR に変換

  • interpreter.py 内の Interpreter クラスに op_HOGE_PIYO 関数が大量にある
  • Numba の IR は ir.py 内に定義されるもので、Interpreter はこれを生成する

3. Numba IR の後処理をする

  • postproc.py 内の PostProcessor
  • ちゃんと読んでないけどあんまり長くないのであまり重要ではないと信じて進む

4. 型を推定・アノテートする

  • typeinfer.TypeInferer が作られる
  • TypeInferer に色々な事前情報を与える（seed_ほげほげ）
  • build_constraint で式等による伝搬ルールを列挙する
  • propagate で constraint による情報を伝播し型を決めていく（収束までループするアルゴリズム）

5. LLVM IR を生成・コンパイル

  • Pipeine.stage_nopython_backend → Pipeline._backend → targetctx.codegen()
  • targetctx は多分 CPUContext や CUDATargetContext
  • CPUContext.codegen は JITCPUCodegen に行く
  • JITCPUCodegen の基底クラス BaseCPUCodegen で LLVM が llvmlite 経由で呼ばれている
  • _engine を見ると MCJIT を使っていることが分かる

メモ

Python から LLVM 叩くならこいつ便利そう https://github.com/numba/llvmlite

LLVM Tutorial をやったメモ

LLVM Tutorial: Table of Contents — LLVM 5 documentation

まだ途中までしかやってないです。Kaleidoscopeという言語の処理系を作っていきます。非常にシンプルな言語です。対話環境で入力されたコードをJITして実行します。

  • LLVM のバージョンで結構コードが動かないので、バージョンに合わせたチュートリアルを見ると良い。
  • 本文のコードは結構間違っている上に、全部の編集箇所を紹介するわけではないので、最終コードと適宜比較しながらやる。
  • 2章末尾で最初にコンパイルするタイミングで 「clang++ -g -O3 toy.cpp でコンパイルしよう！」とか言ってくるけど LLVM のファイルを include してるのでもっとオプションが必要。clang++ toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core`
  • JITに入る前、IR生成して表示する時点で既に定数が畳み込まれるのが観測できる。
  • KaleidoscopeJIT.h は GitHub とかでゲットすると良い。release_39 ブランチが LLVM 3.9 に相当。自分のバージョンに合わせて落とす。 llvm/KaleidoscopeJIT.h at release_39 · llvm-mirror/llvm · GitHub
  • putchard, printd が呼べない時はコンパイル引数に -rdynamic をつけてみる。
  • SSA, φ関数は日本語Wikipediaで普通にすぐ理解できる。 静的単一代入 - Wikipedia
  • チュートリアルに従って作ったJIT処理系が（コンパイルするから当然とはいえ）再帰で書いたfib(40)を0.5秒とかで計算できるのは結構感動した。 time ./a.out <<< "def fib(x) if x < 3 then 1 else fib(x - 1) + fib(x - 2) ; fib(40)"

分散システム 7章「フォールトトレラント性」

部分的な障害の発生は単体システムでは起こらない分散システムの問題である

フォールトトレラント性の導入

基本概念

高信頼性とは：

  • 可用性 (availability)・・・ある瞬間に正常に稼働している確率
  • 信頼性 (reliability)・・・障害を起こすことなくジョブが走り続けられる確率
  • 安全性 (safety)
  • 保守性 (maintainability)

1時間に1ミリ秒ダウンするシステムは可用性は高いが信頼性は低い。1年に2週間メンテナンスするシステムは前の例より可用性は低いが信頼性は高い。

障害の種類：

  • 過渡障害 (transient fault)・・・１度だけ起こるが消滅する
  • 間欠障害 (intermittent fault)・・・一時的に障害が現れることが繰り返す
  • 永久障害 (permanent fault)

障害モデル

  • クラッシュ障害
  • 欠落障害（受信欠落・送信欠落）
  • タイミング障害・・・指定時間内に応答できない
  • 応答障害（値障害、状態遷移障害）
  • 任意障害（ビザンチン障害）・・・最も深刻な障害

冗長性による障害の隠蔽

冗長性の種類：

  • 情報的冗長性・・・誤り訂正符号など
  • 時間的冗長性・・・リトライ
  • 物理的冗長性・・・余分な装置の付加

三重モジュール (TMR; Triple Modular Redundacy) による冗長性・・・電子回路を 3 重化しゲートの直後に毎回多数決を取る。

プロセスのレジリエンス

レジリエンス＝いくつかのプロセスが故障した場合に、システムの残りの部分に大きなダメージを与えないようにするための技術

設計問題

プロセスグループ・・・同じ役割を担う複数のプロセスを作っておく

  • 平坦なグループ・・・全プロセスの役割が同じ
  • 階層的なグループ・・・調整プロセスと実行プロセス

障害隠蔽とレプリケーション

Kフォールトトレラント性・・・K個のコンポーネントが故障しても動作する

  • 停止するだけなら、K+1個あれば十分
  • ビザンチン障害を保つ場合、最低でも2K+1個必要

障害システムにおける同意

  • 2 つの軍隊問題・・・5000の軍隊を持つ赤軍が谷に野営。谷を見下ろす位置に3000+3000で2つの青軍が野営。赤軍に勝てるか？→障害のないプロセスしか考えないとしても信頼性のない通信を仮定すると、2つのプロセス間で合意形成はできない。
  • ビザンチン将軍問題・・・通信は完全だがプロセスは完全でない場合。mプロセスが裏切りに対して2m+1の正しく動作するプロセスが存在すると正しく動作できるアルゴリズム。

TODO：6章（レプリケーション）を読む

高信頼クライアント・サーバ間通信

  • TCPのような高信頼転送プロトコルを用いる
  • クラッシュ時には再接続するしかない

TODO: 障害がある場合の遠隔手続き呼び出し

高信頼グループ間通信

  • 高信頼マルチキャストの基本手法・・・いくつかの仮定を踏まえた簡単なシステム：受信したらACKを送り、喪失に気づいたら再要求をする
  • アトミックマルチキャスト・・・全プロセスに送信されるか、全く送信されないかのどちらか
  • 仮想同期 (virtually synchronous)・・・アトミックマルチキャストであって、メッセージが送信されないのは送信者がクラッシュした場合のみ

TODO: 高信頼マルチキャストにおけるスケーラビリティ

分散コミット

分散コミット・・・あるオペレーションはグループ内の全てのメンバによって行われるか全く行われないかのいずれか（アトミックマルチキャストは分散コミットの１例）

1相コミット (one-phase commit) ・・・コーディネーターが実行するかどうかを通知する。参加者の1つが行うことができなくなった場合に、コーディネータに伝えることができなくなって困る。

2相コミット

  1. コーディネータ：VOTEをマルチキャスト
  2. 参加者：可否をコーディネータに報告
  3. コーディネータ：全員が可能ならCOMMITをマルチキャスト
  4. 参加者：COMMITを受信したら実行

いくつかのケースでブロッキングしてしまう問題がある。解決策の1つは3相コミットである。

回復

  • 後向きエラー回復・・・エラー状態から以前の正しい状態（チェックポイント）へシステムを巻き戻す。
  • 前向きエラー回復・・・実行を継続できる新しい状態に戦意させる。発生する可能性のあるエラーを事前に知っておく必要がある。

チェックポイントづくり

  • 回復ライン (recovery line) ・・・各プロセスのチェックポイントの組み合わせであって一貫性があるもの
  • 独立チェックポイントづくり・・独立にローカルな状態を記録し続ける
  • 協調チェックポイントづくり