読者です 読者をやめる 読者になる 読者になる

技術備忘記

日々調べたこととかとりとめなく

Go1.6 パフォーマンスについて

Go1.6リリース!

去る2016/02/17にGoの1.6がリリースされました。 という訳で色々試してみようと思ったのですが、やりたかったことのほぼ100%を すでにRC版で実施されている方がいましたので有難く内容拝見させて頂きました。 良記事オススメです。 qiita.com

Go1.6 パフォーマンス周りの変更点

上の記事を読んで終わりにしてもアレなので、パフォーマンスに関して少し詳しく触れてみます。

変更点

As always, the changes are so general and varied that precise statements about performance are difficult to make. 
Some programs may run faster, some slower. On average the programs in the Go 1 benchmark suite 
run a few percent faster in Go 1.6 than they did in Go 1.5. 
The garbage collector's pauses are even lower than in Go 1.5, especially for programs using a large amount of memory.

プログラムの作りによって速くなったり遅くなったりだが、1.5に比べて平均数%速度改善し、 GCによるプログラムの停止時間が1.4 => 1.5からさらに短縮されたよ!とのことです。ふむふむ。

There have been significant optimizations bringing more than 10% improvements to implementations of the 
compress/bzip2, compress/gzip, crypto/aes, crypto/elliptic, crypto/ecdsa, and sort packages.

compress/bzip2 compress/gzip crypto/aes sort あたりに10%以上の速度改善を行ったとのこと。 特に sort は日頃から使う機会が多いので気になるところ。ということでベンチを取ってみます。

尚、動作検証時のバージョン切り替えにはgvmを使用しました。

sortパッケージの速度比較

package bench_test

import (
    "math/rand"
    "sort"
    "testing"
    "time"
)

func BenchmarkSort(b *testing.B) {
    n := 1000
    l := make([]int, n)
    for i := 0; i < n; i++ {
        rand.Seed(time.Now().UnixNano() + int64(i))
        l[i] = rand.Intn(n)
    }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        ll := make([]int, n)
        copy(ll, l)
        sort.Sort(sort.IntSlice(ll))
    }
}

1.5.3

BenchmarkSort-5     10000        122986 ns/op        8224 B/op          2 allocs/op

1.6

BenchmarkSort-5     10000        109763 ns/op        8224 B/op          2 allocs/op

確かに10%程改善しています。

Go1.6 におけるパフォーマンスチューニング

Goのパフォーマンスチューニングと言えば、超良記事であるこちら。 qiita.com

こちらの内容が1.6になったことで何か変化があるのかついでに確認してみました。 (テストコード拝借させていただきました)

1.5.3

BenchmarkMemAllocOndemand-5           2000000           650 ns/op         496 B/op          5 allocs/op
BenchmarkMemAllocAllBeforeUsing-5   10000000           154 ns/op         160 B/op          1 allocs/op

BenchmarkFillSliceByAppend-5         5000000           342 ns/op         896 B/op          1 allocs/op
BenchmarkFillSliceByIndex-5          5000000           273 ns/op         896 B/op          1 allocs/op

BenchmarkExclusiveWithChannel-5     20000000            69.9 ns/op         0 B/op          0 allocs/op
BenchmarkExclusiveWithMutex-5       100000000           20.1 ns/op         0 B/op          0 allocs/op

BenchmarkSyncWithChannel-5            300000          4132 ns/op           0 B/op          0 allocs/op
BenchmarkSyncWithWaitGroup-5         1000000          2019 ns/op           0 B/op          0 allocs/op

BenchmarkStringMatchWithRegexp-5     3000000           430 ns/op           0 B/op          0 allocs/op
BenchmarkStringMatchWithoutRegexp-5 50000000            38.5 ns/op         0 B/op          0 allocs/op

BenchmarkGoroutine-5                 1000000          2015 ns/op           0 B/op          0 allocs/op
BenchmarkSequential-5               10000000           187 ns/op           0 B/op          0 allocs/op

BenchmarkLenDirect-5                 2000000           926 ns/op           0 B/op          0 allocs/op
BenchmarkLenCached-5                 2000000           919 ns/op           0 B/op          0 allocs/op

1.6

BenchmarkMemAllocOndemand-5           2000000           672 ns/op         496 B/op          5 allocs/op
BenchmarkMemAllocAllBeforeUsing-5   10000000           156 ns/op         160 B/op          1 allocs/op

BenchmarkFillSliceByAppend-5         5000000           360 ns/op         896 B/op          1 allocs/op
BenchmarkFillSliceByIndex-5          5000000           333 ns/op         896 B/op          1 allocs/op

BenchmarkExclusiveWithChannel-5     20000000            67.9 ns/op         0 B/op          0 allocs/op
BenchmarkExclusiveWithMutex-5       100000000           20.0 ns/op         0 B/op          0 allocs/op

BenchmarkSyncWithChannel-5            500000          3857 ns/op           0 B/op          0 allocs/op
BenchmarkSyncWithWaitGroup-5         1000000          1994 ns/op           0 B/op          0 allocs/op

BenchmarkStringMatchWithRegexp-5     3000000           409 ns/op           0 B/op          0 allocs/op
BenchmarkStringMatchWithoutRegexp-5 50000000            39.0 ns/op         0 B/op          0 allocs/op

BenchmarkGoroutine-5                 1000000          2008 ns/op           0 B/op          0 allocs/op
BenchmarkSequential-5               10000000           185 ns/op           0 B/op          0 allocs/op

BenchmarkLenDirect-5                 2000000           918 ns/op           0 B/op          0 allocs/op
BenchmarkLenCached-5                 2000000           937 ns/op           0 B/op          0 allocs/op

大きな差異は見られません。触れ込み通り速くなったり遅くなったりって感じですね。 ただし、チューニングの効果に関してはどちらのバージョンも一緒のようです。

というわけでこれまで通りの考え方で良さそうですね。

 まとめ

上記以外にも何本か既存の1.5系で書いたプログラムのテストを走らせたりしてみましたが、 特に問題は発生しませんでした。1.4 => 1.5の時もそうでしたが、今回も割とカジュアルに移行できそうな印象です。

ただし、今回は触れませんでしたがmapへの読み書きをgoroutine safeに扱ってなかったりするとpanicするという 結構ドキドキな変更が入っていたりもしますので、、移行前に一度-race を付けてテストを実施することをお勧めします (^^;)

docker-slimによるImageの簡単ダイエット

Docker Container Imageのダイエット

先日こちらに参加してきました。非常に興味深い内容ばかりだったのですが、その中でもこのスライドの内容はとても印象に残りました。

私自身は残念ながら今の職場がオンプレミス環境(一部ハイブリッド)なこともあり、Dockerの本番運用は出来ていないのですが、 Dockerを使ったImmutable Infrastructureな環境下では、Dockerレジストリからpullする際の時間の割合がDeployの多くを占めること、 その時間を短縮することが重要であることは容易に想像がつきます。

サーバー - レジストリの物理的な距離によるレイテンシは自前でレジストリを建てるなり、 AWSではAmazon EC2 Container Registryを利用するなりで解決できる問題ですが、 Container Imageのサイズに関しては、作る際に必要に応じて容量の圧縮(ダイエット)を行う必要があります。

上記スライドにもある通り、基本的には地道に頑張るのが王道だとは思いますが、 怠惰な私からすると非常に辛い作業に映ったので(ディスっているわけではありません。念のため) 何か良いものがないのかを探してみたところ、良さそうなものを見つけましたのでご紹介します。

docker-slim

docker-slim は、 定期的に開催されている Global Docker Hack Day で生まれたプロジェクトですが、 その後も継続的にOSSとして開発が進められているようです。

詳細はREADMEとDemoのビデオを見てもらえればおおよそのイメージはつかめると思いますが、 特徴をいくつかご紹介します。

  • Go製のDocker Container Imageサイズ圧縮自動化ツール
  • 静的(Dockerfile)及び動的(各レイヤーでのプロセスの起動情報など)な解析による最適化
  • ダイエットしたImageだけではなくDockerfileも作成してくれる(リバースエンジニアリング)
  • デモではnode.jsのイメージが431.7MBから14.22MB(約97%削減!)

動かしてみる

インストール手順などは割愛します。GithubのREADMEをご覧ください。

デモと同じことをしても面白くないのでイメージを別で用意して動かしてみました。 今回は公式の golang 1.5のイメージを使用します。 github.com

FROM buildpack-deps:jessie-scm
# gcc for cgo
RUN apt-get update && apt-get install -y --no-install-recommends \
        g++ \
        gcc \
        libc6-dev \
        make \
    && rm -rf /var/lib/apt/lists/*
ENV GOLANG_VERSION 1.5.3
ENV GOLANG_DOWNLOAD_URL https://golang.org/dl/go$GOLANG_VERSION.linux-amd64.tar.gz
ENV GOLANG_DOWNLOAD_SHA256 43afe0c5017e502630b1aea4d44b8a7f059bf60d7f29dfd58db454d4e4e0ae53
RUN curl -fsSL "$GOLANG_DOWNLOAD_URL" -o golang.tar.gz \
    && echo "$GOLANG_DOWNLOAD_SHA256  golang.tar.gz" | sha256sum -c - \
    && tar -C /usr/local -xzf golang.tar.gz \
    && rm golang.tar.gz
ENV GOPATH /go
ENV PATH $GOPATH/bin:/usr/local/go/bin:$PATH
RUN mkdir -p "$GOPATH/src" "$GOPATH/bin" && chmod -R 777 "$GOPATH"
WORKDIR $GOPATH
COPY go-wrapper /usr/local/bin/

まず普通にbuildします

$ mkdir go-wrapper
$ docker build -t docker-slim-test .
Sending build context to Docker daemon 15.36 kB
Sending build context to Docker daemon
・
・
Successfully built 6feb0104128c

725.1MBでした。

$ docker images | grep slim
docker-slim-test              latest              6feb0104128c        40 seconds ago      725.1 MB

docker-slimを実行してみます

注意: サンプル通りdocker-slim実行ファイル直下で行わないと動作しません

$ ./docker-slim build docker-slim-test
docker-slim: [build] image=docker-slim-test http-probe=false remove-file-artifacts=false
INFO[0000] docker-slim: inspecting 'fat' image metadata...
・
・

作成されたイメージを見てみると・・99%以上削減されています。マジか。。

$ docker images | grep slim
docker-slim-test.slim   latest              910ea500b774        5 seconds ago       3.476 MB
docker-slim-test        latest              fcb17a5be00b        47 minutes ago      725.1 MB

DockerFileを見てみます

FROM scratch
COPY files /
WORKDIR /go
ENV PATH /go/bin:/usr/local/go/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
ENV GOLANG_VERSION 1.5.3
ENV GOLANG_DOWNLOAD_URL https://golang.org/dl/go1.5.3.linux-amd64.tar.gz
ENV GOLANG_DOWNLOAD_SHA256 43afe0c5017e502630b1aea4d44b8a7f059bf60d7f29dfd58db454d4e4e0ae53
ENV GOPATH /go
CMD ["/bin/bash"]

まずベースのイメージが上のスライドでも紹介されていた超軽量イメージのscratchに置き換わっています。 まあここは予想通りでした。

あとはオリジナルの方で行っているGoのSDKのダウンロードがバッサリ消されていますね。 おそらく動的な解析の結果、これらのファイルを利用しているレイヤーが無いため不要と判断しているのだと思います。

docker exec /bin/bash でログインして何らかのプロセスを立ち上げる、みたいなコンテナには使用できませんね。 (まあ本番利用ではほぼありえないと思いますが)

まとめ

今回はちょっとサンプルが良くなかった気がしますが、、コード自体もslimで素晴らしいプロダクトだと思います。 Docker Imageのダイエットにお悩みの方は、ぜひ導入ご検討されてみては如何でしょうか。

Go言語でのimport cycle not allowedに対処する

はじめに

golang でのWeb開発では、RubyにおけるRailsのようなデファクトスタンダードフレームワークがないので、 パッケージ構成に関して、開発者に大きな裁量があります。

通常、Web開発では多くのフレームワークが採用しているMVC + Service的な形のパッケージ構成にすることが 無難ではないかと思います。

しかし、標準パッケージやOSSのコードでは結構フリーダムな構成(に見える)が多く、 一時期私も「こういう感じがGoっぽいぜ!」と若干厨二的な発想に陥り、 あえてMVC + Service的な構成を取らずに開発をすることがありました。

結果、表題の import cycle not allowed に悩まされることが増え、 最近またMVC + Serviceの形に戻すようになりました。 (この戻す作業が本当に大変でした...)

パッケージ構成についてはそれはそれで面白いテーマですが、 今回はどうしても避けられないimport cycleが発生した場合、どう対処するか?というお話です。

なぜimport cycleが禁止されているのか?

公式なドキュメントが見つけられなかったのですが、コンパイラ(Go Compiler)の実装をシンプルにするためでしょう。

Go Compilerは、複雑な実装を避けるためCやC++のような高度なオプティマイザも無ければ、 インライン関数もサポートしていません。 同じ理由でこのimport cycleもサポートしていないのだと思います。

Javaなんかは意外とOKなんですね。 昔苦しんだ記憶があるのですが、相互参照による予期せぬ動作、とかだったのかもしれません。

個人的には、やはりGoやC言語のようにコンパイルでエラーにするのが良いと思います。

対処方法

intarfaceを用いるのが一般的なようです。

Before

package foo

import (
    "fmt"
    "bar"
)

type Foo struct{}

func (f Foo) P() {
    fmt.Println("foo")
}

func CallBar() {
    bar.Bar{}.P()
}
package bar

import (
    "fmt"
    "foo"
)


type Bar struct{}

func (b Bar) P() {
    fmt.Println("bar")
}

func CallFoo() {
    foo.Foo{}.P()
}
import cycle not allowed
package foo
  imports bar
  imports foo

After

package foo

import (
    "buz"
    "fmt"
)

type Foo struct{}

func (f Foo) P() {
    fmt.Println("foo")
}

func CallBar(p buz.Printer) {
    p.P()
}
package bar

import (
    "buz"
    "fmt"
)

type Bar struct{}

func (b Bar) P() {
    fmt.Println("bar")
}

func CallFoo(p buz.Printer) {
    p.P()
}
package buz

type Printer interface {
    P()
}
package hoge

import (
    "bar"
    "foo"
)

func Call() {
    foo.CallBar(bar.Bar{})
    bar.CallFoo(foo.Foo{})
}

依存関係は以下のようになります

foo => buz
bar => buz
hoge => foo, bar

最後に

一通り苦しんだ後標準パッケージの構成を改めてみると、 相当な検討、議論があって今の形になっているということがわかった気がします。 外面だけ真似ても駄目ですね(^^;)

IntelliJ IDEAでファイル保存時にgoimportsする

小ネタです。 やろうと思いつつ出来てなかったのですが、 goimportsしないで許されるのは2015年までだよねー、ということでやってみました。

Version

IntelliJ IDEA Version 14.0.3

goプラグインの導入

まずこちらを入れます

goimportsショートカットの割り当て

Preferences > Appearance & Behavior > Keymap > plug-ins > Go で確認します。デフォルトだとショートカットが割り当てられていないので、 適当に割り当てを行います f:id:junchang1031:20160119004047p:plain

ここでは、shift + option + Command + G に割り当てます。 どうでもいいですがこのまま使うと発狂しそうなkemapですね^^;

マクロの登録

Edit > Macros > Start Macro Recroding

を実行し、先ほどのショートカットをタイプします。 その他は余計な操作をせず、

Edit > Macros > Stop Macro Recroding

を実行します。 名前を付けて保存します。 goimports とでもしておきましょう。

マクロの割り当て

Preferences > Appearance & Behavior > Keymap > Macros に goimportsが出来ていると思います。 f:id:junchang1031:20160119004840p:plain

私はvimキーバインドを使っているので、こちらに:wのkeymapを割り当てます。 Vimmerじゃない方は Ctrl + S などに読み替えてください。 f:id:junchang1031:20160119004918p:plain

(※追記 この設定だとVimプラグインのコマンドモードが侵食されてしまいます。 私はとりあえず Ctrl + Sに設定してお茶を濁しました。なにかよい方法があれば更新します..)

適当なファイルを編集して想定通りに動けばOKです。

before

package main

import (
    "fmt"
    "os" // not used.
)

func main() {

    fmt.Println("foo")
}

保存(:w)

after

package main

import "fmt"

func main() {

    fmt.Println("foo")
}

大丈夫そうですね。 これでGopher達にキモーイと言われずに済みそうです。

ZooKeeper を使った Service Discovery入門

ZooKeeper

ZooKeeperとは、CoreOSのetcd や Hashicorpのconsul等とよく並び称される、 いわゆるCordination Serviceツールです。

詳しく知りたい方は、公式ドキュメントを、とりあえずおおまかな特徴を抑えたいという方は こちらの記事が非常によくまとまっていて わかりやすかったので、ご参照頂ければと思います。

尚、本エントリーではZooKeeperの説明は(ほとんど)行いません。 予めご了承下さい。

Service Discovery

従来、Service Discovery といえば service discovery protocol (SDP)や、DNS-SD など、 インフラ、ネットワーク周りのプロトコルやそれらが提供する機能を指すことが多かったかと思います。

昨今は Micoservices という、サービスを細かく分け、それぞれが情報を通信しあって全体を作り上げていく アーキテクチャが主流になりつつこともあり、アプリケーションの領域でも語られるようになってきました。

Microservices の世界では、Continuous Integration や Immutable Infrastracture といったキーワードが象徴するように、 常にアプリケーションを取り巻く環境が変化します。 (一応補足すると、 Immutable とは変化しない、ということではなく、常に0から作り直し、状態を持たないという意味です)

そういった中で、環境の変化、状態を管理・保持するのがアプリケーションにおける Service Discovery であり、 その際に利用されるのが、etcd や consul 、そして ZooKeeper です。

余談ですが、私が最近気になっているGo製の Microservices フレームワーク go-microでは、 consul を使っています。

consul や go-micro に関しては、また別の機会に投稿します。

ZooKeeper を使って Service Discoveryしてみる

ようやく本題です。ZooKeeper は 同じく Apacheプロダクトの KafkaSpark、それ以外にも 本当に色々なところで使われています。

ただし、そういったミドルウェアのバックエンドとして使っていることはあっても、 実際に自分が開発するアプリケーションから ZooKeeper を直接操作をした事が無い、という方は結構多いのではないでしょうか。 かく言う私もそうでした。

という訳で、今回直接 ZooKeeper を操作して、簡単な Service Discovery を実現してみたいと思います。 以後 Go のサンプルコード交えて説明します。全体はこちらにあげています。

今回作るサービスは、 名前を渡すと挨拶をしてくれる Greet サービスです。

f:id:junchang1031:20160115184236p:plain

順を追って説明します。

サービスの起動 ①Pete

まずサービス Pete を起動します。 起動すると以下の様なメッセージが表示されます。

SERVER_NAME=Pete HTTP_PORT=8001 go run server/server.go
2016/01/12 21:32:45 Connected to 192.168.99.100:32772
2016/01/12 21:32:45 Authenticated: id=95156352395182231, timeout=5000
Listen 8001

コードを見てみます。

Server (Pete)

   const Node = "/greet"

    conn, _, _ := zk.Connect([]string{zkServer}, time.Second*5)

    create := func() error {
        var err error
        // try creating ephemeral node
        _, err = conn.Create(Node, []byte(httpPort), zk.FlagEphemeral, zk.WorldACL(zk.PermAll))
        return err
    }

    // ---- Pete は 書込に成功するので if以下には入らない ----
    if create() != nil {
        // watch ephemeral node event.
        another, _, eventChan, _ := conn.GetW(Node)
        fmt.Println("Now listen", string(another))
    loop:
        for {
            event := <-eventChan
            if event.Type == zk.EventNodeDeleted || event.Type.String() == "Unknown" {
                // retry creating ephemeral node
                if create() != nil {
                    break loop
                }
            }
        }
    }

Pete はZooKeeper上の /greet というエフェメラルノードに書込を試みます。

エフェメラルノードとは、和訳すると「一時ノード」です。 ZooKeeper のエフェメラルノードは、作成時に確立したセッションが有効な間だけ存在します。

Pete が起動した段階では /greet は存在しないため書込に成功します。 書き込む内容は、クライアントがアクセスするのに必要な、IPやポートの情報です。 ただし、今回はクラアント、サーバーともにローカル上で動作させるのでポート情報のみ書き込んでいます。

書き込み後、httpのListenを開始します。

func listen() {
    fmt.Println("Listen", httpPort)
    http.HandleFunc("/", greet)
    http.ListenAndServe(":"+httpPort, nil)
}

func greet(w http.ResponseWriter, r *http.Request) {
    name := r.FormValue("name")
    fmt.Println("Greeted in", name)
    fmt.Fprintf(w, "Hello %s! I'm %s", name, serverName)
}

特に難しいところはないと思います。

サービスの起動 ②Brian

次にサービス Brian を起動します。 メッセージが少し変わります。 少しわかりにくいですが、既に8001で別サービスがListenしている旨を表示します。

SERVER_NAME=Brian HTTP_PORT=8002 go run server/server.go
2016/01/12 21:33:40 Connected to 192.168.99.100:32772
2016/01/12 21:33:40 Authenticated: id=95156352395182232, timeout=5000
Now listen 8001

コードは先程と同じです。

Server (Brian)

   // ---- Brian は 書込に失敗するので ノード変更イベントの監視 ----
    if create() != nil {
        // watch ephemeral node event.
        another, _, eventChan, _ := conn.GetW(Node)
        fmt.Println("Now listen", string(another))
    loop:
        for {
            event := <-eventChan
            if event.Type == zk.EventNodeDeleted || event.Type.String() == "Unknown" {
                // retry creating ephemeral node
                if create() != nil {
                    break loop
                }
            }
        }
    }

Brian も同じくZooKeeper上の /greet に書込を試みます。 ただし、/greet は既に Pete が書き込みを行っているため書込に失敗します。 Brianは以後はforの中で、この /greetノードの変更イベントを監視しつつ待機状態となります。

クライアントの起動

次にクライアントを起動します。 名前の入力を求めるメッセージが表示されます。

go run client/client.go
Enter your name.
>

クライアントは、ZooKeeper 上の /greet の読み込みます。 また、同時に/greetノードの変更イベントの監視を別の goroutine で行います。 監視のコードはほぼサーバー側と同じです。

その後、入力を受け付け、enter を押されたらサービスに問合せに行って 受け取った結果を取得して出力します。

Client

func main() {
    zkServer = os.Getenv("ZK_SERVER")
    if zkServer == "" {
        panic("ZK_SERVER is required")
    }
    zkConn, _, _ = zk.Connect([]string{zkServer}, time.Second*5)
    zkConn.SetLogger(new(NoLog))

    go watch()

    var s scanner.Scanner
    s.Init(os.Stdin)
    for {
        fmt.Print("Enter your name.\n> ")
        s.Scan()
        fmt.Println(call(s.TokenText()))
    }
}

func call(name string) string {
    var p string
    for {
        if p = discover(false); p != "" {
            break
        }
    }
    resp, err := http.Get(fmt.Sprintf("http://localhost:%s/?name=%s", p, name))
    if err != nil {
        panic(err)
    }
    defer resp.Body.Close()

    b, _ := ioutil.ReadAll(resp.Body)

    return string(b)
}

func discover(change bool) string {
    servicePortMtx.Lock()
    defer servicePortMtx.Unlock()

    if change || servicePort == "" {
        p, _, _ := zkConn.Get(Node)
        servicePort = string(p)
    }

    return servicePort
}

func watch() {
    var eventChan <-chan zk.Event
    _, _, eventChan, _ = zkConn.GetW(Node)
    for {
        event := <-eventChan
        if event.Type == zk.EventNodeDeleted || event.Type.String() == "Unknown" {
            discover(true)
        }
        _, _, eventChan, _ = zkConn.GetW(Node)
    }
}

Pete が挨拶

Client

Enter your name.
> John
Hello John! I'm Pete

Server(Pete)

Greeted John

Pete が挨拶してくれました。

Pete サービスを落とす

Ctrl+C で Pete を落とします。

Server(Pete)

^Cexit status 2

しばらくすると Brian が立ち上がった旨が表示されます。

Server(Brian)

Listen 8002

Brian が挨拶

Client

Enter your name.
> Paul
Hello Paul! I'm Brian

Server(Brian)

Greeted Paul

想定通り、 Brian が Pete に替わって挨拶してくれました!

まとめ

いかがでしたでしょうか。

今回の実装では実用レベルには程遠いですが、 ZooKeeper を使った Service Discovery の おおよそのイメージは掴んで頂けたのではと思います。

もう少しきちんと実装したうえでの実サービスでの導入も 妄想 検討しているので、 実現の際にはまた記事にしたいと思います。

Go VS Elixir (1)フィボナッチ数列

最近仕事はもっぱら Go を使うことが多いのですが、 Elixir がここ最近気になっており学習をしています。 ということで、思いつきで性能比較をしてみました。

検証環境

フィボナッチ数列での再帰処理

第一弾はみんな大好きフィボナッチ数列です。 Goは再帰が不得意ということは割といろんなところで言われています。 一方、Elixirは関数型言語だし得意な部類に入るのではないか。多分。 ということでどうなるかやってみました。

ナイーブ実装

Go

func fib(n int) int {
    if n < 2 {
        return n
    }
    return fib(n-2) + fib(n-1)
}
$ time go run fib.go 20
6765
go run fib.go 20  0.40s user 0.07s system 118% cpu 0.402 total

time go run fib.go 30
832040
go run fib.go 30  0.45s user 0.09s system 104% cpu 0.519 total

time go run fib.go 40
102334155
go run fib.go 40  1.15s user 0.07s system 103% cpu 1.185 total

Elixir

defmodule Fib do
  def fib 0 do 0 end
  def fib 1 do 1 end
  def fib(n) do fib(n - 1) + fib(n - 2) end
end
time elixir fib.exs 20 
6765
elixir fib.exs 20  0.42s user 0.21s system 100% cpu 0.618 total
time elixir fib.exs 30
832040
elixir fib.exs 30  0.51s user 0.19s system 97% cpu 0.723 total
time elixir fib.exs 40
102334155
elixir fib.exs 40  7.13s user 0.22s system 92% cpu 7.915 total

再帰が深くなると差が縮まると思いきや逆の結果に。 意外です。。

メモ化

Go

var cache map[int]int
func init() {
    cache = map[int]int{}
}

func fib(n int) int {
    if n <= 1 {
        return n
    }
    if cache[n] == 0 {
        cache[n] = fib(n-1) + fib(n-2)
    }
    return cache[n]
}
time go run fib.go 40
102334155
go run fib.go 40  0.41s user 0.08s system 110% cpu 0.443 total

Elixir

defmodule Fib do
  def fib 0 do 0 end
  def fib 1 do 1 end
  def fib(n) do
    case Agent.get(__MODULE__, &Map.get(&1, n)) do
      nil ->
        v = fib(n - 1) + fib(n - 2)
        Agent.update(__MODULE__, &Map.put(&1, n, v))
        v
      v -> v
    end
  end

  def start_link do
    Agent.start_link(fn -> Map.new end, name: __MODULE__)
  end
end
Fib.start_link
time elixir fib.exs 40
102334155
elixir fib.exs 40  0.46s user 0.20s system 94% cpu 0.692 total

Elixirの方がメモ化の恩恵を大きく受けました。

終わりに

elixir ではなく素の erlangだとまた結果は変わるのだろうか。 そのうちまた試してみます。