giantneco’s blog

技術メモ

ScalaMatsuri 2018 に参加してきた (2日目)

今年で参加4回目のイベント。 それほど Scala は書いていないが、関数型言語、DDDあたりの話を聞きに行っている。

今回は 3 日間の開催で、1 日目はトレーニングデー、2 日目は普通のセッション形式、3 日目はアンカンファレンス形式になっている。 1 日目は不参加(あるのに気付いてなかった)で 2, 3 日目に参加した。

以下は 2 日目のメモ、ただし後から調べたこともちょっと入っている。

Why Composability matters @gakuzzzz

http://gakuzzzz.github.io/slides/why_composability_matters/

Scala と他の言語を分けるのは Composability。 Composability は同じ概念の異なる要素を特定の方法で組み合わせて同一概念の別要素を作ること

このセッションでの定義として、「Composability が高い」という場合は合成する手段が多いということを指す。

では、なぜ「Composability が高い」と嬉しいかというと、分割統治をするのに複数の手段があるということになるから。

Functional Performance @mjpt777 Martin Thompson

関数型言語の向けのパフォーマンスの話。とはあったが関数型言語でなくても通じる話だと思う。 メモリあたりの低レイヤの話から、関数型言語向けのデータ構造の話まで出てくる。

資料に出ていた Unified Reservation Station が気になって調べたが、これは命令のアウトオブオーダー実行のための仕組みで、キューに溜まった命令に対して必要なオペランドが揃ったら実行される。 1GB の long 配列の和を Haswell 上で計算する例に出されているが、 周波数を3GHzとして、1サイクルは0.3 nsで、マニュアルをみると 256bit のロード・ストアは 1 サイクルで済むように書いてあるので、 うまくキャッシュに乗っていればベンチマーク結果にある 0.83 ns/op というのもすごく有り得そうな数字に見えてくる。

パフォーマンスのための式としてM/D/1の待ち行列式と、Universal Scalability Law が紹介されている。

M/D/1 の待ち行列{ \displaystyle
\begin{align}
r = \frac{s(2 - \rho)}{2(1-\rho)}
\end{align}
}

USL { \displaystyle
\begin{align}
C(N) = N/1 + \alpha (N - 1) + \beta N (N - 1)
\end{align}
} 個人的にはアムダールの法則をよく使うが、コヒーレンシを考える必要がある場合はこっちのほうが適当か。

CRDTs

モダンな分散環境ではメッセージのやり取りに TCP より UDP の方が向いている。 ただし UDP によるメッセージングだと順序の保証がないので、データ構造も良く考える必要がある 関数型言語が使うデータ構造だと skip list, tree, scoreboard があるが、実装としてはポインタの参照地獄になってしまう。 Immutability のため、また Concurrent Tree Update をしようとすると Path Copy をすることになってパフォーマンスが問題になる。またガベージコレクションも大変になる。

そこで CRDTs = Conflict-Free Replicated Data Type

CRDTs は時間効率、空間効率ともによいデータ構造 CRDTs には 2 種類あり、オペレーションをコピーする CmRDT = Commputative Replicated Data Types とステートをコピーする CvRDT = Convergent Replicated Data Types

CmRDT * オペレーションを複製 * オペレーションは可換 * オペレーションはべき等でない

CvRDT * ステートを複製 * ステートアップデートは単純増加 * つまり追記のみで、削除には特別な操作が必要 * マージ処理は結合的,可換,べき等

Aeron の Log Buffer が上記の CRDT になっているらしく、オペレーションが中断した場合なども

Publishers, Senders, Receivers, Subscribers が単調増加だけするカウンタを持っていてる。 ステートを持つのは悪かもしれないが、単調増加だけする場合は許容できる。

Monad Transformaers Down to Earth , Gabriele Petronella

モナド変換子の話。モナド変換子自体は前から知っていたが説明が抜群にうまかった。見習いたい。

型クラスが入れ子になっているときは Monad の flatmap を使う。

flatpmap: F[F[A]] -> F[A]

なら異なる型クラスで包まれていたら?モナド同士は合成できないので困ったことになる。

F[G[A]]

こういう場合に使うのがモナド変換子で、合成の代わりに変換をする。

F[G[A]] -> GT[F[_], A]

モナド変換子はモナド名+Tという名前にする(Option モナドならモナド変換子は OptionTになる)

実用的な圏論入門 @DanielaSfregola

圏論のハンズオン。途中から別のセッションを聞きに行った。 かなり初心者向けで、手を動かしながら聞けるのでわかりやすい。

Building Distributed System with Akka @anildigital , Anil Wadghule

分散システムと Akka の話。

  • 背景
    • size of internet growing
    • concurrent connections, big data, respoinse time
    • high require
    • reactive prinsiples
  • Distrubuited system をスケールさせるには
    • 読み込みの複製
      • 複雑、一貫性に問題
    • シャーディング
      • これも複雑、データモデルに制限
    • Consistent Hasing
  • CAP 定理
  • Distributed computation strategy
    • fault tolerant system
    • Resilence
  • Akka
    • Actor model on JVM
    • 方針として「Let it crash」
      • Normal flow and Fault recovery flow

Scalaらしいオブジェクト指向プログラミング @tototoshi

Scala でのオブジェクト指向プログラミング Tips。 Scala には合成の方法が複数があるが、それぞれ長所・短所がある。

ScalaJava に対して Immutability と Composability へのサポートが多くて、 Case クラスや、 trait を使える。

  • Case Class
    • 代数的データ型として使える
  • trait
    • Java の interface に相当。 mixin や cake pattern に使える
  • object

DI についても Scala では次のような手法がある * コンストラクタインジェクション * コンストラクタで渡すパターン * Cake Pattern * with句でtraitを渡していくパターン * 関数型プログラミングスタイルなら Reader Monad, Free Monad + tagless final

Extensible Effects in Dotty @halcat0x15a

Dottyの新機能と、Dotty で使えるようになる Extensible Effects の話。 この日のセッションのうち一番話が難しかった。 正直このあたりの話はあまり理解できているとは言いがたいので、手を動かして確認したい。

Dotty は Scala の新しいコンパイラで DOT = Dependent Objectt Types という理論に基づいている。その新機能のひとつに Extensible Effects で使う Open Union がある。

Extensible Effects は複数の操作?を効率的に合成してくれるもので、モナド変換子をネストして使った場合にパフォーマンスが落ちる問題を解決してくれる。

この Extensible Effects に至るまでの話が複雑で、まず Free Monad が出てくる。 Free Monad は Functor を Monad にしてくれるが、Functor にしか適用できない。 これに対して Coyoneda を使って Functor 以外にも適用できるようにしたのが Freer Monad。 ただし Freer Monad は flatMap を複数回適用するため重いという問題がある。 これを解決するために Type-Aligned Queue というものを使って、 早くしたのが Fast Freer Monad。 で、Open Union に Fast Freer Monad を適用したものが Extensible Effects であるらしい。

話の流れだけはなんとなく把握したが、実際どういうことをしているのかがわかっていない。

システムパフォーマンス勉強会第8回

www.slideshare.net

社内で行ったシステムパフォーマンス勉強会の第8回。 下半期で終わらせるつもりだったので、一通り重要そうなところはよんだということでとりあえず終わり。

全体としてコードを書く時に知っておくと良いことも多々あったが、全体としてはパフォーマンスエンジニア向けの内容だった。 正直作った後のチューニングとか、機器選定とかインフラ周りとか自分はあまりやらんだろうし。

また社内でやった意味もあったと思う。メモリとかCPUとか低レイヤだが知っておいたほうがいい知識と、並列処理まわりのパフォーマンス関連の話が多少でも共有できたのは良かったと思う。 もうちょっと人を集められるとよかったが…

4月からはなにやろうか?

システムパフォーマンス勉強会第7回

社内で行っているシステムパフォーマンス勉強会のメモ。

今回は詳解システムパフォーマンスの 9 章ディスクを対象にしている。

勉強会中に出た話としては:

  • ディスクのモデル
    • シンプルディスクとキャッシングディスク
  • コンセプト
    • 計測時間
  • サービス時間、待ち時間、応答時間
  • キャッシング
  • ランダムI/OとシーケンシャルI/O
  • 飽和
    • ディスクデバイスの場合はOSのデバイス待機キューの平均長になる
  • 同期I/O と非同期I/O
  • アーキテクチャ
  • メソドロジ
    • ツールメソッド
      • 使用するツールは iostat, iotop, stap, perf など
    • USE メソッド
      • 使用率はデバイスがビジーだった時間
      • 飽和はI/Oがキューで待機している度合い
      • エラーはデバイスのエラー
      • 最初にエラーをチェックする
        • ディスクはエラーがあった場合に縮退運転するのが一般的なため

これまであまり知らなかった点がある一方で、 普段アプリを作る上で意識する点がそれほど多くなさそう。

最新コンパイラ構成技法 #1

色々復習したいことがあり、最新コンパイラ構成技法を読むことにした。

ここしばらくの作業だとコンパイラのフロントエンド部分しかしていないし、 さらに言うと機能追加が主な作業で既存のコードにちょくちょく修正を入れるだけで それほどコンパイラ屋らしい仕事はしてない。 (仕事としては一区切りついたので、この件についてもそのうちまとめたい)

かなり怪しい部分もあるので一通り読みたいところではある。

第1章では次のようにおおまかなコンパイルの流れについて説明している。

  • 字句解析
  • 構文解析
  • 意味動作
  • 意味解析
  • フレーム割り付け
  • 翻訳
  • 正準化
  • 命令選択
  • 制御フロー解析
  • データフロー解析
  • レジスタ割付け
  • コード生成

この分類だと、ここ最近の仕事ではいわゆるコンパイラフロントエンドと呼ばれる字句解析から意味解析までを中心に扱っていた。 また意味解析はあまり聞き慣れない用語で、構文解析に含まれるんじゃなかろうかとも思う。 フレーム割付けからは下は概念としては知っているが、実際に手を動かしたことがあったかどうか。 動くものが作れれば嬉しい。

実装に使う言語をどうしようかちょっと考え中。本は ML 使っているが、OCaml にするか、それともいっそ Haskell にしてみるか…

社内機械学習勉強会#5

www.slideshare.net

社内で行っている機械学習勉強会の自分担当回。 内容はタネ本にしている詳解ディープラーニングの4.5という狭い範囲なので楽だと思っていたが、 本に書いてある説明だとよくわからないことが多く結局元の論文読んでみるなどして結構詰まった。

数式のこの部分がどういう意図でそうなっているのか、というのは未だによくわからない部分がある、 あと指摘されたのは: - アイディアの元になったアナロジーを理解しておくと理解に役立つ - 二階微分は難しいので近似していることに注意

一応コードも書いて、手元では実験もしていたがあまり見せる機会がなかった。 MNISTを対象にしていると大抵それなりの精度が出るので、 この手法じゃないとうまく行かないデータとかがあったりするといいんだろうか。

システムパフォーマンス勉強会第 5 回

www.slideshare.net

  • 社内で行っているシステムパフォーマンス勉強会
  • 次回メモリの話なので、Meltdownの話も含めたらいいんじゃないかという話があった
  • 勉強会とは関係ないが、TLBのLookasideの意味することがよくわからなかったが、どうも「索引」という意味で使われているみたい