違いが分からないと使い分けられないと思ったため、ByteString と ShortByteString の違いについて記事にします。
0. まとめ
ByteString |
ShortByteString |
|
|---|---|---|
| 用途 | 長いバイト文字列 | 短いバイト文字列 |
| メモリオーバーヘッド GHC の場合 (64 ビット環境) |
大きい 8 ワード (64 バイト) |
小さい 4 ワード (32 バイト) |
| バイト文字列データの場所 | 固定される | 固定されない |
| ヒープの断片化の可能性 | あり | なし |
| 部分文字列取得時の バイト文字列データの扱い |
コピーされない | コピーされる |
| 部分文字列のメモリオーバーヘッド GHC の場合 (64 ビット環境) |
4 ワード (32 バイト) | 4 ワード (32 バイト) |
| サポートされる操作 | 多い | 少ない |
共通点:
-
ByteStringとShortByteStringの変換時にバイト文字列データのコピーが発生する - バイト文字列データ自体のメモリサイズはワード単位に切り上げられる
-
UNPACKプラグマを使用することでメモリオーバーヘッドを 1 ワード (64 ビット環境の場合は 8 バイト) 減らすことができる
参考「6.20.13. UNPACK pragma - 6.20. Pragmas — Glasgow Haskell Compiler 9.6.3 User's Guide」
1. メモリオーバーヘッド
「メモリオーバーヘッド」は「本質的でないところで消費されるメモリ」のことを意味します。
後述しますが、64 ビット環境の GHC であれば ByteString は 64 バイト、ShortByteString は 32 バイトが「バイト文字列データ自体」とは別に必要になります。
ちなみに、ByteString の部分文字列を取得した場合は元文字列とデータの一部を共有するため、部分文字列のメモリオーバーヘッドは 32 バイトになります。
参考「Memory overhead - Data.ByteString.Short」
1.1. ByteString の場合
bytestring パッケージのバージョン 0.12.0.2 では、ByteString の定義は以下のようになっています。
data ByteString = BS {-# UNPACK #-} !(ForeignPtr Word8) -- payload
{-# UNPACK #-} !Int -- length
data ForeignPtr a = ForeignPtr Addr# ForeignPtrContents
data Addr#
data ForeignPtrContents
= PlainForeignPtr !(IORef Finalizers)
| FinalPtr
| MallocPtr (MutableByteArray# RealWorld) !(IORef Finalizers)
| PlainPtr (MutableByteArray# RealWorld)
ByteString の作り方によりますが、例えば pack 関数で ByteString を作成した場合は ForeignPtrContents 型のコンストラクタは PlainPtr になります。
(各関数の定義を見ていけば分かりますが、長くなるため本記事では略。)
data MutableByteArray# s
MutableByteArray# の構造は Haskell のコード上では書かれていませんが、実際は以下のようになります。
PAYLOAD のところにバイト文字列データが置かれます。
+------------+-----------------+-----------------------+
| | | |
| HEADER | SIZE (in bytes) | PAYLOAD |
| | | |
+------------+-----------------+-----------------------+
data {-# CTYPE "HsInt" #-} Int = I# Int#
data Int#
これらをまとめると以下の図のようになり、GHC でのメモリオーバーヘッドは 8 ワードになることが見積もれます。
※ ForeignPtr Word8 および Int は UNPACK プラグマによって BS コンストラクタに取り込まれます。
参考「ByteString - Data.ByteString」
参考「ForeignPtr - GHC.ForeignPtr」
参考「Addr# - GHC.Exts」
参考「ForeignPtrContents - GHC.ForeignPtr」
参考「pack - Data.ByteString」
参考「MutableByteArray# - GHC.Exts」
参考「ByteArray# - GHC.Exts」
参考「Int - GHC.Exts」
参考「Int# - GHC.Exts」
参考「6.20.13. UNPACK pragma - 6.20. Pragmas — Glasgow Haskell Compiler 9.6.3 User's Guide」
1.2. ShortByteString の場合
bytestring パッケージのバージョン 0.12.0.2 では、ShortByteString の定義は以下のようになっています。
newtype ShortByteString =
ShortByteString
{ unShortByteString :: ByteArray
}
deriving (Eq, TH.Lift, Data, NFData)
data ByteArray = ByteArray ByteArray#
data ByteArray#
ByteArray# の構造は Haskell のコード上では書かれていませんが、実際は以下のようになります。
PAYLOAD のところにバイト文字列データが置かれます。
+------------+-----------------+-----------------------+
| | | |
| HEADER | SIZE (in bytes) | PAYLOAD |
| | | |
+------------+-----------------+-----------------------+
これらをまとめると以下の図のようになり、GHC でのメモリオーバーヘッドは 4 ワードになることが見積もれます。
※ ShortByteString 型は newtype 宣言によって定義されているため、メモリ上では ShortByteString 型の値は ByteArray 型の値として扱われます。
参考「ShortByteString - Data.ByteString.Short」
参考「ByteArray - Data.Array.Byte」
参考「ByteArray# - GHC.Exts」
参考「The short version - Newtype - HaskellWiki」
2. バイト文字列データの場所の固定有無
ByteString は バイト文字列データの場所が固定され、ShortByteString は固定されません。
バイト文字列データの場所の固定有無によるメリットとデメリットは以下の通りです。
固定する場合:
- メリット
- バイト文字列データを移動しないため時間がかからない (大きなデータ向き)
- 部分文字列を取得する際にバイト文字列データをコピーしないため高速
- デメリット
- 小さなデータを複数扱うとヒープの断片化が発生する
- 大きなデータの一部の小さなデータのみを使用する場合、大きなデータがメモリ上に残る
固定しない場合:
- メリット
- 小さなデータを複数扱ってもヒープの断片化が発生しない
- 大きなデータの一部の小さなデータのみを使用する場合、大きなデータがメモリ上に残らない
- デメリット
- バイト文字列データを移動するため時間がかかる (小さなデータ向き)
- 部分文字列を取得する際にバイト文字列データをコピーするため低速
参考「Heap fragmentation - Data.ByteString.Short」
3. 部分文字列の扱い
ByteString の部分文字列を取得するとき、バイト文字列データのコピーを行わず、Addr# 型および Int# 型の値を変更し、PlainPtr は元文字列と共有するため、部分文字列のメモリオーバーヘッドは 4 ワードになります。
バイト文字列データをコピーしないため定数時間 $\mathcal{O}(1)$ で処理されます。
一方、ShortByteString の部分文字列を取得するときはバイト文字列データのコピーを行い、新しく ShortByteString を作り直すため、部分文字列のメモリオーバーヘッドは元文字列と同じく 4 ワードになります。
バイト文字列データをコピーするため線形時間 $\mathcal{O}(n)$ で処理されます。
参考「Substrings - Data.ByteString」
参考「Substrings - Data.ByteString.Short」
ByteString の部分文字列のポインタを以下のようにして確認できます。
import Data.ByteString.Internal (ByteString(BS))
import qualified Data.ByteString.Char8 as BSC
f :: ByteString -> IO ()
f byteString = do
print byteString
let (BS foreignPtr int) = byteString
print foreignPtr
print int
main :: IO ()
main = do
let byteString = BSC.pack "foo bar baz"
f byteString
f $ BSC.take 3 . BSC.drop 4 $ byteString
"foo bar baz"
0x000000420043dab0
11
"bar"
0x000000420043dab4
3
※ ShortByteString はメモリ上の場所が移動する可能性があるため、ポインタを取得できません。