Tính toán mức sử dụng bộ nhớ của cây B trong Java

Question

Tôi đã triển khai một đơn giản B-Tree thats ánh xạ dài thành ints. Bây giờ tôi muốn ước tính mức sử dụng bộ nhớ của nó bằng phương pháp sau (chỉ áp dụng cho JVM 32 bit):

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

Nhưng tôi đã thử nó, ví dụ: cho các mục 7mio và phương thức memoryUsage báo cáo giá trị cao hơn nhiều so với cài đặt -Xmx sẽ cho phép! Ví dụ. nó nói 1040 (MB) và tôi đặt -Xmx300! Là JVM bằng cách nào đó có thể tối ưu hóa bố trí bộ nhớ, ví dụ như. cho mảng trống hoặc những gì có thể là sai lầm của tôi?

Update1: Ok, giới thiệu boolean isLeaf làm giảm việc sử dụng bộ nhớ rất nhiều, nhưng vẫn chưa rõ tại sao tôi quan sát giá trị cao hơn Xmx. (Bạn vẫn có thể thử điều này bằng cách sử dụng isLeaf == false cho tất cả các contructors)

Update2: Hmmh, có điều gì đó rất sai. Khi tăng các mục nhập trên mỗi lá, giả sử rằng việc sử dụng bộ nhớ giảm (khi làm nhỏ gọn cho cả hai), vì ít chi phí tham chiếu có liên quan đến mảng lớn hơn (và btree có chiều cao nhỏ hơn). Nhưng phương pháp memoryUsage báo cáo một giá trị gia tăng nếu tôi sử dụng 500 thay vì 100 mục mỗi lá.

Answer 1

Ohh sh ... một chút không khí trong lành đã giải quyết được vấn đề này;)

Khi mục nhập đầy, nó sẽ được chia nhỏ. Trong phương pháp phân chia ban đầu của tôi checkSplitEntry (nơi tôi muốn tránh sự lãng phí bộ nhớ) tôi đã thực hiện một sai lầm lớn chất thải bộ nhớ:

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

Vấn đề ở đây là, rằng trẻ em tuổi con trỏ vẫn tiếp cận được. Và như vậy, trong bộ nhớ của tôiSử dụng phương pháp tôi đếm một số trẻ em hai lần (đặc biệt là khi tôi đã không nhỏ gọn!). Vì vậy, nếu không có thủ thuật này tất cả nên được tốt và B-Tree của tôi sẽ được nhiều hơn bộ nhớ hiệu quả như thu gom rác có thể làm công việc của mình!