> In the typeinfo for every type there should be a function,    bool ScanObjectForPointer(void* object, void* p);   which could be used by the GC to scan blocks;  obviously it'd not be recursive thru pointers so we would also need   struct OPI { void* objptr; TypeInfo* type } OPI[] GetNonNullPointersFromObject(void* object);    .. both functions would use the typeinfo size to determine the extent to scan.  Probably need something to scan arrays of objects as well..
>
> If the compiler provided a framework like this, a non-conservative GC could be built off of it.
>
> At very least some tables would have to be emitted with typeinfo* and offset and size for the members relevant to the GC.

I'd go for a very simple variant. You only need to know where pointers
are, so a normal ~0-terminated array of offsets relative to the struct/class
beginning (for structs and classes only, obviously) should suffice. All pointers
not inside structs/classes are roots by definition, which the compiler obviously
also needs to tell the GC about.

-fg

Walter wrote:
> "Patrick Down" <Patrick_member@pathlink.com> wrote in message
> news:bdf2j3$1rui$1@digitaldaemon.com...
> 
>>The GC does need information from the compiler about data types.
>>Some benafit can be gained from marking or allocating on a
>>separate heap data types that don't have any internal pointers
>>so that they don't need to be scanned.  Boehm has GC_malloc_atomic
>>for this purpose.
> 
> 
> Yes, that can help.
> 
> 
>>Any plugable GC architecture should contain information about the
>>types being allocated.

I know that many people are not big fans of reference counting collectors, but if we're implementing a generic GC interface, then we should include reference/dereference handlers so that refcounters could work.

Or, it occurs to me, you could just have a callback to tell refcounters that "object has changed one or more times."  The refcounter could do lazy refcounting that way.  That callback would be useful as a software write barrier for copying collectors, too....

Of course, any such callback should be inlined (if at all possible); thus, GCs that don't need the callback will simply implement a no-op stub that will vanish when it is inlined.

Russ

> I know that many people are not big fans of reference counting collectors, but if we're implementing a generic GC interface, then we should include reference/dereference handlers so that refcounters could work.

Refcounting cannot even work in the presence of data structures with cyclical references, which includes very basic things like double-linked lists and trees where nodes have pointers to their parents. Making ref-counting work in that case requires either a complete redesign of the datastructures or so-called "weak references", i.e. references that don't "own" the object they're referencing.

This can silently break existing code in a myriad of ways, and it's especially bad because it won't cause any suspicious behavior, it'll just cause memory leaks to pile. As the whole idea was to make memory management *easier* and not more involved and error-prone, I really don't think it's worth it.

-fg

Fabian Giesen wrote:
> 
> > I know that many people are not big fans of reference counting collectors, but if we're implementing a generic GC interface, then we should include reference/dereference handlers so that refcounters could work.
> 
> Refcounting cannot even work in the presence of data structures with cyclical references, which includes very basic things like double-linked lists and trees where nodes have pointers to their parents. Making ref-counting work in that case requires either a complete redesign of the datastructures or so-called "weak references", i.e. references that don't "own" the object they're referencing.
> 
> This can silently break existing code in a myriad of ways, and it's especially bad because it won't cause any suspicious behavior, it'll just cause memory leaks to pile. As the whole idea was to make memory management *easier* and not more involved and error-prone, I really don't think it's worth it.

I always wondered why these approaches are not combined.

Use refcounts, refcount=0 means free (90-95% of all objects) For all others do your chosen GC algorithm.

--
Helmut Leitner    leitner@hls.via.at Graz, Austria   www.hls-software.com

> I always wondered why these approaches are not combined.
>
> Use refcounts, refcount=0 means free (90-95% of all objects) For all others do your chosen GC algorithm.

Because reference counting is quite expensive in terms of CPU time (yes, I know, it's counterintuitive).

-fg

Fabian Giesen wrote:
> 
> > I always wondered why these approaches are not combined.
> >
> > Use refcounts, refcount=0 means free (90-95% of all objects) For all others do your chosen GC algorithm.
> 
> Because reference counting is quite expensive in terms of CPU time (yes, I know, it's counterintuitive).

I know. But in optimization you must often try things that are counterintuitive.

One good paper that was cited (and Walters gc2) use size classes 2^N which give at least 50% memory size overhead. Nobody talks about this. But with this amount of memory you can try a lot of promising algorithms.

-- 
Helmut Leitner    leitner@hls.via.at
Graz, Austria   www.hls-software.com

>> Because reference counting is quite expensive in terms of CPU time (yes, I know, it's counterintuitive).
>
> I know. But in optimization you must often try things that are counterintuitive.

Yeah, but I absolutely don't see how any garbage collector could profit from the reference counts. You are right in the observation that most objects do have a very short lifetime, but you don't need reference counting to know that. And a GC doesn't even touch the dead objects (that is, the ones with refcount 0) - it won't even find them for the precise reason that all references to them are dead :)

I really don't see any way how the reference counts could be useful to a collector. Maybe you could explain your idea?

> One good paper that was cited (and Walters gc2) use size classes 2^N which give at least 50% memory size overhead. Nobody talks about this. But with this amount of memory you can try a lot of promising algorithms.

...on the cost of 50% additional memory overhead. Which pretty much
rules them out of you ask me. We're talking memory management here,
not memory wasting. As long as 50% of additional memory requirement
is no issue because memory usage is low, there's little reason to
worry about GC performance anyway. And for programs that are memory
intensive, ANYTHING you can gain in the allocator will be easily
dwarfed by the cost incurred by negative cache effects and, even worse,
virtual memory - 50% more memory usage will make swapping both start
earlier and have more to do. And anyone who has ever been in that
situation knows that paging, once it begins, can easily slow down a
program by an order of magnitude.

Don't get me wrong, I'm certainly in for new ideas, but I will easily drop them if I think their cost is too high or not well-spent :)

-fg

Fabian Giesen wrote:
> 
> >> Because reference counting is quite expensive in terms of CPU time (yes, I know, it's counterintuitive).
> >
> > I know. But in optimization you must often try things that are counterintuitive.
> 
> Yeah, but I absolutely don't see how any garbage collector could profit from the reference counts. You are right in the observation that most objects do have a very short lifetime, but you don't need reference counting to know that. And a GC doesn't even touch the dead objects (that is, the ones with refcount 0) - it won't even find them for the precise reason that all references to them are dead :)
> 
> I really don't see any way how the reference counts could be useful to a collector. Maybe you could explain your idea?
> 
> > One good paper that was cited (and Walters gc2) use size classes 2^N which give at least 50% memory size overhead. Nobody talks about this. But with this amount of memory you can try a lot of promising algorithms.
> 
> ...on the cost of 50% additional memory overhead. Which pretty much
> rules them out of you ask me. We're talking memory management here,
> not memory wasting. As long as 50% of additional memory requirement
> is no issue because memory usage is low, there's little reason to
> worry about GC performance anyway. And for programs that are memory
> intensive, ANYTHING you can gain in the allocator will be easily
> dwarfed by the cost incurred by negative cache effects and, even worse,
> virtual memory - 50% more memory usage will make swapping both start
> earlier and have more to do. And anyone who has ever been in that
> situation knows that paging, once it begins, can easily slow down a
> program by an order of magnitude.
> 
> Don't get me wrong, I'm certainly in for new ideas, but I will easily drop them if I think their cost is too high or not well-spent :)

Currently I need my brain for the ICFP contest, but I'd like to comment on that in a few days. It's inevitable because I started that Wiki page.

One shouldn't rule out things too early. Only few people are aware that malloc/free typically has a 12-20 byte overhead per allocation. And we don't yet talk about fragmentation.

Anyway I don't think that "state of the art GC" whatever that may be is good enough for D. If D is to replace C (and I hope it will, I'll put some trust and work into it) then it must have an absolutely flawless memory management system. That's the winning point - not some fancy syntax or OO feature.

Any small linear overhead on allocation or deallocation is no problem. But a 10 sec collection pause is.

I would even say, that memory mangement is so important, that all other features must be constructed around it to support its efficiency.

But, as I said, let's discuss this a bit later.

--
Helmut Leitner    leitner@hls.via.at Graz, Austria   www.hls-software.com

> Any small linear overhead on allocation or deallocation is no problem. But a 10 sec collection pause is.

As I said before, there are collectors that can satisfy hard realtime requirements.

-fg

Fabian Giesen wrote:
> 
> > Any small linear overhead on allocation or deallocation is no problem. But a 10 sec collection pause is.
> 
> As I said before, there are collectors that can satisfy hard realtime requirements.

I think I read the link you mentioned. But did you also read that it has an 4-6 (worst case 10) factor between "live object" data and maximum heap size?

That is: when a program at a point has 2 MB of objects it may need at the same time 20MB (ok typical 10 MB) heap to do this real time?

-- 
Helmut Leitner    leitner@hls.via.at
Graz, Austria   www.hls-software.com