Calcolo dell'utilizzo della memoria di un B-Tree in Java

Question

Ho implementato un semplice B-Tree che le mappe desiderano agli inte. Ora volevo stimare l'utilizzo della memoria utilizzando il seguente metodo (vale a 32bit JVM solo):

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)); 
} 

Ma provato ad esempio per 7 milioni di voci e il metodo memoryUsage riporta valori molto più alti di quanto consentito dall'impostazione -Xmx! Per esempio. dice 1040 (MB) e ho impostato -Xmx300! La JVM è in qualche modo in grado di ottimizzare il layout della memoria, ad es. per gli array vuoti o quale potrebbe essere il mio errore?

Update1: Ok, l'introduzione di isLeaf boolean riduce molto l'utilizzo della memoria, ma non è ancora chiaro il motivo per cui ho osservato valori più alti di Xmx. (Puoi ancora provarlo usando isLeaf == false per tutti i controli)

Update2: Hmmh, qualcosa è molto sbagliato. Quando si aumentano le voci per foglia, si presume che l'utilizzo della memoria diminuisca (quando si compatta per entrambi), poiché per gli array più grandi è implicato un minore sovraccarico di riferimenti (e btree ha un'altezza minore). Ma il metodo memoryUsage riporta un valore aumentato se utilizzo 500 anziché 100 voci per foglia.

Answer 1

Ohh sh ... un po 'di aria fresca ha risolto questo problema;)

Quando una voce è piena sarà a spacco. Nel mio metodo split originale checkSplitEntry (dove volevo evitare sprechi di memoria) ho fatto un grosso errore spreco di memoria:

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

Il problema qui è che i puntatori vecchi bambini sono ancora accessibili. E così, nel mio metodo di utilizzo della memoria sto contando alcuni bambini due volte (specialmente quando non compivo!). Quindi, senza questo trucco, tutto andrebbe bene e il mio B-Tree sarà ancora più efficiente in termini di memoria dato che il garbage collector può fare il suo lavoro!