2014-10-14

HTTP2 のカンファレンスを開催します。 #http2conf

http2 http2study http2conf

11/3 に HTTP2 のカンファレンスを開催します。

2012年8月に、 SPDY/3 の仕様をベースとしてスタートした HTTP2.0 は、その正式名称を HTTP2 と変えながら議論を重ね、執筆時点で Draft-14 まで仕様の策定が進みました。

現在は、この Draft をベースに Chrome, FireFox, IE といった主要ブラウザベンダや、 Google, Facebook, Twitter といったパイパージャイアントと呼ばれる大規模サービス、そして、その他仕様に関心のある世界中のエンジニア達によって実装され、検証され、フィードバックされています。

HTTP2 を策定するワーキンググループである IETF の HTTPbis では、 ML を介して今も活発な議論が行われ、その議論の結果は RFC に向けた次なるステップである WGLC(ワーキンググループ・ラストコール) という形にまとめようというフェーズにあります。

要するに HTTP2 の仕様の大枠は見えており、世界中の Web で実用可能な仕様まで詳細を詰めながら形にしていくという、最も重要な時期であるといえます。

このタイミングで、ここまでの http2 を振り返り今後を考える一つの機会として、把握している限りでは世界初の HTTP2 をテーマとしたカンファレンスを開催することになりました。

HTTP2Conference

スケジュールは以下です。

11:00-12:00	受付(受付票を提示下さい)
12:00-12:25	オープニング by @jxck
12:30-13:30	基調講演 by @igrigorik (英語/通訳無し)
13:30-13:45	休憩
13:45-14:45	HTTP2 最速実装*1 by @summerwind
14:45-15:00	休憩
15:00-15:30	h2o by @kazuho
15:30-16:00	nghttp2 by @tatsuhiro_t
16:00-16:30	QUIC by @jovi0608
16:30-16:45	休憩
16:45-17:45	トークセッション*2(英語/通訳無し) by @igrigorik, @kazuho, @tatsuhiro_t, @jovi0608
17:45-18:00	クロージング*3

セッションのキーノートでは、 Google の Web Performance エンジニアかつ Developer Advocate であり、High Performance Browser Networking の著者でもある Ilya Grigorik を招待してトークをお願いします。

次に「HTTP2 最速実装」ですが、これは新しく HTTP2 に興味をもった人が、手を動かすとっかかりとなる題材として http2study のメンバーで持ち回りで行っているハンズオンです。一言で言えば以下のような内容です。

複雑な HTTP2 の仕様の中で、
一番簡単に Hello World レベルまでを実装するための、
最小限の仕様とそれを用いた実装方法の解説

もともと wiki から始まったものですが、これまで 3 回(v1, v2, v3) 実施してきました。

今回は、 HTTP2 仕様の日本語訳を行っている @summerwind さんが担当として、最新のドラフトでの最速実装をライブコーディングを混ぜながらやっていただく予定です。 HTTP2 をこれから始める方も、仕様の理解を深めるとっかかりとなるコンテンツです。

他には、 - ISUCON 周辺でも話題になった @kazuho さんによる h2o のトーク - 世界を代表する HTTP2 の実装である @tatsuhiro_t さんによる nghttp2 のトーク - そしてどこよりも早い @jovi0608 さんによる QUIC のトークなどをお願いしています。

また、トークセッションでは、 Ilya 含めた登壇者達による HTTP2 の現在と今後についてのトークを実施予定です。かなりガチな内容となるでしょう。

HTTP2 (ないしは SPDY や QUIC) に興味がある方々、これから始める方も、すでに HPBN などで知識を得ている方、または実装に着手している方、様々な方々が得るもののあるカンファレンスとなると思うので、是非参加してみてください。

また、これを期に開催の母体となっている #http2study のこれまでの活動を簡単にまとめてみたいと思います。

http2study の活動

日本では元々 SPDY に関心があったメンバーを中心として、2013年8月に最初の勉強会 #http2study を開催しました。

HTTP2 の実装は、ブラウザベンダ以外にも多くの開発者によって行われており、自己申告ではありますが以下の Wiki にまとめられています。 (開発途中も含みますが)

http2 implementation

現時点で 26 の実装が掲載されていますが、この中には世界的に有名な、事実上のリファレンス実装となっている nghttp2 を含め 5 つの実装が日本から出ています。(ここにないものも 2,3 は確認しています)

そのほとんどの日本人開発者が参加する #http2study では以下のような活動をしてきました。

IETF 報告会
HTTP2 最速実装ハンズオン
hpack-test-case
仕様翻訳(ほぼ @summerwind さんによるもの)
仕様に関する議論/実装で得られた知見の共有

IETF 報告会

IETF で定期的に行われる会議は HTTP2 の仕様がまさしく改訂されて行く現場ですが、海外で実施されるため簡単には行けません。そこで、参加者に結果を報告会として共有してもらって、みんなで進捗を把握します。

実際には IETF とは別途行われる httpbis の interim というミーティングの内容や、 interop という相互接続テストの結果なども参加者に共有してもらってきました。

(ちなみに、次回 11/9~14 で行われる IETF の報告会は、 11/27 に予定しています。)

HTTP2 最速実装

高度な議論になりがちな勉強会ですが、新しく HTTP2 に興味をもった人たちにとっては敷居が高すぎるため、 http2study では「HTTP2 最速実装」というハンズオンを定期的に行っています。

最速実装とは簡単にいうとこうです。

「複雑な HTTP2 の仕様の中で、一番簡単に Hello World レベルまでを実装するための、最小限の仕様とそれを用いた実装方法の解説」

最初は自分が書いた wiki で始まったのですが、そこから担当を替え、 @mad_p さん、 @y_iwanaga_ さん、 @syu_cream さんが、その時の最新実装でアップデートしながら続けてきました。

これを見ると、ドラフトのどことどこを見れば、一番簡単な実装が完成するのかを把握し、手を動かすための第一歩となるでしょう。

hpack-test-case

HPACK という仕様の実装のために、テストケースがあったらはかどるだろうと始まったのが、 hpack-test-case です。

hpack-test-case

ここでは、各自の実装でエンコードしたデータを登録し、それを他の実装がデコードすることで、 interop (相互接続テスト) を行うためのテストケース群です。仕様書にあるサンプルだけではカバーしきれないケースもあぶり出し、なにより自分の実装が一定水準を満たしていることが確認できるため非常に有用です。

現在、 HTTP2 のフレームを対象にしたテスケースも同様に作成するために、メンバーで作業中です。また、相互テストの自動化を検討しているメンバーもいます。

仕様翻訳

HTTP2 のドラフトと HTTP2 のリポジトリにある FAQ については @summerwind さんによる日本語訳が公開されています。

素晴らしいことに Draft については Draft-04 から改訂ごとにアップデートされており、最新のものに追従されています。

また、初見で理解するのはなかなか難しい仕様の理解を深めるために、議論も活発に行われています。実装するなかで得られた知見は、そのまま HTTP2 の仕様に反映されたものもあります。

仕様に関する議論/実装で得られた知見の共有

仕様について深く理解するためのディスカッションもよくおこります。HTTP2 の Github リポジトリにある issue や ML であがっているトピックを議論するための issue-thon を開催したこともありました。

特に仕様に熟知した @tatsuhiro_t さんや、標準化に深く関わる @jovi0608 さんがいるため、仕様についての質問をすることができるのも非常に恵まれた環境です。 @kazu_yamamoto さんが共有してくれた、実装を用いたベンチマークは、実際に仕様の変更につながる結果となりました。

前に立つ人だけが発信する一方向なイベントスタイルにとどまらず、個々がどんどん発言する結果、結構ガチな議論が行われる、そんなスタイルで #http2study は活動してきました。拙作ですが、 @tatsuhiro_t さんと @jovi0608 さんには、 #mozaicfm の http2 の回にも出ていただきました。

ここまでを振り返って

なかなかガチというか、実際自分でも着いて行けてないことが多い、ハイレベルはコミュニティだと思います。 (一方でこの密度の勉強会を維持できたのは結構凄いと思ってます)

このコミュニティの活動はそれなりの結果が出ていると思うし、自分はその一部を今年の 3月に IETF89 で発表させてもらったりもしました。

その http2study の活動と HTTP2 という仕様自体の、一つのチェックポイントとして、このカンファレンスを通じて HTTP2 への関心と正しい理解が広がればと思います。

Jxck

2014-09-12

「for やめろ」またはイベントループと nextTick()

node.js nextTick setImmediate

ものすごく遅レスですが、LLDiver で @esehara さんの LT であった話。

forやめろ、あるいは「繰り返し」という呪縛から逃れるために

簡単に言うと、 1~10 までを出力する方法を複数考えるというもの。 for, while, 再帰, goto etc.. と出て、途中で終わっちゃったので結論はよくわかりませんでしたが、 Node ではどれも使わずにできるな、と思ったのでちょっと例を出してみます。

ちなみに、タイトルでネタバレしている通りイベントループの話です。そしてよくある「イベントループとは何か」「なぜ止めてはいけないのか」「process.nextTick() とは何か」「setImmediate() と何が違うのか」などを解説する良い例だったので、書いてるうちに実はそっちがメインの解説となりました。

サンプルの実行結果は Node v0.11.13 です。(書き終わってから stream の古いインタフェースだったことに気づいた、、ごめんなさい)

リソースの読み込み

例えば、ファイルやネットワークからデータを次々に読む場合、そのファイル相当に対して、 read() 的な API を何度も呼ぶことになるでしょう。

ここでは、標準入力経由で大きなデータをガンガン読み込む例を考えてみます。例えば Go で書くとこんな感じになるでしょう。(エラー・終了処理は無視する)

package main

import (
    "fmt"
    "os"
)

func main() {
    file, _ := os.Open("./bigfile")

    for {
        data := make([]byte, 65536)
        n, _ := file.Read(data)
        fmt.Printf("%s", data[:n])
    }
}

Go ではファイルを読む方法はいくつかありますが、ここでは低レベル API を使うため、バッファを毎回確保し for を回してそこに入れています。回さないと一回読み出してプログラムが終了してしまうので、 for が必要です。

しかし、これを Node のイディオムで書くと、以下のようになります。

var fs = require('fs');
var bigfile = fs.createReadStream('./bigfile');

bigfile.on('data', function(chunk) {
  console.log(chunk);
});

for や while、再起、 goto などは使っていません。使っているのは、データが読み込まれたタイミングで発生するイベントです。

for を使っていないのだから、これを用いると出題である「for を使わずに 1~10 まで表示」という問題は、ちょっと変えれば解決します。

var fs = require('fs');
var bigfile = fs.createReadStream('./bigfile');

var c = 1;
bigfile.on('data', function(chunk) {
  console.log(c++);
  if (c > 10) {
    return bigfile.pause();
  }
});
// 1 2 3 4 5 6 7 8 9 10

さて、ではこれは本当に「for を使ってない」と言えるのでしょうか？プログラム上出てきていないので、「このプログラムファイル内」では間違いなく使っていません。しかし、実行時に「ランタイム」では繰り返し相当の処理が行われています。

それが、それこそが、「イベントループ」だ！！

イベント駆動とは何か

Node ではイベント駆動のモデルを採用しています。先の例では、ランタイム内で「データが標準出力から一定量読み込まれた」という状態の変化が発生した時に「 data イベント」というイベントを発生させることによって、それを EventEmitter である、bigfile に通知しています。

ユーザランドでは、そのイベントが発生したときに実施したい操作を、コールバックとして登録しておくことで、イベント発生時の処理を実行しています。

イベントループとは何か

ではランタイムでは、データを読む部分はどうなっているのでしょうか？

実装で言うと、ランタイム内では最初の Go の例と同じように、ループを回して何度もデータを読み出しています。 Node の場合、実際は while 文であり、読み出したデータが一定量溜まったら、ユーザ側にイベントとして通知しています。

ブラウザの中でも考え方は同じで、例えば DOM に対してクリックが発生したかどうかは、内部の while ループの中でずっと監視しています。

この while ループのことをイベントループと呼んでいるといって、差支えないでしょう。

外部リソースに頼らない書き方

さて、さっきの例はファイルを読んでおり、外部からの情報に頼るとかちょっとチート感あるでしょう。

そこで、外部リソースを無くして、純粋にイベントループのみを利用するとこんな感じにも書けます。

process.on('count', function(c) {
  if (c > 10) {
    return;
  }
  console.log(c);
  process.emit('count', ++c); // B
});

process.emit('count', 0); // A
// 0 1 2 3 4 5 6 7 8 9 10

ちゃんとやるなら自分で EventEmitter を継承したものを実装すべきですが、手を抜いてグローバルな process が EventEmitter であることを利用しています。イベントループが回る最初の回で、 count というイベントにコールバックを設定し、その後すぐに登録したイベントを emit() (A) で発火しています。

イベントループの最後に emit() (A) で発火された count のコールバックが実行されます。その中でまた emit() (B) して、次のループの最後にまたコールバックが呼ばれ、また emit() (B) が実行されます。

よって、このソースコードに関しては for なしで命題を実装できているわけです。(同じことは、ブラウザでやるなら addEventListener() と dispatchEvent() などで同じことができます。ちなみに拙作ですが Node.js の events の移植を使うこともできます。)

が、この実装では不十分です。というか、こんな実装したらイスが飛んできてしまいます。

emit はブロックする

一行足せばわかりますが、 emit() は対応するコールバックが終わるまでブロックします。つまり、そのコールバックの中でさらに emit() を呼ぶこの実装では、 emit() が終了待ちの列を作ります。

process.on('count', function(c) {
  if (c > 10) {
    return;
  }
  console.log(c);
  process.emit('count', ++c);
  console.log(c);
});

process.emit('count', 0);
// 0 1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1

要するにこれでは、実質的にただの「再帰」です。

そこで、毎回ループごとに emit() を実行してコールバックが終了するように、 process.nextTick() を使います。

ざっくり言えば、 process.nextTick() とは、このコールバックの実行を、「イベントループの次の周の最初」に実行するように登録する API です。

process.on('count', function(c) {
  if (c > 10) {
    return;
  }
  console.log(c);
  process.nextTick(function() {
    process.emit('count', ++c);
  });
});

process.emit('count', 0);
// 0 1 2 3 4 5 6 7 8 9 10

コールバックが emit() を予約して抜けるようになったイメージです。コールバックが終わっても、イベントループの次の周でまた emit() が実行され、それを繰り返します。

ともかく、 emit() によるループのブロックは防げていることがわかります。

が、しかしこのコードには注意すべき点が二つあります。一つ目は、同じ JS でもブラウザでは使えないこと。二つ目は、 process.nextTick() が実行されるタイミングです。

process.nextTick() が無い場合

ブラウザは、イベントループがあるにもかかわらず process.nextTick() 相当の API が無いため、イベントループの次の周に処理を登録するには、 setTimeout() を使っていました。

setTimeout() はそもそも、イベントループに対して処理を登録し、ループが回るたびに「指定された時間が経過していたら実行」するための API です。

process.on('count', function(c) {
  if (c > 10) {
    return;
  }
  console.log(c);
  setTimeout(function() {
    process.emit('count', ++c);
  }, 0);
});

process.emit('count', 0);
// 0 1 2 3 4 5 6 7 8 9 10

したがって、 setTimeout(fn, 0) のように、 0 秒後にタイムアウトするようにすると、イベントループに登録し、次の周では指定時間が経過していると評価されて、コールバックが実行されます。

これで同様のことが実現でき、ブラウザにはかつてこの方法しかありませんでした。

setImmediate()

しかし、イベントループの次の周に登録することと、 0 秒後に登録するのでは、本質的な意味が違います。また、内部的にも実行されるタイミングが微妙に違います。そこでこの setTimeout(fn, 0) でやりたかったことを標準の API にしたのが setImmediate() です。

この API は現時点では、特定のブラウザと Node.js の v0.9 以降で使用することができます。

process.on('count', function(c) {
  if (c > 10) {
    return;
  }
  console.log(c);
  setImmediate(function() {
    process.emit('count', ++c);
  });
});

process.emit('count', 0);
// 0 1 2 3 4 5 6 7 8 9 10

これで、少なくともこの目的であれば setTimeout(fn, 0) よりは、対応しているのであれば setImmediate() を使うことが推奨されます。では setImmediate() と process.nextTick() は Node 上では何が違うのでしょうか？

イベントループ上での実行タイミング

さて、同じようなことを行う API を二つ紹介しましたが、 Node の JS ランタイムの実装である V8 では、どちらもイベントループ上で実行されるタイミングが微妙に違います。

この辺については、 Object.observe()とNode.jsのイベントループの関係 - ぼちぼち日記で詳細に解説されています。エントリ中の図を引用します。

この図からわかるこの二つの違いは、大きくは I/O イベントの前後どちらで実行されるか、という点です。

process.nextTick(): I/O コールバックの前
setImmediate() : I/O コールバックの後

これは、最初の大きなファイルからの読み込みと組み合わせて書いてみるとよくわかります。

まずは process.nextTick() を使った数え上げの後に、ファイルの読み込み(I/O)を書いた例です。実行すると、数え上げが終わってからやっと I/O が始まっているのがわかります。

これは process.nextTick() が I/O よりも前に再帰展開されるからであり、その再帰が終わるまでイベントループがブロックされるていることを意味します。

var fs = require('fs');
var random = fs.createReadStream('./bigfile');

// I/O read
var c = 1;
random.on('data', function(chunk) {
  console.log('chunk');
  c++;
  if (c > 10) {
    return random.pause();
  }
});

process.on('count', function(d) {
  if (d > 10) {
    return;
  }
  console.log(d);
  process.nextTick(function() {
    process.emit('count', ++d);
  });
});

process.nextTick(function() {
  process.emit('count', 0);
});

// 0 1 2 3 4 5 6 7 8 9 10 chunk chunk chunk ...

同じコードを setImmediate() に一カ所だけ書き換えてみます。すると、 I/O 処理の後に数え上げ処理が実行されるため、両者がおおむね順番に実行されていることがわかります。 (ただし、 I/O の制御はカーネルが行っているため、イベントループ中毎回必ずデータが読まれるとは限らないため、交互とはならないことがあります。)

var fs = require('fs');
var random = fs.createReadStream('./bigfile');

// I/O read
var c = 1;
random.on('data', function(chunk) {
  console.log('chunk');
  c++;
  if (c > 10) {
    return random.pause();
  }
});

process.on('count', function(d) {
  if (d > 10) {
    return;
  }
  console.log(d);
  setImmediate(function() {
    process.emit('count', ++d);
  });
});

setImmediate(function() {
  process.emit('count', 0);
});
// 0 chunk 1 chunk 2 chunk 3 chunk 4 5 chunk...

そして、これは実は再帰じゃありません。イメージとしては、while ループの処理を動的にオン/オフしているイメージでしょうか？

イベントループハラスメント

先ほどの process.nextTick() の再帰のように同期処理によってイベントループを止めるというのは、その後の I/O 処理までループが到達しなくなってしまうことを意味します。これは、例えば再帰でフィボナッチ数列を出すような処理を Node で行うと、そこでイベントループが止まり、非同期 I/O を止めてしまうという意味であり、こうしたイベントループを止めてしまうような処理を「イベントループハラスメント」と言った人もいました。

ネットワーク系、特に Web 系のプログムでは、 I/O 周りがボトルネックになることが多いことから、この点を解決するために非同期 I/O を採用し、イベント駆動にするためにイベントループを回している Node にとって、そのループを止めるのは全てを台無しにする行為なので、そこを理解した上でイベントループを止めないようにするのが重要です。

そして、その一つのイベントループ、正確にはシングルスレッドで回っている while ループの上に処理を登録して、ループごとに完了した I/O を処理することができるのが Node のメリットであり、それが重たい I/O の待ち時間を無駄なく使うことができるアーキテクチャだったため、たくさんのスレッドを立ててロックを取り合い処理するモデルよりもシンプルで省メモリだったのが Node が他のランタイムと違ったところです。

イベントが発火した「後」に処理を登録するためには、確かにコールバックが必要です。コールバックが無いモデルを好む気持ちはわかりますが、イベント駆動でない限り、多くのランタイムは自分でこのイベントループ相当の while を回し、そこにフラグと処理を書くことになるとは思います。それたぶん Node がやってくれてることかもしれません。

(イベントループを止めずに、一周に一回フィボナッチを計算するという処理を setImmediate() で書くこともできます、やってみてください。)

for を使うなイベントループを使え

JavaScript では、あなたが for を回さなくても、イベントループはいつでもそこで回っています。それを止めないように、それに乗っかるように、あなたが書こうとした for が本当に必要か考えてみてはいかがでしょう？

2014-08-22

Web+DB Press vol.82 で Go の特集を書かせて頂きました #wdpress

update

2015/4/20: 技術評論社さんのおかげで、無料で公開されることになりました！

intro

タイトルのとおり、 Web+DB Press の vol.82 に

「はじめての Go」

というタイトルで特集記事を書かせていただきました。

Web+DB press vol.82 届いた。特集で「はじめての Go」を担当させていただきました。初見ももちろん、「Tour of Go の次」を探していた方の参考になれば幸いです！ #wdpress #golangjp pic.twitter.com/UbUue18wlp
— Jxck (@Jxck_) August 20, 2014

WEB+DB PRESS Vol.82

作者: 山口徹,Jxck,佐々木大輔,横路隆,加来純一,山本伶,大平武志,米川健一,坂本登史文,若原祥正,和久田龍,平栗遵宜,伊藤直也,佐藤太一,高橋俊幸,海野弘成,五嶋壮晃,佐藤歩,吉村総一郎,橋本翔,舘野祐一,中島聡,渡邊恵太,はまちや2,竹原,河合宜文,WEB+DB PRESS編集部
出版社/メーカー: 技術評論社
発売日: 2014/08/23
メディア: 大型本
この商品を含むブログ (1件) を見る

Web+DB に Go が載るのは、これが初めてだそうです！

Tour of Go の次

この特集は、 Google の Go 言語について、初心者を対象に書きました。

Go には Tour of Go というチュートリアルが用意されており、数か国語に翻訳されているため、初心者はまずここから始めるというパターンが多いと思います。

しかし、このチュートリアルはかなり初歩的な部分で終わっており、「この次に何をしよう」となると、もう自分でドキュメントを読みながら、コードを書いて覚える。という感じになり、若干飛躍が大きいところがありました。

いくつかある書籍も、ちょっと古い内容になりつつあります。

そこで、 Tour Of Go ではあまり扱われていない、標準パッケージの使い方、もう一歩踏み込んだ interface の使い方、並行処理の考え方などを盛り込んで、

「Tour of Go の次」

を意識して書きました。

もちろん本誌で初めて Go を知り、　Tour of Go をやっていない方でも Go を始められるように、言語の紹介や環境構築についても書いていますので、安心して読んでいただけるように書かせていただきました。

今回、特集を通して使用する Go のバージョンは執筆時点で最新の 1.3 です。

章立て

章立ては以下のようになっています(30 ページくらい)。

第1章：Go言語の特徴と環境構築第2章：基本文法第3章：型システム第4章：標準パッケージ第5章:並行プログラミング

内容

1章

Goが生まれた背景や、全体的な特徴について触れてから、Go の環境構築方法を解説しています。初心者がハマりやすい、環境変数 GOPATH に始まる一連のプロジェクト構成や、ビルドの方法、 Github へのパッケージ公開までできるようになります。

最近主流の GOPATH 固定スタイルや、クロスコンパイルの準備方法など、ちょっと探しづらい情報についても載せています。

2章

ひたすら基本文法を解説しています。 Go の文法仕様は割とコンパクトな方だとは思いますが、書き始めたらページが膨らみすぎたため、やむなく削ったところはたくさんあります。

扱い切れなかったことは多くありますが、それでも基本的にここに載っていることを知っていれば、公式のドキュメントを読み進めたり、公開されているコードを眺める上での第一歩とはなると思います。

3章

この章のテーマは型で、名古屋方面の方々などに殴られそうな表題になっていますが、内容はいたってシンプルに、 Go の type キーワード周辺の扱いについてです。

struct や interface の定義や使い方から、型の埋め込み(embed)、 type assertion や type switch といった内容をまとめています。メインは文法であり、型についての専門的な内容ではないので、ご容赦ください。

4章

Tour of Go に足りてないことの一つが標準パッケージの扱いだったと思っています。 Go は標準パッケージが非常に充実しているので、そのなかから良く使うであろう encoding/json, io, net/http, html/template などを取り上げて扱いを解説し、最後はそれらを組み合わせて簡単なHTTPサーバを作成します。

実は裏テーマとして、 io.Reader/io.Writer の扱いを重視しています。特にサーバのようなものを書く場合、これらの組み合わせ方法を知っておくと非常に役に立ちますし、ドキュメントを読んで、それらがどう組み合わせられるかがわかるようになると思います。

5章

並行処理も Go の特徴的な部分なので、 goroutine, channel, for-select, などを使って並行処理をする方法と、その考え方の基本的な部分を順を追って解説しています。

sync.WaitGroup による同期や、 time.After() によるイベント、バッファ付き channel の扱いなども扱っており、応用することで自分が必要とする並行処理を組むための基礎になると思います。しかし、この章はサンプルコードがどうしても大きくなりがちなので、削ったものも多くありました。ここより先は go concurrency でググれば腐るほどスライドが出てくるので、それらを読むと良いかと思います。

ペア執筆

ペアプロで作業をする方が良い場合が多いように、執筆も1つのキーボードを奪い合って行うスタイルでやると、誤字脱字に対する精度も上がるし、迷う部分をすぐに共有して議論できるし、集中もできるし、なにより数時間 PC に向かってても進捗がゼロという状態を回避できていいのでは、と前々から思っていました。

そこで、 @inao さんから執筆の話を頂いたときに「俺とペア執筆してくれるならやります！」と説得を試みたところ、ちょっと強引ではありましたが、 3, 4 回ペア執筆をする機会を得られることになりました。

スタイルとしては、俺が先にラフ気味な WIP 原稿を書いておき、それを二人で校正しながら、構成や言い回し、記法、誤字脱字を見ていく感じです。編集者である @inao さんと一緒に執筆すれば、 @inao さんが別途校正して gitlab で issue を立てて「これはこうではありませんか？」みたいなやりとりをするコストもだいぶ減るだろうし、俺が書いて分かりにくいところも、すぐに「これではよく分からない」と指摘してくれるので、はかどるのでは無かろうかという狙いです。

あと単純にやってみたかったので、 @inao さん直々に俺の家に来てもらい、1台の Mac を前にペア執筆を試してみました。

結果として、 @inao さんとペアで校正をするメリットはあったと思います。 1つの章の校正がおおむね三時間くらいで終わり、これは校正と修正が別になった時のトータルコストと、俺が修正するふりして思わず Twitter やらハテブを開いてしまうリスクを限りなくゼロにできるので良かったと思います。

しかし、校正までの Go の解説原稿を書く部分については、やっぱり俺が先に用意しないといけないのですが、そこの用意があまり進まず、結果的に俺ができてない現行を書いてるのを、俺の隣で稲尾さんが監視するという感じになってしまい、最終的には「やっぱりあまり効果出てないね」ということで普通のスタイルに収まっていってしまいました。

俺がもうすこし原稿部分の作業を前もってやれれば、かなり効率よく校正進められたんじゃないかなと思います。原稿部分をまた別の人とペア執筆するというのも面白かったかも。ともあれ、もう少しうまくやれたらという反省とともに、悪くはないなと思いました。

あと、毎回終わった後 @inao さんとご飯を食べにいって、色々な話をしたのが楽しかったです。そこでのやり取りは、先日公開した #mozaicfm の REST の回にも濃く影響していたりしますw

謝辞

Web+DB はこれで三回目ですが、なんどやっても執筆はなかなか難しいですね。。

そんな中でも、俺のわがままにつきあって仕事終わりに俺の家までペアプロしに来てくれた @inao さんには本当に感謝しています。楽しかったです！

筆が止まってた頃に、原宿某社で行われた黙々会で、その場ハンズオンをやらせてもらったおかげで、それがそのまま 4, 5 章の原型になりました。 @hokaccha さん、 @yosuke_furukawa さん、 @sugyan さんありがとうございました。

そして、 ~~暇そうにしてるところを俺につかまって~~ 大事な休日を空けて、つきっきりでレビューしてくれた @tenntenn には感謝してます。あれも濃い議論もできたし、楽しかった。

書き物業はお腹いっぱいなので、しばらくはコード書く方に専念したいです。

2014-07-26

Go のスライスでハマッたところ

go golang Fossil slice

intro

先日 GoのSliceもヤバイ - Qiita こんな記事をみて、別の挙動だけどスライスの内部を理解しきれていなかった頃のことを思い出した。

結構前に謎に思っていた挙動についての話。以前この挙動を解説しようと思って、前提として書いたスライスの内部構造の記事が、 Go のスライスの内部実装だったのですが、そっちを書き終わって満足してしまい、本題を忘れていました。

この挙動は、先のブログで説明した内容がわかっていないと、なかなか理解できないかも。わかってしまえば簡単ですが。

やりたいのは、関数側でスライスを操作したときの呼び出し側での結果。順を追ってみてみます。

配列を関数内で変更する

関数は値渡しで、配列はそれ自体が値なので、まるっとコピーされます。以下の例は、戻り値で返さないと、呼出側は変化しません。

package main

import (
    "log"
)

func init() {
    log.SetFlags(log.Lshortfile)
}

func increment(a [3]int) {
    // a は配列自体のコピー
    for i := range a {
        a[i] += 1
    }
    log.Println(a) // [2 3 4]
}

func main() {
    a := [3]int{1, 2, 3}
    increment(a)
    log.Println(a) // [1 2 3]
}

スライスを関数内で変更する

スライスは、配列(以下、内部配列という)への参照を持つ構造になっているので、スライスを値渡しして関数内で操作した場合、同じ内部配列を参照しているスライス(つまり同じスライス)にも、変更が反映される。

package main

import (
    "log"
)

func init() {
    log.SetFlags(log.Lshortfile)
}

func increment(a []int) {
    // slice の値渡しなので、参照先の配列は同じ
    for i := range a {
        a[i] += 1 // ここは参照先配列の値を変える
    }
    log.Println(a) // [2 3 4]
}

func main() {
    a := []int{1, 2, 3} // slice
    increment(a)
    log.Println(a) // [2 3 4]
}

関数内でスライスに append() (cap 無し)

しかし、 append() は、 cap のサイズが足らない場合は、内部配列を確保しなおすため、以下は戻り値としてスライスを返さないと、呼び出し側のスライスには変更が反映されない。

func add(a []int) {
    a = append(a, 4) // 新しい内部配列を作る
    log.Println(a)   // [1 2 3 4]
}

func main() {
    a := []int{1, 2, 3} // この時点で cap は 3
    add(a)
    log.Println(a) // [1 2 3]

}

スライス自体のポインタを渡す方法を使うならこう。

func add(a *[]int) {
    *a = append(*a, 4) // 新しい内部配列を作る
    log.Println(*a)    // [1 2 3 4]
}

func main() {
    a := []int{1, 2, 3} // この時点で cap は 3
    add(&a)
    log.Println(a) // [1 2 3 4]
}

スライスを関数内で append() (cap あり)

append() はもし cap に余裕があるなら、新しい内部配列は作りなおさず、そのまま末尾に追加する。内部配列を作り直さない場合、 append() の戻り値は同じスライスらしい。(なので、 append() の戻り値をとらなくてもよさそうだが、戻り値をとらないとコンパイルエラーになる)

func main() {
    a := []int{1, 2, 3}
    log.Printf("%p, %v", a, a) // 0x18244010, [1 2 3]
    a = append(a, 4)
    log.Printf("%p %v", a, a) // 0x18239240 [1 2 3 4]

    a = make([]int, 3, 4)
    a[0], a[1], a[2] = 1, 2, 3 // まだ cap に余裕がある
    log.Printf("%p, %v", a, a) // 0x18244080, [1 2 3]
    a = append(a, 4)
    log.Printf("%p %v", a, a) // 0x18244080 [1 2 3 4]
}

ここまでが前提。

問題の挙動

append() を関数内で行う。この場合、 cap に余裕があった場合は、内部配列の空き部分にそのまま追加されて、呼び出し側にも反映されるだろうという予想。

しかし、実際はそうならない。

package main

import (
    "log"
)

func init() {
    log.SetFlags(log.Lshortfile)
}

func add(a []int) {
    a = append(a, 4)           // 配列自体は更新されないはず
    log.Printf("%p, %v", a, a) //  0x18244010, [1 2 3 4]
}

func main() {
    a := make([]int, 3, 4)
    a[0], a[1], a[2] = 1, 2, 3 // まだ cap に余裕がある
    log.Printf("%p, %v", a, a) //  0x18244010, [1 2 3]
    add(a)
    log.Printf("%p, %v", a, a) // 0x18244010, [1 2 3]
}

内部配列には余裕があり、そこに追加されているはず。スライスのアドレスは変わっていないため、間違いなく同じものを表示している。しかし、関数内では 4 つになっているのに、呼び出し側が更新されていないのはなぜか。またはどうしたら表示されるようになるか。

関数のシグネチャは一切変えず、最後の出力の手前に一行追加するだけで解決できます。

良かったら考えてみてください。

2014-06-23

Go 1.3 で入った sync.Pool

go golang

Intro

先週 Go 1.3 が公開されましたが、 sync パッケージに Pool という API が追加されました。ぱっと見なんだかよくわからなかったので調べてみました。

sync.Pool

とりあえず、 GoDoc を訳したのでそれは最後に全部掲載します。要点としては以下。

従来独自に実装していた、 Free List を標準に入れた
Weak Map (弱参照)になっている
goroutine safe である

用途

一般的な FreeList の役割は、既に割り当て(Allocate)されたメモリが不要になった時、開放する代わりに List に持っておいて、メモリが必要になったらそこから取るというもの。(という理解) もし、不要になったメモリを捨てると、 GC の負荷が上がるし、再割り当ての負荷もあがるので、無駄が多くなる。 Go は C や C++ でやっていたような、システムに近い低レイヤのプログラムを書く用途でも使われるので、 GC はあるものの、こうした細かいメモリ管理を行いチューニングを行うこともあります。

実際に、標準でも fmt と regexp で、こうした用途の実装がなされていました。(go1.2)

多少実装はことなりますが、概ね以下の指針で実装されています。

[]interface{} に格納
Get(), Put() を持つ
sync.Mutex などでロックを取る

fmt では具体的にはこんな感じ。

type cache struct {
    mu    sync.Mutex
    saved []interface{}
    new   func() interface{}
}

func (c *cache) put(x interface{}) {
    c.mu.Lock()
    if len(c.saved) < cap(c.saved) {
        c.saved = append(c.saved, x)
    }
    c.mu.Unlock()
}

func (c *cache) get() interface{} {
    c.mu.Lock()
    n := len(c.saved)
    if n == 0 {
        c.mu.Unlock()
        return c.new()
    }
    x := c.saved[n-1]
    c.saved = c.saved[0 : n-1]
    c.mu.Unlock()
    return x
}

func newCache(f func() interface{}) *cache {
    return &cache{saved: make([]interface{}, 0, 100), new: f}
}

var ppFree = newCache(func() interface{} { return new(pp) })

しかし、これにはいくつかの問題があります。

パッケージごとに同じような実装が必要
気をつけて Lock-UnLock しないと goroutine-safe にならない
キャッシュから明示的に参照を消さないと GC されない

そこで、こうした機能自体を Go 標準に持ってはどうかという話を、前回の GoCon にも来日した Bradfiz が提案したのがことの始まりのようです。そもそもこうした機能を標準に持つのか？名前は Cache か Pool か? API はどうするか？など色々議論が重ねられた末に、今の形に落ち着き、今回 go1.3 に取り込まれたようです。

API

sync.Pool の API は非常にシンプルです。

http://golang.org/pkg/sync/#Pool

// キャッシュが切れたときのメモリ確保の方法を指定
type Pool struct {
    New func() interface{}
}

// キャッシュから取得
func (p *Pool) Get() interface{}

// キャッシュに戻す
func (p *Pool) Put(x interface{})

Put() したオブジェクトと、 Get() で取り出したオブジェクト間に参照関係はないものとして扱う必要があります。(例え 1 個入れて 1 個出したとしても)

WeakMap になっているため、 Get() で取り出したオブジェクトへの参照が切れれば、それは GC の対象になるようです。

実例としては、先ほど紹介した fmt のキャッシュ部分が 1.3 以降ではまさしくこの Pool を使って実装し直されています。

go1.2-1.3 での diff

簡単に言うと、以下だけで終わり。あとは get(), put() で実装されていたものが Get(), Put() に変わっただけです。

var ppFree = sync.Pool{
    New: func() interface{} { return new(pp) },
}

探せてないけど、他にもありそう。

注意点というか、よくわかってないところとして、 GoDoc の以下が引っかかっている。

逆に、 寿命の短いオブジェクトの free list を管理する用途では、 Pool は向いていない。
なぜなら、そのシナリオではオーバーヘッドが減らないから。そうしたオブジェクトでは、独自に free list を実装した方が良い。

どの程度から、使い分けるべきなのだろうか。

翻訳

理解のために GoDoc 適当に翻訳したので張っておきます。

A Pool is a set of temporary objects that may be individually saved and retrieved.
Pool は個別に管理され回収される、一時オブジェクトのセット。


Any item stored in the Pool may be removed automatically at any time without notification. If the Pool holds the only reference when this happens, the item might be deallocated.
Pool にストアされたどんなアイテムも、通知なしに自動で消されることがある。
もし、 Pool が参照しか持たない場合にこれが起こると、アイテムはメモリから消去される。（deallocated)


A Pool is safe for use by multiple goroutines simultaneously.
Pool は複数 goroutine から同時に使用可能。


Pool's purpose is to cache allocated but unused items for later reuse, relieving pressure on the garbage collector. That is, it makes it easy to build efficient, thread-safe free lists. However, it is not suitable for all free lists.
Pool は、メモリに割り当てられているがもう不要なアイテムをキャッシュし、後で再利用することで、 GC の負荷を下げることを目的としている。
これにより、効率よくスレッドセーフな free list を作ることができる。しかし、すべての free list に適しているわけではない。


An appropriate use of a Pool is to manage a group of temporary items
silently shared among and potentially reused by concurrent independent clients of a package.
Pool の適した使い方は、並行する独立した、クライアントのパッケージから暗黙的に共有される、
再利用される可能性のある、複数の一時的なアイテムを管理すること。


Pool provides a way to amortize allocation overhead across many clients.
Pool は、複数のクライアントからのメモリ割り当てのオーバーヘッドを削減する方法を提供する。


An example of good use of a Pool is in the fmt package,
which maintains a dynamically-sized store of temporary output buffers.
The store scales under load (when many goroutines are actively printing) and shrinks when quiescent.
例えば、適した用途として、 動的にサイズを割り当てる一時的な出力バッファを管理する（標準出力としての） fmt パッケージがある。
複数の goroutine が頻繁に出力すれば、サイズは増えるし、少なければ縮小する。


On the other hand, a free list maintained as part of a short-lived object is not a suitable use for a Pool, since the overhead does not amortize well in that scenario. It is more efficient to have such objects implement their own free list.
逆に、 寿命の短いオブジェクトの free list を管理する用途では、 Pool は向いていない。
なぜなら、そのシナリオではオーバーヘッドが減らないから。
そうしたオブジェクトでは、独自に free list を実装した方が良い。

Outro

細かいチューニングが必要なプログラム以外では、あまり使うことは無いかもしれないですが、知っておいて損はなさそうです。

2014-05-12

ハイパフォーマンスブラウザネットワーキング書評

書評 performance

Intro

執筆段階から、 Web で無料閲覧できた High Performance Browser Networking が、紙の本として出版され、その翻訳本が完成したということで、献本を頂きました。

原著には本当にお世話になったし、 HTML5Experts.jp で書いた Make the Web Faster の連載でもよく参考にした本なので、日本語で読めるようになったのは非常にありがたいですね。

本当はレビュアの依頼を頂いたのですが、色々あって他の方に振ったりしてしまったので、せめて全力で書評させていただきます。

やっと献本頂いたイリヤ本ゆっくり読める。日本語で読めるのは素晴らしい。 #http2study pic.twitter.com/Zy00OOy6ve
— Jxck (@Jxck_) 2014, 5月 11

Make the Web Faster

ところで、 Google が Make the Web Faster というプロジェクトを持っているのをご存知でしょうか？この “Make the Web Faster” のページには、文字通り Google が「Webを速くするため」に開発したプロダクトや、新しい仕様の提案、ベストプラクティスなどがリストされています。

具体的には以下の様なものが上がっています。

WebP
TCP Fast Open
Google DNS
Google Hosted Libraries
Page Speed
SPDY
etc.

見ると、それぞれ仕様だったり、プロダクトだったり、サービスだったりと粒度は違います。もちろん、ページ内ではもう少し整理されていますが、これらはレイヤの上から下まで、 Google が「Web を速くするため」にやってきたことが全て集約されているためです。

Web のパフォーマンスといえば「ハイパフォーマンス Web サイト」という書籍があります。この本では、 Web のフロントエンド寄りのエンジニアに対して、サイトを構築する上でのノウハウをいくつかのプラクティスにまとめ、それを紹介しています。

この本の初版が 2008 年に出版され、その 2 年後には「続編」が倍のページになって出版されました。その理由には以下の様なものが見て取れます。

Web に求められるパフォーマンスの要件が、刻々とシビアになった。
Web に求められるユースケースが、文書閲覧にとどまらず、ゲームなども含め格段に増えた。
右肩上がりと目されていたエンド帯域が、モバイルの普及によって一旦下がった。
パフォーマンスチューニングするための選択肢が、格段に増えた。

この変化に対して、包括的に適切な対策をするのは、決して簡単なことではありません。そこで、 Google はこうした変化に対する適切な対策についてノウハウを構築し、合わせてツールやライブラリ、 Google がホストするサービス、新しい仕様としての提案などとしてリリースし、それを積み上げたのが "Make The Web Faster" なのです。

Ilya Grigorik

Ilya は、今は Google の Developers Advocate (俗にいうエヴァンジェリスト的なポジション) として、この Google が培ったパフォーマンスのプラクティスや、ツール・サービスの紹介を含めた啓蒙活動をしています。(元々は Google Analytics かなんかでエンジニアをやっていたはず)

そのため Google I/O や Youtube の Chrome Developers のチャネルなどでも度々登場し、 Make The Web Faster にあるようなパフォーマンスに関するありとあらゆるレイヤの話をしています。日本にも一度、 Google Page Speed あたりの話をしに来日していました。

彼が凄いのは、ネットワークに係る本当に全てのレイヤについてキチンと理解しており、さらにコード(Ruby)も書けてデプロイもできる優秀な技術者だということです。(しかも確かすごく若い)

この本の冒頭には、先に述べた「ハイパフォーマンス Web サイト」の筆者である Steve Souders の Forward(前書き) が寄せられています。

“Good developers know how things work. Great developers know why things work.”
「良い開発者はどのように動作するかを知っている、素晴らしい開発者はなぜ動作するかを知っている。」

そして Steve は Ilya が殆ど全てのレイヤについて、「どのように動作し」、「なぜ動作するのか」を知っているエンジニアであり、この本は、 Ilya が最先端のネットワークの基礎と最新の進化を、「なぜ動作するのか」まで書き下ろした本であると紹介しています。

ハイパフォーマンス "ブラウザ" ネットワーキング

Web というレイヤで開発をしていれば、 "HTTP" つまり Layer7 のアプリケーション層だけ知っていれば十分かというと、そうでないだろうことはハイパフォーマンス Web サイトなどを通じて、ある程度一般に認識されたものかと思います。

なぜなら、それらをキチンと分かっていないと、複雑なアプリを、複雑なネットワーク環境に乗せて、多様なユーザに適切なパフォーマンスで提供することはもはや不可能だからです。

では、実際にどの程度の範囲で知識を持っていれば良いのかというと、難しいところです。 TCP/UDP の基本的な知識はもちろん、近年では Wifi やモバイルのネットワークについての知識も必要かもしれないし、アプリのレイヤでも HTTP だけではなく WebSocket や WebRTC なども出てきています。

この本は、「ブラウザ」という文字が入っており、実際にブラウザをインタフェースとした時に関わる、 Web 開発者が知っているべき技術のほとんどが紹介されています。ちなみに日本語版のサブタイトルは「ネットワークアプリケーションのためのパフォーマンス最適化」となっていますが、原著のサブタイトルは以下です。

"What every web developer should know about networking and web performance"
「ネットワークとパフォーマンスについて、全ての Web 開発者が知るべきこと」

その通り、各技術は「どのように動作するのか？」という API の話と合わせて、「なぜ動作するのか？」という Protocol のレベルまで解説されています。また、観点として「パフォーマンス」を意識した解説がされており、ベストプラクティスやチューニングの観点、ものによっては計算の方法などが載っており、章末には「パフォーマンスチェックシート」が付録される構成になっています。速度的なパフォーマンスだけでなく、モバイルの章ではバッテリの消費などにまで言及されているあたりからも、網羅性を見て取れると思います。

範囲としても、 TCP(TCP-FO や SlowStart の話も) や UDP(NAT トラバーサルも) の本当に基礎の部分から、 WebSocket(subprotocol 含む) や WebRTC(TrickleICE まで) など、プロトコルの基礎から最新動向まで紹介されています。

もちろん、現在策定中の HTTP2 についても紹介されており、SPDY から続く HTTP 改善の歴史や、設計の方針などについて解説されています。 (章だてが HTTP2.0 となっているのからもわかるように、 Draft こそ少し古いですが、読んだところ HTTP2 の概念を理解する上では十分に最新な記述だったと思います)

これからの Web 開発の現場では、参照したくなる場面が必ず増えていくと思うので、少なくともまだ原著は Web で無料で見られることは知っておいて損は無いでしょう。

そして、それが翻訳されて日本語で読めることに 4000 円の価値が見いだせるなら、是非手元に置いておくことをおすすめします。

ハイパフォーマンスブラウザネットワーキング ―ネットワークアプリケーションのためのパフォーマンス最適化

作者: Ilya Grigorik,和田祐一郎/株式会社プログラミングシステム社
出版社/メーカー: オライリージャパン
発売日: 2014/05/16
メディア: 大型本
この商品を含むブログを見る

Outro

この本は、これからの Web パフォーマンスについて言及する際に、かなりの確立でリファレンスされることになるでしょう。この本が日本語で読めることには、とても価値があると思います。

翻訳者の方、ならびに短い時間でレビューをこなしたレビュアの方々、本当にお疲れ様でした。

Jxck

2014-04-30

Go のスライスの内部実装

golang go slice

History

14/05/09: Merge2 を修正しました。http://twitter.com/jbking/status/464659353945911297

Intro

Go のスライスは、いわゆる LL 系の言語が持つ可変長配列の実装と似ています。よって LL のような手軽な扱いをすることもできますが、その内部実装を知ることでより効率の良いメモリハンドリングができ、パフォーマンスを改善や、メモリーリークの防止などに繋がる可能性があります。

この辺は SWrap というライブラリを作りながら勉強したので、今回は、この Go のスライスの内部実装を解説します。

Go の配列

スライスを知るためには、まず配列について知っておく必要があります。

Go の配列は固定長のため、以下のように長さを指定して宣言します。

var arr [4]int

func main() {
    arr = [4]int{1, 2, 3, 4}
    log.Println(arr)
}

配列は長さを含めて型です。つまり、以下の関数は [4]int のみを引数として許し、 [5]int は型が合わずコンパイルでエラーになります。

func fn(arr [4]int) {
    log.Println(arr)
}

func main() {
    arr4 := [4]int{1, 2, 3, 4}
    arr5 := [5]int{1, 2, 3, 4, 5}
    fn(arr4) // ok
    fn(arr5) // cannot use arr5 (type [5]int) as type [4]int in function argument
}

関数に渡した場合は、値渡しになります。つまり渡した先では配列がまるっとコピーされます。参照渡しにしたい場合は、ポインタを渡します。

func fnV(arr [4]int) {
    for i, _ := range arr {
        arr[i] = 0
    }
    log.Println(arr) // [0, 0, 0, 0]
}

func fnP(arr *[4]int) {
    for i, _ := range arr {
        arr[i] = 0
    }
    log.Println(arr) // [0, 0, 0, 0]
}

func main() {
    arr := [4]int{1, 2, 3, 4}
    fnV(arr)
    log.Println(arr) // [1, 2, 3, 4]
    fnP(&arr)
    log.Println(arr) // [0, 0, 0, 0]
}

また、配列の長さは変更できないため、長さを増やしたいなどの場合は、長い配列を宣言し自分で移し替える必要があります。(後述する append() や copy() は、配列には使用できません)

Slice

スライスは、可変長配列のようなものです。その実体は、固定長配列への View として実装されています。

まず、使いかたを見てみます。

配列の宣言から長さの情報を消すと、スライスとして宣言されます。長さの情報が無いため、関数に渡す際に実際いくつの要素が入っていても、要素の型が同じなら渡すことができます。

関数に渡す場合は、ただスライスを渡せば、渡した先で中身を書き換えることができます。 fnP() のようにスライス自体のポインタを渡すことも可能です。

func fnV(arr []int) {
    for i, _ := range arr {
        arr[i] = 10
    }
    log.Println(arr) // [10, 10, 10, 10]
}

func fnP(a *[]int) {
    arr := *a // 一旦中身をとりだす
    for i, _ := range arr {
        arr[i] = 20
    }
    log.Println(arr) // [20, 20, 20, 20]
}

func main() {
    arr := []int{1, 2, 3, 4}
    fnV(arr)
    log.Println(arr) // [10, 10, 10, 10]
    arr = []int{1, 2, 3, 4}
    fnP(&arr)
    log.Println(arr) // [20, 20, 20, 20]
}

内部実装

内部では、スライスは固定長配列への View として実装されています。具体的な構造は、以下のようなイメージです。

宣言

まず、以下のようにスライスの宣言と初期化同時に実行してみます。この時、内部的には固定長配列である [4]int のメモリが確保され、値が入り初期化されます。スライスはその固定長配列への参照(コメント内の * )を持ちます。 len() を使って、値の数も見てみましょう。

// []int    *
//          |
// [4]int  [1, 2, 3, 4]
arr := []int{1, 2, 3, 4}
log.Println(arr, len(arr)) // [1 2 3 4] 4

make()

次にスライスのもう一つの宣言方法、 make() を使って書きなおしてみます。 make() は第一引数に型を、第二引数に長さ(len)を指定します。以下の場合は、配列 [4]int のメモリを確保し、型に応じたゼロ値で初期化します。 (int の場合は 0 です)

変数 arr は、その配列への参照が格納されます。

// []int    *
//          |
// [4]int  [0, 0, 0, 0]
arr := make([]int, 4)
log.Println(arr, len(arr)) // [0 0 0 0] 4

したがって、値は index 0~3 までは代入可能です。 index 4 は、 index out of range になります。

// []int    *
//          |
// [4]int  [1, 2, 3, 4]
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5 // index out of range

append

len よりも外側の領域まで値を追加していくためには append() を使います。 apeend() は、スライスの末尾に値を追加し、その結果を返します。以下は先ほど初期化したサイズの外、 arr[4], arr[5] まで値を格納しています。

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr = append(arr, 5)
arr = append(arr, 6)
log.Println(arr, len(arr)) // [1, 2, 3, 4, 5, 6] 6

では、この時内部の固定長配列はどうなっているのでしょうか？それを知るためには、 cap() について知る必要があります。

cap

cap() で内部配列のサイズを知ることができます。まず、以下の例で見てみましょう。

先ほどの make([]int, 4) で生成したスライスの cap() は 4 です。これは、内部配列の長さが 4 だからです。

よってこのスライスに対し 4 つまでは、値を格納できますが、 append() によって配列のサイズ以上に値を追加する場合は、内部の配列を拡張する必要があります。

Go は append() で内部の配列を拡張する時、必ず現在の配列の 倍の長さ の配列を確保し、そこにコピーするという実装になっています。実際に確認してみると、最後のスライスは、 len() が 5 で、 cap() は 8 を返しています。

// []int    *
//          |
// [4]int  [0, 0, 0, 0]
arr := make([]int, 4)
log.Println(arr, len(arr), cap(arr)) // [0 0 0 0] 4 4

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
log.Println(arr, len(arr), cap(arr)) // [1 2 3 4] 4 4
arr = append(arr, 5) // 内部で [8]int が確保され、そこに 5 つの値がコピーされる
log.Println(arr, len(arr), cap(arr)) // [1 2 3 4 5] 5 8
// []int    *
//          |
// [8]int  [1, 2, 3, 4, 5, , , ,]

最後の状態は、内部的には [8]int があり、そのうちの index 0~4 までが使われている状態です。 len() は値の入っている数、 cap() は内部配列のサイズ、 append() は末尾への追加と、足らない場合の配列の拡張を行っています。

make() で cap の指定

スライスに最初から沢山の値を入れることがわかっている場合、 append() で何度も配列を拡張するより、最初から大きな配列を内部に確保すれば、メモリ確保の回数を減らすことができます。

この、最初に確保する配列のサイズは、 make() の第三引数で指定できます。

例えば、 cap = 0 でスライスを確保し 5 個の値を append() していくと、合計で 5 回の配列確保(allocate) が行われます。

func Append1() {
    arr := make([]int, 0, 0) // 0, 0 (alloc)
    arr = append(arr, 0)    // 1, 1 (alloc)
    arr = append(arr, 1)    // 2, 2 (alloc)
    arr = append(arr, 2)    // 3, 4
    arr = append(arr, 3)    // 4, 4 (alloc)
    arr = append(arr, 4)    // 5, 8 (alloc)
}

cap を最初から 5 にしておけば alloc は最初だけで済みます。

func Append2() {
    arr := make([]int, 0, 5) // 0, 5 (alloc)
    arr = append(arr, 0)    // 1, 5
    arr = append(arr, 1)    // 2, 5
    arr = append(arr, 2)    // 3, 5
    arr = append(arr, 3)    // 4, 5
    arr = append(arr, 4)    // 5, 5
}

make() の第一引数 len を 0 にしているのは、値を初期化しないためです。初期化してしまうと、その範囲は添字アクセス、それ移行は append() と使い分ける必要もあるため、こうした指定をしています。

// []int    *
//          |
// [10]int  [ , , , , , , , , , ]
arr := make([]int, 0, 10)
log.Println(arr, len(arr), cap(arr)) // [] 0 10

ちなみに以下のような宣言では、暗黙的に len=0, cap=0 になります。

var arr []int // 0, 0

このように、スライスの下にある実配列を意識することで、効率の良いメモリ確保が可能になる場合があります。具体的には、一度確保(Allocate)したメモリを使い回し、確保の回数を減らすことで処理を高速化するといった場合です。

メモリの使い回し

上記を踏まえて次の「スライスの連結」を考えてみましょう。

以下のような実装の、メモリ確保面での効率を考えてみます。

func Merge1(a, b []int) []int {
    for i := range b {
        a = append(a, b[i])
    }
    return b
}

筋は悪そうですが、もし a の cap に b の len 分の余裕が必ずあるなら、配列の再確保は行われないため、これでも問題ないでしょう。しかし、 b の len が大きく、 a の cap が小さい場合は、再確保が何度も起こる可能性があります。

毎回、必ず一回確保することを選ぶのであれば、こうなります。 copy() は、第二引数のスライスの内容を、第一引数のスライスに移します。最初から、必要な長さを確保しているので、 alloc は一回で済みます。

func Merge2(a, b []int) []int {
    c := make([]int, len(a)+len(b))
    copy(c, a)
    copy(c[len(a):], b)
    return c
}

といいつつ実は append() はこんな書き方ができます。

func Merge3(a, b []int) []int {
    return append(a, b...)
}

配列確保も 1 回で最適化されるので、基本的にこの方法を使うのが良いでしょう。

GC

スライスから見える値が消えていても、内部配列に残っていることで GC されず値が残る場合があります。例えば、スライスから指定したインデックスの値を削除し、その分前に詰めて返す del() 関数を考えてみます。既にある内部配列内の移動だけで済ませれば、再確保はいらないので、以下のようにしてみます。

func del(a []int, i int) []int {
    copy(a[i:], a[i+1:])
    a = a[:len(a)-1]
    return a
}

func main() {
    a := []int{1, 2, 3, 4, 5}
    a = del(a, 2)
    log.Println(a, len(a), cap(a)) // [1 2 4 5] 4 5
}

メモリの Allocate も無く、スライス側から見ると値は消えています。

しかし、内部配列はどうでしょうか。 del() の後は、以下のようになっています。 (実際に a[:cap(a)] で確認できます。)

// []int    *
//          |
// [5]int  [1, 2, 4, 5, 5]
log.Println(a[:cap(a)])

このように、スライスからは見えない値が、内部の配列に残っている場合があります。例えば大きなサイズの構造体の参照を持つスライスなどの場合は、内部配列に参照が残っていることにより、 GC されない可能性もあります。

万全を期すためには、 del() を以下のようにし、末尾の値に、型に応じたゼロ値(宣言して初期化しないことで生成可能)を代入しておく方法があります。 int の場合は 0 ですが、参照型のスライスの場合は、ここが nil になります。

var zero int // ゼロ値
func del(a []int, i int) []int {
    copy(a[i:], a[i+1:])
    a[len(a)-1] = zero // ゼロ値, nil の代入
    a = a[:len(a)-1]
    return a
}

削除する範囲が大きい場合は、一旦別のスライスに対比することで GC を促す方法もあるでしょう。この辺の話は、 Slice Tricks や Arrays, slices (and strings): The mechanics of 'append' - The Go Blog、 Go Slices: usage and internals - The Go Blog などで紹介されています。

まとめ

Go のスライスの内部実装について、色々と細かい解説をしましたが、そういったことを抽象化して全て len=0, cap=0 で宣言したスライスを append() だけで拡張していくこともできるのが Go の手軽な部分です。カジュアルな用途では、それで十分でしょう。

しかし、スライスを多用したり、そこにサイズの大きい構造体を格納したり、詰替えや拡張をよく行うようになると、こうしたことを知っておくだけで効率が数倍変わることもあります。

処理の速度やメモリ確保については testing パッケージを用いたベンチマークを記述し、 go test コマンドにある、 -benchmem オプションを用いてベンチマークを実行すると、以下の様な感じで実行時間とともに alloc 回数を知ることができます。

PASS
BenchmarkAppend1   5000000         741 ns/op       120 B/op        4 allocs/op
BenchmarkAppend2  50000000        48.8 ns/op         0 B/op        0 allocs/op
ok    jxck  6.825s

あらかじめ、おおよそのサイズを見積もり、テストやベンチで測定と検証を繰り返しながらチューニングすることで、より効率の良いプログラムの作成に繋がると思います。

何か間違いなどありましたら、遠慮なく指摘頂けると幸いです。