C ++的垃圾收集器 [英] A garbage collector for C++
问题描述
大家好。
我为标准C ++应用程序编写了一个垃圾收集器。主要功能有
。
1）确定性终结
提供确定性终结，系统可以管理资源
以及对象。编程风格清晰简单，符合C ++程序员的RAII（资源获取初始化）习惯用法./ b $ b程序员。内存使用非常有效，非循环垃圾是在删除最后一次引用时回收的
。一个精心设计的
应用程序，它消除了循环数据结构，不需要昂贵的垃圾收集，并且总是以最小的内存运行
使用。
2）C ++的精确GC
它是一个完全准确的跟踪垃圾收集器。所有垃圾对象
都由系统识别，没有保守的堆栈帧猜测。
完全C ++优化编译器支持。
3 ）没有暂停（小于1us）
在这个系统中，所有应用程序代码自动完全可以中断和GC-Safe
。因此，清除可以从任何地方开始
而没有会合要求。一个特殊的并发跟踪垃圾
收集器成功地避开了根集扫描，并且根本不会导致任何线程暂停。在最糟糕的赛车情况下，延迟
小于1微秒（而不是毫秒）。对于实时系统，它非常满意
。
4）小开销
应用程序线程的运行时成本很高不到正常
引用计数。如果没有同时运行的清理
操作，则没有写入屏障开销，没有强大的内存排序
要求，没有同步开销。为GC安全点注入没有额外的代码或
数据结构。整个系统并不需要强大的内存排序，它适用于大多数现代的处理器架构。多处理器并发可以通过mutator和collector的多线程属性进一步利用
。
5）兼容对象模型
与传统的C ++一样，系统支持多继承，
对象作为成员变量和对象数组。支持C ++原始指针，
原生对象和追踪。
6）广泛的便携式
即使进行准确的追踪，系统也不需要任何
来自编译器的特殊信息。应用程序可以使用任何标准的C ++
编译器，例如Visual C ++ 8和GCC。没有特殊的平台
要求，例如Win32系统调用：SuspendThread，GetWriteWatch，
移植到更广泛的区域。
有没有人对这个系统感兴趣？欢迎任何评论！
Mingnan G.
Hello everyone.
I have written a garbage collector for standard C++ application. It has
following main features.
1) Deterministic Finalization
Providing deterministic finalization, the system can manage resources
as well as objects. The programming style is clear and easy, conforming
to RAII (Resource Acquisition Is Initialization) idiom of C++
programmers. The memory usage is very efficient, acyclic garbage is
reclaimed when the last reference to it is removed. A well-designed
application, which eliminates cyclic data structure, does not need
expensive garbage collection and is always running with minimum memory
usage.
2) Accurate GC for C++
It is a fully accurate tracing garbage collector. All garbage objects
are identified by the system, no conservative stack frame guessing.
Fully C++ optimization compiler support.
3) No Pause (less than 1us)
In this system, all application codes automatically become fully
interruptible and GC-Safe. Therefore, scavenge can start at any place
without rendezvous requirement. A special concurrent tracing garbage
collector successfully evades root-set scanning, and does not cause
suspension of any thread at all. In the worst racing case, the latency
is less than one microsecond (not millisecond). It is very satisfied
for real-time systems.
4) Small Overhead
The runtime cost of application threads is far less than a normal
reference counting. If there is no concurrently running scavenging
action, there is no write-barrier overhead, no strong memory ordering
requirement, no synchronization overhead. There is no extra code or
data structure injected for GC safe point. The whole system does not
require strong memory ordering, it is suitable for most modern
processor architecture. Multi-processor concurrency can be further
exploited by the multi-threading property of mutator and collector.
5) Compatible Object Model
As well as conventional C++, the system supports multiple-inheritance,
object as member variables, and object arrays. Support C++ raw pointer,
unions, bit-fields and hidden pointers. Support C++ templates. Support
native object and tracing.
6) Widely Portable
Even conducting an accurate tracing, the system does not require any
special information from compiler. Application can use any standard C++
compiler, such as Visual C++ 8 and GCC. There is no special platform
requirement, such as Win32 system call: SuspendThread, GetWriteWatch,
etc. Even virtual memory support is not necessary. Thus, it can be
ported to a wider area.
Does anyone have any interest in this system? Any comments are welcome!
Mingnan G.
推荐答案
2006年4月21日17 ：45：03-0700，Mingnan G. < le ******* @ yahoo.com.cn>
写道：
On 21 Apr 2006 17:45:03 -0700, "Mingnan G." <le*******@yahoo.com.cn>
wrote:
大家好。
我为标准C ++应用程序编写了一个垃圾收集器。它具有以下主要功能。
1）确定性终结
提供确定性的最终化，系统可以管理资源和对象。编程风格清晰简单，符合C ++程序员的RAII（资源获取初始化）习惯。内存使用非常有效，当删除最后一次引用时，回收非循环垃圾。
这可能意味着某种重新计算的智能指针。使用
真实指针和新编辑的对象你很难得到RAII ??
有没有人对这个系统感兴趣？欢迎提出任何意见！
Hello everyone.
I have written a garbage collector for standard C++ application. It has
following main features.
1) Deterministic Finalization
Providing deterministic finalization, the system can manage resources
as well as objects. The programming style is clear and easy, conforming
to RAII (Resource Acquisition Is Initialization) idiom of C++
programmers. The memory usage is very efficient, acyclic garbage is
reclaimed when the last reference to it is removed.
This probably means some kind of ref-counted "smart" pointer. With
real pointers and new-ed objects you can hardly get RAII??
Does anyone have any interest in this system? Any comments are welcome!
除非您想将GC作为商业产品出售，否则您只需发布下载和文档链接即可获得
。
祝你好运，
Roland Pibinger
Unless you want to sell your GC as a commercial product you could just
post links to download and documentation.
Best regards,
Roland Pibinger
" Mingnan G." <乐******* @ yahoo.com.cn>在消息中写道
news：11 ********************** @ j33g2000cwa.googlegr oups.com ...
"Mingnan G." <le*******@yahoo.com.cn> wrote in message
news:11**********************@j33g2000cwa.googlegr oups.com...
大家好。
我为标准C ++应用程序编写了一个垃圾收集器。它具有以下主要功能。
[...]
4）小开销
应用程序线程的运行时成本远低于正常的参考值数数。
通过使用名为proxy的东西，我发布了一些东西，通过使用代理这个东西，将引用计数的成本分摊到
几乎为零。垃圾
集合。不幸的是，我似乎无法在Google上找到确切的消息，
因此我将我的*副本附加到此消息的末尾...
如果没有同时运行的清理动作，则没有写入屏障开销，没有强大的内存排序要求，没有同步开销。
收集者与其变异者之间发生了什么样的交易
在清除期间操作？在清除操作期间，您的mutators是否有任何#StoreLoad
依赖项？我认为收藏家可以在扫描期间确实中断变异器，对吗？
没有为GC注入额外的代码或
数据结构安全点。整个系统不需要强大的内存排序，它适用于大多数现代处理器架构。可以通过mutator和collector的多线程属性进一步利用多处理器并发性。
我猜，但从这一点来看，听起来你的设计允许加载
传递商店（例如，＃LoadStore依赖）对吗？如果是这样，你的东西如何与以下方案不同：
http://citeseer.ist.psu.edu/domani00implementing.html
http://groups.google.com/group/comp....60411bcd?hl = en
[...]
欢迎任何评论！
FWIW，我使用了一个更轻松的同步模式版本我简单说明了这里描述的
：
http://groups.google.com/group/comp .... afb8e0a3？hl = en
对于我在此简要介绍的代理gc：
http://groups.google.com/group/comp....684aa070964e6a
如您所见，周期性/偶发性同步使用模式
在连续的时期内分摊内存障碍的成本。这个
允许mutators进行无同步的本地引用计数
调整;不需要原子操作或内存屏障。同样的
用于收集器< - > mutator通信。因此，一个mutator可以通过这样做来实际调整引用计数：
++ this_mutator-> refs [whatever];
Both VZOOM和Joe Seighs RCU-SMR可以通过以下方式实现：
可以解析操作系统提供的静态状态
信息......除了，因为我之前说过，我发明的东西可以基于我创建的更轻松的同步模式来获得
。
BTW，谈到发明，如果你认为你有一些真正新奇的东西，
并且让你与现有技术区别开来，我建议你考虑做一个
的专利可行性研究，并且可能会考虑专利申请
流程。我建议您阅读以下主题：
http://groups.google.com/group/comp....9072fea09fb64e
：O
我还建议您将comp.programming.threads包含在
讨论中......
* ----------------
"大卫霍普伍德 <哒****************** @ blueyonder.co.uk>在消息中写道
新闻：11 ********************* @ i39g2000cwa.googlegro ups.com ... [通过Google发帖，因为新闻服务器问题 - 对不起，如果这是重复的那样]
Chris Thomasson写道：
Hello everyone.
I have written a garbage collector for standard C++ application. It has
following main features.
[...]
4) Small Overhead
The runtime cost of application threads is far less than a normal
reference counting.
I posted something on amortizing the cost of reference counting down to
virtually zero by using by using something called "proxy" garbage
collection. Unfortunately, I can''t seem to find the exact message on Google,
so I appended my *copy to the end of this message...
If there is no concurrently running scavenging
action, there is no write-barrier overhead, no strong memory ordering
requirement, no synchronization overhead.
What sort of transactions occur between your collector and its mutators
during a "scavenge" operation? Do your mutators have any #StoreLoad
dependencies during a scavenge operation? I take it that the collector can
indeed interrupt mutators during scavenges, correct?
There is no extra code or
data structure injected for GC safe point. The whole system does not
require strong memory ordering, it is suitable for most modern
processor architecture. Multi-processor concurrency can be further
exploited by the multi-threading property of mutator and collector.
I am guessing, but from this, it sounds like your design allows for loads to
pass stores (e.g., #LoadStore dependency ) right? If so, how does your stuff
differ from the following scheme:
http://citeseer.ist.psu.edu/domani00implementing.html
http://groups.google.com/group/comp....60411bcd?hl=en
[...]
Any comments are welcome!
FWIW, I use a more relaxed version of the synchronization pattern I briefly
described here:
http://groups.google.com/group/comp....afb8e0a3?hl=en
For my proxy gc that I briefly introduced here:
http://groups.google.com/group/comp....684aa070964e6a
As you can see, the periodic/episodic synchronization usage pattern
amortizes the cost of memory barriers over successive epochs in time. This
allows mutators to make synchronization-free local reference count
adjustments; no atomic operations or memory barriers are required. The same
goes for collector<->mutator communications. So, a mutator can literally
adjust a reference count by doing this:
++this_mutator->refs[whatever];
Both VZOOM and Joe Seighs RCU-SMR can be implemented in a way that can that
can dissect quiescent-states out of operating system provided
information... Except, as I stated before, the stuff that I invented can be
based on a more relaxed sync pattern I created.
BTW, speaking of inventions, If you think you have something truly novel,
and sets you apart from prior art, I suggest that you think about doing a
patent feasibility study, and possibly going thought the patent application
process. I suggest that you read the following thread:
http://groups.google.com/group/comp....9072fea09fb64e
:O
I would also suggest that you include comp.programming.threads into the
discussion...
* ----------------
"David Hopwood" <da******************@blueyonder.co.uk> wrote in message
news:11*********************@i39g2000cwa.googlegro ups.com... [posting via Google because of news server problems -- sorry if this is
a duplicate]
Chris Thomasson wrote:
Sergey P. Derevyago写道：
Sergey P. Derevyago wrote:
Joe Seigh写道：
>问题是：您可以使用XXX代理GC并将其插入，就像
> Boehm GC一样吗？
不，RCU之类的东西......不能用于存储管理。它们用于在多线程环境中读取/写入问题的无锁解决方案。
所以我说得对：没有GC /没有阻止世界的C ++。
似乎任何GC / C ++都不可能停止
世界。
Joe Seigh wrote:
> The question is: Can you take XXX proxy GC and plug it just like
>Boehm GC?
No, things like RCU, etc... aren''t used for storage management. They''re
used for read lock-free solutions to the reader/writer problem in a
multi-threaded environment.
So I was right: there is no GC/C++ that doesn''t "stop the world".
And it seems like it''s not possible for any GC/C++ not to "stop the
world".
你不需要垃圾收集一切。代理收集可以让应用程序远离传统的GC，以及随之而来的所有开销。
You don''t need to garbage collect everything. Proxy collection can allow
an application to get away from traditional GC, and all of the overhead
that comes along with them.
我总觉得它很奇怪人们谈论GC的开销虽然
虽然其他内存管理技术没有任何管理费用。
你不应该假设GC和其他一些内存混合管理
技术将比将GC应用于所有对象的开销更低。如果
其他技术是某种形式的引用计数（通常是
情况下使用代理GC时），那么它绝对不会; refcounting非常低效。
I always find it odd when people talk about the "overhead of GC" as
though
other memory management techniques had no overheads.
You shouldn''t assume that a hybrid of GC and some other memory
management
technique will have lower overhead than applying GC to all objects. If
the
other technique is some form of reference counting (as is commonly the
case
when using proxy GC), then it definitely won''t; refcounting is very
inefficient.
我同意，无原子锁定引用计数可能非常昂贵。但是，如果您使用
重新计算，那么，当您实施代理收集器时，您可以简单地分摊引用计数的成本。你没有引用计算所有内容，只是收集器结构。 IMO，
使用无锁原子引用计数来保护每个节点的数据结构会产生巨大的开销。但是，正如您可能知道的那样，还有其他一些方法可以分摊计算收集器结构的实际成本。我为我的VZOOM收集器创建了一个直接的
使用模式，该模式基于每个线程
周期性/情节同步...
- 每次访问共享的
数据结构时，您都不需要激活收集器......您可以设置运行时可配置的动态比率
accessses：syncs ...不幸的是，像RCU这样的算法与
这个设置不兼容，因为它只需要任意数量的引用
持续超过静止状态状态。如果您尝试使用RCU执行此操作，您的应用程序将从悬崖上开车
！ IMO，甚至RCU-SMR也不能真正适合这个
账单，因为它并不是真的旨在让用户获得任意数量的引用......
- 另外，我提出的收藏家可以用POSIX实现，并且依赖
加载订购。因此，应用程序可以使用它在许多不同的操作系统和处理器组合上实现无锁读取器
模式。可以
a传统GC与便携式用户空间代理的灵活性竞争
收集器是否解决了无锁算法中的读写器问题？
I agree, atomic lock-free refcounting can be very expensive. However, you
can simply amortize the cost of reference counting, if your using
ref-counting to begin with, when your implementing a proxy collector. You
don''t reference count everything, "just" the collector structures. IMO,
using lock-free atomic reference counting to protect each node of a
data-structure would generate massive overheads. However, as you probably
know, there are other methods that can amortize the cost of actually
reference counting the collector structures. I created a straightforward
usage pattern for my VZOOM collector that is based on per-thread
periodic/episodic synchronizations...
- You don''t need to activate the collector every time you access a shared
data-structure... You can setup a runtime configurable dynamic ratio of
accesses:syncs... Unfortunately, algorithms like RCU are not compatible with
this setup because it simply requires an arbitrary number of references to
persist over quiescent states. Your application will drive right off a cliff
if your try to do this with RCU! IMO, even RCU-SMR can''t really fit this
bill because it was not really designed to allow the user to grab an
arbitrary number of references...
- Also, the collector I came up can be implemented with POSIX and dependant
load-ordering. So, an application can use it to implement lock-free reader
patterns on many different operating systems and processor combinations. Can
a traditional GC compete with the flexibility of a portable user-space proxy
collector wrt solving the reader/writer problem in lock-free algorithms?
>使用真正的指针和新编辑的对象你很难得到RAII？
我不确定我明白你的意思。在这个系统中，C ++ raw
指针被视为Java的弱引用。他们不会保留一个活着的对象。只有智能指针才能使对象保持活着状态。新的
对象的创建类似于C ++ new运算符。例如：
class Foo {...};
CLockedPtr< Foo> p = hgc_new（Foo，（arguments ...））;
系统将在适当的时候调用类Foo的析构函数。当
对象是非循环的时，系统将立即回收。当
对象被循环引用时，系统将通过跟踪
垃圾回收来回收它。程序员不需要关心这些事情，他们只需要将他们的本机资源管理代码放在析构函数中，然后让系统做其他事情。
>With real pointers and new-ed objects you can hardly get RAII??
I am not sure I understand what you mean. In this system, C++ raw
pointers are treated as weak references as Java. They will not retain
an object alive. Only smart pointers will keep an object alive. New
objects are created similar to C++ new operator. For example:
class Foo { ... };
CLockedPtr<Foo> p = hgc_new(Foo, (arguments...));
The system will invoke the destructor of class Foo at proper time. When
the object is acyclic, the system will reclaim immediately. When the
object is circular referenced, the system will reclaim it by tracing
garbage collection. Programmers need not care about these thing, they
should only puts their native-resource management code in destructor
method, and let the system to do the else things.
...您可以发布下载和文档链接。
... you could just post links to download and documentation.
感谢您的好意见。我现在正在这样做。我需要一个地方
来放置我的文档和源代码，我需要一些时间。
Thanks for your kind advice. I am doing that currently. I need a place
to put my documentation and source code, and I need some time.
这篇关于C ++的垃圾收集器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
