GoConference 2014 Autumn に参加してきました & ReadMIMEHeader() で使われているテクニック

GoCon 2014 Autumn に参加してきました。娘の誕生のために Spring には参加しなかったので１年ぶりになります。今年は去年に比べて、圧倒的に production で使ってるという話が聞けたのが印象に残りました。

残念ながら私はそういった話ができなかったのですが、Go で production 用に開発中のプロジェクトは社内に複数あるので、次回こそは (私でなくても KLab の誰かが) そういった発表をしてくれると思います。

ということで私は今年も低レイヤーな話になったのですが、私の時間配分が悪かったためにもうちょっと詳しく解説したかった net/textproto の ReadMIMEHeader() 関数についてさらっと流すしかできませんでした。

(一応資料は SlideShare にありますが、実際は時間の大半がデモだったのでスライドだけ見てもあまり伝わらないかもしれません)

ということで、ここで code reading していきます。

func (r *Reader) ReadMIMEHeader() (MIMEHeader, error) {
    // Avoid lots of small slice allocations later by allocating one
    // large one ahead of time which we'll cut up into smaller
    // slices. If this isn't big enough later, we allocate small ones.
    var strs []string
    hint := r.upcomingHeaderNewlines()
    if hint > 0 {
        strs = make([]string, hint)
    }

    m := make(MIMEHeader, hint)

ここで、 r.upcomingHeaderNewline() は buffered reader の中をチェックして、 \r\n\r\n までの間にある改行の数をカウントします。これをヒントに MIMEHEader (実態は map[str][]str) のヒントを与えます。同時に使ってる strs []string はあとで出てきます。

   for {
        kv, err := r.readContinuedLineSlice()
        if len(kv) == 0 {
            return m, err
        }

        // Key ends at first colon; should not have spaces but
        // they appear in the wild, violating specs, so we
        // remove them if present.
        i := bytes.IndexByte(kv, ':')
        if i < 0 {
            return m, ProtocolError("malformed MIME header line: " + string(kv))
        }
        endKey := i
        for endKey > 0 && kv[endKey-1] == ' ' {
            endKey--
        }
        key := canonicalMIMEHeaderKey(kv[:endKey])

ループの前半、 1line を読み込んで key を取得するまでです。 r.readContinuedLineSlice() は、バッファの中の []byte スライスを直接返します。 HTTP ヘッダは途中で改行が入ってる場合があるのですが、その場合もインラインで改行を空白に置き換えて、新しい []byte の確保をしないようにしています。

最後の canonicalMIMEHeaderKey() では、 key を Cache-Control の用に先頭の1文字を大文字にする処理をインラインで行っていて、別のバッファの確保＋メモリコピーはしていません。しかも、最後で string() に変換するところで一工夫.

   // The compiler recognizes m[string(byteSlice)] as a special
    // case, so a copy of a's bytes into a new string does not
    // happen in this map lookup:
    if v := commonHeader[string(a)]; v != "" {
        return v
    }
    return string(a)

init() で commonHeader というグローバル変数に

   for _, v := range []string{
        "Accept",
        "Accept-Charset",
        "Accept-Encoding",
...
        "X-Forwarded-For",
        "X-Imforwards",
        "X-Powered-By",
    } {
        commonHeader[v] = v
    }

と、よくある HTTP ヘッダを用意しておいて、そこにある key ならそれを返すことで、新しい string の確保を回避しています。この部分のコメントを読んで初めて、 m[string(byteSlice)] のアクセスでは実際に string を作らないという最適化があることを知りました。

さて、ループ後半、こんどは value の部分です。

       // Skip initial spaces in value.
        i++ // skip colon
        for i < len(kv) && (kv[i] == ' ' || kv[i] == '\t') {
            i++
        }
        value := string(kv[i:])

        vv := m[key]
        if vv == nil && len(strs) > 0 {
            // More than likely this will be a single-element key.
            // Most headers aren't multi-valued.
            // Set the capacity on strs[0] to 1, so any future append
            // won't extend the slice into the other strings.
            vv, strs = strs[:1:1], strs[1:]
            vv[0] = value
            m[key] = vv
        } else {
            m[key] = append(vv, value)
        }

HTTP ヘッダでは同一のキーが複数回出現することがあります。なので MIMEHeader の型は map[string]string ではなく map[string][]string になっています。

しかし、実際は大抵の場合、同じ key は1回しか出てきません。それなのに、 key ごとに長さ1の []string というスライスを用意するために、それぞれ配列をアロケートするのはもったいないです。

そこで最初に strs []str を用意しておき、 strs[:1:1] で長さ1かつ capacity も 1 のスライスを切り出しています。この : が2つ付くスライスはGo 1.2 で追加されました。 (Three-index slies) これにより、同じ key が複数回出現した場合にも普通に append すれば、後ろの要素を上書きすることなく新しい配列をアロケートするようになります。

まとめると、 HTTP ヘッダをパースする間にアロケートされる回数は、典型的には以下のようになります。

map (の内部のハッシュテーブル) -- 1回
strs []str -- 1回
string(value) -- ヘッダの数

map[string][]string というシンプルかつ高級な形で HTTP ヘッダを返す裏で、とても丁寧に余分なメモリアロケートやメモリコピーを避けるコードを書かれていることが解ります。