Java: Filling in-memory sorted batches

Question

So I'm using Java to do multi-way external merge sorts of large on-disk files of line-delimited tuples. Batches of tuples are read into a TreeSet, which are then dumped into on-disk sorted batches. Once all of the data have been exhausted, these batches are then merge-sorted to the output.

Currently I'm using magic numbers for figuring out how many tuples we can fit into memory. This is based on a static figure indicating how may tuples can be roughly fit per MB of heap space, and how much heap space is available using:

long max = Runtime.getRuntime().maxMemory();
long used = Runtime.getRuntime().totalMemory();
long free = Runtime.getRuntime().freeMemory();      
long space = free + (max - used);

However, this does not always work so well since we may be sorting different length tuples (for which the static tuple-per-MB figure might be too conservative) and I now want to use flyweight patterns to jam more in there, which may make the figure even more variable.

So I'm looking for a better way to fill the heap-space to the brim. Ideally the solution should be:

• reliable (no risk of heap-space exceptions)
• flexible (not based on static numbers)
• efficient (e.g., not polling runtime memory estimates after every tuple)

Any ideas?

Answer 1

Filling the heap to the brim might be a bad idea due to garbage collector trashing. (As the memory gets nearly full, the efficiency of garbage collection approaches 0, because the effort for collection depends on heap size, but the amount of memory freed depends on the size of the objects identified as unreachable).

However, if you must, can't you simply do it as follows?

for (;;) {
    long freeSpace = getFreeSpace();
    if (freeSpace < 1000000) break;
    for (;;freeSpace > 0) {
        treeSet.add(readRecord());
        freeSpace -= MAX_RECORD_SIZE;
    }
}

The calls to discover the free memory will be rare, so shouldn't tax performance much. For instance, if you have 1 GB heap space, and leave 1MB empty, and MAX_RECORD_SIZE is ten times average record size, getFreeSpace() will be invoked a mere log(1000) / -log(0.9) ~= 66 times.