2017-12-04

Big bag of pagesで型情報を節約する

技術メモ知見

言語実装アドベントカレンダー20174日目の記事です。

言語実装、特に動的型付け言語の実装においては、実行時に値を扱う際、値本体の他に型などのメタ情報を持たせる必要がある。静的に解析が可能な言語と違って実行時にしか解析ができないからだ。しかし、言語の特性を考慮して実装をしないと非効率的なメモリの使い方をしてしまう場合がある。その対応策として Big bag of pages というメモリの扱い方があるので、どういう部分で有用なのか紹介する。

例えば、C言語で純粋に実装をすると、ゲスト言語*1上で整数を解釈する場合

// guest language input: 35

typedef struct lang_value {
        union {
                int i;
                double d;
                struct fat_struct object;
        } val;
        enum lang_type type;
} lang_value;

lang_value* p = malloc(sizeof(lang_value));
p->val.i = 35;
p->type = Int;

と記述するのが最も簡易的であるし、様々なアーキテクチャ間での互換性を保つことができる。しかし、この方法で例えば1 + 2 + 3 + ... といった整数値の確保を大量に行うのであれば、 unionによってintのサイズより大きく確保されている構造体を扱う必要があるし、メタ情報も毎回確保しなければならないので非効率になる。

こういった実装を効率化する方法として、javascriptやmruby、CRubyのなどの処理系では、ビットの未使用区間を再利用することで、ポインタそのものに型情報を付与するNaN boxingやTagged pointerの手法が取られたりしている。

Big bag of pages

Big bag of pages（以下、bibop）は、ビットそのものに工夫をするといった方法を取らず、ヒープ領域を独自に管理することによって、値のメタ情報の提供を外部テーブルに任せる仕組みである。具体的には下図のように、ヒープに対して予め型ごとにページを決定しておき、実行時は決められた領域の先頭アドレスを返すだけでメタ情報がメモリアクセスをすること無く引くことができる。

f:id:everysick:20171203181621j:plain 単純な構想では番地ごとにメタ情報が必要なように見えるが、図のようにパターンがある場合は型情報はビット演算で算出することも可能である。また、こうして割り当てられている型ごとのページは、それぞれの型の純粋なサイズで確保されるため、unionを使った共通部分の不要なメモリを削減することもできる。

glibcなどの提供するメモリ管理機構におんぶ抱っこすることができないため、実装コストは大きくなるが、メモリ使用量・メモリアクセス共に効率化を図ることができる。

サンプル実装

sbrk(2)を用いて非常に小さなサンプルを実装した。free_listなどの実装を含んでいないため、メタ情報に使用状況を載せている。また、出力に用いた部分の実装などは本質ではないため省いている。必要であればリポジトリを参考*2。

#define TYPE_NUM 3
#define MAX_PAGE 6

enum type {
    Integer,
    Float,
    Char
};

enum state {
    Free,
    Used
};

typedef struct page_info {
    type t;
    void* p;
    int state;
} page_info;

int main(int argc, char** argv) {
    int i, j;

    page_info pages[MAX_PAGE];

    void *start_address, *end_address;
    size_t total_size;
    size_t type_size[3] = {
        sizeof(int),
        sizeof(float),
        sizeof(char),
    };

    total_size = type_size[0] + type_size[1] + type_size[2];
    start_address = sbrk(0);

    // 型の要求サイズ * ページ分ヒープを拡張
    end_address = sbrk(total_size * MAX_PAGE);

    // ページの先頭アドレスとメタ情報を紐付ける
    for (i = 0; i < MAX_PAGE; i++) {
        size_t size_offset = 0;

        for (j = 0; j < (i % TYPE_NUM); j++) {
            size_offset += type_size[j];
        }

        pages[i].t = (type)(i % TYPE_NUM);
        pages[i].p = start_address + (total_size * (i / TYPE_NUM)) + size_offset;
        pages[i].state = Free;
    }

    // 全ページ出力
    print_page_info(pages);

    // ページの4つ目（int）に対して値を割り当てる
    int* same_value = (int*)pages[3].p;
    pages[3].state = Used;
    *same_value = 100;

    // 全ページ出力
    print_page_info(pages);

    return 0;
}

出力はこんな感じ

start_address: 0x1ef4000
end_address: 0x1ef4000
page[0]:
    pointer: 0x1ef4000
    type is Integer
    State: free
page[1]:
    pointer: 0x1ef4004
    type is Float
    State: free
page[2]:
    pointer: 0x1ef4008
    type is Char
    State: free
page[3]:
    pointer: 0x1ef4009
    type is Integer
    State: free
page[4]:
    pointer: 0x1ef400d
    type is Float
    State: free
page[5]:
    pointer: 0x1ef4011
    type is Char
    State: free


Try allocate integer value 100 to pages[3]
page[0]:
    pointer: 0x1ef4000
    type is Integer
    State: free
page[1]:
    pointer: 0x1ef4004
    type is Float
    State: free
page[2]:
    pointer: 0x1ef4008
    type is Char
    State: free
page[3]:
    pointer: 0x1ef4009
    type is Integer
    Value: 100
page[4]:
    pointer: 0x1ef400d
    type is Float
    State: free
page[5]:
    pointer: 0x1ef4011
    type is Char
    State: free

page[3]に意図した通りの値が載ってる。よかったね。

*1:実装する言語をホスト、実装される言語をゲストと呼び分ける

*2:GitHub - s4ichi/big_bag_of_pages: sample implementation of big bag of pages

2017-09-25

Cookpad 5day service dev internship に参加した！

参加記

2017/09/11 から 5日間で開催されたcookpadのサービス開発インターンシップにエンジニア枠で参加してきた。

internship.cookpad.com

インターンシップ概要

cookpadのインターンシップは二種類あって、今回参加したのはサービス開発を実践的に行う方です。こちらのインターンシップは就業フェーズは無くて、5日間かけてサービス開発のサイクルを回して１つのサービスを作ろう！という趣旨らしい。

サービス開発は “デザイナー” と “エンジニア” がペアになって、課題発見・価値仮説・ユーザーストーリー・実行・検証といった一連の流れをcookpad製のフレームワークに沿って行っていく。もちろん価値が見いだせなければ価値仮説まで戻ってやり直すし、ユーザの導線や周知ストーリーも考えないといけない。

日程としては

１日目：元々価値仮説の済んでいる状況から検証まで行いサービス開発に慣れる
４〜５日目：実際に価値仮説から開始して最終発表までサービス開発

で行われる。もちろん後半は実装時間も含まれているし、発表資料も用意する必要があるしで大変……。

f:id:everysick:20170925164007p:plain — やっていってる

インターン成果物

今回のインターンシップテーマは “一人暮らししている人の料理が楽しみになるサービス” を作れというもので、自分たちのチームは課題発見から価値仮説までがすんなり進んだおかげか、検証もある程度行えて、最終発表までにカタチにすることができた。作ったアプリは僕の実装が雑なので完成度が高いとは言えないけど、ペアの方が優秀だったのでデザインの適用がサクッと進んで本当に助かった。

ちなみに作ったのはkurashiruやクックパッド料理動画のようなサクサク見れる料理動画をスマホ１つで簡単に撮れるアプリ。以下は最終発表資料で、少しだけ内容を簡素に手直ししている。

speakerdeck.com

余談というか、成果物をApp storeに載せたいと考えていたんだけど、機種別の対応が必要なのと、先日iOS11にしたらまったく起動しなくなってしまったのでまだ先になりそう…。

以下、ポエムと感想。

提供することは難しい

インターンシップでもっとも大変だったことが「これ本当に価値あるの？」という問いに対して、自分の感性だけでなく定性・定量的なデータを持って「あります。」と言い切るまでブラッシュアップすることだった。このインターンシップではユーザインタビューという形で定性的なフィードバックをもらい、価値仮説をし直したりしたので最終的には自信を持って取り組めたけど、最初はやっぱり手が進みそうにない感があった。

もちろん、ユーザーインタビューをするにはアプリとして動作の流れができていないといけないし、多少自信が無くても価値を提供できることを想定して作らないといけない。それでユーザーインタビューの結果ズタボロになると結構ずっしりくる。講義段階で、社内デザイナーの方が “正解はない” という言葉を使っていた。でも “外れはある” と思う。ただその外れを引いたときには絶対に間違った方向はわかるから、正解を見つけるためでなく、失敗を理解するために何度も開発サイクルを回すのは本当に大切なんだと実感ができた。

サービスを実装すること

今回はiOS向けでアプリを作ったのだけど、macOS使ってるけどxcode開かないユーザーだったので結構実装は大変だった。メンターの方がiOSエンジニアで本当に助かったし、頼りになる方だったのでtipsとか色々聞くこともできた。たぶん違う業種の方だったら終わらなかったかもしれない…。

大変だった。大変だったんだけど、実装はしないとそもそもアプリは完成しない。頑張って、苦しんで、機能をすべて実装しても、それはアプリとして最初から想定していた最低限の機能だからあって当たり前だと思っている。自分のマインドとして、全て実現できなかったらそれは設計段階で「無理」と言い切れなかったエンジニアの落ち度だし、もしくは実力不足だと考えてる。

正直、今回も全てを実装しきれたわけではなかったので悔しいと思っているし、見積もりも甘かったと思ってる。これから先何を仕事にしていくかわからないけど、エンジニアとして知識や技量を積んで、実現能力を高めたいなと実感した。

さいごに

お昼は人事の方が美味しいごはん作ってくれたので体験が最高だった…本当に美味しかったです…ありがとうございました…。普段は１日１食か２食しか食べないのだけど、インターンシップ期間中で３食摂る癖が付いて今も調子が良い。すごい。講師・メンターの方々、人事の方々、他参加者の方々、５日間ありがとうございました。お疲れ様でした！

f:id:everysick:20170925003225j:plain — 美味しかった幻のカレーと出汁茶漬け

f:id:everysick:20170925003246j:plain — 美味しかった幻のカレーと出汁茶漬け

2017-09-08

NGINX unit v0.1 と所感

環境構築知見

せっかくなので動作までの作業ログと所感をまとめて書いておく。最新のインターフェースや環境構築については公式README.mdのほうが詳しいので参考程度に。記事内リンクについてはv0.1時点のものを引用しているためmasterとは差分があるので注意。

www.nginx.com

環境

Vagrantでubuntu-xenialを用意してgolangの受け答えができるところまで作った

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.2 LTS"

構築

unitの本体を入れる

configurationの受け答えしたり、（将来的に）アプリケーションのリロードや監視などのAPIが生えるであろうパッケージ。yum だと面倒な手順いらないらしいけどaptだとkeyの登録が必要だったりする。インストール手順はREADME.md#ubuntu-packagesを見てほしい。

goのプロジェクト作成

テスト環境なのでディレクトリはGOPATH以下に作ってしまう

$ mkdir -p $GOPATH/src/github.com/your-name/nginx-unit
$ cd $GOPATH/src/github.com/your-name/nginx-unit
$ touch nginx-unit.go

nginx-unit.go

このunitパッケージはgolangだけ必要らしい。PHP, pythonはピュアな応答をするモジュールを作成するだけで済むが、Golangはおそらくバイナリ上でポート設定等をgracefulにやりたかったのでパッケージを別にする必要があったのだと思ってる*1。それはそうと、unitって名前どうにかならないのかな。リネーム前のnginext よりはいいんだけど。

package main

import (
    "fmt"
    "net/http"
    "unit"
)

func handler(w http.ResponseWriter, r *http.Request) {
    w.Header().Add("Content-Type", "text/plain")

    fmt.Fprintf(w, "Proto  : %s\n", r.Proto)
    fmt.Fprintf(w, "Method : %s\n", r.Method)
    fmt.Fprintf(w, "URL    : %s\n", r.URL.Path)
    fmt.Fprintf(w, "Host   : %s\n", r.Host)
}

func main() {
    http.HandleFunc("/", handler)
    // port はダミーなので適当で良い
    unit.ListenAndServe("8080", nil)
}

nginx/unitをコンパイル

各種言語用のパッケージをコードからビルドする必要があるのでcloneしてきて必要なものをビルドしていく。依存パッケージのインストールからパッケージのインストールまでをやると動く。特にv0.1に関しては入れるだけで済んだ。

起動

goのプロジェクトをビルドしてパスを控える

$ cd $GOPATH/src/github.com/your-name/nginx-unit
$ go build

unit本体の起動

$ sudo service unitd start

一応socket探す（手元では /run/control.unit.sockにあった）

$ find / -name 'control.unit.sock'

config.json

configuration用のjson。executableへは先程のビルドしたバイナリファイルへのパスを書く。また、ポート・ワーカー数などは適当な数に設定する

{
  "listeners": {
    "*:8040": {
      "application": "golang"
    }
  },
  "applications": {
    "golang": {
      "type": "go",
      "workers": 1,
      "executable": "full/path/to/nginx-unit/binary/file",
    }
  }
}

jsonの内容はAPI、もしくはserviceに生えてるインターフェースから適用する

$ sudo curl -X PUT -d @config.json --unix-socket /run/control.unit.sock http://127.0.0.1:8040/
# または
$ sudo service unitd restoreconfig /full/path/to/json

ここまでするとconfigに書いた内容でgolangのプロセスが立ち上がっているのでcurlで確認

$ curl curl http://localhost:8080/foo/bar
Proto  : HTTP/1.1
Method : GET
URL    : /foo/bar
Host   : localhost:8040

さらにconfig.json書き換えることで複数のパスを指定し、複数のプロセスを管理することもできる。

おお、簡単に動くじゃんと思ったが、機能としては現状ここまでらしく、hot reload がされなかったり（インターフェースがまだない？）unitをrestartするとconfigurationは全てpurgeしたり*2するなど全く実用段階ではないことがわかった。

所感

そもそもNGINX unitで何が嬉しいのかっていうと、今のところ言語間のインターフェースを吸収することでUnicornとかuwsgiを必要とせず、さらにアプリケーション内にデプロイ用のコードを個別に実装する必要がなくなるっていうのが強みにかなと思う。あとはHTTPで橋渡しができるのでそれがとにかく楽であった。公式のKey Featuresを見る限りは動的なプロセス管理の対応や、サービスメッシュになっていくぞという宣言があるのでそこにも期待していきたい。所詮NGINX Application Platformの一機能としてのNGINX unitだが、unitのKey Featuresだけでも高機能なので、完動すればだいぶ心地の良いものになるんじゃないかと思っている。

*1:https://github.com/nginx/unit/blob/9e8328f758ea518530fc92576b1aaf673f687375/src/go/unit/unit.go#L87

*2:https://github.com/nginx/unit/issues/16