Quote: Original post by WitchLord
I need to resolve potential circular references with the introduction of script structures, and I believe a GC is the easiest way to do this. Doing what you said with having the release method search for circular references, seems to be complicated and kind of backwards. I could be wrong, but this is what I feel.

Hmm, why do you feel this way? The algorithm is almost the same in all cases anyway, all you do is walk the graph. Regardless of which method you choose, you might want to look into using boost graph library. Most of the code is already written for you in a generic manner! [smile] I'm not sure how these cases are different, I feel they're almost the same... Also, you don't need to walk the graph on every release call, you can just add objects in question to an internal container for later examination.

Quote: Original post by WitchLord
I'd like to learn more about Python's way of doing it. Do you have an article you recommend?

Here's a good one. It's a bit sparse on the details but it's a start.
Also google scholar is priceless. You'll have to read through a lot of convoluted ideas you can't use but you can pick up a lot of ideas along the way.

Quote: Original post by WitchLord
I'm also slightly worried about multithreading, and how that impacts the garbage collection.

I think you'll run into the same problems with either method. I haven't gone through this yet so I can't really give much useful advice [smile]

Quote: Original post by Trap
A tracing GC that supports multithreading isn't easy to write either. It looks easy at the first sight because an incremental tracing GC always behaves similar to a second thread, but a true multithreaded GC is one of the more difficult things to write.

You're probably right about that. I may end up dumping support for multithreading completely, though I'd prefer not to.

Quote:
@WitchLord:
I certainly won't implement a gc of the same quality as the lisp ones in C++. It is far too much work (probably it is not even possible since the GC depends on compiler support in Lisp). You can't implement refcounting in Lisp.

I didn't say you should. I too think it is too much work. Still my point of comparing algorithm efficiencies in different languages is valid. There are just too many other factors involved that skews the result.

A fully working GC for C has been implemented though, but I can't remember the author's name right now. If I remember correctly it simply assumed all words could be a pointer, and if the potential pointer was pointing to an allocated memory block that memory block wouldn't be freed.

Quote:
Do you know/have a faster refcounting implementation?

I always implement the reference counting myself inside the class, but as you found out the intrusive_ptr is a lot faster.

Quote:
It is obvious to me that a refcounting gc has to be slower at reversing lists, as reversing lists is almost 100% pointer handling and refcounting at least doubles the price of pointer handling.
A good tracing GC has almost zero additional cost to pointer handling.

Agreed, unless the GC decides to start working during your reversal, which would either block the execution until the GC finished or at least take a percentage of the CPU resources depending on the GC implementation. The biggest problem with GC is that it is difficult to control exactly when it will kick in. But by using an incremental GC at least the slowdown will be more or less constant, so that the performance won't be too bumpy.

Quote:
Edit: Redone the bench with boosts intrusive_ptr, C++ is now down to 1.9s with -Os, 0.7s with -O3, quite impressive...

That is impressive indeed. I knew shared_ptr was slow but not that slow :)

CoffeeMug:

Well, one thing that I just thought of is that the library don't have the entire graph. References can be kept outside the library, and script objects can hold references to objects outside the library.

Thanks for the links. I'll be sure to read them.

Anonymous Poster:

Thanks for your links as well.

Yes, that is exactly it. :D Thanks for the link.

I remembered only his first name, Hans.

[Edited by - WitchLord on May 5, 2005 12:59:20 PM]

Quote: Original post by WitchLord
Well, one thing that I just thought of is that the library don't have the entire graph. References can be kept outside the library, and script objects can hold references to objects outside the library.

If you don't have the entire graph than any other form of GC will suffer from the same problems as reference counting, won't it?

I've never used intrusive_ptr, but why would it make such a tremendous difference? It saves you one pointer dereference, there is no way that could have such an effect. I need to look into boost smart pointer code in more detail...

Quote:
If you don't have the entire graph than any other form of GC will suffer from the same problems as reference counting, won't it?

It could be. I haven't figured everything out yet, at the moment I'm basically just fishing for ideas.

In either case, if there are any external references to an object, then the library cannot free the object. I'll have to use an reference counting for external references, there is no doubt about that. The application will also be responsible for resolving any circular references involving external references so I'm not worried about those.

You might also want to take a look at this. This is FAQ for Parrot virtual machine, scroll down to find a small discussion on reference counting. They're strongly against it (and I strongly disagree with their reasoning).

After reading the document about Garbage Collection for Python, I have to say that their way is looking very attractive. Thanks a lot for that link, CoffeMug.

I don't think it should be too difficult to implement either.

Still, I'm continuing my investigation into the best way to handle my garbage collection needs.