Linear is Uniqueness ?

幾つかの言語では線形型システム(Linear type system)を採用することによって、線形型を持つオブジェクトを正確に一度だけ使用するということを型システム上で検査している。 それらの型情報は、メモリ管理、ファイルIOなどの資源に対するアクセスを制限するのに役立つ。 具体的には、破壊的変更による副作用の隠蔽や、静的にメモリを解放することが可能になったりする。 また、似たような概念として、たびたび一意型(Uniqueness type)という存在が提示されるときがある。 この一意型も線形型と同じく、オブジェクトを正確に一度だけ使用するということを保証している。

線形型・一意型はそれぞれ部分構造型システム(Substructural type system)の一種である。 部分構造型システムは、部分構造論理という計算規則に制限を加えた論理体系上で計算される型システムの呼称で、いくらかの言語の型システムには線形型のなどが採用されている*1。 他にも、Affine type system(アフィン型システム)はRustが採用しているなどの理由でよく聞くようになった。*2

これらはそれぞれどういう違いがあるのか、ある程度まとまったので日本語にして書き出してみた。 結果から述べると、オブジェクトがただ一つ存在しているという事実の証明にはどちらを用いても変わりはない。しかし、これらが保証する性能は実行時の計算に役立つことがある。

まず言葉の定義として、オブジェクトが線形性を持つということを、この記事では型システムによって線形型が付けられたこととし、 オブジェクトが一意性を持つということを、この記事では型システムによって一意型が付けられたこととする。 このとき、線形性・一意性は以下のような意味を持つ。

線形性

オブジェクトに対して線形性が認められるとき、"以降にオブジェクトは複製(参照)されない" ということが保証される。つまり、全てのオブジェクトに対して線形性が示された場合、各オブジェクトは一度の使用で破棄をしても問題はないことが保証される。また、非線型のオブジェクトの存在を認めたとき、"以降にオブジェクトは複製(参照)されない" という事実はそのオブジェクトの未来に対する再利用可能性を示す。

一意性

オブジェクトに対して一意性が認められるとき、"以前にオブジェクトは複製(参照)されていない" ということが保証される。つまり、全てのオブジェクトに対して一意性が示された場合、各オブジェクトは一度の使用で破棄をしても問題はないことが保証される。また、非一意のオブジェクトを認めたとき、"以前にオブジェクトは複製(参照)されていない" という事実はそのオブジェクトの過去に対する再利用可能性を示す。


これらの解釈は参考文献*3を基に独自に解釈した部分が混ざっているため、必ずしも正確であることは言えない。もし明らかに異なる言葉の用途や定義などが存在している、または見当違いのことを書いているのを発見した場合はコメント等で指摘してほしい。

*1:ATS2では線形型、Cleanでは一意型によって参照がただ一つということを型システム上で検査している

*2:正しくはRustの前身であるCycloneにおけるRegionにてAffine typeを採用している[要出典]。Rustコミュニティが使っていると示唆する文献は無い

*3:De Vries, Edsko, Rinus Plasmeijer, and David M. Abrahamson. ”Uniqueness typing simplified.” Symposium on Implementation and Application of Functional Languages. Springer Berlin Heidel- berg, 2007.

References will be Garbage

参照カウント方式のメモリ管理機構ではメモリ解放のプロセスを分散できるために、他のメモリ管理と比べて目に見える停止時間が少ない。 ただ、純粋な参照カウント方式では全てのオブジェクトの状態を管理することは難しくて、例えば循環参照などの問題が発生する。 歴史は色々あるのでそうした問題解決方法について少し調べたものをまとめてみた。 GCハンドブックなどを見れば一通り書いてあるので、気になったら書籍を参考にしてもらえればと思ったり。

循環参照の解決

参照を持っていればオブジェクトは破棄されない。そのため参照カウント方式のメモリ管理機構では参照の状態が循環状態になるとオブジェクトは一生解放されないという問題点がある。以下はReferenceクラスのインスタンス変数としてお互いを参照している例である。この状態ではa, bそれぞれ他のオブジェクトからの参照が残っているため、参照カウント方式のメモリ管理ではどちらも解放されない。(rubyっぽく書いているが一応疑似コード)

class Reference
  instance_var :ref
end

a = classA.new
b = classB.new

a.ref = b
b.ref = a

弱参照と強参照

一つの手段として参照に強弱を持たせる。それぞれ強参照、弱参照と呼び、強参照は一般的な参照と似たようなもので。参照されている先のオブジェクトは参照が残っている限り破棄されない。 対して、弱参照は参照先から強参照が消えると破棄される。つまり破棄を防ぐ強制力を持たない。

対策としてしばしば参照カウント方式のメモリ管理機構には弱参照の概念が導入される。 例えば、イミュータブルな参照を弱参照で扱ったり、強弱両方の参照記法を用意し、プログラマに明示させるなどの方法がある。

もともと手動管理であったり、 静的にメモリを管理できる機構が備わっている場合は負担は少ないだろうけど、 記述のミスが原因でメモリリークを引き起こしたりする可能性があるため若干怖い節がある。

ちなみにC++11以降ではスマートポインタ、objective-cではARC(Auto reference count)、RustではArc・Rcが似たような機能を持っている。

ガベージコレクションGC)の分散

また、別の対策としてあるのが、別のGCを導入することである。 例えば Mark and sweep を導入し、使用未使用の状態をフラグで管理することで循環参照状態のオブジェクトを発見、破棄できる。

逆に Mark and sweep のみの構成ではMarkフェーズ、sweepフェーズの負荷が大きく、プログラムに停止時間を与える可能性がある。 そのため、参照カウントを用いて適度にオブジェクトの破棄を進めつつ、参照カウントで破棄できないオブジェクトをまとめて破棄する。 互いの欠点を補いつつ複数のアルゴリズムGCしていくのは一般的な手段であると言える。

例えば、Python2.2では参照カウント方式のGCと Mark and sweep を組み合わせてメモリ管理を動的に行っている。 最近あったその手の話では、instagramがWebサーバーへのリクエスト時にMark and sweepによるGCを停止させ、参照カウントのみでメモリ管理を一時的に行うことで性能を向上させるなどの工夫があった。*1

参照カウントのトレードオフ

闇雲に参照カウントを入れればフルGCの機会が減って性能が向上するわけでもない。 オブジェクトの参照をカウントするにはそれ専用の領域が必要になる。すなわち、オブジェクトが確保するヒープ領域には最大オブジェクト数分のカウントが可能な領域が余分に確保される。 余分に確保されるということはヒープ領域をフルに活用できるない。フルに活用できないのであればメジャーGCの頻度は向上するだろう。 結局、参照カウントによって分散できるはずが、総フルGC時間が長くなってしまい、逆に性能が悪化する恐れがある。

そこで例えば、参照カウント用のビット数を絞る方法なども考えられる。例えば、ビット数を1ビットとして参照カウントをし、2つ以上の参照があった場合には参照カウントによるGCを諦め、他のGCに処理を移譲する。 こういった方法は一般的なオブジェクトの生存期間や参照の数について統計やベンチマークを行い、言語やフレームワーク、設計の特性からビット数を工夫することで性能は向上する可能性がある。

mastodon運用していく

Mastodon

IDでアイデンティティを確保してきた人間的には、OStatus準拠のサービスをやっていくうえで、独自ドメインとらないと気分になれないというのが動機としてあった。流行っているというのもあるし、railsだしpostgresだしsidekiqだし、自分の持っている技術スタックでいい感じやっていけそうな気分になったということで、ある程度まともな感じで運用してみることにした。

方針というか、どういうコミュニティがというポリシーは一切無いし、強いて言うなら自分の好きなことをやっていくつもり。 例えばHEADをガンガンデバッグしつつchankoとか使ってこのインスタンスだけの機能みたいなのを実装していくとか。 あとは、外部の人間の登録をどうするかとか、そういうのも考えないといけない気がするけど、自由にしてもらっていいんじゃないですかね。

mstdn.everysick.com

specifications

サービスはAWSだと高いのでさくらのクラウドで、dockerとかfigとか使わずにsystemd使いつつ単一のサーバー内で全てを簡潔させる感じに構築した。SSLが必須というわけではないけど、パスワードを収集するマストドンになるつもりもないので、CloudFlare使ってSSL化している。こんな感じ。

[Browser]---(HTTPS)---[CloudFlare]---(HTTPS)---[mstdn.everysick.com]

あとは、mailgunではなくSendGridとかで置き換えてみようかなと思ったりしている。 当初はSendGridでやろうと思っていたけど審査結果がまだらしい。来たらやっていこう。

Follow me

mstdn.everysick.com

また何か進捗があったら書くぞ。