5

long を int にマップする単純なB ツリーを実装しました。ここで、次の方法を使用してそのメモリ使用量を見積もりたいと思いました (32 ビット JVM のみに適用されます)。

class BTreeEntry {

    int entrySize;
    long keys[];
    int values[];
    BTreeEntry children[];
    boolean isLeaf;
    ...
    /** @return used bytes */
    long capacity() {
        long cap = keys.length * (8 + 4) + 3 * 12 + 4 + 1;
        if (!isLeaf) {
            cap += children.length * 4;
            for (int i = 0; i < children.length; i++) {
                if (children[i] != null)
                    cap += children[i].capacity();
            }
        }
        return cap;
    }
}
/** @return memory usage in MB */
public int memoryUsage() {
    return Math.round(rootEntry.capacity() / (1 << 20));
}

しかし、たとえば 7mio エントリに対して試してみたところ、memoryUsage メソッドは -Xmx 設定が許可するよりもはるかに高い値を報告しました。たとえば、1040 (MB) と表示されているので、-Xmx300 を設定します。JVM は何らかの方法でメモリ レイアウトを最適化できますか。空の配列の場合、または私の間違いは何ですか?

Update1: わかりました。isLeaf ブール値を導入すると、メモリ使用量が大幅に削減されますが、Xmx よりも高い値が観測された理由はまだ不明です。(すべてのコンストラクターに対して isLeaf == false を使用して、これを試すことができます)

Update2: うーん、何かが非常に間違っています。葉ごとのエントリを増やすと、メモリ使用量が減少すると想定されます (両方に対して圧縮を行う場合)。これは、配列が大きいほど参照のオーバーヘッドが少なくなるためです (また、btree の高さが小さいため)。しかし、リーフごとに 100 エントリではなく 500 エントリを使用すると、メソッド memoryUsage は増加した値を報告します。

4

1 に答える 1

0

ああ…少し新鮮な空気がこの問題を解決しました;）

エントリーがいっぱいになると分割されます。私の元の分割方法checkSplitEntry（メモリの無駄を避けたかった）で、大きなメモリの無駄の間違いを犯しました：

// left child: just copy pointer and decrease size to index
BTreeEntry newLeftChild = this;
newLeftChild.entrySize = splitIndex;

ここでの問題は、古い子ポインターがまだアクセス可能であることです。そのため、私の記憶では、Usage メソッドでいくつかの子を 2 回カウントしています (特に、圧縮しなかった場合)。したがって、このトリックがなくてもすべて問題なく、ガベージ コレクターが機能するため、B ツリーのメモリ効率がさらに向上します。

于 2013-04-09T10:16:38.277 に答える