evolutional:

Thanks for the tip. Actually, my own thoughts were moving along those lines, which is a good thing.

With GC it is always complicated in knowing when and how often to invoke the GC. This is another one of my open questions, but one that I think will be quite easy to resolve simply by allowing the application to decide.

Also, thanks for the hint. Of course, I meant to say incremental GC ;)

Trap:

Thanks for the link to the pdf file. I much prefer pdf over ps, since it much more accessible. The article is quite large though, so it will take a while to read it. I'm sure it will be worth it though.

Yes, I've been thinking about dropping internal reference counting. Still having internal reference counting can make it easier for the GC, since it will immediately know that the object can be freed. External reference counting obviously cannot be dropped, since the GC will not have access to memory allocated outside the library.

CoffeMug:

No GC algorithm is perfect in all situations, and neither is reference counting. Actually, I would classify reference counting just another form of GC.

I'll probably end up using reference counting to clean up non-cyclic references and an algorithm similar to what evolutional explained for the cyclic references. I believe this would give the best of both worlds. And of course, the application writer will have as much control as possible over how the GC is invoked.

I agree, that the ability to move objects around in memory would be a valuable feature. But it would require an extra pointer lookup when accessing object members, and a lot of work to change how AngelScript currently handles objects. Maybe it's something that I'll implement for a future version, but right now I feel that it's not an issue.

---

Please, don't turn this into a discussion of which is better: reference counting or garbage collections. They both have their merits and disadvantages.

Quote: Original post by Trap
The profile says 1/2 the time is spend in shared_ptr dispose and 1/4 the time in operator new().

Hmm, if it takes longer to dispose than to allocate something has to be wrong. What exactly is dipose method doing?

The tremendous difference has little to do with GC, it's mostly the fact that managed memory languages have constant time allocation while standard malloc is linear. It's absolutely necessary to use custom allocators for containers (stl already does this) if you want good allocation speed.

Quote: Original post by WitchLord
Please, don't turn this into a discussion of which is better: reference counting or garbage collections. They both have their merits and disadvantages.

Sorry, didn't mean to do that. I'm working on a similar system now and I'm interested in finding a good general purpose algorithm. I've read a lot of papers but for truly generic system I can't find anything that beats Python's approach. If someone could point me to something, I'd be very thankful [smile]

In general it appears that people confuse garbage collection with heap management (defrags, etc.) In particular, if you're writing a garbage collector it's very easy to defrag the heap. That gives you O(1) allocation and free deallocation (aside from the sweep process). Reference counting generally doesn't include any heap management functions, which is where confusion comes from. I think for a reference counting approach it's absolutely necessary to create a good small object allocator. Malloc is just no good.

More on this later.

It's true that malloc is very slow in memory allocation.

AngelScript currently relies heavily on malloc, but it's only because I haven't put any effort into optimizing this version yet. Once I have the most important features I have planned implemented I'll start doing the optimizations. The memory allocation is one of the biggest optimizations I can do I believe, also AngelScript is currently doing quite a few unecessary allocations and object copies.

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.

I'd like to learn more about Python's way of doing it. Do you have an article you recommend? I'll do that search on Google you mentioned, but I prefer recommendations since they tend to lead to better articles. ;)

I'm also slightly worried about multithreading, and how that impacts the garbage collection. AngelScript doesn't have official support for multithreading, though some parts have been prepared already and I'll try to continue to support it as well as possible. Reference counting and multithreading doesn't work very well together, there are too many interactions that may screw things up. GC seems to be much safer in a multithreaded environment.

Trap:

If you are trying it is to show that GC is faster than reference counting then I believe you are going about it the wrong way. Lisp is obviously optimized to handle these cases, and your C++ code is far from optimized. Also, in this case the Lisp GC probably doesn't even kick in until after the program ends.

The boost shared_ptr<> isn't meant to be efficient, it is only meant to be easy to use. In fact the entire STL has been designed first most with ease-of-use in mind and efficiency comes almost as an after thought.

The boost shared_ptr<> is using reference counting, but it is doing so without changing the object's structure. Also by using it you're adding a pretty heavy overhead with the overloaded -> operator.

If you implemented the reference counting directly in the link structure, and skipped shared_ptr all together you would get a much better result.

If you want to compare efficiency of algorithms you must do so by implementing both in the same language.