はじめに

引き続き、GoのHTTP実装と絡めて書く。今日はFIFO実装について。
経緯はこちら

Russ CoxによるHTTPクライアントのFIFO実装が工夫されていて非常に興味深かった。
コメントを見ると、Okasaki's purely functional queueを元に、少し工夫したものらしい。

今回はそれらに触れた上でGoでFIFOを5通りの方法で実装していきたいと思う。

実装およびテストコードはGitHubにあげてあります。

FIFO実装

実装方法を紹介していく。
ここでは、簡単なため、自分が実装した型名をもとに紹介していきます。

TwoListSlice実装はほぼコピペなので実装は正しいはずです。その他は何も参考にせずに実装したものなのでバグがあるかもしれません。悪しからず。

SList

とてもシンプルな実装で、ただのsingly linked listです。
各要素は値と次要素へのリンクを保持し、リスト構造としてはheadとtailを保持します。

もっともオーソドックスな実装なため説明は省きますが、一点補足すると、PopFront時に返却する要素のリンクをnilで上書きしています。これはGCにより回収されるようにするためで、Goの標準ライブラリのdoubly linked list実装を参考にしたものです。

PList

これは単純にSListに対してPushBackとPopFront時に全要素をコピーして作り直します。
SListのテストコードに書いたようにSListはpersistentでないため、キューAをキューBに代入した後キューAの操作がキューBに影響を与えてしまいます。

これを単純に回避するために全要素を操作時に毎回コピーしています。

この実装は明らかに重く、TwoListの方が良い実装です。

TwoList

これはOkasaki's purely functional queueの中で紹介されているpersistentなFIFO実装です。

本に興味はありますが私は読んでません。20分でわかるPurely Functional Data Structuresがとてもわかりやすく、TwoListの詳細な説明はそちらに譲ります。

TwoListだけであれば5分くらいで理解できると思います。銀行家キューが少し難しく、それ以降は自分はよく理解していません。

簡単にエッセンスを説明すると、キューを内部的に二つもちます。headから始まるキュー、tailから始まるキューを持ち、それぞれsingly linked list(それぞれリストの先頭要素のみ保持すればよいのがSListとは異なる)とします。

PushBack時にはtailから始まるキューの先頭（末尾ではない）に挿入します。PopFront時にはheadから始まるキューの先頭から取得しますが、空の場合はtailから始まるキューをreverseしてheadから始まるキューとしてswitchingしてから先頭から取得します。

これだけでpersistentになるのすごくないですか？？
騙された気分になりましたが、「persistentにするには、更新操作において、元構造から辿れるデータには更新は発生させないようにする」のがポイントと自分は理解しました。

reverseするのは一見計算量として不利になりそうですが、そうでもありません。また、さらなる改良をあり、そのあたりは先ほどの資料をみると良いと思います。

NaiveListSlice

リストではなく、goのSliceを利用した実装です。テストからわかるようにpersistentではありません。goのsliceは内部的に配列を参照し、データを共有するためです。
十分にシンプルなのでそのままコードを載せて説明は省略します。

package fifo

type NaiveListSlice []interface{}

func (l *NaiveListSlice) Len() int {
    return len(*l)
}

func (l *NaiveListSlice) PushBack(v interface{}) {
    *l = append(*l, v)
}

func (l *NaiveListSlice) PopFront() interface{} {
    list := *l
    if len(list) == 0 {
        return nil
    }
    v := list[0]
    *l = list[1:]
    return v
}

TwoListSlice

Russ CoxによるHTTPクライアントのFIFO実装で利用されている実装です。
^のコメントをそのまま載せちゃいます。

// A wantConnQueue is a queue of wantConns.
type wantConnQueue struct {
    // This is a queue, not a deque.
    // It is split into two stages - head[headPos:] and tail.
    // popFront is trivial (headPos++) on the first stage, and
    // pushBack is trivial (append) on the second stage.
    // If the first stage is empty, popFront can swap the
    // first and second stages to remedy the situation.
    //
    // This two-stage split is analogous to the use of two lists
    // in Okasaki's purely functional queue but without the
    // overhead of reversing the list when swapping stages.
    head    []*wantConn
    headPos int
    tail    []*wantConn
}

コメントの通りですが、TwoListと同様に二つのキューを利用しており、Sliceで実現します。ポイントは

• headPosを利用して、sliceを進めさせないこと(NaiveListSliceでいうところの*l = list[1:]はしない)
• switchingは発生するが、その際にreverseが発生しないこと

だと思いました。なお、テストからわかるように、この構造自体はpersistentではないので注意が必要です。

この構造はNaiveListSliceのような単純なFIFO実装と比べるとメモリを使い回すことができ、PushBack/PopFront操作が一定回数以上続くような場合に良いと思われます。

とても単純なPushBackとPopFrontが交互に一回ずつ続くケースを考えてみましょう。

NaiveListSliceの実装では、PushBack時のappendにおいて毎回1要素分のメモリ確保が発生します。なお、append実装に詳しくありませんが、自分の環境では1 -> 2 -> 4-> 8とメモリを確保していたのでそれ前提になります。

TwoListSlice実装では、最初の２回のPushBackのみ1要素分のメモリ確保を行い、その後は確保済みのメモリを使いまわします。

逆にいうと、使い回すからこそpersistentになりえないです。

HTTP実装

TwoListSliceですが、HTTPクライアントのidleConnWaitとconnsPerHostWaitに利用されています。

両方とも接続先のホスト(厳密にはconnectMethodKey)ごとに保持されます。それぞれ簡単に説明します。

idleConnWaitはidleとなるconnectionを待つキューです。idleなコネクションプールではなく、待つキューであることに注意してください。

idleなコネクションプールは全体の制限であるMaxIdleConns(デフォルト100)とホストごとの制限であるMaxIdleConnsPerHost(デフォルト2)により制限があります。

クライアントはリクエストを行う際、idleなコネクションが利用できないとわかると、idleConnWaitに「コネクションが欲しいという情報」をPushBackした後、接続先に対してdialします。dialの結果を受け取るより先に、idleConnWaitでの待ち順番が回り、idleなコネクションが利用できるようになった場合にはそれを利用し、不要となったdial結果のコネクションはidleなコネクションとして他のリクエストに再利用されます。そうでない場合は普通にdialの結果のコネクションをリクエストに利用します。

connsPerHostWaitはもっと簡単です。MaxConnsPerHost(デフォルト無効)によりホストごとのコネクション数が制限されていて、その制限を超過する場合、接続を試みる前にconnsPerHostWaitにPushBackされます。待ち順番が回り、接続を試ることが許可された場合、PopFrontされます。

では、なぜこれら二つのFIFOキュー実装にTwoListSlice構造を利用したのでしょうか。

それは、リクエストが一時的に多くなり、PushBackとPopFrontが連続的に行われ、キューがなかなか空にならないことを想定し、メモリを使いまわせるためだと思います。

実際、この実装がされた当初のレビューの際には以下のようにRuss Coxがコメントしてました。

I wanted to do something that would work well for an extreme case where there are many requests queued up on a small per-host limit, so I was careful in how I wrote the wantConnQueue,

おわりに

本当はキリもいいですし、銀行家キューも実装して「FIFOを6通りで実装する」としたかったのですが、銀行家キューは「遅延評価」、「メモ化」などの実装を関数型でないGoでおこなうのがやや大変そうだったので今回はあきらめました。

そのうち、銀行家キューも実装しようとおもってます。