他们说，压缩垃圾收集器比传统的内存管理更快，因为它们只需要收集活动对象，并通过重新排列它们在内存中，以便一切都在一个连续的块，你最终没有堆碎片。但是，怎么可能迅速完成？这在我看来，这是相当于装箱问题，这是 NP难并不能在时间上我们对计算的认识在当前范围内的一个大型数据集的合理费用完成。我在想什么？

They say that compacting garbage collectors are faster than traditional memory management because they only have to collect live objects, and by rearranging them in memory so everything's in one contiguous block, you end up with no heap fragmentation. But how can that be done quickly? It seems to me that that's equivalent to the bin-packing problem, which is NP-hard and can't be completed in a reasonable amount of time on a large dataset within the current limits of our knowledge about computation. What am I missing?

推荐答案

压实意味着将在内存中对象，使某些对象被删除（死者的对象，该GC应该收回），和所有其余的对象，成为连续的RAM

Compaction means moving objects in RAM so that some objects are removed (the dead objects, that the GC is supposed to reclaim) and all remaining objects become contiguous in RAM.

一大部分的单的，连续的从操作系统获取区域内的压缩GC工作，通过分配对象。压实然后等方法去除死对象，然后推动所有剩余活动对象向左，挤掉孔。如果GC的工作原理是压实，然后分配是简单地向上移动指针的分配的区域端的问题。合成，分配区域之内，有一个指针，使得该自由区域由该指针后的字节。分配空间为对象，指针简单地由新的对象大小向上移动。偶尔，在GC判定其是时间运行，检测死对象，挤压孔出来，因此降低了分配指针。

Most compacting GC work by allocating objects within a single, contiguous area obtained from the operating system. Compaction is then like removing the dead objects, and then pushing all remaining live objects "to the left", squeezing out the holes. If the GC works by compaction, then allocation is simply a matter of moving up the "end of allocated area" pointer. Synthetically, within the allocation area, there is a pointer such that the free area consists of the bytes after that pointer. To allocate space for an object, the pointer is simply moved up by the new object size. Occasionally, the GC decides that it is time to run, detects the dead object, squeezes the holes out, and thus lowers the allocation pointer.

这是一个压缩GC的性能提升来自几个方面：

The performance gains from a compacting GC come from several sources:

对于分配，有没有需要找到一个合适的洞：由建设，剩余空间，在任何时候，一个单一的，大面积，它足以只需动指针向上。 在没有碎裂。压实将所有活动的对象在一起，但可以的被看作是将所有孔的连成一个大的自由空间 在局部性的改善。通过将活动对象为邻近地区，关于高速缓存的行为得到改善。特别是，压实算法倾向于保持对象在其各自的分配顺序（对象滑动但不交换）已经被报道为大多数应用启发式良好。 For allocation, there is no need to find a suitable "hole": by construction, free space is, at all times, a single, big area, and it suffices to just move a pointer up. There is no fragmentation: the compaction moves all live objects together, but this can be seen as moving all holes together into a single big free space. Locality is improved. By moving live objects into adjacent areas, behaviour with regards to cache memory is improved. In particular, compaction algorithms tend to keep objects in their respective allocation order (objects are slided but not swapped) which has been reported to be heuristically good for most applications.

如果的操作系统拒绝给一个分配领域，而不是产生若干块，然后事情就变得更加复杂了一下，可能开始看起来像装箱问题，因为压实GC则必须决定在哪个块进入每个活动对象。然而，装箱的复杂性就是找到在一般情况下，完美的比赛;近似​​的解决方案已经是一个内存分配就好了。

If the operating system refuses to give a single allocation area, instead yielding several blocks, then things become a bit more complex, and could begin to look like the bin-packing problem, because the compacting GC then has to decide in which block goes each live object. However, the complexity of bin-packing is about finding the "perfect" match in the general case; an approximate solution is already good enough for a memory allocator.

在一个压缩算法，算法的难度有关更新所有的指针，以便它们指向新的目标位置。通过严格的类型，在.NET虚拟机可以明确地决定在RAM中的每个单词是否是一个指针或没有，但有效地更新所有的指针，而无需使用太多额外的内存可能会非常棘手。 H.B.M. Jonkers描述了一个奇妙的智能算法，在快速垃圾压实算法（信息处理快报，第9卷，第1号，1979年，页26-30）。我无法找到该文件的浩瀚的互联网上的一个副本，但该算法在垃圾回收描述书琼斯和林斯（第5.6节）。我热烈推荐这本书的人谁是兴趣了解的垃圾收集器。 Jonkers算法需要在活动对象两个线性通行证，原来是容易实现的（几十行的code，没有更多的，最困难的部分是理解为什么它的工作原理）。

The algorithmic difficulty in a compaction algorithm is about updating all pointers, so that they point to the new object location. Through strict typing, the .NET virtual machine can unambiguously decide whether each word in RAM is a pointer or not, but updating all pointers efficiently without using too much extra RAM can be tricky. H.B.M. Jonkers has described a wonderfully smart algorithm for that, in "A Fast Garbage Compaction Algorithm" (Information Processing Letters, Volume 9, Number 1, 1979, pp. 26-30). I could not find a copy of that paper on the Vast Internet, but the algorithm is described in the "Garbage Collection" book by Jones and Lins (section 5.6). I warmly recommend that book to anyone who is interested in understanding garbage collectors. Jonkers' algorithm requires two linear passes on the live objects and turns out to be easy to implement (a few dozen lines of code, no more; the most difficult part is understanding why it works).

附加复杂性来自的代收藏家的这些尝试，大部分的时间，留下大部分对象不变，工作preferentially只有年轻的对象。这里，这意味着压实堆的唯一的结束;充分压实被应用很少。这里的要点是，一个完整的压实，虽然直链的，仍然可以诱导明显的暂停。代GC试图使这种暂停罕见。有一次，琼斯和林斯的书是必读的。

Additional complexity comes from generational collectors which try, most of the time, to leave most of the objects untouched, working preferentially with young objects only. Here, this means compacting only the end of the heap; full compaction being applied only rarely. The point here is that a full compaction, although linear, could still induce a noticeable pause. Generational GC tries to make such pauses rarer. There again, Jones' and Lins' book is a must-read.