FIFOの作り方を考える

FIFO(First In, First Out) を利用したときにソフトウェアだとArrayにメソッドとして実装されていたり、またKVSに実装されていたりして、あまり中身意識をすることが無いかもしれないけど、定期的に振り返って実装を考えると頭の体操になって楽しい。といってもそんなに難しいものじゃない。

雑に書いてしまえば以下の様な形になる。*1

FIFOの深さを256(8bit)、Push/Popされる値の大きさを32bitで考えることにしてみる。型をきっちり指定したいのでGoで。

package main
import "fmt"

var pushAddr, popAddr uint8
var stack[256] int

func push(value int) {
  stack[pushAddr] = value
  pushAddr++
}

func pop() (popValue int){
  if popAddr >= pushAddr {
    panic("NO stack values.")
  }

  popValue = stack[popAddr]
  popAddr++
  return
}

func main() {
  push(1)
  push(2)
  push(3)
  fmt.Println(pop())
  fmt.Println(pop())
}

上を実行してみると

$ go run fifo.go
1
2

最初にPushしたものが最初にPopされている。非常にシンプル。FIFOのどこのアドレスまでPushされているか管理する変数と、逆にどこまでPopされているかを管理する変数があればよいだけである。

こうすることでアドレスの加算だけで表現できる。上の例だと pushAddr は符号なし8bitの変数なので255までアドレスの値が到達すると更にpushされたときは0に戻るのでその点も気にすることがない。いくらか雑に書いているのでFIFOがあふれる処理とかを書いていないので厳密ではないがおおよそこういった中身になっているということを知って使うだけでも少し考え方が変わったりするかもしれない。

最近できるだけ原理的なところも知ろうとする様にしている。とはいっても、端折ってしまうことも正直多いのだけど概略だけでも抑えておく意味合いでも。

*1:一つの実装の考え方なので他の実装方法もあると思う