Java:填充内存排序的批

Question

所以我使用Java对行分隔元组的磁盘上的大型文件进行多路外部合并排序。元组的批被读取到TreeSet中，然后将其转储到磁盘上排序的批中。一旦所有数据都用完了，这些批处理就会合并排序到输出中。

目前，我正在使用幻数来计算内存中可以容纳多少元组。这是基于一个静态数字，该数字指示每MB堆空间可以大致容纳多少元组，以及使用可以获得多少堆空间

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

然而，这并不总是很好地工作，因为我们可能正在对不同长度的元组进行排序（对于这些元组，每MB的静态元组数字可能过于保守），并且我现在想使用轻量级模式来在其中插入更多，这可能会使数字变得更加可变。

所以我正在寻找一种更好的方法来填满堆的空间。理想情况下，解决方案应该是：

• 可靠（没有堆空间异常的风险）
• 灵活（不基于静态数字）
• 高效（例如，不在每个元组之后轮询运行时内存估计）

有什么想法吗？

Answer 1

由于垃圾收集器的垃圾处理，将堆填满可能是个坏主意。（当内存接近满时，垃圾收集的效率接近0，因为收集的工作量取决于堆大小，但释放的内存量取决于被标识为不可访问的对象的大小）。

然而，如果你必须这样做，你就不能简单地按如下方式做吗？

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

发现空闲内存的调用将是罕见的，所以不应该对性能征税太多。例如，如果您有1GB的堆空间，并且保留1MB为空，并且MAX_RECORD_SIZE是平均记录大小的十倍，那么getFreeSpace()将仅被调用log（1000）/-log（0.9）~=66次。

Answer 2

为什么要计算你能容纳多少物品？让java告诉你什么时候已经用完了所有的内存，捕捉异常并继续。例如，

    // prepare output medium now so we don't need to worry about having enough 
    // memory once the treeset has been filled.
    BufferedWriter writer = new BufferedWriter(new FileWriter("output"));
    Set<?> set = new TreeSet<?>();
    int linesRead = 0;
    {
        BufferedReader reader = new BufferedReader(new FileReader("input"));
        try {
            String line = reader.readLine();
            while (reader != null) {
                set.add(parseTuple(line));
                linesRead += 1;
                line = reader.readLine();
            }
            // end of file reached
            linesRead = -1;
        } catch (OutOfMemoryError e) {
            // while loop broken
        } finally {
            reader.close();
        }
        // since reader and line were declared in a block their resources will 
        // now be released 
    }
    // output treeset to file
    for (Object o: set) {
        writer.write(o.toString());
    }
    writer.close();
    // use linesRead to find position in file for next pass
    // or continue on to next file, depending on value of linesRead

如果您的内存仍然有问题，只需将读卡器的缓冲区调大，即可保留更多内存。

BufferedReader中缓冲区的默认大小为4096字节。因此，当完成阅读时，你将释放超过4k的内存。在此之后，您的额外内存需求将降至最低。您需要足够的内存来为集合创建迭代器，让我们慷慨地假设200个字节。您还需要内存来存储元组的字符串输出（但只是暂时的）。你说元组包含大约200个字符。考虑到分隔符（400个字符，即800个字节），我们将其增加一倍。因此，您真正需要的只是额外的1k字节。所以你很好，因为你刚刚发布了4k字节。

您不需要担心用于存储元组的字符串输出的内存，因为它们的寿命很短，并且只在循环的输出中引用。请注意，Writer会将内容复制到其缓冲区中，然后丢弃字符串。因此，下次垃圾收集器运行时，可以回收内存。

我已经检查过了，add中的OOME不会使TreeSet处于不一致的状态，并且在修改内部表示之前会为新的Entry（用于存储键/值对的内部实现）分配内存。

Answer 3

您可以使用直接内存写入将堆填满（Java中确实存在这种情况！）。它在sun.misc.Unsafe中，但并不推荐使用。请参阅此处了解更多详细信息。我可能建议编写一些JNI代码，并使用现有的C++算法。

Answer 4

我会把它作为一个想法来添加，包括使用SoftReference作为低内存的"嗅探器"。

SoftReference<Byte[]> sniffer = new SoftReference<String>(new Byte[8192]);
while(iter.hasNext()){
   tuple = iter.next();
   treeset.add(tuple);
   if(sniffer.get()==null){
      dump(treeset);
      treeset.clear();
      sniffer = new SoftReference<String>(new Byte[8192]);
   }
}

这在理论上可能很有效，但我不知道SoftReference的确切行为。

在虚拟机抛出OutOfMemoryError之前，保证已清除对软可访问对象的所有软引用。否则，不会对清除软引用的时间或清除对不同对象的一组此类引用的顺序施加任何约束。然而，鼓励虚拟机实现偏向于清除最近创建或最近使用的软引用。

希望听到反馈，因为在我看来这是一个优雅的解决方案，尽管虚拟机之间的行为可能会有所不同？

在我的笔记本电脑上测试，我发现它的软参考很少被清除，但有时清除得太早，所以我想把它和meritin的答案结合起来：

SoftReference<Byte[]> sniffer = new SoftReference<String>(new Byte[8192]);
while(iter.hasNext()){
   tuple = iter.next();
   treeset.add(tuple);
   if(sniffer.get()==null){
      free = MemoryManager.estimateFreeSpace();
      if(free < MIN_SAFE_MEMORY){
         dump(treeset);
         treeset.clear();
         sniffer = new SoftReference<String>(new Byte[8192]);
      }
   }
}

再次，欢迎思想！