読み取り専用の文字列コレクション:一致を保存

多くの場合、プログラムが一部のデータをメモリにロードし、それを長時間(または作業の終了まで)変更せずにそのままにしておきます。 読み取りと書き込みの両方に最適化されたデータ構造を使用します。 たとえば、 Ensemblデータベースから、すべてのヒト遺伝子の識別子のリスト(すべての種類のmiRNAなどを含む、50,000を少し超える)を引きます。 標準のArrayListでそれらを読むと、32ビットのHotSpotでは4メガバイトを少し超えて消費します。 コレクションが変更されないことを知って、メモリを節約することは可能ですか?



データベースからデータを部分的に読み取る機能については触れません。これは別の議論のトピックです。 さらに、ここで説明する方法と部分的な読み取りを組み合わせて、メモリをさらに節約できます。 また、たとえば、仮想マシンのオプション-XXを使用しません。+ UseCompressedStrings:この場合、メモリを節約するだけでなく、メソッドと組み合わせることもできます。



何かを最適化する前に、それを測定する必要があります。 私たちの場合、リストが占有しているメモリの量について話しています。 そして、もちろん、浅いサイズ(ArrayListオブジェクト自体のサイズ)ではなく、保持されたサイズ(ArrayListと、それが直接または間接的に参照するすべてのオブジェクトのサイズ)に関心があります。 Eclipse Memory Analyzerを使用して測定します。 ヒープ上の目的のオブジェクトを(たとえば、クラス名で)検索し、[保持セットの表示]オプションを使用します。 次の図が表示されます。







予想どおり、ArrayList自体の重量は非常に少なく、24バイトです。 Object []文字列参照の配列はArrayList内で決定的に重くなりますが、それでもスペースの90%以上は文字列オブジェクト自体とそれに関連付けられたchar []配列によって消費されます。



Object []配列を実際の要素数にトリミングすることで、わずかな改善を実現できます。 ご存じのように、ArrayListは、要素が追加されるたびに再割り当てされないように、マージンを使用してスペースを割り当てます。 これ以上要素が追加されないことがわかっているため、このストックは必要ありません。 これは、次のように簡単かつ効果的に実行できます。



List<String> genes = readGenes(); genes = Arrays.asList(genes.toArray(new String[genes.size()]));
      
      







ここでは、結果はもはやArrayListではありません(より正確にはArrayListですが、別のリストです)。 まず、目的の長さの配列のコピーを作成し、それをコピーにラップします。 保持されたセットは次のようになります。







配列は少し小さくなりましたが、最終的にはスペースを0.44%節約しました。 まあ、何も、私たちはただウォームアップします。



これらのchar []配列を見てみましょう。 これらには、タイプ「ENSG00000121410」の遺伝子識別子(15文字-30バイト)、オブジェクトに関するシステム情報の別の8バイト、および長さの4バイトが含まれています。 そして、これらの42バイトは8に揃えられます。つまり、6個の未使用バイトが追加されます。 したがって、48バイトのうち、30のみが有用な情報を保持します(+ UseCompressedStringsを使用すると、15に減らすことができ、「超過」情報の割合はさらに増加し​​ます)。 これで何ができますか?



String.substringの仕組みを思い出してください。 結果の行は、共有バッファーchar []によって親行と共有されます。オフセットとカウントは、それに応じて子行に設定されます。 同時に、子行はユーザーの視点と変わりませんが、メガバイト行から1文字を切り取った場合でも、親行が削除されている場合、完全なバッファーが保存されます。 面倒な場合があります。コード内でそのような場所を探して新しい文字列に署名する必要がありますが、今では逆に役立ちます。 配列のすべての行を1つのchar []バッファーに配置します。 これを行うには、いくつかのユーティリティクラスで補助メソッドを記述します。



 public static List<String> compactify(Collection<String> list) { StringBuilder sb = new StringBuilder(); for( String item : list ) sb.append(item); String data = sb.toString(); List<String> result = new ArrayList<String>(list.size()); int index = 0; for( String item : list ) { result.add(data.substring(index, index + item.length())); index += item.length(); } return result; }
      
      







このメソッドは、最初にソースコレクションのすべての行を1つの長い文字列に接着してから、部分文字列を使用して部分文字列にスライスします。 この一見役に立たない操作を通して遺伝子リストを実行し、保持されているセットを見てみましょう。







ええ、すでに重要です。 上記の余分なバイトをほぼすべて節約し、合計で元のサイズの24%を獲得しました。 配列の行が15文字より短い場合、節約量はさらに大きくなります。 ところで、ArrayListを作成するときに、その長さを明示的に指定したため、Object []には余分な要素が含まれていないことに注意してください。つまり、最初の最適化は失われません。



結果の配列は録音に安全に使用できます。配列の行は他のすべてをドラッグするため、行を削除することにした場合、すべてのメモリを解放しないことに注意してください。 しかし、配列が読み取り専用であることに同意したため、すべてが正常です。 入力配列に重複する行がある場合は注意してください。関数はこれをチェックしないため、取得するよりも多くを失う可能性があります。



しかし、24%は少数です。 基本的に役に立たない文字列オブジェクト(char []のデータ自体)が目を引きます。 たぶんあなたはそれらを保存することはできませんが、オンデマンドで文字列をカットしますか? これを行うには、Listの実装を記述し、行の先頭のオフセットを保存する必要があります。



 public class CompactStringList extends AbstractList<String> implements RandomAccess { private String data; private int[] offsets; public CompactStringList(Collection<String> list) { StringBuilder sb = new StringBuilder(); offsets = new int[list.size()]; int offset = 0, i = 0; for( String item : list ) { sb.append(item); offsets[i++] = offset; offset+=item.length(); } data = sb.toString(); } public String get(int index) { return index == offsets.length - 1 ? data.substring(offsets[index]) : data.substring(offsets[index], offsets[index + 1]); } public int size() { return offsets.length; } }
      
      







コンストラクターで、すべての入力行を再び1つに接着し、行の先頭のオフセットを記憶して配列にしました。 要素を受け取ったら(簡単にするために、パラメーターの正確さを確認しません)、文字列から目的の部分を切り取ります。 この場合、新しいStringオブジェクトのみが作成され、データ自体はコピーされません。 そのようなオブジェクトの保持されたセットを見てください:







元のバージョンと比較して55.5%の節約になりました。ここでは、すでにダンスを楽しむことができます。



もちろん、最新の最適化は最も物議を醸すものであり、さらなるユースケースに依存します。 たとえば、同じ要素を頻繁に取得し、結果の文字列を他のコレクションに保存すると、Stringオブジェクトが増えます。 これらは共通のバッファを指しますが、1行あたり40バイトを失います(32ビットHotSpotで)。 最適化のために最適化に夢中にならないでください。悪化する可能性があります。 ただし、多くのアプリケーションでは、この方法が役立つ場合があります。 さて、または最後の手段として、Java機能の理解を読者に広げます。



All Articles