銀行家キューをGoで実装してみた

はじめに

GoのHTTP実装を読んだ知見をまとめる~FIFOを5通りで実装する~
でFIFOの実装を紹介しました。

そちらで銀行家キューも紹介したかったのですが、実装が難しそうなので保留にしていたのですが、実装することができたのでどのように実装したか紹介したいと思います。

実装は以下にあります。

https://github.com/KeiichiHirobe/go-http-learning/blob/main/fifo/banker_list.go
https://github.com/KeiichiHirobe/go-http-learning/blob/main/fifo/banker_list_test.go

実装してみた感想としてはバグなく（今もバグがあるかもしれません。そしたら優しく教えてください）作り込むまで結構苦労しました。

最初に設計考えて、実装、テスト書くまでは2時間くらいでできましたが、その後「これではダメでは？」と気づき、再度設計しなおしたりで、追加で3,4時間くらいかかりました。

そのあたりのことも紹介したいです。

銀行家キューとは

Purely Functional Data Structuresを紹介している20分でわかる Purely Functional Data Structuresが非常にわかりやすいです。

自分も本をよんでいるわけではなく、このスライドだけを頼りに実装しました。

Persistent data structure

まずは、この記事におけるPersistentの意味するところを明確にすると、
a = bとしたときのa/bに対する操作がb/aに影響を及ばさないこととします。

今回実装するのはFIFOなので、PushBack PopFrontが操作となりますので、a.PushBack(el) a.PopFrontがbに影響をあたえてはいけません。

安全にConcurrentに実行できるのかという観点でいうと、aとbに対するお互いの操作は安全に実行可能とします。例えばa.PushBack(el)とb.PopFront()を同時によんでも問題ないです。

一方、a/bそれぞれに対してのConcurrentな操作の安全性は保証していません。保証するには内部的にlockをとるようにすればいいだけですが、クライアントが今回の実装ではserialに呼ぶことを前提とします。

最後に補足しておくと、一般的にはPersistentな操作を保証するメソッドはnewA=a.PushBack(el) といったように戻り値に更新後のオブジェクトを返却し、aには操作を行わないことが多いです。

ただその場合は操作のたびにオブジェクトを新規に構築しなおさないといけません。Goの場合はコンパイラによるレシーバの暗黙的変換があるのを利用し、クライアントに違和感なく、以下のように書くことができます。

// PList represents a persistent singley linked list.
// The zero value for List is an empty list ready to use.
type PList struct {
    head *Element
    tail *Element
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
// レシーバはポインタ
func (l *PList) PushBack(v interface{}) *Element {
     // l.tail/l.headを更新
}

l := PList{}
l.PushBack(1)
l2 := l

この方法だとオブジェクトを構築し直さなくてよく、クライアントも呼び出し方がシンプルになる一方、代入によって構造体のコピーが発生します。また、代入先での操作が代入元へ影響しないのが直感的でない場合もあるでしょう。

これは一長一短かもしれませんが、GoのOSSでわりとみる気がしています。これがGoのイディオムなのかよくわかってませんが触れられている記事とかあれば教えていただきたいです。

これが気にいらないのであれば、オブジェクトを返却するようにすればいいだけであり、本質的には些細な点です。この場合は上記の例だとクライアントはPListのポインタを利用することになり、代入先は代入元と同じキューを指すでしょう。ライブラリ等で不特定多数に利用してもらう場合はこちらのほうがよさそうですね。

今回紹介するTwoListQueue/銀行家キューは両方Persistentです。

TwoListQueue

詳細は先ほどのpdfをみていただきたいのですが、そちらを参照しなくても記事が理解できるくらいには説明したいと思います。なお、計算量の観点ではここでは触れません。

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

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

先ほどのpdfに紹介されているhaskell実装は以下です。

data Queue a = Q [a] [a]
pushBack (Q front rear) e = Q front (e:rear)
popFront (Q [] r) = popFront (Q (reverse r) [])
popFront (Q (e:f) r) = (e, Q f r)

流れの例は以下です。

• PushBack(1) head:[] tail:[1]
• PushBack(2) head:[] tail:[2,1]
• PushBack(3)head:[] tail:[3,2,1]
• PopFront head:[1,2,3] tail:[] -> head:[2,3] tail:[]

こちらのGoでの実装も
https://github.com/KeiichiHirobe/go-http-learning/blob/main/fifo/two_list.go
https://github.com/KeiichiHirobe/go-http-learning/blob/main/fifo/two_list_test.go
にあります。

BankerQueue

銀行家キューのことです。
TwoListQueueの改良版です。
TwoListQueueではheadが空になった場合にreverseしてましたが、そうではなく len(head)+1 == len(tail) になったら遅延評価でreverseします。そしてその評価結果はメモ化しないといけません。

先ほどのpdfに紹介されているhaskell実装は以下です。

data Queue a = Q [a] Int [a] Int
-- fはhead,flはheadの長さ、rはtail、tlはtailの長さ
pushBack(Q f fl r rl) e = chk (Q f fl (e:r) (rl+1))
popFront(Q (e:f) fl r rl)= (e, chk (Q f (fl-1) r rl))
-- reverseはデフォルトで遅延評価される
chk (Q f fl r rl) =
if fl+1 == rl then (Q (f++reverse r) (fl+rl) [] 0)
else (Q f fl r rl)

流れの例は以下です。

• PushBack(1) head:r[1] tail:[]
• PushBack(2) head:r[1] tail:[2]
• PushBack(3)head:r[1]r[3,2] tail:[]
• PopFront head:[1]r[3,2] tail:[] -> head:r[3,2] tail:[]
• PopFront head:[2,3] tail:[] -> head:[3] tail:[]

BankerQueueのGoでの実装

前置きがだいぶ長くなりましたが、ここからが本題です。上記のhaskellのコードをGoで書き直しましょう。

まず、満たさないといけないことを整理しましょう
1. reverseは遅延評価する
2. 評価結果はメモ化する必要がある(一度評価したら次回評価時には評価結果を利用可能)
3. headでのリストの連結表現をPersistentにする

3だけ補足する必要があると思います。haskellではリストの連結はデフォルトでPersistentなので特に考慮不要なのですが、普通にGoにてsingly linked list等で実装してしまうとその部分がPersistentでなくなってしまうので全体としても当然Persistentではなくなってしまいます。

PersistentなFIFOの実装をしようと思ったらPersistentなFIFOの実装が必要になっているということです。
うまくやる方法があるのか、詳しい方いたら教えて欲しいのですが、今回はTwoListQueueで実装しました。

1,2については、Goだとsync.Onceを使えば良いでしょう。
sync.Onceの実装を念の為確認しましたが、同時にDoが呼ばれた場合、最初のfunc実行が完了するまで他方はブロックされるので、reverseされる前のheadが利用されることはありません。

// headL represents a singly linked list.
// reverse lazily and result is memorized.
type headL struct {
    head *Element
    once sync.Once
}

// eval may be called concurrently.
func (l *headL) eval() {
    l.once.Do(
        func() {
            // reverse list
            l.head = headAfterReverse
        },
    )
}

ここまでは順調に実装できたのですが、自分がおおいにハマったのは「reverse後のリストを他のリストとどのように連結するか」です。

たとえば、r[7..4]r[15..8]がheadにある状態でPopFrontしたとしましょう。このとき、[5,6,7]r[15..8]をどのように表現したら良いでしょう。

一番最初に思いついたのは[5,6,7]を一つの要素として扱うというものです。r[7..4]も一つの要素として扱っていたので実装は一番簡単です。この場合、PopFrontされた場合、headL.headの位置を一つ進めることになります。

ただこの実装は間違っています。複数のキューが共有していた場合、一方が位置を進めてしまうともう一方も進んでしまいます。これはよく考えれば当然でTwoListQueueによるPersistentはリスト操作に対して保証されているのであって要素への変更操作（例では5,6,7->6,7にすること等）は保証されません。

次に思いついたのは、[5,6,7]を３つの要素として扱うという方針です。unnestといえば伝わりやすいかもしれません。r[7..4]r[15..8]->567r[15..8]->67r[15..8]という流れになります。実装観点では、 headLに追加でtailフィールドを追加しておき、unnest時に、tailの次の要素をunnest前の次の要素に付け変えてあげればよいでしょう。

実はこの実装も間違ってます。複数のキューがr[7..4]を共有し、一方はr[7..4]r[15..8]もう一方はr[7..4]r[25..18]と成長した後それぞれ順にPopFrontを行った場合、後操作が上書きしてしまい、7の次のPopFront結果は共に18となってしまいます。

自分が思いついた正解は、^を改良したもので、reverseした後unnestするが、そのリストを元のリストから完全に切り離して管理するというものです。ソースコードをよんでしまった方が理解できそうですが、あえて表現すると、([],r[7..4]r[15..8]) -> ([5,6,7],r[15..8])となります。

一応最終実装を載せておきます(内容はGitHubと同じ)

package fifo

import (
    "sync"
)

func nop() {}

var (
    testHookEvaluated = nop
)

// BankerList represents a banker queue.
// BankerList is persistent list.
// The zero value for List is an empty list ready to use.
// see also http://www.kmonos.net/pub/Presen/PFDS.pdf
type BankerList struct {
    // head is a list of *headL.
    // head is a persistent queue.
    head TwoList
    // reversed is a list after evaluation of reverse.
    // at PopFront, first see reversed, and if empty PopFront from head and reverse the list and set to reversed.
    reversed *Element
    // the number of element like tailN, not the number of element for head.
    headN int
    tail  *Element
    tailN int
}

// headL represents a singly linked list.
// reverse lazily and result is memorized.
type headL struct {
    head *Element
    once sync.Once
}

// eval may be called concurrently.
func (l *headL) eval() {
    l.once.Do(
        func() {
            // reverse list
            var prev *Element
            for e := l.head; e != nil; e = e.next {
                el := &Element{
                    Value: e.Value,
                }
                if prev != nil {
                    el.next = prev
                }
                prev = el
            }
            l.head = prev
            // for test.
            testHookEvaluated()
        },
    )
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (l *BankerList) PushBack(v interface{}) *Element {
    e := &Element{
        Value: v,
    }
    if l.tail == nil {
        l.tail = e
    } else {
        e.next = l.tail
        l.tail = e
    }
    l.tailN++
    l.Chk()
    return e
}

// PopFront removes e from head of list l and returns e.
// Return nil if empty.
func (l *BankerList) PopFront() *Element {
    if l.reversed == nil {
        el := l.head.PopFront()
        if el == nil {
            return nil
        }
        he := el.Value.(*headL)
        he.eval()
        l.reversed = he.head
    }
    if l.reversed == nil {
        panic("Must not be empty")
    }
    el := l.reversed
    l.reversed = l.reversed.next
    l.headN--
    l.Chk()
    return el
}

// Check and move from tail to head if need.
func (l *BankerList) Chk() {
    if l.tailN == l.headN+1 {
        l.headN += l.tailN
        l.tailN = 0
        // reverse lazily
        lazyL := &headL{
            head: l.tail,
        }
        l.tail = nil
        l.head.PushBack(lazyL)
    }
}

　

まとめ

銀行家キューをGoで実装してみたところ100行ほどで実装できましたが、ここまで至るのに5,6時間かかり、わりと苦労しました。
haskellと比べると実装が大変なのでGoはむいてないとか言われちゃいそうですが、それは観点が違うような気がします。どちらかというとhaskellのリスト実装自体が銀行家キューのような工夫した構造をもっており、内部的には今回書いたような手続き型な処理がされているのではないだろうか。haskellは全く詳しくないのであくまで想像です。

参考までに、自分が少しは理解している関数型言語Scalaについては、コップ本の22章にそのようなことが紹介されており、以下引用します。

ScalaのListやListBufferクラスの実装における重要な部分をみてきた。リストは「見かけ上」は純粋関数型だが、「内実」ではリストバッファーを使った命令型実装になっている。これは、Scalaプログラミングではごく一般的な戦略だ。純粋性から逸脱する操作の効果を注意深く囲い込み、純粋性と処理効率の両方を手に入れようとするのである。

最後に注意深く考えたつもりであるが、間違っている点やもっと良い実装方針があると教えていただけるとうれしいです。