6

我正在为合并排序和快速排序做一个基准测试。

我实施了Random_list.create,Mergesort.sort_list和Quicksort.sort_list. 我们可以假设这三个功能都已正确实现，并且在这个问题中实现并不重要。

我想问的是关于 OCaml 的 GC。

这是我的基准代码：

let _ = 
  let l = Random_list.create 10000000 in

  let len1 = List.length (Mergesort.sort_list l) in
  Printf.printf "mergesort done for %d elements" len1;

  let len2 = List.length (Quicksort.sort_list l) in
  Printf.printf "quicksort done for %d elements" len2

如果我运行上面的代码，它会Fatal error: exception Out_of_memory在mergesort done for 10000000 elements.

内存不足，没问题。输出也告诉我Out_of_memory成功后发生mergesort。

然后我所做的就是拆分代码并分别测试：

let _ = 
      let l = Random_list.create 10000000 in
      let len1 = List.length (Mergesort.sort_list l) in
      Printf.printf "mergesort done for %d elements" len1

接着

let _ = 
      let l = Random_list.create 10000000 in
      let len2 = List.length (Quicksort.sort_list l) in
      Printf.printf "quicksort done for %d elements" len2

没有. _ Out_of_memory

这是我的问题：

从我的基准代码中，是的，我进行了串行排序：合并排序，然后是快速排序。

在执行期间，应该创建 3 个主要列表：l来自 mergesort 的列表和来自 quicksort 的列表。

但是，从合并排序创建的列表应该GCed在快速排序之前，对吧？并且该列表没有任何参考，对吗？

在快速排序之前，只有一个原始的主要列表l，对吗？

为什么它仍然给出Out_of_memory错误？

4

2 回答 2

2

我认为问题在于您使用的列表非常大。垃圾收集器保留两个不同的堆来管理内存：

  • 小型/短寿命对象的小堆。
  • 存放持久对象的主要堆。

次要堆被定期清除，如果一个对象存活的时间足够长，它就会被提升到主要堆。

然而，真正的大对象直接进入主堆。问题是主要堆需要停止世界，即停止应用程序。因此，主要堆收集分几个步骤完成，以确保应用程序不会长时间停止，并且也不会像次要堆收集那样频繁。

也许在您的情况下，当您开始快速排序时仍未收集 merge_sort 列表，因此所有 3 个列表同时存在于内存中。

你可以要求 GC 做一个完整的主要收集，看看它是否能解决问题：

let _ = 
  let l = Random_list.create 10000000 in

  let len1 = List.length (Mergesort.sort_list l) in
  Printf.printf "mergesort done for %d elements" len1;

  Gc.full_major ();

  let len2 = List.length (Quicksort.sort_list l) in
  Printf.printf "quicksort done for %d elements" len2
于 2013-07-18T17:16:38.967 回答
2

不看代码很难下结论，但可能是在第一个程序中，堆栈帧中存在指向Mergesort.sort_list l和Quicksort.sort_list l的指针，从而阻止了第一个列表被垃圾收集，而在第二种情况下，堆栈帧被释放两个let _ = ...？

于 2013-07-19T19:43:03.633 回答