バイト列の同値性(『プログラミング言語 Go』読書会より)

第5回『プログラミング言語Go』オンライン読書会」に参加してみたです。

以前 Discord で某エベントに参加したことがあったけど,やっぱオンラインイベントはしんどい。 それでもメインで喋る人が決まってるから,今回は楽なほうだったかな。 Discord にしろ Zoom にしろ,オンラインでフリートーク・イベントはかなり難しいと思うのだが,みんなどうしてるんだろう。

閑話休題 (それはさておき)

今回,のっけから面白い話を聞いた。 『プログラミング言語 Go』4.2章「スライス」に書かれている

配列と異なりスライスは比較可能ではありませんので,二つのスライスが同じ要素で構成されているかを検査するために == は使えません。標準ライブラリは二つのバイトスライス([]byte)を比較するために高度に最適化された bytes.Equal 関数を提供しています。しかし…
プログラミング言語 Goより

という部分(強調は私がやりました)。 実際にコードを見てみると

// Equal reports whether a and b
// are the same length and contain the same bytes.
// A nil argument is equivalent to an empty slice.
func Equal(a, b []byte) bool {
	// Neither cmd/compile nor gccgo allocates for these string conversions.
	return string(a) == string(b)
}

てなことになっている。 で,「これのどこが『高度に最適化』なん?」という話があったらしい。

バージョンを遡ってみると 1.12.7 までは

// Equal returns a boolean reporting whether a and b
// are the same length and contain the same bytes.
// A nil argument is equivalent to an empty slice.
func Equal(a, b []byte) bool {
	return bytealg.Equal(a, b)
}

となっていた。 ちなみに internal/bytealg は内部パッケージで,中身はほぼ(アーキテクチャ毎に)アセンブラで記述されている。 実は Go 1.13 では string 周りが大幅に強化されていて,その辺の影響が出ているのかもしれない。

それなら,どの程度のパフォーマンスか気になるよね。 というわけで,こんなコードを用意してみた1

package eq

import (
	"bytes"
	"fmt"
	"testing"
)

var (
	hello1  = "I could tell you my pass phrase, but then I would have to kill you."
	hello2  = "I could tell you my pass phrase, but then I would have to kill you."
	helloA1 = [67]byte{0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x74, 0x65, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6d, 0x79, 0x20, 0x70, 0x61, 0x73, 0x73, 0x20, 0x70, 0x68, 0x72, 0x61, 0x73, 0x65, 0x2c, 0x20, 0x62, 0x75, 0x74, 0x20, 0x74, 0x68, 0x65, 0x6e, 0x20, 0x49, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x68, 0x61, 0x76, 0x65, 0x20, 0x74, 0x6f, 0x20, 0x6b, 0x69, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x2e}
	helloA2 = [67]byte{0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x74, 0x65, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6d, 0x79, 0x20, 0x70, 0x61, 0x73, 0x73, 0x20, 0x70, 0x68, 0x72, 0x61, 0x73, 0x65, 0x2c, 0x20, 0x62, 0x75, 0x74, 0x20, 0x74, 0x68, 0x65, 0x6e, 0x20, 0x49, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x68, 0x61, 0x76, 0x65, 0x20, 0x74, 0x6f, 0x20, 0x6b, 0x69, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x2e}
	helloS1 = []byte{0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x74, 0x65, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6d, 0x79, 0x20, 0x70, 0x61, 0x73, 0x73, 0x20, 0x70, 0x68, 0x72, 0x61, 0x73, 0x65, 0x2c, 0x20, 0x62, 0x75, 0x74, 0x20, 0x74, 0x68, 0x65, 0x6e, 0x20, 0x49, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x68, 0x61, 0x76, 0x65, 0x20, 0x74, 0x6f, 0x20, 0x6b, 0x69, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x2e}
	helloS2 = []byte{0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x74, 0x65, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6d, 0x79, 0x20, 0x70, 0x61, 0x73, 0x73, 0x20, 0x70, 0x68, 0x72, 0x61, 0x73, 0x65, 0x2c, 0x20, 0x62, 0x75, 0x74, 0x20, 0x74, 0x68, 0x65, 0x6e, 0x20, 0x49, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x68, 0x61, 0x76, 0x65, 0x20, 0x74, 0x6f, 0x20, 0x6b, 0x69, 0x6c, 0x6c, 0x20, 0x79, 0x6f, 0x75, 0x2e}
)

func BenchmarkByteEqual1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if hello1 != hello2 {
			fmt.Printf("false")
		}
	}
}

func BenchmarkByteEqual2(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if !bytes.Equal([]byte(hello1), []byte(hello2)) {
			fmt.Printf("false")
		}
	}
}

func BenchmarkByteEqual3(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if helloA1 != helloA2 {
			fmt.Printf("false")
		}
	}
}

func BenchmarkByteEqual4(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if string(helloA1[:]) != string(helloA2[:]) {
			fmt.Printf("false")
		}
	}
}

func BenchmarkByteEqual5(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if !bytes.Equal(helloA1[:], helloA2[:]) {
			fmt.Printf("false")
		}
	}
}

func BenchmarkByteEqual6(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if string(helloS1) != string(helloS2) {
			fmt.Printf("false")
		}
	}
}

func BenchmarkByteEqual7(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if !bytes.Equal(helloS1, helloS2) {
			fmt.Printf("false")
		}
	}
}

hello1, hello2string 型,helloA1, helloA2byte 配列,helloS1, helloS2[]byte 型で中身はみんな同じ。 これらを使って同値性(equallity)をチェックするのだが,内訳はこんな感じ。

関数名 比較手順
BenchmarkByteEqual1 string == string
BenchmarkByteEqual2 bytes.Equal([]byte(string), []byte(string))
BenchmarkByteEqual3 <byte array> == <byte array>
BenchmarkByteEqual4 string(<array>[:]) == string(<array>[:])
BenchmarkByteEqual5 bytes.Equal(<array>[:], <array>[:])
BenchmarkByteEqual6 string([]byte) == string([]byte)
BenchmarkByteEqual7 bytes.Equal([]byte, []byte)

では,実際に動かしてみようか。

$ go test -bench ByteEqual -benchmem
goos: linux
goarch: amd64
pkg: sample
BenchmarkByteEqual1-4   	301173402	         4.04 ns/op	       0 B/op	       0 allocs/op
BenchmarkByteEqual2-4   	 8552673	       122 ns/op	     160 B/op	       2 allocs/op
BenchmarkByteEqual3-4   	182939372	         6.27 ns/op	       0 B/op	       0 allocs/op
BenchmarkByteEqual4-4   	191359716	         6.29 ns/op	       0 B/op	       0 allocs/op
BenchmarkByteEqual5-4   	191511163	         6.27 ns/op	       0 B/op	       0 allocs/op
BenchmarkByteEqual6-4   	168382664	         7.16 ns/op	       0 B/op	       0 allocs/op
BenchmarkByteEqual7-4   	167058468	         7.06 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	sample	12.140s

分かりやすく表にしておく。 ちなみに私の環境では 1ns 未満は誤差の範囲なのであしからず。

比較手順 処理時間 (ns/op) Alloc 回数
string == string 4.04 0
bytes.Equal([]byte(string), []byte(string)) 122.00 2
<byte array> == <byte array> 6.27 0
string(<array>[:]) == string(array>[:]) 6.29 0
bytes.Equal(array>[:], <array>[:]) 6.27 0
string([]byte) == string([]byte) 7.16 0
bytes.Equal([]byte, []byte) 7.06 0

string[]byte へのキャスト時にアロケーションが発生している点に注意。

つか string 同士の比較処理が速いな! 配列と slice で若干差が出るのは仕方ないが,元が同じ型なら殆ど差がないようだ。 まぁ,これなら確かに

func Equal(a, b []byte) bool { return string(a) == string(b) }

でもいっか,って気になるよな。

ブックマーク

参考図書

photo
プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
Alan A.A. Donovan (著), Brian W. Kernighan (著), 柴田 芳樹 (翻訳)
丸善出版 2016-06-20
単行本(ソフトカバー)
4621300253 (ASIN), 9784621300251 (EAN), 4621300253 (ISBN), 9784621300251 (ISBN)
評価     

著者のひとりは(あの「バイブル」とも呼ばれる)通称 “K&R” の K のほうである。この本は Go 言語の教科書と言ってもいいだろう。

reviewed by Spiegel on 2016-07-13 (powered by PA-APIv5)


  1. ちなみに “I could tell you my pass phrase, but then I would have to kill you.” という物騒なフレーズは Simson Garfinkel 氏の『PGP』に載っていたパスフレーズの事例である(笑) ↩︎