そのため、次のタスクがありました。
1. 16文字の文字列（一意のキー）と、それぞれ4バイト長の2つの整数値で構成される最大1億件のレコードをメモリに保存します。
2.キーでレコードをすばやく見つけて編集します。
問題番号1の解決策。 メモリ内の場所。
投稿から始めましょう。 レコード内の有用な情報の総量は24バイトです。 データ配列全体が約2.4 GBを占める必要があります（1024境界に沿った正確な再計算は扱いません）。 ここでは、最初のトラブルを待っている：x32のWindows OSのプロセスに2 GBのみを割り当てることができます。 実際には、.Netプロセスでは、この値はさらに小さく、約1.8 GBのどこかに割り当てることができました。 私は宇宙の残りの部分は、プロジェクトで使用されているライブラリによって占められているとします。 T.O. 問題を完全に解決するため、我々は唯一のx64プラットフォーム上ですることができます。 例では、比較のためにx32を引き続き考慮します。
だから、前置きなしに、フェザー（マウスとキーボード）をとると、すぐに頭に浮かぶ何かを彫刻開始。 メモリ内のレコードの代表を作成します。
public class Entry { public string Key; public int IntValue1; public int IntValue2; }
intエイリアスはクロスプラットフォームであり、常にInt32と一致するため、x32とx64で同じになります。
単純な配列を行い、10万のレコードで充電：
public Entry[] Entries = new Entry[10000000]; private void btnCreate_Click(object sender, EventArgs e) { int i; for (i = 0; i < Entries.Length; i++) { Entries[i] = new Entry() {Key = i.ToString("0000000000000000")}; } GC.Collect(); var msg = string.Format("Created {0}, Memory {1}", i.ToString("0,0"), GC.GetTotalMemory(true).ToString("0,0")); lbLog.Items.Add(msg); }
[ public Entry[] Entries = new Entry[10000000]; private void btnCreate_Click(object sender, EventArgs e) { int i; for (i = 0; i < Entries.Length; i++) { Entries[i] = new Entry() {Key = i.ToString("0000000000000000")}; } GC.Collect(); var msg = string.Format("Created {0}, Memory {1}", i.ToString("0,0"), GC.GetTotalMemory(true).ToString("0,0")); lbLog.Items.Add(msg); }
E） public Entry[] Entries = new Entry[10000000]; private void btnCreate_Click(object sender, EventArgs e) { int i; for (i = 0; i < Entries.Length; i++) { Entries[i] = new Entry() {Key = i.ToString("0000000000000000")}; } GC.Collect(); var msg = string.Format("Created {0}, Memory {1}", i.ToString("0,0"), GC.GetTotalMemory(true).ToString("0,0")); lbLog.Items.Add(msg); }
そして、約760 MB（x32）と1040 MB（x64）を占有していることがわかります。 レコードごとに正確に76/104 B、そのうち24だけが有用で、1億で7.6 / 10.4 GBが必要になることがわかりました。
52/80 Bかかったのは何ですか？ メモリ位置のインフラ.NETオブジェクトとアライメント：いくつかあります。 最初のものから始めましょう。 良い記事はここで読むことができます 。 それは私たちがリンク上のクラスBのインフラ8/16とさえ4/8 Bに失っていることが判明した（クラスインスタンスの私達の配列は、実際のインスタンスへのポインタの配列です）。 クラスを構造体に置き換えて確認します。
public struct Entry ...
測定では、記録あたり64/80 Bのコストが示されました。 すべてが収束します-12/24 Bを保存しました。構造はValueTypeであるため、配列にはリンクではなく値自体があると仮定するのが論理的です。 そのため、実際にリンクで4/8 B節約しました。 構造自体のインフラストラクチャには何もかかりません。 さらに先へ進み、Keyの最適化を開始する前に、明らかに私たちは多くを失いつつあるので、1つの重要なポイントに焦点を合わせます。 レコードを構造体に転送して、自分用の穴を掘りました-構造体の1つの配列にデータを入れると、非常に大きなメモリブロックが1つ必要になります。 十分な空きメモリが固体ブロックの断片化が原因ではないかもしれないとしても。 実際には、私は問題の以上500メガバイトの割り当てに対処するために始めました。 この問題は2番目の問題で解決します。 さらに、レコードを転送するたびに、構造のクローンを作成するとき、およびリンクを整理するとき（パッケージ化/ボックス化解除（ボックス化/ボックス化解除））で失われます。 しかし、どこへ行くにも、スペースを節約する必要があります。
[キー]フィールドに進みます。 String型はクラスであるため、レコードですぐに12/24 Bを失います。 実際には、この行は非常に太く、例としてここを読むことができます 。 実際には、長さ16のストリングの配列を作成したので、キーフィールド56/72 Bが書き込みのために占有していると確信しています。 合計：
クラスの場合：8（2つの整数）+ 56/72（キー）+12/24（クラスインフラストラクチャ+リンク）= 76/104 B
8（2つのINT）+ 72分の56（キー）= 80分の64 B.：構造用
Keyフィールドをchar []に変換してみましょう。 両方のプラットフォームで8 Bの利益を得ています。 配列もクラスであるため、インフラストラクチャには保存せず、文字列自体の内部組織にのみ保存しました。その内部にはchar配列も格納されているためです。 それぞれの文字 - Unicodeと2バイトです。 さらに、メモリの配置のどこかが役割を果たす可能性があります。 それについて話す時間です。
多くの人が、メモリ内のデータをプラットフォーム固有の境界、たとえばInt32境界に沿って整列させることが有利であることを知っていると思います。 詳細については、 こちらをご覧ください 。 この場合、クラスの場所/構造エントリ我々はので、何も失っていません すべてのフィールドが4バイトの境界上に正確にある（ - リンクキーことを覚えておいてください）。 StructLayout属性の設定を変更し、Marshal.SizeOf（新しいエントリ（））メータリングを使用して実験できます。 あなたが代わりにbyte型のint型の単一のフィールドを作成した場合でも、それは、配列全体我々は同じ量のメモリを占有し、そしてあなたがあるStructLayoutパック= 1でプロパティを設定しても、int型ことが判明します 構造自体は1バイトの境界でパックされますが、配列の要素は4バイトの境界で配置されます。 配列のパッキングの問題は解決しなかったとすぐに言わなければなりません。 問題の最終的な解決策はこれを必要としませんでした。 したがって、このトピックは、文字列/文字のトピックと同様に、ここでは完全に開示されていません。 また、StructLayout属性のCharSet = CharSet.Ansiの値が、文字列でもchar []でも、占有メモリのサイズに影響を与えなかったことを追加します。
そのため、現時点では、記録時に20/32 Bを節約しました。 なぜなら このタスクの文字列は非ユニコードではなく、char []の代わりにbyte []を使用することが決定されました。 両方のプラットフォームでさらに16バイト節約します。 現在、1つのレコードには40/56 Bが必要です。余剰-アレイの編成には16/32B。 .Netには、安全でないモードを使用して静的な固定バッファーを編成する機能があることがわかります。
private unsafe fixed byte _key[16];
ここで、最後に、100％の合理性を達成します。記録は両方のプラットフォームのメモリで正確に24 B必要です。 x32では約75百万（1.8 GB）、x64では1億（2.4 GB）をダウンロードできます。 x64の最大数は、基本的に利用可能なメモリのサイズによって制限されます。 この幸福は、安全ではない固定ブロックでのみ使用できます。 ここではパフォーマンスが低下するという疑いがありますが、どれだけ-私は知りません、私は測定をしませんでした、なぜなら 最終バージョンはニーズを完全に満たしました。
私たちは喫煙して、2番目の問題の解決に進みます。
問題番号2の解決策。 クイックアクセス。
1億件のレコードにすばやくアクセスするには、ハッシュテーブルのようなものが必要です。 標準のハッシュテーブルは適切ではありません。 Objectを使用します。これは、各レコード構造が特別なクラス（ボックス化）に配置され、クラスのインフラストラクチャで再び失われ始めることを意味します。 ジェネリックが必要です。 1つあります-辞書<TKey、TValue>。 使用と逆アセンブルの試みが失敗した後、次のことがわかります（ ここでハッシュテーブルを読み取る方法の原則に詳しくない人）。
-エントリごとに8 Bを超える：
[StructLayout(LayoutKind.Sequential)] private struct Entry { public int hashCode; public int next; public TKey key; public TValue value; }
ハッシュコードの保存とリンクリストの構成が失われます（連鎖方法が使用されます）。 ここで、ところで、キー用と値用の2つの構造が必要です。
- データの一つのセグメント：
private Entry<TKey, TValue>[] entries;
1つの大きなメモリブロックを割り当てるという深刻な問題があります。
- ハッシュセグメントは、容量（多くの疑問が生じる）以上であります
private void Initialize(int capacity) { … num = HashHelpers.GetPrime(capacity); this.buckets = new int[num]; …
-塗りつぶしの際、最小2倍のマージンでサイズ変更が行われ、ハッシュセグメントがこのサイズに適合し、それに応じて再ハッシュされます。
private unsafe void Resize() { … num = HashHelpers.GetPrime(this.count * 2); numArray = new int[num]; … entryArray = new Entry<TKey, TValue>[num]; … this.buckets = numArray; this.entries = entryArray; }
> [NUM]。 private unsafe void Resize() { … num = HashHelpers.GetPrime(this.count * 2); numArray = new int[num]; … entryArray = new Entry<TKey, TValue>[num]; … this.buckets = numArray; this.entries = entryArray; }
これがすべてを導くものを詳細に説明すべきではないと思います。 少なくとも、100万分の1の倍増のロジックを考慮してください。
そのような不適切な動作を発見したので、私はもはやより合理的な何かのために私のネイティブのコレクションを掘り下げ始めませんでしたが、自分の辞書を書きました。 実際には、すべてのものは、私が標準を実装した機能の90％を必要としない、特に以来、非常に簡単です。 コードは提供せず、重要なポイントのみを示します。
-キーと値を別々に使用しないでください。すべて1つのエントリ構造で使用してください。
-Entry構造で、GetHashCode（）メソッドがブロックされました（そして、構造内で何かをどのように重複させることができますか？！） ここから変更されたFNVメソッドを使用しました （図4）
- ブロックされた構造のエントリー方法は、（オブジェクトOBJ）に等しいです。 比較は重要です。
-コンストラクターでカスタム化されたハッシュセグメントのサイズ。 サイズの変更と再ハッシュは提供されていません。
-ハッシュセグメントのインデックスは、ハッシュコードをハッシュセグメントのサイズで割った余りとして計算されます。
-各ハッシュセグメントセルは通常のリストであり、同じハッシュコードのエントリで満たされています。 これは、1つの大きなメモリブロックの問題が解決される場所です。
組織にどれだけのメモリを費やすかを計算します。
- heshsegment =リストへのリンク（4/8サイズheshsegmentaの*のB）のアレイ。
-リストインスタンス=クラスインフラストラクチャ+リストフィールド（ハッシュセグメントサイズ*（8/16 +28/44））。
合計で、100万のセグメントの組織では、約40/68 Mbを費やします。
すべてが素晴らしいことだし、それはシャンパンを飲む時間です。 しかし、そこにありました。 リストは次のとおりです。
-標準辞書が2倍になると成長するように：
private void EnsureCapacity(int min) { … num = (((int) this._items.Length) == null) ? 4 : (((int) this._items.Length) * 2); …
）== nullの）？ private void EnsureCapacity(int min) { … num = (((int) this._items.Length) == null) ? 4 : (((int) this._items.Length) * 2); …
* private void EnsureCapacity(int min) { … num = (((int) this._items.Length) == null) ? 4 : (((int) this._items.Length) * 2); …
-過度に占有されたメモリを解放する機能は、0.1ボリュームを解放しません：
public void TrimExcess() { int num; num = (int) (((double) ((int) this._items.Length)) * 0.9); if (this._size >= num) { goto Label_002A; } this.Capacity = this._size; Label_002A: return; }
-さて、付録では、フィールドとクラスとは冗長です（目的のために）：
public class List... { private const int _defaultCapacity = 4; private static T[] _emptyArray; private T[] _items; private int _size; [NonSerialized] private object _syncRoot; private int _version; ...
カスタムの線形成長を使用して、メモリを完全に解放し、_syncRootフィールドと_versionフィールドに8バイトを節約して、独自のリストを作成する必要がありました。 それでもB. 12を保存し、構造に翻訳することが可能です
問題はすべて解決しました-シャンパンを飲みます！
そして少し練習
2,66 @ PCコア2クワッドQ9400、RAMの4 Gbは、Windows Server 2008 R2の標準のx64
Heshsegment百万は、25の高さを表示します。
100ミリ充填、5分50秒 メモリ2.46 GB、ピーク3.36 GB。
統計：100％、最小チェーン56、最大152、10の標準偏差を埋めます。
1億個のメモリと外部の1億個の4分10秒の比較。
ハッシュセグメント200万、リスト成長20。
100ミリ充填4分43秒 メモリ2,53 GB GBピーク3.57。
統計：100％、チェーン20、最小値、最大値89、標準偏差7を充填します。
メモリ内の1億個と外部1億個2分56秒の比較。
小さな発言：.NETはすぐに私たちは多数のオブジェクトをリリースしている場合でも、メモリを解放しませんでした。 これは、ガベージコレクション後に発生しない場合があります。 メモリは、将来の使用のために予約されたままであり、システム内のメモリが大幅に不足している場合は解放されます（おそらく他の基準によって）。
この経験が、最適化の問題を解決する他の誰かに役立つことを願っています。