How can one calculate how much memory a Java TreeMap needs to handle each mapping?
I am doing an experiment with 128 threads, each dumping 2^17 longs in its own array.
All these 2^24 longs are then mapped to ints (TreeMap<Long,Integer>), each array reference is nulled before moving to the next.
That should amount to 128+64 MB for the keys+values. I am surprised to get OutOfMemoryError during the mapping with 512MB assigned to this VM.
You seem to assume that a Long, Integer key/value pair in a map occupies only 12 bytes of memory. That is wrong.
Even if you copy from a primitive long array, autoboxing will automatically create Long and Integer object instances as wrappers for the primitive values when you use them as map keys and values. The memory requirements for the object instances is VM implementation specific, but I think that Sun's VM lies in the range 32-48 bytes for these objects, with instances in a 64 bit VM being slightly larger. In addition, the map need additional object instances for each key/value pair to manage the internal data structures.
Apperently from this Tree Map 4 Docs the default size of the tree is 64M. It will report an OutOfMemoryError if you exceeed that. If you don't specify a maximum size it will default to that.
Hope that helps Bob
EDIT: Ignore this. Its all wrong.
Each Long is at least 16 bytes, and each Integer is at least 12 16 bytes, due to the 8-byte object overhead and 8-byte alignment. On a 32-bit machine, each node is at least 24 32 bytes (object header, key, value, two children, and flags for balancing). That means at least 2^24 * (12+24+16) = 832MB.
Edit: It appears objects are 8-byte aligned, so bump the Integer to 16 bytes. Also, a tree node probably has another field for balancing the tree, so count 32 bytes for it. That brings us to a minimum of 1024MB.