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. 13 3816
On 21 Apr 2006 17:45:03 -0700, "Mingnan G." <le*******@yaho o.com.cn>
wrote: 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!
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." <le*******@yaho o.com.cn> wrote in message
news:11******** **************@ j33g2000cwa.goo glegroups.com.. . 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.programmin g.threads into the
discussion...
* ----------------
"David Hopwood" <da************ ******@blueyond er.co.uk> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com... [posting via Google because of news server problems -- sorry if this is a duplicate]
Chris Thomasson wrote: Sergey P. Derevyago wrote: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".
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.
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.
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 synchronization s...
- 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?
>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.
"Mingnan G." <le*******@yaho o.com.cn> wrote in message
news:11******** **************@ z34g2000cwc.goo glegroups.com.. . 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.
You have to use smart pointers to keep a "specific object alive"? What kind
of "per-object overhead" are we talking about here? How does a mutator
thread use the smart pointer to interact with your collectors "scavenging "
operations?
FWIW, this was one of the reasons why proxy gc was created, mutator threads
can use raw pointers and dependant load-ordering to access shared
data-structures; no per-object smart-pointer logic needed. As you probably
know, dependant load-ordering is supported on every existing arch, except
DEC alpha; it happens to require a rmb(). On Linux this type of "special"
barrier is expressed as read_barrier_de pends(); its a no-op on everything
but alpha.
As I stated in an earlier post, your mutator threads do not need to track
each object individually. You can convert your per-object smart pointers,
into per-epoch smart pointers and follow a simple RCU pattern: http://www.rdrop.com/users/paulmck/RCU/
enter_non_quies cent();
// access shared data-structures
leave_non_quies cent();
This could be expressed in C++ as:
{
gc::scoped_non_ quiescent collected_scope ;
// access shared data-structures
}
The overhead behind enter_non_quies cent() can be as simple as a normal load,
and leave_non_quies cent() can be as simple as a normal store. No atomic ops
and no #StoreLoad or #LoadStore memory barriers required. No kidding.
"Mingnan G." <le*******@yaho o.com.cn> wrote in message
news:11******** **************@ z34g2000cwc.goo glegroups.com.. . 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.
Do your smart pointers have an atomic CAS or XCHG operation? I mean, can I
do something like this pseudo-code:
static your_strongptr< Foo > p_Foo = your_new( Foo ... );
{
your_weakptr< Foo > c_Foo, x_Foo = your_new( Foo ... );
do {
c_Foo = p_Foo;
if ( c_Foo ) {
x_Foo->LocalModify( c_Foo );
}
} while ( p_Foo.cas( c_Foo, x_Foo ) );
if ( c_Foo ) {
c_Foo->ProcessExchang edWith( x_Foo );
}
}
Can I do 100% lock-free programming with your smart pointers?
I am glad to see your kindly messages and suggestions, thanks very
much.
I am still carefully reading your posts and links. Followings are
questions I know to answer. What sort of transactions occur between your collector and its mutators during a "scavenge" operation?
During a "scavenge" operation, the system uses multi-threading
synchronization mechanism between collector and mutators. There is some
overhead. However, since most objects are acyclic, scavenge operation
need not run as frequently as prior-art garbage collector. I recommend
tracing garbage collection runs with higher priority than normal
application threads, but lower than real-time threads. So that,
expensive tracing GC can finished sooner, and real-time threads are not
affected.
Do your mutators have any #StoreLoad dependencies during a scavenge operation? I take it that the collector can indeed interrupt mutators during scavenges, correct?
Mutators have #StoreLoad dependencies during a scavenge operation. The
collector can interrupt any application threads at any place, and start
a tracing collection without delay.
Do your smart pointers have an atomic CAS or XCHG operation?
Yes, but not always. During the "scavenge" operation, there is some
complicate synchronization overhead. These synchronization will use
atomic CAS or XCHG.
your_weakptr< Foo > c_Foo, x_Foo = your_new( Foo ... );
In this system, your_weakptr< Foo > will not keep the newly created Foo
object alive. Therefore, when the execution of this statement is
finished, the newly created object is reclaimed immediately. That maybe
not you wanted.
Mingnan G.
> Can I do 100% lock-free programming with your smart pointers?
Maybe, I am studying those links you posted. The problem is that I want
to provide strict deterministic finalization, all acyclic garbage
objects are reclaimed in a predictable ordering. I am not sure
per-epoch smart pointers may work.
"Mingnan G." <le*******@yaho o.com.cn> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com... I am glad to see your kindly messages and suggestions, thanks very much.
I am still carefully reading your posts and links. Followings are questions I know to answer.
What sort of transactions occur between your collector and its mutators during a "scavenge" operation? During a "scavenge" operation, the system uses multi-threading synchronization mechanism between collector and mutators. There is some overhead. However, since most objects are acyclic, scavenge operation need not run as frequently as prior-art garbage collector. I recommend tracing garbage collection runs with higher priority than normal application threads, but lower than real-time threads. So that, expensive tracing GC can finished sooner, and real-time threads are not affected.
Do your mutators have any #StoreLoad dependencies during a scavenge operation? I take it that the collector can indeed interrupt mutators during scavenges, correct? Mutators have #StoreLoad dependencies during a scavenge operation. The collector can interrupt any application threads at any place, and start a tracing collection without delay.
Do your smart pointers have an atomic CAS or XCHG operation? Yes, but not always. During the "scavenge" operation, there is some complicate synchronization overhead. These synchronization will use atomic CAS or XCHG.
Okay. So you are using atomic operations for the scavenge operations...
Humm... your_weakptr< Foo > c_Foo, x_Foo = your_new( Foo ... ); In this system, your_weakptr< Foo > will not keep the newly created Foo object alive. Therefore, when the execution of this statement is finished, the newly created object is reclaimed immediately. That maybe not you wanted.
Your correct. I wanted the newly created Foo object (x_Foo) to be CAS'd into
the global "smart-pointer" (p_Foo), therefore keeping it alive. The "old"
object (c_Foo) is the one that can be garbage collected. Humm, I wonder if I
can do atomic lock-free COW or PCOW based algorithms with your setup...
Humm... How about this:
static your_strongptr< Foo > p_Foo = your_new( Foo ... );
{
your_strongptr< Foo > c_Foo, x_Foo = your_new( Foo ... );
do {
c_Foo = p_Foo;
if ( c_Foo ) {
x_Foo->LocalModify( c_Foo );
}
} while ( p_Foo.cas( c_Foo, x_Foo ) );
if ( c_Foo ) {
c_Foo->ProcessExchang edWith( x_Foo );
}
}
Now there is no weak pointers, could this work in your setup?
"Mingnan G." <le*******@yaho o.com.cn> wrote in message
news:11******** **************@ j33g2000cwa.goo glegroups.com.. . Can I do 100% lock-free programming with your smart pointers? Maybe, I am studying those links you posted. The problem is that I want to provide strict deterministic finalization, all acyclic garbage objects are reclaimed in a predictable ordering. I am not sure per-epoch smart pointers may work.
Well, one of the good things about per-epoch smart pointers is that they are
very friendly to large shared linked data-structures. Reader threads can
walk through a such a data-structure by using normal raw pointers, and
normal loads and stores to access the structures nodes:
{
gc::scoped_non_ quiescent collected_scope ;
node_t *nx, *n = collection::hea d;
while ( n ) {
nx = n->nx;
whatever( n );
n = nx;
}
}
When you are using per-object smart pointers, reader threads have to access
the smart pointer logic every time they access a node. The larger the linked
data-structure, the more overheadgets; negative scalability:
{
your_strongptr< node_t > nx, n = collection::hea d;
while ( n ) {
nx = n->nx;
whatever( n );
n = nx;
}
}
This is a simple example of why per-object stuff can be "very" expensive... This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Bob |
last post by:
Are there any known applications out there used to test the performance of the .NET garbage collector over a long period of time? Basically I need an application that creates objects, uses them, and then throws them away and then monitors the garbage collection and store statistics on it, preferably in C#. I want to know what is the longest period of time that an application may lock up while garbage collection is processing. Thanks!
|
by: pachanga |
last post by:
The Hans-Boehm garbage collector can be successfully used with C and
C++, but not yet a standard for C++.. Is there talks about Garbage
Collector to become in the C++ standard?
|
by: Ben |
last post by:
Could someone please verify if what I am doing as follow is corrected:
1. when dealing with custom class objects:
.....
public myObject as myClass
myObject as New myClass
.......here I am going to fill up myObject with info....tons of them
myObject = nothing
System.GC.Collect()
|
by: lelandguo |
last post by:
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
|
by: Goalie_Ca |
last post by:
I have been reading (or at least googling) about the potential addition
of optional garbage collection to C++0x. There are numerous myths and
whatnot with very little detailed information.
Will this work be library based or language based and will it be based
on that of managed C++? Then of course there are the finer technical
questions raised (especially due to pointer abuse). Is a GC for C++
just a pipe dream or is there a lot of work...
| |
by: jacob navia |
last post by:
Abstract
--------
Garbage collection is a method of managing memory by using a "collector"
library. Periodically, or triggered by an allocation request, the
collector looks for unused memory chunks and recycles them.
This memory allocation strategy has been adapted to C (and C++) by the
library written by Hans J Boehm and Alan J Demers.
Why a Garbage Collector?
-----------------------
|
by: Paul.Lee.1971 |
last post by:
Hi everyone,
A program that I'm helping to code seems to slow down drastically
during initialisation, and looking at the profiling graph, it seems to
be the garbage collector thats slowing things down. I must point out
that a heck of a lot of data are being read in and manipulated, and I
was wondering if there were any metrics to show much of a performance
hit is occurring during the initialisation? If it turns out that the
GC is having a...
|
by: Johnny E. Jensen |
last post by:
Hellow
I'am not sure what to think about the Garbage Collector.
I have a Class OutlookObject, It have two private variables.
Private Microsoft.Office.Interop.Outlook.Application _Application = null;
Private Microsoft.Office.Interop.Outlook.NameSpace _Namespace = null;
The Constructor:
public OutlookObject()
|
by: Carlo Milanesi |
last post by:
Hello,
traditionally, in C++, dynamically allocated memory has been
managed explicitly by calling "delete" in the application code.
Now, in addition to the standard library strings, containers, and
auto_ptrs, gurus suggest that may be better to use a reference-counted
smart pointer, or a garbage-collector.
But in which cases it is better to use one technique and in which cases
another? IOW, which is the design criterion?
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |