在这个关于为什么 substring 在 C# 中采用 O(n) 的流行问题中，提供的主要答案之一认为，如果分配了一个大数组并且通过让新字符串计算的子字符串只引用数组的一小部分，那么垃圾收集器将即使不再引用原始字符串，也无法回收包含较大字符串的字符数组。
这似乎是一个完全有效的答案，但在理论上似乎可以为数组构建一个垃圾收集器，允许对数组的大部分进行垃圾收集，同时留下一些仍在使用的小子数组。换句话说，如果有一个 50,000 元素的数组，其中只有一个小的 100 元素切片仍在使用，垃圾收集器可以将数组分成三部分 - 100 元素切片之前的元素，100 元素切片之前的元素切片本身，以及 100 元素切片之后的元素 - 然后垃圾收集这些片段中的第一个和最后一个。
我的问题是是否有任何语言实现实际上使用这种垃圾收集器，或者它是否仅存在于理论上。有谁知道有这样一个垃圾收集器的语言实现的例子吗？
理论上，是的……这是可能的。但是 GC 有一个问题：要收集垃圾，它需要知道存储在内存中的数据的布局，并且它还必须存储数据以指示内存块是否正在使用……但是布局信息与运行时共享，因为运行时需要知道对象类型（即内存布局）才能进行类型转换。
GC 开始读取它知道的根对象。它获取所有引用并将它们标记为in-use。对于这些被引用的对象中的每一个，它会获取布局并从这些对象中读取更多引用，并将它们标记为正在使用……这个过程继续进行，直到没有更多的引用存在。
注：我使用了类型信息和布局信息，含义相同。
例子：
Imagine we have some object layouts:
====================================
A: { int, object, double, object }
B: { object, object }
C: { int }
Memory Data:
============
Now we need to describe what is in memory.
The following list is composed of memory positions,
and the data contained in each position.
There are 2 kinds of notation I will use:
- Address: ROOT[ list-of-root-references ]
- Address: type-identifier { object-data }
Note that each object can span multiple memory
positions from the first one.
e.g. 90: B { 0, 0 } -- this reads as
"stored at address 90: type-identifier of B followed by raw data { 0, 0 }"
- A reference is represented by a number,
that point to the memory address of the pointed object.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 } There is a self-reference here!
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 } Note that 0 is a null reference!
The GC need to know the layout of each object.
Otherwise it wouldn't be abled to tell
what knid of information is stored in each memory position.
Running the GC:
===============
Garbage collecting steps, to clean the memory described above:
Step 1: Get ROOT references: 2, 3, 9 and mark as 'in-use'
Step 2: Get references from 2, 3 and 9: 3, 6, 7. Note that 0 is a null reference!
Step 3: Get references from 3, 6 and 7: 6, 7, 8, and mark them.
Step 4: Get references from 6, 7, 8, and mark them: only 8!
Step 5: Get references from 8... it has none! We are finished with marking objects.
Step 6: Delete unmarked objects.
This shows what happened in each step with each object stored in the memory.
Step -> 1 2 3 4 5
Memory
20 x
30 x x
40 DELETE
50 DELETE
60 x x
70 x x
80 x x
90 x
我描述的是一个非常基本的 GC 算法。
看看三色标记……真是太棒了！这就是真正的现代 GC 的制作方式。
垃圾收集（计算机科学） - 描述了一些现代 GC 方法。
这个问题很重要，因为它会影响 GC 和运行时。要进行快速类型转换，类型信息必须放在引用附近或分配的内存附近。我们可以考虑将类型信息存储在分配的内存块的目录中，但是......类型转换需要访问目录，就像 new 运算符和 GC 需要删除对象时一样。
如果我们将布局信息存储在引用附近，那么对同一对象的每个引用都会重复相同的信息，以及指针本身。
例子：
To represent the memory data I will introduce the following notation:
- Address: { object-data } -- this time object type is not at the begining!
- A reference is represented by a type-identifier and an address-number,
that point to the memory address of the pointed object,
in the following format: type/number...
e.g. A/20 -- this reads as: "at address 20, there is an object of type A"
Note that: 0/0 is a null reference,
but it still requires space to store the type.
The memory would look like this:
1: ROOT[ B/90, A/20, B/30 ]
20: { 1236, B/30, 0.5, C/60 }
30: { C/60, A/70 }
40: { 1237 }
50: { 1238, A/20, 0.8, A/50 }
60: { 1234 }
70: { 1234, 0/0, 0.7, C/80 }
80: { 1235 }
90: { 0/0, 0/0 }
如果我们将布局信息存储在分配的内存块附近，那就太好了！它速度快，并且避免了重复的布局信息。
例子：
The memory looks like the first sample:
*This is the same notation used at the begining of this answer.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 }
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 }
我们注意到的第一件事是我们不能再将布局信息存储在分配的内存附近。
想象一个具有共享内存的数组：
例子：
I'll introduce a new notation for arrays:
type-identifier < array-length >
1: ROOT[ 20, 31 ] -- pointer 31 is invalid, destination has no type-identifier.
20: INT<5> -- info about layout of the next memory data (spans by 10 memory units)
30: 2
31: 3 -- should have type-identifier, because someone
32: 5 is pointing here!! Invalid memory!!
33: 7
34: 11
我们仍然可以尝试将布局信息放在指针旁边。现在可以使用共享内存数组：
例子：
1: ROOT[ INT<5>/30, INT<2>/31 ]
30: 2
31: 3
32: 5
33: 7
34: 11
请记住，这种方法使我们在各处重复布局信息......但这里的重点是使用更少的内存不是吗？？？但是为了共享内存，我们需要更多的内存来存储布局数据/指针。我们还没有甜甜圈。=(
这是我的答案 - 我认为这是可能的 =>
使用内存分配目录来存储类型信息怎么样？
这可以做到，但是动态转换会受到影响，GC 也会受到影响。记得我告诉过 GC 需要访问内存目录，只是为了删除对象......好吧，现在它每次找到引用时都需要访问目录，而不仅仅是删除。我的天啊！！我们即将用这个来杀死 GC 性能，以及运行时性能。我觉得成本太高了！
<= 这是我的答案
但是......如果运行时不支持动态转换？如果编译器在编译时知道有关类型的所有信息……那么 GC 甚至不存在……它需要有关该类型的信息，因为该信息告诉它该类型使用的内存布局是什么。
也许我完全错了。但我想不出比现在更好的方法了。现代 GC 比这还要复杂……我这里只介绍了基础知识，我认为，现代 GC 正在以其他方式进行优化，也就是其他更可靠的方式。
其他参考：
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
http://www.memorymanagement.org/glossary/t.html
D 语言支持具有这种 GC 行为的数组切片。查看http://www.dsource.org/projects/dcollections/wiki/ArrayArticle#WhosResponsible了解更多信息。
有谁知道有这样一个垃圾收集器的语言实现的例子吗？
不，我认为目前没有任何语言实现这样做。
真正的语言最接近的事情是什么？函数式语言经常用分层树代替平面数组。如此大的字符串由称为绳索的数据结构表示。如果程序从绳索中获取子字符串，则可以收集大部分字符串，而无需复制绳索内仍可访问的所有数据。然而，这样的函数式数据结构比平面数组慢很多。
我们为什么不这样做？可能是因为人们认为这些方法引入了很多复杂性并解决了一个相对不重要的问题（我从来没有遇到过切片保持太多可访问空间的问题）。此外，有使用禁止内部指针的 GC 的传统，因此 GC 无法理解切片。特别是，生产 GC 都将每个对象的元数据放在堆分配内存块开头的标头中。
实际上，我编写了一个 VM ( HLVM )，它通过使用四字引用来避免标头，即元数据是随引用而不是在它指向的对象中携带的。从引用计数研究中，我们知道绝大多数对象的引用计数为 1，因此每个引用标头的潜在重复实际上比您想象的要便宜。缺少标头意味着 HLVM 的数组内部表示是 C 兼容的，因此互操作性更容易和更快。同样，切片可以是对数组中间的引用。然后，合适的 GC 算法（例如标记区域）可以释放堆分配的内存块中不再可访问的部分，并在保留可访问切片的同时重用它们。
另一种解决方案是使用虚拟内存。您可以“伪造”将我的映射逻辑页面复制到同一个物理页面上，GC 可以收集无法访问的页面。然而，这是非常粗粒度的，因此更加利基。
当然，制造“更智能”的垃圾收集器的危险总是以某种方式削弱用户，要么阻止代码工作，要么为过分热心的垃圾收集器提供变通的解决方法。
我认为所有关联数组的实现（PERL、PHP、javascript..）都必须以这种方式完成。您将此称为“垃圾收集”，但这意味着必须首先取消设置（删除、删除）特定项目，以便垃圾收集器知道它们未使用。所以这是正常的删除/删除/取消设置，这肯定不仅反映在关联数组中，而且反映在特定语言实现所使用的数据结构中。否则，内存可能会被几乎空的数组耗尽......