[Haskell] ByteString と ShortByteString の違い

違いが分からないと使い分けられないと思ったため、`ByteString` と `ShortByteString` の違いについて記事にします。 

# 0. まとめ

||`ByteString`|`ShortByteString`|
|-|-|-|
|用途|長いバイト文字列|短いバイト文字列|
|メモリオーバーヘッド<br>GHC の場合 (64 ビット環境)|大きい<br>8 ワード (64 バイト)|小さい<br>4 ワード (32 バイト)|
|バイト文字列データの場所|固定される|固定されない|
|ヒープの断片化の可能性|あり|なし|
|部分文字列取得時の<br>バイト文字列データの扱い|コピーされない|コピーされる|
|部分文字列のメモリオーバーヘッド<br>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](https://downloads.haskell.org/ghc/latest/docs/users_guide/exts/pragmas.html?highlight=unpack#unpack-pragma)」

# 1. メモリオーバーヘッド

「メモリオーバーヘッド」は「本質的でないところで消費されるメモリ」のことを意味します。

後述しますが、64 ビット環境の GHC であれば `ByteString` は 64 バイト、`ShortByteString` は 32 バイトが「バイト文字列データ自体」とは別に必要になります。

ちなみに、`ByteString` の部分文字列を取得した場合は元文字列とデータの一部を共有するため、部分文字列のメモリオーバーヘッドは 32 バイトになります。

参考「[Memory overhead - Data.ByteString.Short](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString-Short.html#g:2)」

## 1.1. `ByteString` の場合

`bytestring` パッケージのバージョン `0.12.0.2` では、`ByteString` の定義は以下のようになっています。

```haskell
data ByteString = BS {-# UNPACK #-} !(ForeignPtr Word8) -- payload
                     {-# UNPACK #-} !Int                -- length
```

```haskell
data ForeignPtr a = ForeignPtr Addr# ForeignPtrContents
```

```haskell
data Addr#
```

```haskell
data ForeignPtrContents
  = PlainForeignPtr !(IORef Finalizers)
  | FinalPtr
  | MallocPtr (MutableByteArray# RealWorld) !(IORef Finalizers)
  | PlainPtr (MutableByteArray# RealWorld)
```

`ByteString` の作り方によりますが、例えば `pack` 関数で `ByteString` を作成した場合は `ForeignPtrContents` 型のコンストラクタは `PlainPtr` になります。

(各関数の定義を見ていけば分かりますが、長くなるため本記事では略。)

```haskell
data MutableByteArray# s
```

`MutableByteArray#` の構造は Haskell のコード上では書かれていませんが、実際は以下のようになります。

PAYLOAD のところにバイト文字列データが置かれます。

```text
+------------+-----------------+-----------------------+
|            |                 |                       |
|   HEADER   | SIZE (in bytes) |       PAYLOAD         |
|            |                 |                       |
+------------+-----------------+-----------------------+
```

```haskell
data {-# CTYPE "HsInt" #-} Int = I# Int#
```

```haskell
data Int#
```

これらをまとめると以下の図のようになり、GHC でのメモリオーバーヘッドは 8 ワードになることが見積もれます。

![図: ByteString のメモリオーバーヘッド](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/232067/5d95f60d-975e-b66b-6c94-f4c68a04bc97.png)

※ `ForeignPtr Word8` および `Int` は `UNPACK` プラグマによって `BS` コンストラクタに取り込まれます。

参考「[ByteString - Data.ByteString](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString.html#t:ByteString)」
参考「[ForeignPtr - GHC.ForeignPtr](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-ForeignPtr.html#t:ForeignPtr)」
参考「[Addr# - GHC.Exts](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-Exts.html#t:Addr-35-)」
参考「[ForeignPtrContents - GHC.ForeignPtr](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-ForeignPtr.html#t:ForeignPtrContents)」
参考「[pack - Data.ByteString](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString.html#v:pack)」
参考「[MutableByteArray# - GHC.Exts](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-Exts.html#t:MutableByteArray-35-)」
参考「[ByteArray# - GHC.Exts](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-Exts.html#t:ByteArray-35-)」
参考「[Int - GHC.Exts](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-Exts.html#t:Int)」
参考「[Int# - GHC.Exts](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-Exts.html#t:Int-35-)」

参考「[6.20.13. UNPACK pragma - 6.20. Pragmas — Glasgow Haskell Compiler 9.6.3 User's Guide](https://downloads.haskell.org/ghc/latest/docs/users_guide/exts/pragmas.html?highlight=unpack#unpack-pragma)」

## 1.2. `ShortByteString` の場合

`bytestring` パッケージのバージョン `0.12.0.2` では、`ShortByteString` の定義は以下のようになっています。

```haskell
newtype ShortByteString =
  ShortByteString
  { unShortByteString :: ByteArray
  }
  deriving (Eq, TH.Lift, Data, NFData)
```

```haskell
data ByteArray = ByteArray ByteArray#
```

```haskell
data ByteArray#
```

`ByteArray#` の構造は Haskell のコード上では書かれていませんが、実際は以下のようになります。

PAYLOAD のところにバイト文字列データが置かれます。

```text
+------------+-----------------+-----------------------+
|            |                 |                       |
|   HEADER   | SIZE (in bytes) |       PAYLOAD         |
|            |                 |                       |
+------------+-----------------+-----------------------+
```

これらをまとめると以下の図のようになり、GHC でのメモリオーバーヘッドは 4 ワードになることが見積もれます。

![図: ShortByteString のメモリオーバーヘッド](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/232067/969b36d3-fef3-9242-404c-5921dc795fcb.png)

※ `ShortByteString` 型は `newtype` 宣言によって定義されているため、メモリ上では `ShortByteString` 型の値は `ByteArray` 型の値として扱われます。 

参考「[ShortByteString - Data.ByteString.Short](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString-Short.html#t:ShortByteString)」
参考「[ByteArray - Data.Array.Byte](https://hackage.haskell.org/package/base-4.18.1.0/docs/Data-Array-Byte.html#t:ByteArray)」
参考「[ByteArray# - GHC.Exts](https://hackage.haskell.org/package/base-4.18.1.0/docs/GHC-Exts.html#t:ByteArray-35-)」

参考「[The short version - Newtype - HaskellWiki](https://wiki.haskell.org/Newtype#The_short_version)」

# 2. バイト文字列データの場所の固定有無

`ByteString` は バイト文字列データの場所が固定され、`ShortByteString` は固定されません。

バイト文字列データの場所の固定有無によるメリットとデメリットは以下の通りです。

固定する場合:

- メリット
    - バイト文字列データを移動しないため時間がかからない (大きなデータ向き)
    - 部分文字列を取得する際にバイト文字列データをコピーしないため高速
- デメリット
    - 小さなデータを複数扱うとヒープの断片化が発生する
    - 大きなデータの一部の小さなデータのみを使用する場合、大きなデータがメモリ上に残る

固定しない場合:

- メリット
    - 小さなデータを複数扱ってもヒープの断片化が発生しない
    - 大きなデータの一部の小さなデータのみを使用する場合、大きなデータがメモリ上に残らない
- デメリット
    - バイト文字列データを移動するため時間がかかる (小さなデータ向き)
    - 部分文字列を取得する際にバイト文字列データをコピーするため低速

参考「[Heap fragmentation - Data.ByteString.Short](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString-Short.html#g:3)」

# 3. 部分文字列の扱い

`ByteString` の部分文字列を取得するとき、バイト文字列データのコピーを行わず、`Addr#` 型および `Int#` 型の値を変更し、`PlainPtr` は元文字列と共有するため、部分文字列のメモリオーバーヘッドは 4 ワードになります。

バイト文字列データをコピーしないため定数時間 $\mathcal{O}(1)$ で処理されます。

![図: ByteString のメモリオーバーヘッド](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/232067/5d95f60d-975e-b66b-6c94-f4c68a04bc97.png)

一方、`ShortByteString` の部分文字列を取得するときはバイト文字列データのコピーを行い、新しく `ShortByteString` を作り直すため、部分文字列のメモリオーバーヘッドは元文字列と同じく 4 ワードになります。

バイト文字列データをコピーするため線形時間 $\mathcal{O}(n)$ で処理されます。

![図: ShortByteString のメモリオーバーヘッド](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/232067/969b36d3-fef3-9242-404c-5921dc795fcb.png)

参考「[Substrings - Data.ByteString](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString.html#g:11)」
参考「[Substrings - Data.ByteString.Short](https://hackage.haskell.org/package/bytestring-0.12.0.2/docs/Data-ByteString-Short.html#g:11)」

`ByteString` の部分文字列のポインタを以下のようにして確認できます。

```haskell
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
```

```text:実行結果の例
"foo bar baz"
0x000000420043dab0
11
"bar"
0x000000420043dab4
3
```

※ `ShortByteString` はメモリ上の場所が移動する可能性があるため、ポインタを取得できません。