Chapter 05

bufioパッケージによるbuffered I/O

さき(H.Saki)
さき(H.Saki)
2021.04.30に更新
このチャプターの目次
  1. はじめに
  2. buffered I/O
    1. bufio.Reader型の特徴
    2. bufio.Writer型の特徴
    3. ベンチマークによる実行時間比較
  3. bufio.Scanner
    1. トークン
    2. Scanner構造体について
    3. Scannerを使ってデータを読み取る
    4. (余談)Scannerを使わなきゃ困っちゃう場面
  4. まとめ

はじめに

標準パッケージの中にbufioパッケージというものがあります。
ドキュメントによると、「bufioパッケージはbuffered I/Oをやるためのもの」[1]と書かれています。

Package bufio implements buffered I/O.
出典:pkg.go.dev - bufio

これは普通にI/Oと一体何が違うのでしょうか。
使い方と一緒に解説していきます。

buffered I/O

bufio.Reader型の特徴

bufioパッケージにはこのパッケージ特有のbufio.Reader型が存在します。
NewReader関数を用いることで、io.Reader型からbufio.Reader型を作ることができます。

func NewReader(rd io.Reader) *Reader

出典:pkg.go.dev - bufio#NewReader

作ったbufio.Readerは、普通のio.Readerとは何が違うのでしょうか。中身を見てみましょう。

type Reader struct {
	buf          []byte
	rd           io.Reader // reader provided by the client
	r, w         int       // buf read and write positions
	err          error
	lastByte     int // last byte read for UnreadByte; -1 means invalid
	lastRuneSize int // size of last rune read for UnreadRune; -1 means invalid
}

出典:[https://go.googlesource.com/go/+/go1.16.2/src/bufio/bufio.go#32]

ここで重要なのはNewReader関数の引数として与えられたio.Readerを格納するrdフィールドがあるということではなく、バイト列のbufフィールドがあるということです。

このbufがどんな役割を果たしているのでしょうか。それはRead(p []byte)メソッドの実装を見ればわかります。

  1. len(p)が内部バッファのサイズより大きい場合、読み込み結果を直接pにいれる
  2. len(p)が内部バッファのサイズより小さい場合、読み込み結果を一回内部バッファbufに入れてから、その中身をpにコピー

出典:[https://go.googlesource.com/go/+/go1.16.2/src/bufio/bufio.go#198]

このように、ある特定条件下においては、「読み込んだ中身を内部バッファbufに貯める」という動作が行われます。
そのため、「もう変数pに内容を書き込み済みのデータも、bufio.Readerの内部バッファには残っている」状態になります。

bufio.Writer型の特徴

bufio.Readerがあるならbufio.Writerも存在します。
作り方もbufio.Readerと同様に、io.Writer型をNewWriter関数に渡すことで作ります。

func NewWriter(w io.Writer) *Writer

出典:pkg.go.dev - bufio#NewWriter

こうして作ったbufio.Writerにも、内部バッファbufが存在します。

type Writer struct {
	err error
	buf []byte
	n   int
	wr  io.Writer
}

出典:[https://go.googlesource.com/go/+/go1.16.2/src/bufio/bufio.go#558]

Write(p []byte)メソッドが実装されるときに、この内部バッファbufがどう動くのでしょうか。
実際に実装を確認してみると、以下のようになっています。

<pの中身が全て処理されるまでこれを繰り返す>

  1. len(p)が内部バッファの空きより小さい場合(=pの中身をbufに書き込んでもbufに空きが余る場合)
    • pの中身を一旦bufに書き込んでおく
  2. len(p)が内部バッファの空きより大きい場合(=pの中身を一旦全部bufに書き込むだけの余裕がない場合)
    • bufが先頭から空いているなら、pの中身を直接メモリに書き込む(=bufを使わない)
    • bufの空きが先頭からじゃないなら、
      1. bufに入るだけデータを埋める
      2. bufの中身をメモリに書き込む[2]
      3. pの中でbufに書き込み済みのところを切る

つまり、「実際にデータをメモリに書き込むのは、内部バッファbufの中身がいっぱいになったときのみ」という挙動をします。

わざわざこんな面倒なことをする理由に、OSがメモリを管理する方法が関連しています。
基本的にOSは、ブロック単位(4KBだったり8KBだったりものにより様々)でメモリを割り当てています。
そのため、「1byteの書き込みを4096回」と「4096byte(=4KB)の書き込みを1回」だったら後者の方が早いのです。

ユーザースペースでバッファリングすることで、中途半端な長さの書き込みを全て「ブロック単位の長さの書き込み」に整形することができるので、処理速度をあげることができるのです。

ベンチマークによる実行時間比較

本当にbufioパッケージを使うことでI/Oが早くなっているのでしょうか。

Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest.
(よく言われる意訳) 推測するな、計測しろ
出典:Rob Pike's 5 Rules of Programming[3]

こんな言葉もあることですし、それに従い実際にベンチマークをとって検証してみましょう。

検証環境は以下のものを使用しました。

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i5-8279U CPU @ 2.40GHz

Readメソッド

まずはio.Readerとbufio.Reader型のReadメソッドを検証します。

以下のような関数を用意しました。

// サイズがFsizeのファイルをnbyteごと読む関数
func ReadOS(r io.Reader, n int) {
	data := make([]byte, n)

	t := Fsize / n
	for i := 0; i < t; i++ {
		r.Read(data)
	}
}

そして、ベンチマーク用のテストコードを以下のように書きました。

// ただのio用
func BenchmarkReadX(b *testing.B) {
	f, _ := os.Open("read.txt")
	defer f.Close()

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		ReadOS(f, X)
	}
}

// bufio用
func BenchmarkBReadX(b *testing.B) {
	f, _ := os.Open("read.txt")
	defer f.Close()
	bf := bufio.NewReader(f)

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		ReadOS(bf, X)
	}
}

ベンチマーク関数の名前BenchmarkYReadX()の名前は

  • Y: なしなら普通のio, Bならbufioでの検証
  • X: Xbyteごとにファイルを読み込んでいく

です。

go test -bench .でのテスト結果は、以下のようになりました。

BenchmarkRead1-8               1        1575492668 ns/op
BenchmarkRead32-8             21          51526989 ns/op
BenchmarkRead256-8           181           5954220 ns/op
BenchmarkRead4096-8         3544            338707 ns/op

BenchmarkBRead1-8             79          14302113 ns/op
BenchmarkBRead32-8          1071          39197576 ns/op
BenchmarkBRead256-8         1306           5104346 ns/op
BenchmarkBRead4096-8        3427            373660 ns/op

1byteごと書き込んでいる場合、bufioの有無で110倍ものパフォーマンス差が生まれる結果となりました。

Writeメソッド

今度はio.Readerとbufio.Reader型のWriteメソッドを検証します。

検証用として以下のような関数を用意しました。

// サイズBsize分のデータを、nbyteごとに区切って書き込む
func WriteOS(w io.Writer, n int) {
	data := []byte(strings.Repeat("a", n))

	t := Bsize / n
	for i := 0; i < t; i++ {
		w.Write(data)
	}
}

そして、ベンチマーク用のテストコードを以下のように書きました。

// ただのio用
func BenchmarkWriteX(b *testing.B) {
	f, _ := os.Create("write.txt")
	defer f.Close()

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		WriteOS(f, X)
	}
}

// bufio用
func BenchmarkBWriteX(b *testing.B) {
	f, _ := os.Create("write6.txt")
	defer f.Close()
	bf := bufio.NewWriter(f)

	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		WriteOS(bf, X)
	}
	bf.Flush()
}

go test -bench .でのテスト結果は、以下のようになりました。

BenchmarkWrite1-8                    117          10157577 ns/op
BenchmarkWrite32-8                  3280            330840 ns/op
BenchmarkWrite256-8                27649             49118 ns/op
BenchmarkWrite4096-8              206610              6637 ns/op

BenchmarkBWrite1-8                 39537             29841 ns/op
BenchmarkBWrite32-8               232269              5700 ns/op
BenchmarkBWrite256-8              255998              5996 ns/op
BenchmarkBWrite4096-8             193617              7128 ns/op

1byteごと読み込んでいる処理の場合、bufio使用なし/ありでそれぞれ10157577ns/29841nsと、約340倍ものパフォーマンスの差が出る結果となりました。
読み込み単位のバイト数を増やすごとにパフォーマンス差はなくなっていきますが、それを抜きにしてもユーザースペースでのバッファリングの威力がよくわかる結果です。

bufio.Scanner

bufioパッケージには、Readerとは別にbufio.Scannerという読み込みのための構造体がもう一つ存在します。
bufio.Reader()での読み込みが「指定した長さのバイト列ごと」なのに対して、これは「トークンごとの読み込み」をできるようにすることで利便性を向上させたものです。

この章ではbufio.Scannerについて詳しくみていきます。

トークン

トークンとその利便性

bufio.Scannerで可能になる「トークン」ごとの読み取りですが、これは例えば

  • 単語ごと(=スペース区切り)に読み取りたい
  • 行ごと(=改行文字区切り)に読み取りたい

といった状況のときに威力を発揮します。
上2つの例の場合、それぞれ「単語(word)」と「行(line)」をトークンにしたbufio.Scannerを用意することで簡単に実現可能です。

これをbufio.Readerでやろうとすると、トークンごとの長さが時と場合によって変わるので、「まずは1000byte読み込んで、そこから単語や行ごとに区切って……」といった複雑な処理を自前で書かなくてはいけなくなります。
bufio.Scannerはこの面倒な処理からユーザーを開放してくれます。

トークン定義

トークンの定義は、bufioパッケージ内のSplitFunc型で行います。

type SplitFunc func(data []byte, atEOF bool) (advance int, token []byte, err error)

SplitFunc is the signature of the split function used to tokenize the input.
(訳)SplitFunc型は、入力をトークンに分割するために使用する関数シグネチャです。
出典:pkg.go.dev - bufio#SplitFunc

このSplitFunc型に代入することができる関数が、bufio内では4つ定義されています。

func ScanBytes(data []byte, atEOF bool) (advance int, token []byte, err error)
func ScanLines(data []byte, atEOF bool) (advance int, token []byte, err error)
func ScanRunes(data []byte, atEOF bool) (advance int, token []byte, err error)
func ScanWords(data []byte, atEOF bool) (advance int, token []byte, err error)

つまり、bufioでデフォルトで定義されているトークンは以下の4つです。

  • バイトごと
  • 行ごと
  • ルーンごと
  • 単語ごと

Scanner構造体について

内部構造

bufio.Scannerの内部構造は以下のようになっています。

type Scanner struct {
	r            io.Reader // The reader provided by the client.
	split        SplitFunc // The function to split the tokens.
	token        []byte    // Last token returned by split.
	buf          []byte    // Buffer used as argument to split.
	// (以下略)
}

出典:[https://go.googlesource.com/go/+/go1.16.3/src/bufio/scan.go#30]

bufio.Reader型と同様に、内部にバッファを持っていることがわかります。
つまり、bufio.Scannerの利用の裏ではbuffered I/Oが行われているのです。

また、splitフィールドには、トークンを定義するSplitFunc型関数が格納されており、これに従ってスキャナーはトークン分割処理を行います。

scanner内では、tokenごとに区切るSplitFunc型の関数を内部に持っている。
それをセットするのがsplit()メソッド。デフォルトはlineで区切られるようになっている。

スキャナーの作成

bufio.Scannerの作成は、bufio.Readerの作成と同様に、io.Readerを引数に渡すNewScanner関数で行います。

func NewScanner(r io.Reader) *Scanner

出典:pkg.go.dev - bufio#NewScanner

これで作成されたスキャナーは、デフォルトで「行」をトークンにするように設定されています。
変更したい場合は、Splitメソッドを使います。

// 引数で渡したSplitFuncでトークンを作る
func (s *Scanner) Split(split SplitFunc)

出典:pkg.go.dev - bufio#Scanner.Split

Scannerを使ってデータを読み取る

スキャナーを使ってデータを読みとるためには、「Scan()メソッドで読み込み→Text()メソッドで結果を取り出す」という手順を踏みます。

例えば、以下のようなテキストファイルを用意します。

apple
bird flies.
cat is sleeping.
dog

これを行ごとに読み取る処理を実装するには、例えば以下のようになります。

func main() {
	// ファイル(io.Reader)を用意
	f, _ := os.Open("text.txt")
	defer f.Close()

	// スキャナを用意(トークンはデフォルトの行のまま)
	sc := bufio.NewScanner(f)

	// EOFにあたるまでスキャンを繰り返す
	for sc.Scan() {
		line := sc.Text() // スキャンした内容を文字列で取得
		fmt.Println(line)
	}
}

/*
出力結果

apple
bird flies.
cat is sleeping.
dog
*/

(余談)Scannerを使わなきゃ困っちゃう場面

実はこのbufio.Scanner、Goで競プロをやっている方なら馴染みがある概念ではないでしょうか。

fmt.ScanでTLEが出ちゃう問題

競技プログラミングの問題において、大量のデータの入力が必要になる場合が存在します。
例えば、このAtCoder Beginner Contest 144 - E問題は、2*N+2個ものの数字が以下のように与えられます。

N K
A1 A2 ... AN
F1 F2 ... FN

この問題の場合、Nの最大値は2*10^5なので結構な数の入力があることになります。
そのため、fmt.Scanを使うとTLE(時間切れによる不正解)判定が出てしまいます。

// TLEになったコードの断片
var N, K int
fmt.Scan(&N, &K)
 
A := make([]int, N)
for i := 0; i < N; i++ {
	fmt.Scan(&A[i])
}
F := make([]int, N)
for i := 0; i < N; i++ {
	fmt.Scan(&F[i])
}

解決策

これの解決策がbufio.Scannerの使用です。
以下のようなコードはGoで競プロやるかたにとってはテンプレなのではないでしょうか。

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	// (以下略)
}

これをファイル冒頭に入れておくことで、この問題での入力処理は以下のように書き換えられます。

N, K := scanInt(), scanInt()
 
A, F := make([]int, N), make([]int, N)
for i := 0; i < N; i++ {
	A[i] = scanInt()
}

for i := 0; i < N; i++ {
	F[i] = scanInt()
}

筆者はこの修正を施すことで無事にAC(正解)を通しました。

まとめ

以上、bufioパッケージによるbuffered I/Oについて掘り下げました。

次章では、最後の競プロでも出てきたfmtでの標準入力・出力について掘り下げます。

脚注

  1. "bufio"の名前の由来はおそらく"buffer"のbufと"I/O"のioを足したものでしょう ↩︎

  2. この動作をflushといいます ↩︎

  3. Go言語の父と呼ばれている人です ↩︎