Subscribed unsubscribe Subscribe Subscribe

詳解bytestring

haskell

というタイトルでbytestringパッケージの包括的ガイドを書こうと思ったけど、まさにそんな内容のスライドをbytestringのBuilderを書いた人が公開していたのを見つけてしまったので、是非そちらを見て欲しい。

A guided tour through the bytestring library

以上、Haskell Advent Calender 2013 22日目の記事でした。



と、これで終わらせてしまってはさすがに良くないので、今回は上のスライドが作られた時点から加えられた主な変更を二つ紹介する。これらの変更は最新のリリース版GHCにバンドルされているbytestringパッケージにはまだ含まれていないので、利用したい場合は適宜cabalファイルにバージョン指定する必要がある。

ShortByteString

ShortByteStringはByteStringから使えるAPIを大幅に制限することで、メモリ効率を高めたデータ構造である。

通常のstrictなByteStringは一つのByteStringに対して9ワード分の領域を余分に消費する。十分に長いByteStringであればこのオーバヘッドは無視できるかもしれないが、短いByteStringを多数扱うプログラムにおいては相対的に影響が大きくなる。

ShortByteStringで使えるAPIは最小限である。

data ShortByteString
toShort :: ByteString -> ShortByteString
fromShort :: ShortByteString -> ByteString
pack :: [Word8] -> ShortByteString
unpack :: ShortByteString -> [Word8]
empty :: ShortByteString
null :: ShortByteString -> Bool
length :: ShortByteString -> Int
index :: ShortByteString -> Int -> Word8

slice系のAPIを無くすことでoffset値が不要になり、さらにFFIとの連携を諦めることでForeignPtrのindirectionを省き直接ByteArray#を格納することで、一つのShortByteStringに対して4ワードのオーバヘッドに押さえられている。

data ShortByteString = SBS ByteArray#

また、ShortByteStringはunpinned memoryが使われている点もByteStringと異なる。ByteStringではデータをFFIで呼び出す(Cなどの)関数に渡しても、GC中にオブジェクトが移動されてしまわないようにpinned memoryが使われているが、多数のByteStringを保持するプログラムでは、これがヒープ領域の断片化を招くことがある。ShortByteStringではunpinned memoryを使うためこの断片化は起こらない。

使い分けはShortByteStringのHaddockにあるように

  • 短いバイト列を多数保持する必要があるデータ(の内部表現)にはShortByteString
  • 公開するAPIやFFIについてはByteString

とするのがよいだろう。

Builderの改良

最新のbytestringではBuilderに幾つかの改良が加えられた。

  • 文字列リテラルからのBuilderの生成
    • IsStringのインスタンスが追加されたため"foobar" :: Builderのように文字列リテラルとしてそのまま書けるようになった。
  • blaze-textualで提供されていたような数値の10進ASCIIへの変換が追加された
  • Builderの低レベルAPIが追加された
    • (例えばHandle以外の)ユーザが提供する任意のバッファへの書き込みなども実装できる
  • Data.ByteString.Builder.Primが追加された
    • 性能に対する要求が非常に高いところでは、少々ぎこちないAPIのプリミティブを使うように書き換える(つまり手動で最適化する)ことで、BuilderのAPIを使うよりもさらに効率的なコードを書くことができる。
    • bounded primitivesがblaze-builderのWriteに相当するものだと思われる
  • blaze-builderで行われた最適化の移植
    • 少し前まではblaze-builderとbytestring builderはBuildSignalが少し違う実装になっていて、bytestringではlazy ByteStringの継続を使っていたが、これも一部のフィールドの正格性を除いてはblaze-builderと同じstrict ByteStringを使った実装へと書き換えられた
      • このパッチによる性能改善が具体的にどの程度のものなのかとか、他にblaze-builderとの細かい違いがどの程度あるのかはまだ調べていない。

まとめ