9

現在、非常に大きな double の配列を割り当てているアルゴリズムがあり、頻繁に更新および検索しています。配列のサイズは N^2/2 で、N はアルゴリズムが動作する行数です。また、アルゴリズムを取り巻くアプリケーションに関連する目的のために、全体のコピーを保持する必要があります。

もちろん、これにより、競合するヒープの制限があるため、アルゴリズムが処理できる行数に制限が課されます。この時点まで、アルゴリズムを使用している人々に -Xmx 設定を更新してより多くのスペースを割り当てるように依頼することから逃れましたが、それはうまくいきました。ただし、この配列をメモリに収まるよりも大きくする必要があるという本当の問題があります。

この大規模な配列の必要性を軽減し、その分野でいくつかの有望な結果を得るために、アルゴリズムを変更する計画が既にあります。ただし、これはプロセスの根本的な変更であり、現在のコードの高度に洗練された状態に到達するまでには、さらに多くの作業が必要になります。

そのため、新しいアルゴリズムを完成させながら、既存のアルゴリズムの寿命を延ばしたいと考えていました。つまり、膨大な double 配列の割り当てに関連するヒープ制限に取り組む必要がありました。

私の質問は、それに対処する最善の方法は何ですか? nio FileChannel と MappedByteBuffer を使用する必要がありますか、それともより良い方法がありますか。nio アプローチを使用する場合、同じサイズのメモリ内配列と比較して、どのようなパフォーマンス ヒットが予想されるでしょうか?

ありがとう

4

7 に答える 7

6

使用可能なメモリが不足し始めている場合、おそらくすぐに使用可能な配列インデックスも不足し始めます。配列のサイズは に制限されInteger.MAX_VALUEており、配列要素として double を使用する場合、サイズは「わずか」32GB です。 .

32GB のメモリを搭載したマシンを入手するのは費用がかかりますが、アルゴリズムを変更する時間と関連するすべてのテストほど費用はかからないでしょう。

ただし、クライアントがメモリの限界まで実行されていて、そのデータセットがまだ成長している場合は、今すぐ弾丸をかじって、いつでもより少ないメモリを使用できるように変更を加えることが理にかなっています。とにかくすぐに配列を超えてしまうでしょう。

配列がややまばらに埋められていると仮定すると、他のオプションは、さまざまなまばらな配列データ構造の 1 つを使用することですが、これらは配列が 20% 未満である場合にのみ有益である傾向があります。

編集：すでに代替案を調査しているように見えるので、MappedByteBufferが適切な方法である可能性があります。明らかに、これはパフォーマンスに影響を与えますが、配列からの読み取りと書き込みがほとんどシーケンシャルである場合、これはそれほど悪くはありません。ランダムな読み取りと書き込みを行っている場合、これは非常に遅くなります。または、非常にゆっくりと非常にゆっくり...これらのことをどのように見るかによって異なります;-)

于 2009-12-16T22:52:57.000 に答える
2

PC で実行している場合、マップされたファイルのページ サイズは 4 キロバイトになる可能性があります。

したがって、問題は、データをディスクにスワップアウトし始めた場合、「現在ファイルになっている RAM へのランダムアクセスはどのくらいランダムか」ということから始まります。

そして (...もしそうなら...) 次の 4K ディスクフェッチの前に各ページで一度にいくつかではなく、4K ページ内の double が同時にアクセスされるケースを最大化するために double を注文するにはどうすればよいですか?

標準 IO を使用する場合でも、チャンクで読み書きする必要があるかもしれませんが、チャンクは小さくなる可能性があります。セクターは少なくとも 512 バイトで、ディスク クラスターより大きくなりますが、IO ごとにカーネル ラウンド トリップのオーバーヘッドがあることを考えると、どのサイズの読み取りが最適でしょうか?

申し訳ありませんが、次の最善のステップは、使用しているアルゴリズムとデータに大きく依存します。

于 2009-12-16T23:02:07.927 に答える
1

私は Java の MappedByteBuffers について一般的に良い経験をしてきました。-Xmxこれにより、変更に再び対処する必要がなくなる可能性があります。2 ～ 4 GB を超えるアドレス指定可能スペースが必要な場合は、64 ビットの CPU、OS、および JVM が必要になることに注意してください。

インデックスの問題を乗り越えるために、ページング アルゴリズムを記述することができます。これは、Java でソートされた (メモリ マップされた ?) ファイルでの Binary searchInteger.MAX_VALUEに対する関連する回答でここで行ったようにです。

于 2009-12-17T11:38:25.993 に答える
0

一部のオペレーティング システムは、他のオペレーティング システムよりもメモリ マッピングのサポートが優れていることに注意してください。

私はこれをしたくなるでしょう：

  1. すべての配列の get/put をオブジェクト インターフェイスの背後に配置して (まだ存在していない場合)、実装を簡単に変更できるようにします。
  2. 各 SoftReference がその行の double の配列を指す SoftReferences の配列を使用します。ReferenceQueue を使用して、GC がアレイを追い出すときにアレイをディスクに保存します。get() が null を返す場合、ディスクから取得します。

そうすれば、パフォーマンスをより細かく制御できることに気付くかもしれません - -Xmx は必要に応じて微調整できます。

于 2009-12-17T14:24:21.443 に答える
0

キャッシュ (CPU のメモリ キャッシュなど) を最適に利用するソフトウェアを作成する方法の領域に移動しています。これを正しく行うのは難しく、「正しい」方法は、アルゴリズムの設計方法によって異なります。

では、あなたのプログラムは実際にアルゴリズム的に何をしているのでしょうか?

于 2009-12-16T22:58:38.017 に答える
0

問題がメモリ不足である場合、簡単な解決策は、ハードウェアをアップグレードしてメモリを増やしたり、Java ヒープ サイズを増やしたり、64-bi5t JVM に切り替えたりすることです。

一方、配列のサイズに関する Java の制限に逆らって実行している場合は、ByteBuffer ルートをたどるか、配列の配列を使用するように切り替えることができます。後者は、Sun が推奨する回避策です。

N配列アプローチの配列を使用すると、(理論的には) に近い値に対処できます2**31。実際には、制限は、所有している物理メモリの量と、OS / JVM の組み合わせを使用して対処できる量によって決まります。

于 2009-12-17T03:52:04.583 に答える
0

配列を行としてデータベース テーブルに格納し、ストアド プロシージャを使用して更新と検索を行うことができます。

別のアイデア:

B-Tree を配列として使用し、いくつかの葉をディスクに保持します。B-Tree のノードを 1 ページまたは複数ページのサイズにするようにしてください。

于 2009-12-16T23:03:31.017 に答える