Obliczanie użycia pamięci drzewa B w Javie

Question

Wdrożyłem prostą B-Tree, która jest mapą longs do ints. Teraz chciałem oszacować zużycie pamięci o nim stosując następujący sposób (dotyczy tylko 32-bitowy 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)); 
} 

Ale próbowałem go np dla 7 milionów wpisów i metoda memoryUsage zgłasza znacznie większe wartości niż dopuszcza ustawienie -Xmx! Na przykład. mówi 1040 (MB), a ja ustawiam - Xmx300! Czy JVM w jakiś sposób jest w stanie zoptymalizować układ pamięci, np. dla pustych tablic lub co może być mój błąd?

Update1: Ok, wprowadzenie boolean isLeaf znacznie zmniejsza zużycie pamięci, ale wciąż nie jest jasne, dlaczego zaobserwowałem wyższe wartości niż Xmx. (Nadal możesz wypróbować to za pomocą isLeaf == false dla wszystkich contructors)

Update2: Hmm, coś jest bardzo źle. Przy zwiększaniu liczby wpisów na liście można założyć, że zużycie pamięci maleje (gdy robi się kompaktowy dla obu), ponieważ mniejszy narzut odniesień dotyczy większych macierzy (a btree ma mniejszą wysokość). Ale metoda memoryUsage zgłasza zwiększoną wartość, jeśli użyję 500 zamiast 100 wpisów na liście.

Answer 1

Ohh sh ... trochę świeżego powietrza rozwiązać ten problem;)

Gdy wejście jest zapełniona, zostanie on podzielony. W moim oryginalnym sposobie podziału checkSplitEntry (gdzie chciałem uniknąć marnowania pamięci) Zrobiłem duża strata pamięci błędu:

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

tu problem jest to, że stare dzieci wskaźniki są jeszcze dostępne. I tak, w mojej metodzieUsage metoda liczę trochę dzieci dwa razy (zwłaszcza gdy nie kompaktowałem!). Bez tej sztuczki wszystko powinno być w porządku, a moje B-drzewo będzie jeszcze wydajniejsze w pamięci, ponieważ śmieciarz może wykonać swoją pracę!