为什么由于类型弱而在C中实现垃圾收集"不可能"？

一个相当聪明的人告诉我你不能在C中实现垃圾收集,因为它的类型很弱.基本的想法似乎是C给你太多的自由.他提到了没有类型检查的铸造指针......

我并没有真正理解这个想法.有人可以给我一个解释,也可能是一个代码示例,说明为什么这不起作用.

注意:显然C是关于速度的,为什么要添加垃圾收集？我真的很好奇.

他可能提到了这样一个事实,即您可以将指针强制转换为int并返回原始指针类型.当你这样做时,GC几乎不可能正确清理,考虑:

char * p = (char *) malloc(16);
int i = (int) p;
p = 0;
// GC runs and finds that the memory is no longer referenced
p = (char *) i;
// p is now a dangling pointer

编辑:上面只会产生一个带有精确GC的悬空指针.正如其他人所指出的那样,保守的收集器仍然可以正确处理这种情况,因为它假定任何可能是有效指针的位模式实际上都是一个指针,因此不会释放分配的内存.然而,当我进一步修改以使其不再看起来像收集器的有效指针时,这当然不再可能,例如如下:

char * p = (char *) malloc(16);
int i = ~((int) p);
p = 0;
// GC runs and finds that the memory is no longer referenced
p = (char *) ~i;
// p is now a dangling pointer

而且,(正如其他人已经指出的那样)如果你想保留语言的全部功能,那么实现GC的GC是不可能的.如果您不使用上述技巧(即您将自己局限于可能的操作的子集),那么GC确实是可行的.

完全可以在C中实现你能想到的任何内存管理器.问题是你必须专门使用它的分配/释放函数,并将你的"指针魔法"限制在它可以跟踪的事物上.另外,内存管理可能仅限于某些支持的类型.

例如,Objective-C的保留/释放系统和自动释放池基本上是用C实现的内存管理器.许多库也实现了自己的简单形式的内存管理,如引用计数.

然后,有Boehm垃圾收集器.要使用它,只需将您的malloc()/ realloc()呼叫替换为Boehm版本,您就不必free()再次呼叫.了解这种方法可能存在的问题.

另外,请查看此维基百科页面,以快速了解保守垃圾收集器的工作原理.

如果您阅读了正确的论文并且您拥有CS的学士学位,那么为C 实施一个体面的保守垃圾收集器实际上非常容易- 我有十几个学生已经做了大约四周的课堂练习.然后花20年时间改进它,你就得到了Boehm收藏家(libgc).

基本思路很简单:如果寄存器,堆栈,全局变量或实时堆对象中的任何位置都存在位模式,并且该位模式恰好是属于分配的对象内的地址malloc,比那个对象被认为是活的.任何不活动的对象都不可能通过以下指针到达,因此可以回收并用于满足将来的分配请求.这种技术在指针的硬件表示上运行,它完全独立于指针的类型 ---类型在这里是无关紧要的.

确实存在一个警告:保守的垃圾收集技术可以通过故意隐藏指针来欺骗.压缩包含指针的结构,将指针的唯一副本保留在磁盘上,通过XORing对指针进行模糊处理0xdeadbeef,所有这些技术都会破坏保守的收集器.但除非故意这样做,否则这种问题极为罕见.优化编译器的作者通常小心不要隐藏这样的收集器的指针.

你问题中最有趣的部分是为什么这样做.三个原因:

它消除了许多内存管理错误的可能性.

它简化了API,因为不再需要指定谁分配内存,谁拥有分配的内存,是否需要复制内存,以及谁负责释放内存.

信不信由你,它可能比使用malloc和更快free.