0 Replies - 843 Views - Last Post: 10 June 2016 - 02:16 AM

#1 davidnichols   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 10-June 16

Prompt Collection in Memory-Managed Programming Languages

Posted 10 June 2016 - 02:16 AM


What I mean by "Prompt Collection" is basically that objects are collected / destroyed immediately when they go out of scope, in this context, even if they participate in a directed cyclic graph.

Here is a link about this topic:
* http://cs.stackexcha...mory-management

This is a problem that to my knowledge affects the design of all garbage-collected languages that allow directed cyclic graphs of memory objects to be created but do not support destructors or "prompt" finalization of the objects due to the non-deterministic nature of garbage collection when such objects participate in directed cyclic graphs (for example Java and C#/.NET).

Basically I have implemented this for Qore, which is a multithreaded scripting language that has similar challenges with recursive directed cyclic graphs of objects. In Qore's case objects, which are passed as copies of a reference to the object similar to Java, and closure-bound local variables can participate in recursive directed cyclic graphs and additionally are managed with a shared_ptr-like reference count, and therefore require a realtime graph scan to detect recursive cycles to support prompt collection. Objects in a recursive cycle can only be collected when there are no valid strong references to any of the objects in the graph, in which case collection / destruction for one object can be initiated which causes a chain reaction that causes all objects in the graph to be collected.

In this way, Qore supports the RAII idiom and still has automatic (meaning in this case completely system-managed) and predictable memory management.

My question is: basically if anyone, particular those with theoretical and practical experience with garbage collection and/or the practical application of graph theory in similar contexts would care to review or comment on the implementation?

I am not an expert in graph theory, and I am not sure how to formalize the practical limits of my algorithm nor of its scalability with very large graphs. The threading and deadlock avoidance approach is also novel, using a transactional approach with deadlock detection, rollbacks, and notifications. After extensive practical testing, the algorithm looks solid and is performing well already in production code, but could actually have a hidden race condition somewhere due to an error in the design.

I hope that it's appropriate to use this web site to present this sort of development and ask if there is interest in it. I believe that it is significant, because the lack of RAII in languages like Java and C#/.NET is due exactly to the difficulty of solving this problem.

I would like to say "the problem is solved", but because I believe that my solution has limits and will not be perfectly applicable to every use case (for example - the current implementation may not scale well for very large graphs), I think that it's too early to make such a statement, but on the other hand the algorithm appears to be working well with very good performance in complex code where there is a significant number of recursive cyclic graphs of objects, and everything (so far) is collected on time and correctly. Additionally, the deadlock detection, avoidance, and notification code is working properly.

Some links describing the implementation:
* http://qoreprogrammi...collection.html
* http://qoreprogrammi...g-raii-and.html

(I have been using "deterministic garbage collection" to describe the approach, but now it seems that "prompt collection" is more appropriate)

Any constructive comments or questions are welcome.

Is This A Good Question/Topic? 0
  • +

Page 1 of 1