MS_LargeDataProcessing2

大量データの処理方式2

• 戻る（大量データの処理方式）
  • 大量データの処理方式2
  • 大量データの処理方式1 / 大量データの処理方式3

概要

こちらでは、メモリに保持可能なデータ量の場合の設計ディシジョンについて説明します。
この場合、メモリの大量消費による同時実行性の低下や CPU 時間が問題となります。

詳細

ステートメントレベルの性能

メモリ上のデータへのアクセス時間を 1 億回実行して測定してみました。

• データの保持方式
  • データはグローバル変数に保持。
  • このようにすればスタックに積まれることもないので高速。

以下結果

100000000回

Only for :ExT:277[msec],   CT:281[msec],   KT:0[msec], UT:281[msec]
→　forループのオーバーヘッド
if       :ExT:291[msec],   CT:281[msec],   KT:0[msec], UT:281[msec]
→　ifステートメント
intRef   :ExT:217[msec],   CT:218[msec],   KT:0[msec], UT:218[msec]
→　int変数の参照＋代入
strRef   :ExT:216[msec],   CT:218[msec],   KT:0[msec], UT:218[msec]
→　string変数の参照＋代入
crRef    :ExT:281[msec],   CT:281[msec],   KT:0[msec], UT:281[msec]
→　オブジェクト・メンバ変数の参照＋代入
arryRef  :ExT:234[msec],   CT:234[msec],   KT:0[msec], UT:234[msec]
→　配列の参照＋代入
arryRef4 :ExT:715[msec],   CT:718[msec],   KT:0[msec], UT:718[msec]
→　4次元配列の参照＋代入
lstRef   :ExT:498[msec],   CT:499[msec],   KT:0[msec], UT:499[msec]
→　リストの参照＋代入
lstRef4  :ExT:1570[msec],  CT:1560[msec],  KT:0[msec], UT:1560[msec]
→　4階層リストの参照＋代入
dicRef   :ExT:2996[msec],  CT:3011[msec],  KT:0[msec], UT:3011[msec]
→　Dictionaryの参照＋代入
dicRef4  :ExT:11695[msec], CT:11684[msec], KT:0[msec], UT:11684[msec]
→　4階層Dictionaryの参照＋代入

以下プログラム

計測プログラム（C#）の全文は、本ページの添付ファイル
ConsoleApplication.zipに収録されている。
骨格は以下のとおり。

class Program
{
    static void Main(string[] args)
    {
        int i = 0;
        const int num = 100000000;
        Console.WriteLine(num.ToString() + "回");

        PerformanceRecorder pr = new PerformanceRecorder();
        //--------------------------------------------------
        // ウォームアップ
        //--------------------------------------------------
        for (i = 0; i < num; i++)
        {
        }
        for (i = 0; i < num; i++)
        {
        }

        //--------------------------------------------------
        // Only for
        //--------------------------------------------------
        pr.StartsPerformanceRecord();
        for (i = 0; i < num; i++)
        {
        }
        Console.WriteLine("Only for:" + pr.EndsPerformanceRecord());
        //--------------------------------------------------

        // 以下、if / int / string / クラスメンバ / 配列 / 4次元配列 /
        //       List / 4階層List / Dictionary / 4階層Dictionary を
        //       同じ形で計測する。
        //--------------------------------------------------
        // 例：4階層Dictionary
        //--------------------------------------------------
        pr.StartsPerformanceRecord();
        for (i = 0; i < num; i++)
        {
            strVal = dicRef4["G"]["G"]["G"]["G"];
        }
        Console.WriteLine("dicRef4:" + pr.EndsPerformanceRecord());
        //--------------------------------------------------
    }
}

移行メモ（体裁）: 元ページには上記の計測プログラム約 250 行が
全文掲載されていたが、10 種類の計測が同じ形の反復であるため、
骨格と代表例に絞って掲載した。
全文は添付ファイル
ConsoleApplication.zipを参照。

以下結論

メモリ上のアクセス時間は、配列や、Generic の 4 階層を使用し始めると

• 辿るポインタが増え、時間が増加し始めます。

• 配列より Generic の List → Dictionary の方が遅い。

• Dictionary が特に遅いのは

  • 内部でハッシュの計算とアドレスの解決をしているためと思われる。
  • ハッシュキーを string から int に変更した場合、性能改善する（≒ List）。

（余談：if のオーバーヘッドはあまり無いようです。）

従って、データ保持は、

1. レコード（フィールド）は → Class（メンバ）に保持
2. キー階層は → 配列、Generic の List → Dictionary

を使用することになると思います。

• 配列は、キーが数字の場合に利用する。
  「可変長か？固定長か？」で「配列か？Generic の List か？」の
  使い分けがあるかもしれません。

• Dictionary はハッシュでのアクセスが遅いので、キーが数字以外の場合に利用する。

ということだと思います。

移行メモ（誤字）: 元ページの「キーが数字以外の場合に利用可能する」は
「利用する」の誤記と思われる。

補足（string キーが遅い理由）: 本文の観察は正確で、
Dictionary<string, T> が遅いのはハッシュ計算の対象が文字列だからである。
int キーなら GetHashCode() が値そのものに近く極めて安いのに対し、
文字列は全文字を走査してハッシュを計算し、
さらに衝突時は文字列比較（全文字比較）が走る。

現在の .NET で改善する手段は以下。

手段	効果
FrozenDictionary<TKey,TValue>（.NET 8 以降）	構築後は不変。読み取りに特化して最適化される
StringComparer.Ordinal を明示	既定のカルチャ依存比較より高速
キーを int / enum に置き換える	最も効果的
CollectionsMarshal.GetValueRefOrNullRef	検索と更新を 1 回のルックアップで済ませる

なお、.NET Core 以降で Dictionary の実装自体も
大きく最適化されているため、本測定（.NET Framework / 32bit 時代）の
絶対値は現在には当てはまらない。
傾向（配列 < List < Dictionary、階層が深いほど遅い）だけを読むこと。

チューニング

階層が増える場合、チューニング手段としてよくやる
VB の With ステートメントを使用する要領で、辿るポインタ数を減らします。

//--------------------------------------------------
pr.StartsPerformanceRecord();
for (i = 0; i < num; i++)
{
  strVal = dicRef4["G"]["G"]["G"]["G"];
}
Console.WriteLine("dicRef4:" + pr.EndsPerformanceRecord());
//--------------------------------------------------

↓↓↓

//--------------------------------------------------
pr.StartsPerformanceRecord();

dicRef = dicRef4["G"]["G"]["G"];
for (i = 0; i < num; i++)
{
  strVal = dicRef["G"];
}
Console.WriteLine("dicRef4性能対策実施版:" + pr.EndsPerformanceRecord());
//--------------------------------------------------

以下のように、性能が改善します。

dicRef:
  ExT:2996[msec],  CT:3011[msec],  KT:0[msec], UT:3011[msec]
dicRef4:
  ExT:11754[msec], CT:11747[msec], KT:0[msec], UT:11747[msec]
dicRef4性能対策実施版:
  ExT:3137[msec],  CT:3089[msec],  KT:0[msec], UT:3089[msec]

補足（ループ不変式の巻き上げ）: この最適化は
一般に **loop-invariant code motion（ループ不変式の外出し）**と呼ばれる。
ループ内で値が変わらない式を外に出すという、言語を問わず有効な基本技法である。

4 階層のうち 3 階層分のルックアップが 1 億回 → 1 回になるため、
実測どおり dicRef（1 階層）とほぼ同じ時間まで改善する。
JIT はこの種の最適化を参照型の添字アクセスに対しては行えない
（途中で辞書が書き換わる可能性を排除できないため）ので、
人手で書く価値がある。

データ容量の影響

要素数が増えた場合、若干遅延します。

dicRef:要素数7
  ExT:3003[msec], CT:2948[msec], KT:0[msec], UT:2948[msec]
dicRefBigdata:要素数100万
  ExT:3979[msec], CT:3994[msec], KT:0[msec], UT:3994[msec]

補足（O(1) でも遅くなる理由）: ハッシュ表の計算量は O(1) なので
「要素数が増えても変わらない」はずだが、実測では約 33% 遅くなっている。
これはCPU キャッシュのヒット率が原因である。

要素数 7 なら全体が L1/L2 キャッシュに収まるが、
100 万要素ではメモリへのランダム アクセスとなり
キャッシュ ミスが発生する。
計算量の理論値だけでなく、
データ量とキャッシュの関係が実性能を決めるという好例である。

データのロード

• ロードするデータがメモリに収まるかどうかがポイントになります。

• 処理時間が問題となる場合は、ロード処理の時間も問題になる可能性があります。

• .NET では、オブジェクトとしてロードされるのでファイル サイズと
  異なる可能性があります。

• また、どういうオブジェクト・モデルにロードするかによってサイズが変わってきます。

• 使用可能なメモリ・サイズを超えるとページングが発生し、処理時間内に完了しません。

• CSV データをオブジェクト表現した際にサイズはどうなるか？

  • 以下の CSV データ 10MB を Unicode でファイルに保存、
    オブジェクト・モデルにロードしてデータ サイズの差分を確認する。

xxxxxxxxxx,xxxxxxxxxx,・・・,xxxxxxxxxx
xxxxxxxxxx,xxxxxxxxxx,・・・,xxxxxxxxxx
xxxxxxxxxx,xxxxxxxxxx,・・・,xxxxxxxxxx
  ・・・
xxxxxxxxxx,xxxxxxxxxx,・・・,xxxxxxxxxx

• Unicode で保存するのは、文字列のプログラム表現が Unicode のため、
  オブジェクト・モデル化によるデータ サイズ増加を把握し易くするため。

• データのロードには、Microsoft.VisualBasic.FileIO.TextFieldParser を使用した。

• データの保持方式
  ステートメント レベルの性能で高速であった方式を選択した。

  1. スタックに積まれないようにグローバル変数とする。
  2. レコード（フィールド）は → Class（メンバ）に保持する。
  3. 上記の Class を Generic の List に保持する。

以下結果

• ファイル サイズ 10MB に対して、プロセス メモリ サイズは 22MB
• 試しにファイル サイズ 20MB にした所、プロセス メモリ サイズは 41MB

となりました。

• その他

  • キー部分が共通なものを配列、Generic の階層にまとめるとデータの削減になる。

  • 以下、オブジェクト・モデルにロードするまでの性能情報

45318record(10MB)
  End:ExT:1002[msec], CT:983[msec], KT:31[msec], UT:952[msec]
90636record(20MB)
  End:ExT:2095[msec], CT:2044[msec], KT:172[msec], UT:1872[msec]

以下プログラム

class Program
{
    static List<ClassRecord> ListClassRecord = new List<ClassRecord>();

    static void Main(string[] args)
    {
        // CSVファイルを読み込むには？［2.0のみ、C#、VB］ － ＠IT
        // http://www.atmarkit.co.jp/fdotnet/dotnettips/487csvparser/csvparser.html

        TextFieldParser parser = new TextFieldParser("CSV.csv", System.Text.Encoding.GetEncoding("utf-16"));

        int i = 0;

        PerformanceRecorder pr = new PerformanceRecorder();
        pr.StartsPerformanceRecord();
        using (parser)
        {
            parser.TextFieldType = FieldType.Delimited;
            parser.SetDelimiters(","); // 区切り文字はコンマ

            // parser.HasFieldsEnclosedInQuotes = false;
            // parser.TrimWhiteSpace = false;

            while (!parser.EndOfData)
            {
                i++;
                //// コンソールに出力
                //Console.WriteLine(i.ToString());

                // 1行読み込み
                string[] row = parser.ReadFields();
                // クラスにロード
                Program.ListClassRecord.Add(new ClassRecord(row));
            }
        }

        Console.WriteLine(i.ToString() +"record");
        Console.WriteLine("End:" + pr.EndsPerformanceRecord());
        Console.ReadKey();
    }
}

以下結論

データ サイズは単純に 2 倍になっているが、何処が肥大しているか？

• レコード数なのか？
• カラム数なのか？

が不明確であるので測定してみないと解らない。

また、フィールドのサイズ次第で増大する比率が変わってくる。

補足（2倍になる内訳）: 「何処が肥大しているか」への回答は、
オブジェクトごとのヘッダとポインタのオーバーヘッドである。
64bit の .NET では、

要素	オーバーヘッド
オブジェクト ヘッダ（同期ブロック + 型ポインタ）	16 バイト／オブジェクト
string の長さフィールド + 終端	約 6 バイト／文字列
参照（ポインタ）	8 バイト／フィールド
ヒープのアラインメント	8 バイト境界に切り上げ

つまり、フィールド数（カラム数）× レコード数だけ
string オブジェクトが生成されるため、
1 フィールドが短いほど（10 文字程度なら）オーバーヘッドの比率が高くなる。
元ページの「フィールドのサイズ次第で増大する比率が変わる」という観察は正しい。

削減の手立ては以下。

手段	効果
string.Intern / 自前の辞書で文字列を共有	同じ値が繰り返し出るカラム（区分値等）で劇的に効く
数値・日付は文字列のままにせず値型に変換	string オブジェクト自体を作らない
class ではなく struct にする	ヘッダ 16 バイト／件を削減（ただし大きすぎるとコピー コストが増える）
ストリーミング処理にする	そもそも全件を保持しない。これが最も確実

最後の「そもそも全件をメモリに載せない」が本質的な解であり、
大量データの処理方式1の
マージ出力の考え方につながる。

マシンスペック

以下、性能情報の取得に使用したマシンのスペック。

------------------
System Information
------------------
Time of this report: 9/5/2014, 21:04:22
   Operating System: Windows 7 Professional 32-bit (6.1, Build 7601) Service Pack 1
           Language: Japanese (Regional Setting: Japanese)
System Manufacturer: Hewlett-Packard
       System Model: HP ProBook 6570b
          Processor: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz (4 CPUs), ~2.5GHz
             Memory: 4096MB RAM
Available OS Memory: 2954MB RAM
          Page File: 4026MB used, 1969MB available

移行メモ（体裁）: マシン名など環境固有の情報は除外し、
測定条件として意味のある項目に絞って掲載した。

補足（この測定を現在どう読むか）: 測定環境は
2014 年・Windows 7・32bit・メモリ 4GB である。
このため、

• 32bit プロセスのアドレス空間は 2GB が上限（WOW64）であり、
  「メモリに収まるか」の閾値が現在よりはるかに低い
• 「使用可能なメモリを超えるとページングが発生」という前提も、
  物理メモリが潤沢な現在の 64bit 環境では起きにくい

という点を割り引く必要がある。
相対的な傾向（階層を減らす、オブジェクト数を減らす、
ストリーミングにする）は現在も有効だが、
絶対値と閾値はそのまま適用できない。
現在計測するなら BenchmarkDotNet を使い、
ウォームアップと GC の影響を含めて測るのが標準的である。

添付ファイル

• ConsoleApplication.zip（本ページの計測プログラム一式）

---

Tags: 移行, データアクセス