kawasin73のブログ

技術記事とかいろんなことをかくブログです

Go でビットベクトルライブラリを作った話

Go 作ったもの

この記事は、DMM.com Advent Calendar 2018 の 15 日目の記事です。

Go 言語でエンディアン（ビッグエンディアン、リトルエンディアン）を指定できるビットベクトルライブラリを作ったのでその紹介をします。

このライブラリは、mmap でファイルがマッピングされたメモリを直接扱うことを想定し、ビットベクトルの中身がマシンのエンディアンに関わらず指定したエンディアンになるように操作を行います。

そのため、ファイルに保存したビットベクトルのバイト列を異なるエンディアンのマシンで扱うことができるようになります。

また、不必要なコピーとエンディアンの変換処理が発生しないように設計されています。そのために内部で unsafe パッケージを使って []byte から []uint64 へのキャストを行なって、バイト列を直接扱えるように工夫しています。

github.com

ビットベクトルとは

ビットベクトルとは、 ある非負の整数と true, false の 2 値をマッピングする 簡潔データ構造 の一種で、空間的にも計算量的にも効率良く動作します。

ある非負の整数とブーリアン型とのマッピングデータ構造の一例として例えば []bool が考えられます。

Go 言語においてブーリアン型は 1 バイトのメモリを必要とし、[]bool は N 個の bool 値を保存するのに N バイトを消費 します。（厳密にはスライス構造体もメモリを消費しますが、ここでは無視します。）

fmt.Println(unsafe.Sizeof(true)) // 1

boolVec := make([]bool, N)

// N bytes for N items
// [ true | false | false | true | true | false | false | false | .... ]

i 番目の値を引いてくる計算は、スライスのインデックスを渡すことで一発で引いてくることができます。

boolVec[i] // true or false

0 ~ N の値の中で true がセットされていない最小の数値を見つける計算（ Find First Zero ）は、最悪で N 回のループを処理します。

for i := 0; i < N; i++ {
    if !boolVec[i] {
        // i is false!
    }
}

一方、ビットベクトルは true, false の値を 1 ビットの 1, 0 として表し、N 個の値を保存するのに N / 8 バイトを消費 します。つまり、メモリ空間の消費量は 1/8 に圧縮 されます。

// N / 8 bytes for N items
[ 10011000 ... ]

また、ビットベクトルは 64 ビットの符号なし整数の配列 []uint64 で表されます。

bitVec := make([]uint64, (N + 63)/64)
[ 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 |
  00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 |
  ....]

i 番目の値は、[]uint64 の i / 64 番目の 64 ビットのうち下から i % 64 ビット目のビットが 0 か 1 かどうかを調べることでわかります。

実際には割り算の計算は重いため、ビットの操作によって軽く計算します。

  • i / 64：i を6 ビット右シフトさせたもの（i >> 6）
  • i % 64：i の下位 6 ビット（i & 63）
  • i % 64 ビット目のビットマスク：1 << (i & 63)
bitVec[i >> 6] & (1 << (i & 63)) != 0 // true or false

0 ~ N の値の中で true がセットされていない最小の数値を見つける計算（ Find First Zero ）は 64 ビットごとに検索し、N / 64 回のループ処理で検索することができます。つまり、計算量は 1 / 64 に圧縮 されます。

これは、CPU が一度に 64 ビットずつ計算を行うためです（64 ビット CPU アーキテクチャの場合。32 ビット CPU アーキテクチャの場合は 32 ビットずつです）。

このように、ビットベクトルを使うと true, false の値を空間的にも計算量的にも効率よく保存できます。

ビッグエンディアン、リトルエンディアンとは

ここまででビットベクトルの説明をしたわけですが、ファイルにビットベクトルを書き出す時にはエンディアンを意識する必要があります。

エンディアン（ Endianness ）とはバイトの並び順のことで、ビッグエンディアン（ Big Endian ）とリトルエンディアン（ Little Endian ）の2種類があります。（ミドルエンディアンなど他のエンディアンもあるらしいですがごく少数派らしいです）また、バイトオーダーとも呼ばれます。

ビッグエンディアンは上位のバイトから並べていく方式で、リトルエンディアンは下位のバイトから並べていく方式です。

例えば Go 言語の uint64 の場合 64 ビットの整数であるためこれは 8 バイトで表されます。

16進数で 0x0123456789abcdef と表される数値は、ビッグエンディアンでは 0x01 | 0x23 | 0x45 | 0x67 | 0x89 | 0xab | 0xcd | 0xef と、リトルエンディアンでは 0xef | 0xcd | 0xab | 0x89 | 0x67 | 0x45 | 0x23 | 0x01 と表されます。

エンディアン - Wikipedia

エンディアンは CPU のアーキテクチャによって変わります。よく使われている amd64 のCPU（Intel や AMD などの CPU）では、リトルエンディアンです。

また、CPU によってはビッグエンディアンとリトルエンディアンを指定できる CPU もあるみたいです。

同一プロセスのメモリ上の値は全て同じエンディアンで扱われているため、通常のメモリ上の値を操作するプログラミングをする場合はエンディアンを気にする必要はありません。

しかし、マシンをまたいでバイナリデータをやり取りする場合はこのエンディアンに注意しないと、マシンによって全く異なる値に認識されてしまうことになります。（TCP/IP などのネットワークプロトコル操作やバイナリエンコードされたファイルを異なるマシンで扱うときなど）

Go言語でのビットベクトルライブラリ

ここまでで、ビットベクトルとエンディアンの説明をしました。ここからが本題です。

Go 言語にはすでにビットベクトルのライブラリとして、github.com/willf/bitset があります。

github.com

Go のバージョン 1.7 から対応しているとても良いライブラリなのですが、外部のメモリを直接扱えず willf/bitset 内で管理している []uint64 にコピーする必要があるという欠点があります。

willf/bitset はバイト列ストリームへエンディアンを指定した書き出しと読み込みをする WriteTo() と ReadFrom() インターフェイスを提供しており、これによりファイルへの書き出しと読み込みが可能になります。

しかし、ファイルへの書き出しでは変更された部分だけではなく全てを書き出すため、必要のないコピーが発生します。また、初期値のロードでは必ずカーネルランドからユーザーランドへのメモリコピーが発生します。

willf/bitset は内部のメモリ []uint64 をマシンのエンディアンで処理します。そして、書き出しと読み込み時に内部で binary.Write() と binary.Read() を使い指定されたエンディアンに変換します。エンディアンの変換ではマシンのエンディアンに関わらず 8 バイトごとに変換処理をするため、頻繁にファイルと同期をとる場合はこの 変換のコスト と コピーのコスト が大きくかかってきます。

ビットベクトルライブラリを作る

ファイルへの書き出しと読み込みの メモリコピーのオーバヘッド と、エンディアンの変換処理のオーバーヘッド を極力抑えるために github.com/kawasin73/bitset というビットベクトルのライブラリを作成しました。

github.com

このライブラリは外部から提供されたバイト列 []byte を直接扱います。

mmap はファイルがマッピングされたカーネル側のメモリをユーザーランドから直接操作することができる機能です。

kawasin73/bigset では mmap によってファイルがマッピングされたメモリも直接扱うことができるため、初期値のロードのメモリコピーが発生せず、ファイルへの書き戻しのメモリコピーも必要なくなります。

また、ビットベクトルの操作ではマシンのエンディアンによって処理を切り替えることによって、エンディアンの変換処理のオーバーヘッドをなくすことができます。

このライブラリを作る上では、https://github.com/willf/bitset を参考にして実装し、以下の点を工夫しました。

  • []byte から []uint64 へのゼロコピー変換
  • それぞれのマシンエンディアンに最適化されたビットベクトル操作

[]byte から []uint64 へのゼロコピー変換

通常 []byte から []uint64 への変換は、8 バイトずつ binary.BigEndian.Uint64() または、binary.LittleEndian.Uint64() によって変換してコピーを行います。しかし、それでは mmap されたメモリを操作することはできず、またメモリコピーのコストがかかります。

そこで、以下のようにして unsafe パッケージを使い []byte から []uint64 へコピーすることなく変換しています。

buf := make([]byte, 8 * n)
header := *(*reflect.SliceHeader)(unsafe.Pointer(&buf))
header.Len /= 8
header.Cap /= 8

vec := *(*[]uint64)(unsafe.Pointer(&header))

この手法では従来のバイト列が 8 の倍数でなかった場合、末尾のあまりの部分は無視されます。

利用者にとって想定外の領域の切り詰めが起こらないように、このライブラリでは8 の倍数でない長さのバイト列の場合は初期化時に bitset.ErrInvalidLength エラーを返すようにしています。

変換された []uint64 だけを bitset.BitSet に vec として保持して元の []byte の参照を消した時、バイト列が GC されて vec の内容が別の処理に書き換えられるバグがあったため、元の []byte も bitset.BitSet に orig として保持して GC されないように工夫しています。

マシンエンディアンに最適化されたビットベクトル操作

このライブラリではマシンのエンディアン（hostEndian）を検出し、利用者が指定したエンディアン（userEndian）と hostEndian を比較して処理を切り分けています。

hostEndian と userEndian の組み合わせは、(hostEndian, userEndian) = (LittleEndian, LittleEndian), (BigEndian, LittleEndian), (LittleEndian, BigEndian), (BigEndian, BigEndian) の全部で 4 通り あります。

しかし、リトルエンディアン と ビッグエンディアン は逆に並んでいるだけであるので、hostEndian と userEndian が 同じ か 違う かの 2 通りだけを考えればよい ということになります。

初期バージョンでは、以下の 64 ビットを 8ビットずつ反転させるスワップ関数を利用して実装しました。

func swapUint64(n uint64) uint64 {
    return ((n & 0x00000000000000FF) << 56) |
        ((n & 0x000000000000FF00) << 40) |
        ((n & 0x0000000000FF0000) << 24) |
        ((n & 0x00000000FF000000) << 8) |
        ((n & 0x000000FF00000000) >> 8) |
        ((n & 0x0000FF0000000000) >> 24) |
        ((n & 0x00FF000000000000) >> 40) |
        ((n & 0xFF00000000000000) >> 56)
}

hostEndian と userEndian が異なる時に、以下の手順で操作を行うとユーザーが指定したエンディアンでメモリ操作ができます。

  1. メモリから反転させて一時メモリに読み出し
  2. マシンのエンディアンで処理を行い
  3. 反転させてメモリに書きもどす

初期バージョンの実装とテストが終わった後に、それぞれのエンディアンが異なる時の操作を最適化された処理に書き換えています。

テスト

このライブラリはビッグエンディアンとリトルエンディアンに対応してものであると謳っている以上、それぞれのエンディアンのマシンでテストをする必要があります。

travis の上でビッグエンディアンをエミュレートしてテストする手法は以下の記事にまとめています。

kawasin73.hatenablog.com

利用方法

だいたいこんな感じで使います。（README.md からコピーしてきました。）

func main() {
    // in memory usage
    buf := make([]byte, 2*8)
    b, _ := bitset.New(buf, binary.LittleEndian)
    for _, v := range []uint{0, 1, 3, 6, 10, 64, 127, 128} {
        b.Set(v) // when v == 128 returns false because overflow
    }
    fmt.Println(buf) // [75 4 0 0 0 0 0 0 1 0 0 0 0 0 0 128]

    b.Unset(127)
    fmt.Println(b.Get(127)) // false

    for v, ok := b.FindFirstOne(0); ok; v, ok = b.FindFirstOne(v + 1) {
        fmt.Println(v) // 0 1 3 6 10 64
    }

    // File + mmap usage
    const pageSize = 4 * 1024
    f, _ := os.OpenFile("example.bit", os.O_RDWR|os.O_CREATE, 0666)
    f.Truncate(pageSize)
    buf, _ = syscall.Mmap(int(f.Fd()), 0, pageSize,
        syscall.PROT_READ|syscall.PROT_WRITE,
        syscall.MAP_SHARED)
    defer func() {
        f.Sync()
        syscall.Munmap(buf)
        f.Close()
    }()

    b, _ = bitset.New(buf, binary.BigEndian)
    for v, ok := b.FindFirstOne(0); ok; v, ok = b.FindFirstOne(v + 1) {
        fmt.Println(v) // 0 1 3 6 10 64  if executed twice
    }
    for _, v := range []uint{0, 1, 3, 6, 10, 64, 127, 128} {
        b.Set(v) // when v == 128 returns false because overflow
    }
    fmt.Println(buf) // [0 0 0 0 0 0 4 75 128 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 ....
}

今対応している操作はこのくらいなので、今後操作の種類を追加していけるといいなと思っています。

  • func (b *BitSet) Count() uint
  • func (b *BitSet) FindFirstOne(i uint) (uint, bool)
  • func (b *BitSet) FindFirstZero(i uint) (uint, bool)
  • func (b *BitSet) FindLastOne() (uint, bool)
  • func (b *BitSet) Get(i uint) bool
  • func (b *BitSet) Set(i uint) bool
  • func (b *BitSet) Unset(i uint) bool

制約

https://github.com/willf/bitset では、大きな違いとして、メモリサイズの自動拡張機能があります。ビットベクトルの範囲を超えた整数に Set があった場合は []uint64 のサイズを自動で拡張してくれる機能です。

このライブラリでは、mmap したメモリも想定しているので自動でメモリを拡張することができません。（拡張すると違うメモリ空間にビットベクトルが移動し、mmap したメモリへの変更がされなくなる）

このライブラリ自体は、mmap したメモリ以外のヒープメモリも受け付けるものなので、サイズを自動で拡張する機能があれば便利だなと考えています。

最後に

長かったですが以上です。

ビットベクトルを使いたい時にぜひ使ってみてください。