一个用于共享数组子范围的智能垃圾收集器？

Question

在这个流行的问题中,为什么substring在C#中占用O(n),所提出的主要答案之一认为,如果分配了一个大数组,并且通过让新字符串仅引用数组的一小部分来计算子字符串,那么垃圾收集器就会即使原始字符串不再被引用,也无法回收包含较大字符串的字符数组.

这似乎是一个非常有效的答案,但似乎理论上可以为数组构建一个垃圾收集器,允许对大多数数组进行垃圾收集,同时留下一些仍在使用的小型子数组.换句话说,如果有一个5​​0,000个元素的数组,其中只有一个小的100个元素的片仍然在使用,垃圾收集器可以将数组分成三个部分--100个元素切片之前的元素,100个元素切片本身,以及100个元素切片之后的元素 - 然后垃圾收集这些碎片的第一个和最后一个.

我的问题是,任何语言实现是否实际使用这种垃圾收集器,或者它是否仅在理论上存在.有没有人知道一个像这样的垃圾收集器的语言实现的例子？

Answer 1

理论上,是的......这是可能的.但是GC存在一个问题:要收集垃圾,它需要知道存储在内存中的数据的布局,它还必须存储数据以指示是否正在使用内存块......但布局信息与运行时共享,因为运行时需要知道对象类型(即内存布局)才能进行类型转换.

GC如何工作？

GC开始读取它知道的根对象.它获取所有引用并将它们标记为正在使用中.对于每个引用的对象,它获取布局并从这些引用中读取更多引用,并将它们标记为正在使用 ...并且此过程将继续,直到不再有引用为止.

注意:我使用了类型信息和布局信息,含义相同.

例:

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和运行时.要进行快速类型转换,必须将类型信息放在引用附近或分配的内存附近.我们可以考虑将类型信息存储在已分配内存块的目录中,但是......类型转换需要访问目录,就像新操作符和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

http://www.cs.purdue.edu/homes/sbarakat/cs456/gc-2.pdf

三色增量更新GC:是否需要扫描每个堆栈两次？