[Unity] C# JobSystem + Burst でテキストファイルを非同期に高速パース

以前の記事:
[[Unity] C# JobSystem を利用してテキストファイルを非同期でパースする](https://qiita.com/kawai125/items/13390f25700dd89c0f2e)
で、Unityで外部のテキストファイルを非同期かつそこそこの速度でパースすることを実現しました。
しかし、その結びに課題の一つとして以下の点を挙げていました。

> ◎Burstでもっと速くならない？
> いつになるかは不明ですが、公式の案内では char には対応する予定らしいので、その暁にはもっと早くなるはず。
>Burst does not support the following types:
>- char (this will be supported in a future release)
>- string as this is a managed type
> ライブラリ内部ではASCII範囲の値しか検索、比較していないので、 char をすべて unit16 あたりにキャストして、関数ポインタ経由でBurstさせればもっと早くなる可能性は大いにあります。
> しかし、公式が対応すると明言していますし、上記の手法で Burst による高速化が特に期待されるホットスポットは TryParse() や Split() 関数なので、Burst が char に対応したならユーザーデータクラスの ParseLine(line) をまるごと適用したほうがはるかに効果的でしょう。

本記事は「キャストするだけなら機械的に書き換えればいいし楽そうだからやってみよう」と、適当に手を出してハマった箇所のレポートと、その成果物の紹介です。

# 成果物
[前回](https://qiita.com/kawai125/items/13390f25700dd89c0f2e)に続き、今回の記事の内容をアップデートしたものを公開しています。

GitHub
[NativeStringCollections](https://github.com/kawai125/NativeStringCollections)

基本的な利用方法やライブラリの大まかな設計については[前回の記事](https://qiita.com/kawai125/items/13390f25700dd89c0f2e)をご参照ください。

# 動作環境
- Unity 2019.4.24f1
  - Collections 0.9.0-preview.6
  - Burst 1.4.7

- Unity 2020.3.25f1
  - Collections 0.17.0 or 1.1
  - Burst 1.6.3

# Burst 版の性能評価
検証環境:

| |parts|
|:-|:-|
|OS|Windows 10|
|CPU|Ryzen5 3600X|
|GPU|GTX 1070|
|Storage|NVMe SSD (PCIe Gen3 x4)|

50万Charaのテキストデータ(ノイズ、追加データあり。約59万行。デモシーン付属のジェネレータで生成)のパース時間を計測した。
`AsyncTextFileReader<T>` の測定シーンは
`Assets/NativeStringCollections/Samples/Demo/Scenes/Demo_ReadingLargeFile.unity`
を、
C#の標準機能のみを用いた場合の測定には
`Assets/NativeStringCollections/Samples/Demo/Scenes/Demo_StandardCSharp_(comparison).unity`
使用した。

|条件|Time [ms]|備考|
|:-|-:|:-|
|C# standard (参考値)|710 ~ 850|C# の標準機能のみ利用|
||||
|C# IL2CPP (Burstなし)|500 ~ 550||
|ParseLinesWorker (改行コード解析) をBurst|450 ~ 460|ライブラリ内部の関数なのでデフォルトで有効|
|Burst適用例(1) 小規模関数を個別に: Split(), TryParse()|430 ~ 450|NativeStringCollections.BurstFunc にデリゲートを定義済み|
|Burst適用例(2) 大きな処理単位で　: ParseLines(), PostReadProc() 全体|150 ~ 170|対象のファイルに合わせてユーザが実装|

次に、先と同様の50万Charaのテキストデータを複数用意し、`AsyncTextFileLoader<T>`を用いた並列ファイルパース実行時の性能を、  
(1):ParseLines(), PostReadProc()全体へBurstを適用した場合,
(2):ユーザ側でのBurst適用を行わない場合  
の2通りについて計測した。
測定シーンには
`Assets/NativeStringCollections/Samples/Demo/Scenes/Demo_AsyncMultiFileManagement.unity`
を使用した。

|並列Job数|(1) Time (Burst) [ms]|(2) Time [ms]|
|-:|-:|-:|
|1|150 ~ 170|440 ~ 480|
|2|155 ~ 170|450 ~ 500|
|3|165 ~ 190|480 ~ 540|
|4|170 ~ 200|500 ~ 580|
|6|190 ~ 250|550 ~ 650|
|8|200 ~ 300|600 ~ 700|

上記の結果から、`NativeStringCollections` を使用した場合は**ユーザーが特別な実装をしなくてもファイル読み込み速度が約1.5倍ほど高速になります。**

さらに、ユーザーがBurstを適用した`ITextFileParser.ParseLines()`を実装した場合、**C#標準と比較し、最高で5倍近く速くなります。**

また、およそ**CPUの物理コア数以下のJob数であればほとんど性能低下はなく**、同時実行Job数の上限は`AsyncTextFileLoader.MaxJobCount`プロパティにより容易に制御できます。

処理はネイティブメモリ上で行われるので、大規模なテキストを処理してもマネージドメモリを圧迫せずGCを起こしません。
上記の並列Jobの性能計測では1つあたり約37MBのテキストファイル24個、合計約870MBを処理しています。

次項で説明しますが、手間になる部分は`NativeStringCollections`側であらかじめ実装してありますので、利用時にはユーザー側で`ITextFileParser.ParseLines()`のBurst版を実装することを推奨いたします。

# ユーザー定義パーサーでのBurstの使い方

## ▽`ITextFileParser.ParseLines()`にBurstを適用 (推奨)

<details><summary>Burst direct-call による実装例 (要 Burst 1.6 以降、折り畳み)</summary><div>

```C#
using Unity.Burst;

using NativeStringCollections;
using NativeStringCollections.Utility;

public struct YourDataElem
{
    public ReadOnlyStringEntity text;
    public int somethingData;
}

public class YourDataParser : ITextFileParser, IDisposable
{
    // 処理したいデータの実体
    public NativeList<YourDataElem> data_list;

    private NativeStringList text_field_list;

    // ReadOnlyStringEntity.Split() の一時結果格納用
    private NativeList<ReadOnlyStringEntity> str_list; 

    private bool _allocated;

    // Burst に処理対象を渡すためのデータパック
    // ref struct で渡す必要があるのでまとめておくと楽
    public struct DataPack
    {
        // コンテナに対する UnsafeReference (NativeContainer はそのままでは渡せない)
        //   NativeStringCollections.Utility に定義済みの UnsafeRefTo**** を利用するか、
        //   Unity.Collections.LowLevel.Unsafe にある Unsafe なコンテナを使用、
        //   またはそれらをもとに自作する
        public UnsafeRefToNativeList<YourDataElem> data_list;
        public UnsafeRefToNativeStringList text_field_list;

        public UnsafeRefToNativeList<ReadOnlyStringEntity> str_list;
    }
    private DataPack pack;

    public void Init()
    {
        data_list = new NativeList<YourDataElem>(Allocator.Persistent);
        text_field_list = new NativeStringList(Allocator.Persistent);

        str_list = new NativeList<ReadOnlyStringEntity>(Allocator.Persistent);

        // DataPack に UnsafeRef を作成
        //   NativeStringCollections.Utility に定義済みの支援関数を利用するか、
        //   Unity.Collections.LowLevel.Unsafe にある Unsafe なコンテナを使用、
        //   またはそれらをもとに自作する
        pack.data_list = data_list.GetUnsafeRef();
        pack.text_field_list = text_field_list.GetUnsafeRef();
        pack.str_list = str_list.GetUnsafeRef();

        _allocated = true;
    }
    public void Clear()
    {
        data_list.Clear();
        text_field_list.Clear();
    }
    public bool ParseLines(NativeStringList lines)
    {
        // Burst でコンパイルされた関数の呼び出し
        var input_lines = lines.GetUnsafeRef();
        return YourDataParserBurst.ParseLines(ref pack, ref input_lines);
    }
    public void PostReadProc()
    {
        // Burst 実装例は割愛 ParseLines() と同様に

        // NativeStringList にテキストを保存する場合は
        // StringEntity の取り出しはデータの追加が終わったこのタイミングで行う
        // (内部バッファの再確保でそれまで生成した StringEntity が無効な参照になる)
    }
    public void UnLoad()
    {
        // 略
    }

    public void Dispose()
    {
        if (_allocated)
        {
            data_list.Dispose();
            text_field_list.Dispose();
            str_list.Dispose();
            _allocated = false;
        }
    }
    ~YourDataParser()
    {
        this.Dispose();
        GC.SuppressFinalize(this);
    }
}

// Burst でコンパイルされる関数を実装する static class
[BurstCompile]
public static class YourDataParserBurst
{
    // Burst でコンパイルされた関数を呼ぶためのインターフェイス
    //   普通の C# 関数でラップすれば ref 渡しや void にこだわる必要はない
    public static bool ParseLines(ref YourDataParser.DataPack pack,
                                  ref UnsafeRefToNativeStringList lines)
    {
        ParseLinesBurstEntry(ref pack, ref lines, out bool continueRead);
        return continueRead;
    }

    // Burst でコンパイルされる関数の実装
    //   返値は void,
    //   引数は ref struct, struct*, in struct, out struct のいずれか
    //   (Burst <-> C# script の境界の制約)
    [BurstCompile]
    private static void ParseLinesBurstEntry(ref YourDataParser.DataPack pack,
                                             ref UnsafeRefToNativeStringList lines,
                                             out bool continueRead)
    {
        continueRead = true;
        for(int i=0; i<lines.Length; i++)
        {
            continueRead = ParseLineImpl(ref pack, lines[i]);
            if(!continueRead) return;
        }
    }
    // Burst でコンパイルされる関数 の中で呼ばれる関数は
    // 参照型さえ使わなければ普通の書き方でよい
    private static bool ParseLineImpl(ref YourDataParser.DataPack pack,
                                      ReadOnlyStringEntity line)
    {
        if (line.Length < 1) return true; // 空行

        line.Split(',', pack.str_list);   // CSVとして ',' 区切りで分割


        // 以下は "ElemName,IntValue" な CSV の場合の実装例
        pack.text_field_list.Add(pack.str_list[0]);

        var elem = new YourDataElem();
        pack.str_list[1].TryParse(out elem.somethingData);

        pack.data_list.Add(elem);

        return true;
    }
}
```

</div></details>

[Burst direct-call](https://docs.unity3d.com/Packages/com.unity.burst@1.6/manual/docs/CSharpLanguageSupport_Lang.html#directly-calling-burst-compiled-code) を使用する場合、渡せる型の制約はあるものの見かけ上 static な関数に `[BurstCompile]` 属性をつけるだけなので、非常に簡便に実装することができます。

<details><summary>Burst function pointer による実装例 (折り畳み)</summary><div>

```C#
using Unity.Burst;

using NativeStringCollections;
using NativeStringCollections.Utility;

public struct YourDataElem
{
    public ReadOnlyStringEntity text;
    public int somethingData;
}

public class YourDataParser : ITextFileParser, IDisposable
{
    // 処理したいデータの実体
    public NativeList<YourDataElem> data_list;

    private NativeStringList text_field_list;

    // ReadOnlyStringEntity.Split() の一時結果格納用
    private NativeList<ReadOnlyStringEntity> str_list; 

    private bool _allocated;

    // Burst に処理対象を渡すためのデータパック
    // ref struct で渡す必要があるのでまとめておくと楽
    public struct DataPack
    {
        // コンテナに対する UnsafeReference (NativeContainer はそのままでは渡せない)
        //   NativeStringCollections.Utility に定義済みの UnsafeRefTo**** を利用するか、
        //   Unity.Collections.LowLevel.Unsafe にある Unsafe なコンテナを使用、
        //   またはそれらをもとに自作する
        public UnsafeRefToNativeList<YourDataElem> data_list;
        public UnsafeRefToNativeStringList text_field_list;

        public UnsafeRefToNativeList<ReadOnlyStringEntity> str_list;
    }
    private DataPack pack;

    public void Init()
    {
        data_list = new NativeList<YourDataElem>(Allocator.Persistent);
        text_field_list = new NativeStringList(Allocator.Persistent);

        str_list = new NativeList<ReadOnlyStringEntity>(Allocator.Persistent);

        // DataPack に UnsafeRef を作成
        //   NativeStringCollections.Utility に定義済みの支援関数を利用するか、
        //   Unity.Collections.LowLevel.Unsafe にある Unsafe なコンテナを使用、
        //   またはそれらをもとに自作する
        pack.data_list = data_list.GetUnsafeRef();
        pack.text_field_list = text_field_list.GetUnsafeRef();
        pack.str_list = str_list.GetUnsafeRef();

        _allocated = true;
    }
    public void Clear()
    {
        data_list.Clear();
        text_field_list.Clear();
    }
    public bool ParseLines(NativeStringList lines)
    {
        // Burst でコンパイルされた関数の呼び出し
        var input_lines = lines.GetUnsafeRef();
        return YourDataParserBurst.ParseLines(ref pack, ref input_lines);
    }
    public void PostReadProc()
    {
        // Burst 実装例は割愛 ParseLines() と同様に

        // NativeStringList にテキストを保存する場合は
        // StringEntity の取り出しはデータの追加が終わったこのタイミングで行う
        // (内部バッファの再確保でそれまで生成した StringEntity が無効な参照になる)
    }
    public void UnLoad()
    {
        // 略
    }

    public void Dispose()
    {
        if (_allocated)
        {
            data_list.Dispose();
            text_field_list.Dispose();
            str_list.Dispose();
            _allocated = false;
        }
    }
    ~YourDataParser()
    {
        this.Dispose();
        GC.SuppressFinalize(this);
    }
}

// Burst でコンパイルされる関数を実装する static class
[BurstCompile]
public static class YourDataParserBurst
{
    private delegate void ParseLinesDelegate(ref YourDataParser.DataPack pack,
                                             ref UnsafeRefToNativeStringList lines,
                                             out bool continueRead);
    private static ParseLinesDelegate _parseLinesDelegate;

    // Player 開始時にBurstでコンパイルしdelegateに格納
    [RuntimeInitializeOnLoadMethod]
    public static void Initialize()
    {
        _parseLinesDelegate = BurstCompiler.
            CompileFunctionPointer<ParseLinesDelegate>(ParseLinesBurstEntry).Invoke;
    }

    // Burst でコンパイルされた関数を呼ぶためのインターフェイス
    //   普通の C# 関数でラップすれば ref 渡しや void にこだわる必要はない
    public static bool ParseLines(ref YourDataParser.DataPack pack,
                                  ref UnsafeRefToNativeStringList lines)
    {
        _parseLinesDelegate(ref pack, ref lines, out bool continueRead);
        return continueRead;
    }

    // Burst でコンパイルされる関数の実装
    //   返値は void,
    //   引数は ref struct, struct*, in struct, out struct のいずれか
    //   (Burst <-> C# script の境界の制約)
    [BurstCompile]
    [AOT.MonoPInvokeCallback(typeof(ParseLinesDelegate))]
    private static void ParseLinesBurstEntry(ref YourDataParser.DataPack pack,
                                             ref UnsafeRefToNativeStringList lines,
                                             out bool continueRead)
    {
        continueRead = true;
        for(int i=0; i<lines.Length; i++)
        {
            continueRead = ParseLineImpl(ref pack, lines[i]);
            if(!continueRead) return;
        }
    }
    // Burst でコンパイルされる関数 の中で呼ばれる関数は
    // 参照型さえ使わなければ普通の書き方でよい
    private static bool ParseLineImpl(ref YourDataParser.DataPack pack,
                                      ReadOnlyStringEntity line)
    {
        if (line.Length < 1) return true; // 空行

        line.Split(',', pack.str_list);   // CSVとして ',' 区切りで分割


        // 以下は "ElemName,IntValue" な CSV の場合の実装例
        pack.text_field_list.Add(pack.str_list[0]);

        var elem = new YourDataElem();
        pack.str_list[1].TryParse(out elem.somethingData);

        pack.data_list.Add(elem);

        return true;
    }
}
```

</div></details>

[Burst function pointer](https://docs.unity3d.com/Packages/com.unity.burst@1.6/manual/docs/AdvancedUsages.html#function-pointers) を使用する場合、 static class に関数の実装とコンパイル結果を保持するdelegateを定義する必要があり、ボイラープレート的な記述が増えるためやや手間です。引数などの制約はdirect-call も function pointer も同じ(direct-callではfunction pointerのdelegadeに相当する部分をBurstのILポストプロセスで自動生成している)なので、新しいバージョンのBurstが使用可能であれば direct-call の利用を推奨します。  
いずれにせよ、`NativeStringCollections`が提供している`NativeStringList`と`StringEntity`およびその補助関数類を利用する限り具体的な処理部分について特に変わった実装をする必要はありません。

NativeContiner は[スレッドセーフの実現のために内部に参照型を持っており](https://qiita.com/mao_/items/220ccf3b2ef929388036)、Burstでコンパイルする領域では参照型は使えないのでBurstが扱える型に変換しないと渡せません。技術的な詳細は後述しますが、NativeStringCollections では以下のユーティリティーを提供しています。

```C#
using NativeStringCollections;
using NativeStringCollections.Utility;

// for container
UnsafeRefToNativeList<T> 
    ref_to_native_list = NativeList<T>.GetUnsafeRef();
UnsafeRefToNativeStringList 
    ref_to_native_string_list = NativeStringList.GetUnsafeRef();
UnsafeRefToNativeJaggedList<T> 
    ref_to_native_jagged_list = NativeJaggedList<T>.GetUnsafeRef();

// for Base64 converter
UnsafeRefToNativeBase64Encoder
    ref_to_base64_encoder = NativeBase64Encoder.GetUnsafeRef();
UnsafeRefToNativeBase64Decoder
    ref_to_base64_decoder = NativeBase64Decoder.GetUnsafeRef();
```

これらの unsafe な reference は各コンテナおよびコンバータの内部データへの参照を取得するため、UnsafeRefTo**** への変更は本体へ反映されます。参照の生成も `GetUnsafeRef()` により簡易に所得できますので、利用にあたって特に難しいことはないと思います。

残念ながら、`NativeList<T>` 以外のコンテナには内部のunsafeなコンテナを取り出すAPIが用意されていなかったので、上記のようなユーティリティを用意できませんでした。  
`NativeHashMap<Tkey, TValue>`や`NativeQueue<T>`などを使いたい場合、当面は必要に応じて対応するunsafeコンテナ(`UnsafeHashMap<TKey, TValue>`や`UnsafeRingQueue<T>`)を作成し、Burst化した関数を呼ぶ前後に適宜中身をコピーして運用することになると思います。

こちらの実装法をとるか否かで __パース速度がおよそ3倍__ 違うので、多少の手間はかかるもののユーザー自身でBurstを適用した`ParseLines()`を実装することを推奨します。

## ▽`NativeStringCollections.BurstFunc` (定義済み delegate) の利用

<details><summary>`NativeStringCollections.BurstFunc` を利用する例 (折り畳み)</summary><div>

```C#
using NativeStringCollections;
using NativeStringCollections.Utility;

public struct YourDataElem
{
    public ReadOnlyStringEntity text;
    public int somethingData;
}

public class YourDataParser : ITextFileParser, IDisposable
{
    // 処理したいデータの実体
    public NativeList<YourDataElem> data_list;

    private NativeStringList text_field_list;

    // ReadOnlyStringEntity.Split() の一時結果格納用
    private NativeList<ReadOnlyStringEntity> str_list; 

    private bool _allocated;

    public void Init()
    {
        data_list = new NativeList<YourDataElem>(Allocator.Persistent);
        text_field_list = new NativeStringList(Allocator.Persistent);

        str_list = new NativeList<ReadOnlyStringEntity>(Allocator.Persistent);

        _allocated = true;
    }
    public void Clear()
    {
        data_list.Clear();
        text_field_list.Clear();
    }
    public bool ParseLines(NativeStringList lines)
    {
        bool continueRead = true;
        for(int i=0; i<lines.Length; i++)
        {
            continueRead = ParseLineImpl(lines[i]);
            if (!continueRead) return false;
        }
        return true;
    }
    private bool ParseLineImpl(ReadOnlyStringEntity line)
    {
        if (line.Length < 1) return true; // 空行

        line.Split(',', str_list);   // CSVとして ',' 区切りで分割


        // 以下は "ElemName,IntValue" な CSV の場合の実装例
        text_field_list.Add(str_list[0]);

        var elem = new YourDataElem();
        BurstFunc.TryParse(str_list[1], out elem.somethingData); // Burst 適用済み delegate

        data_list.Add(elem);

        return true;
    }
    public void PostReadProc()
    {
        // 略
    }
    public void UnLoad()
    {
        // 略
    }

    public void Dispose()
    {
        if (_allocated)
        {
            data_list.Dispose();
            text_field_list.Dispose();
            str_list.Dispose();
            _allocated = false;
        }
    }
    ~YourDataParser()
    {
        this.Dispose();
        GC.SuppressFinalize(this);
    }
}
```

</div></details>

あらかじめ以下の関数を `NativeStringCollections.BurstFunc` に定義してありますので、これを利用します。

  - Split()
  - Strip(), Lstrip(), Rstrip()
  - TryParse(), TryParseHex()
  - Base64Encoder.GetChars(), Base64Decoder.GetBytes()

通常の実装と比べほとんど書き換える必要はありませんが、効果は限定的です。
(およそ5~10%程度)

また、前章のように `ITextFileParser.ParseLines()` 全体に Burst を適用する場合、このような関数ポインタを経由した実装が混入すると [Burst は関数ポイントを跨いだ最適化を行えません。](https://docs.unity3d.com/Packages/com.unity.burst@1.4/manual/docs/AdvancedUsages.html#performance-considerations)

効果が限定的であること、また誤って使用すると最適化に悪影響を及ぼす可能性があることから、こちらの定義済み delegade は非推奨です。性能比較のため実装は残してありますが `[Obsolete]` です。

# Burst 適用への道

## ▽関数ポインタを使う前に

ライブラリ全体のデザインは[前回の記事](https://qiita.com/kawai125/items/13390f25700dd89c0f2e)と同様なので、以下ではさらに Burst を適用するにあたってつまずいた点について解説します。

今回の事例でいえば、NativeStringCollections ではテキストバイナリのデコードに `System.Text.Encoding`を, ジョブの時間計測に `System.Diagnostics.Stopwatch` を使用しており、これらの参照型をJobに持ち込むせいで Unity 公式が推奨する Job 構造体の Burst 適用ができません。

以下はこのように、何らかの理由で JobSystem を用いた Burst 適用ができない場合に、関数ポインタ経由で Burst を利用する場合の Tips 集となります。

[公式ドキュメント](https://docs.unity3d.com/Packages/com.unity.burst@1.4/manual/docs/AdvancedUsages.html#performance-considerations)にもある通り、Burst は JobSystem に適用する場合に最大のパフォーマンスを得られます。**手間のかかる小細工を弄する前に**、標準的な手法で実現可能な課題かどうかしっかり検討しましょう。

## ▽System.Char は Burst で使えない

そもそも単純な struct であるはずの `Char` がなぜ Burst で使えないのかというと、Burst が実際にコードを生成する C++ では基本的に char を **8bit整数(エンコーディングは実装依存!)** として取り扱っており、一方 C# では **16bit整数(UTF16)** を採用したため、単なる数値としてではなく **文字コードとして考えると適当に相互コピーしたのでは破綻するためと考えられます。**

これはC++のDLLなどで文字列解析ライブラリ等を使おうとするなら重大な問題ですが、今回はすべての実装をC#で書いてしまってそれをBurstでトランスコードする形になるので、内部のビット表現が C# のCharと同じ符号なし16bit整数である `UInt16` をメンバに持つ struct `Char16` を作り、これをベースに `NativeStringList` や `StringEntity`, `Split()`, `TryParse()`... などを書き換えました。

```C#:Char16.cs(抜粋)
public struct Char16
{
    private UInt16 Value;

    public Char16(Char16 c) { Value = c; }
    public Char16(char c) { Value = c; }

    public static implicit operator Char16(char c) {return new Char16 { Value = (UInt16)c } }
    public static implicit operator char(Char16 c) {return (char)c.Value; }

    // そのほか、byte, UInt16 との相互変換、
    // Equals(), 比較演算子(==, !=, <=, <, >=, >)などを一通り実装
}
```

これを NativeStringCollections では UTF-16 の符号を格納する struct として扱いますが、Burstコンパイラからは単なる UInt16 (ushort) 型に見えるので、Burstにコンパイルさせることができるようになります。

## ▽NativeContainer はそのままでは Burst に持っていけない

BurstはC#の参照型を一切扱えず、操作できる型はプリミティブ型と `unmanaged struct`,およびそれらのポインタに限定されます。
一方でUnityが用意している NativeContainer はスレッドセーフおよびメモリリークの監視を実現するために内部で参照型を使用しており、このためNativeContainerを含む struct をそのまま Burst コンパイルの delegade に渡してしまうと、

```
MarshalDirectiveException: Type System.Diagnostics.StackTrace which is passed to unmanaged code must have a StructLayout attribute.
```

と実行時にエラーが起きて止まります。普段NativeContainerでやらかす時と異なり、NativeContainerではなくC#のマーシャラー(C# と C++ の間でデータのやり取りの仲介を行うライブラリ)からエラーが飛んでくるのでちょっとわかりづらいです。

事象の深堀はおいておいて、扱いやすいバッファである `NativeList` を持ち込めれば大変便利なので、これをBurstが扱えるように加工します。

Collections パッケージを Package Manager からインストールすると、Unity 2019.4.24 ではプロジェクトフォルダの
`Library/PackageCache/com.unity.collections@0.9.0-preview.6/Unity.Collections
にダウンロードされ、ここでNativeContainerの実装を見ることができます。

すると NativeList<T> の正体は以下のような、UnsafeList へのポインタを持つだけのものです。

```C#:NativeList.cs(抜粋)
public unsafe struct NativeList<T>
  where T : struct 
{
    [NativeDisableUnsafePtrRestriction]
    internal UnsafeList* m_ListData;

    public UnsafeList* GetUnsafeList() => m_ListData;
};
```

データの実体に対してはポインタのポインタで関節参照していることになるので、インデクサによるアクセスやLengthフィールドの取得が妙に遅かったのはそういうことか、などという余談はさておき、

この [UnsafeList](https://docs.unity3d.com/Packages/com.unity.collections@0.9/api/Unity.Collections.LowLevel.Unsafe.UnsafeList.html)はCapacityと要素数を管理するだけの最小構成に近い実装で、これ単体では `Add<T>()` はできますがインデクサがありません。ただ、`NativeList<T>.GetUnsafeList()` という[APIが用意されており](https://docs.unity3d.com/Packages/com.unity.collections@0.9/api/Unity.Collections.NativeList-1.html#Unity_Collections_NativeList_1_GetUnsafeList)、NativeListが管理している`UnsafeList`のポインタを取り出すことができます。
これに `public T this[int index]` などの NativeList に近い挙動のラッパーを被せたものとして `UnsafeRefToNativeList<T>` を作ります。

```C#:UnsafeRefToNativeList.cs(抜粋)
namespace NativeStringCollections.Utility
{
    // UnsafeRef を簡単に作成するための拡張メソッド
    public static class NativeListExt
    {
        public static UnsafeRefToNativeList<T> GetUnsafeRef<T>(this NativeList<T> target)
            where T : unmanaged
        {
            return new UnsafeRefToNativeList<T>(target);
        }
    }

    /// <summary>
    /// This unsafe reference disables the NativeContiner safety system.
    /// Use only for passing reference to BurstCompiler.CompileFunctionPointer.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    [StructLayout(LayoutKind.Sequential)]
    public unsafe struct UnsafeRefToNativeList<T>
        where T : unmanaged
    {
        [NativeDisableUnsafePtrRestriction]
        internal UnsafeList* _list;

        /// <summary>
        /// Create the unsafe reference to NativeList<T>.
        /// </summary>
        /// <param name="passed_list"></param>
        public UnsafeRefToNativeList(NativeList<T> passed_list)
        {
            // NativeList<T> 内部の UnsafeList へのポインタを取得
            // 参照先が共通なので UnsafeRef への変更は元の NativeList にも反映される
            _list = passed_list.GetUnsafeList();
        }

        public T this[int index]
        {
            get
            {
                CheckIndexInRange(index, _list->Length);
                return UnsafeUtility.ReadArrayElement<T>(_list->Ptr, AssumePositive(index));
            }
            set
            {
                CheckIndexInRange(index, _list->Length);
                UnsafeUtility.WriteArrayElement(_list->Ptr, AssumePositive(index), value);
            }
        }

    /* 以下、NativeList.cs の実装で必要そうなものをコピー */

    }

    public unsafe static class UnsafeViewForNativeListUtility
    {
        public static void* GetUnsafePtr<T>(this UnsafeRefToNativeList<T> list)
            where T : unmanaged
        {
            return list._list->Ptr;
        }
    }

}
```

これで `NativeList<T>` を Burst で使える参照 `UnsafeRefToNativeList<T>` に変換できるようになりました。
これを使えば、`NativeList<T>` を内部バッファに使用している `NativeJaggedArray<T>` や `NativeStringList` のUnsafeRef も容易に作成できます。

また、自分でUnsafeなコンテナを作るのではなく、領域の確保はNativeListにやらせてBurstに渡す時にだけ型変換する、という方針をとることで、メモリリークの監視やBurstの外でのレースコンディションの検知など、NativeContainerの安全システムの恩恵に与ることができます。

## ▽Boxing に注意

Burst は参照型を扱えないため、関数の引数定義によってBoxingが発生したりすると参照型への変換ができないためにコンパイルエラーとなります。メタプログラミングを意識してインターフェイスを利用している場合にはその使い方に注意が必要です。

```C#
// interface
public interface IPtrGetter 
{
    public void* GetUnsafePtr();
}

// 普通のInterfaceの使い方 -> Boxing が起きる
// Burst でコンパイルできない
public unsafe void Func1(IPtrGetter source)
{
    var ptr = source.GetUnsafePtr();
    /* ポインタを使う処理 */
}

// Generic Interface の書き方 -> struct を渡す時には参照型を生成しない (高速)
// Burst でコンパイルしてさらに速くできる
public unsafe void Func2<T>(T source)
  where T : IPtrGetter
{
    var ptr = source.GetUnsafePtr();
    /* ポインタを使う処理 */
}
```

## ▽Burst がコンパイルする delegade の引数はジェネリックにできない

Generic Interface を使えるようになると何となく必要な型制約だけをつけたGenericな引数で関数を定義したくなりますよね。
しかし、Burstのコンパイル結果は delegade 型の変数に格納される = この時点で関数ポインタのエントリポイントの型情報が確定している、というわけで型情報を確定できない Generic な引数は使えません。

もっとも、この制約はC#とC++の境界になる関数ポインタへの引数だけなので、下記の例のように delegade を呼ぶ関数をオーバーロードしたり、Burstでコンパイルされる関数内で Generic な関数を使うことに問題はありません。

```C#
// BurstFunc が受け取れる型 Data
public struct Data { };

// Data への暗黙の型変換を実装した型
public struct DataType2
{
    public implicit operator Data(DataType2 data) {return new Data(/* converion */)};
};

// 関数のオーバーロードで該当するメンバを取り出して渡す例
public struct DataType3
{
    public Data data_member;
};

[BurstCompile]
public static class BurstFunc
{
    private void FuncDelegade(ref Data data);
    private static FuncDelegade _funcDelegade;

    [RuntimeInitializeOnLoadMethod]
    public static void Initialize()
    {
        _funcDelegade = BurstCompiler.
            CompileFunctionPointer<FuncDelegade>(FuncBurst).Invoke;
    }

    // Burst 関数ポインタへのエントリポイント
    [BurstCompile]
    [AOT.MonoPInvokeCallback(typeof(FuncDelegade))]
    private static void FuncBurst(ref Data data)
    {
        var report = Proccess(data);
    }
    // Burstへのエントリポイント以外では参照渡ししなくても、
    // Genericな関数を使っても、
    // void以外を返してもよい
    private static bool Proccess<T>(T data)
    {
        /* 何かする */
        return true;
    }

    // Data と DataType2 を渡せる　(暗黙にDataへの型変換が行われる)
    public static void Func(ref Data data)
    {
        _funcDelegade(ref data);
    }
    // DataType3 を渡せる (オーバーロード)
    public static void Func(ref DataType3 data)
    {
        _funcDelegade(ref data.data_member);
    }
}
```

## ▽OSSで公開されているライブラリのBurst対応について
最近のC#では特に高速な参照を扱うために `Span<T>` 、 `ReadOnlySpan<T>` が導入されており、高速化を志向したライブラリでは多用されていますが標準のUnityでの対応は2021以降で、2019, 2020で使用するためには[DLLを手動で追加する必要があります。](https://ikorin2.hatenablog.jp/entry/2020/06/07/162659)
(Burst自体は 1.7 以降で  `Span<T>` 、 `ReadOnlySpan<T>`  に対応したようです。)

`NativeStringCollections` はある程度ポータブルなライブラリとして設計したので、単にパッケージを導入すれば済むようにコンパイル時定数として使用されていた `ReadOnlySpan<T>` を `static readonly T[]` に置き換えました。

また、ほとんどの参照型を排除するためにいくつか仕様を変更する部分が出てくることがあり、移植の難易度は実装の詳細を見てみないと予測が難しところです。

今回の [csFastFloat](https://github.com/CarlVerret/csFastFloat) では汎用性のために数値文字列の表現フォーマットを Enum `System.Globalization.NumberStyles` で指定できるようになっていましたが、Burst は現状 `Enum.HasFlag()` に未対応なので当該部分を削除しました。

## ▽Burst が行う最適化の特徴

Burst は JobSystem などの複数のCPUコアへ処理を割り振るのではなく、CPUコア内の演算実行ユニットにできるだけ処理を詰め込んで処理を高速にしようとする最適化を行います。
一般的にSIMD化とパイプライン化と呼ばれる最適化になります。

### 〇 SIMD化

我々が普段扱う変数はintやfloatといったものですが、これらのバイナリサイズは32bitです。
一方、今日のPC用CPUでは加減乗除やビット演算など、同じ演算を同時に複数の変数に適用するための機能がついており、これは現行製品ではAVX2(256bit幅, AMDとIntel両社が対応)やAVX512(512bit幅, 現状Intelのみ)などが利用可能です。
iOSやAndroid端末でも Arm NEON として同様の機能が実装されています。

これを用いることで、例えば8つのfloatを別の8つのfloatと足し算する処理(ちょうどクォータニオン2つ分ですね)でfloatの足し算を8回処理しなければならないところ、AVX2が使える環境では全部まとめて1回の処理で計算が終わります。(32bit x 8 = 256bit)

同じ演算でなければ利用できないとか、大量のデータの読み書きができないとデータが来なくて結局計算ができない **(=うまくデータがキャッシュに乗っているかが重要。つまりNativeContainerやECSとセットで使わないとそもそも性能を発揮できない)** とか制約はありますが、うまく適用できれば大変な高速化になります。

### 〇 ソフトウェアパイプライニング

SIMD化は一回の命令で処理できるデータを増やす方法でしたが、CPUの命令にはもう一つ特徴があり、たいていの命令は実行してから結果が得られるまでの時間(=Latency)と、次の命令を開始できるようになる時間(=Throughput)が違うことが多いです。

たとえば Latency=5, Throughput=2 の命令を使うとして、いちいち結果が出るのを待ってから次の命令を開始していると20クロックで4回しか処理できませんが、結果に依存性がないデータをThroughputが許す限り、2クロックごとに詰め込めるだけ詰め込んでいけば19クロック時点で8回目のデータの結果が得られます。

こちらも大きな性能向上をもたらす可能性があり、しかしやはりデータが到着しなければ処理が始まりませんので、**データがちゃんとキャッシュメモリに(以下略**

### 結局Burstが最適化しやすい処理とは？

SIMD化もパイプライニングも、マルチコアでの並列化と同様、同時に処理しているデータの処理結果について互いに依存関係にないことが前提として必要です。
つまり得意な処理対象も同じ、**できるだけ大きなforループ**です。

今回のテーマである文字列のパース処理は、極端に単純化すれば文字列の先頭から1文字ずつ比較していって合致した場所をさがすという超巨大なforループです。
比較的Burstが得意な処理に該当するので、 `ITextFileParser.ParseLines()` をBurst化した時には**2倍～3倍程度の高速化が達成できました**。

一方で、`NativeStringCollections.BurstFunc` の delegate を使用した場合にさほど大きな性能向上がなかったのは、ParseLines()ではブロックごとの処理内容がそのまま渡されるために数千文字分の巨大なループとして処理を詰め込めたのに対し、Split() や TryParse() 関数単独ではせいぜい数文字から数十文字といったところでCPUコアの演算器を埋め尽くすにはデータが足りなかったと考えられます。

# 参考資料

Basics of NativeStringCollections:
[[Unity] C# JobSystem を利用してテキストファイルを非同期でパースする](https://qiita.com/kawai125/items/13390f25700dd89c0f2e)

Qiita:
[【Unity】BurstCompilerをJobSystem以外でも使いたい](https://qiita.com/mao_/items/876fa56fb42bc5110345)
[【Unity】NativeArrayについての解説及び実装コードを読んでみる](https://qiita.com/mao_/items/220ccf3b2ef929388036)

Blog:
[相互運用時に戻り値にNon-Bittable型が含まれる場合例外が発生する件](https://takap-tech.com/entry/2017/08/16/224102)
[【C#】え、Generic Interfaceでメソッド引数を設定すれば構造体のBoxingを回避できるの？](https://tsgcpp.hateblo.jp/entry/2020/08/22/182943)

Official:
[Burst User Guide](https://docs.unity3d.com/Packages/com.unity.burst@1.6/manual/index.html)
[Scripting API / Unity.Colections](https://docs.unity3d.com/Packages/com.unity.collections@0.9/api/Unity.Collections.html)
[Burstを使ってSHA-256のハッシュ計算を高速に行う話](https://learning.unity3d.jp/6155/)

Ported Library:
[csFastFloat](https://github.com/CarlVerret/csFastFloat)