another approach to memory management that solves the referential cycles problem
Dear boost members, I have placed in the boost Vault, under the section "memory", the file 'mm.zip' which contains: 1) a file "readme.txt" with a little documentation. 2) a file 'main.cpp' which contains a reference implementation and test. This (I wouldn't not call it new, but certainly interesting) approach to memory management solves the problem of cycles and it can also provide a sort of garbage collection, without the issues of other approaches (explained in the readme). Suggestions, comments, ideas, etc are welcomed.
on Mon Feb 23 2009, "Achilleas Margaritis" <axilmar-AT-gmail.com> wrote:
Dear boost members,
I have placed in the boost Vault, under the section "memory", the file 'mm.zip' which contains:
1) a file "readme.txt" with a little documentation. 2) a file 'main.cpp' which contains a reference implementation and test.
This (I wouldn't not call it new, but certainly interesting) approach to memory management solves the problem of cycles and it can also provide a sort of garbage collection, without the issues of other approaches (explained in the readme).
Suggestions, comments, ideas, etc are welcomed.
If you want people to take the trouble to look, a direct link (and a little more detail in your email about what you're doing) would help. Cheers, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
If you want people to take the trouble to look, a direct link (and a little more detail in your email about what you're doing) would help.
Certainly. The code and readme can be found here (file mm.zip): http://www.boostpro.com/vault/index.php?PHPSESSID=843094baef93383a0caec167435795b3&direction=0&order=&directory=Memory The trouble with shared ptrs is that cyclic references can not be reclaimed. The problem can be solved using weak pointers, but this approach does not scale well in big projects that evolve over time with different developers. Sometimes the knowledge of cycles is lost during the transition from one developer to the other. The file above contains a test implementation of an idea for solving the problem of cyclic references reclamation. The idea goes like this: In order to solve the problem of cyclic references, a garbage collector that scans the object graph for pointers needs to know the root set. Unfortunately, this is not possible in c++ because the compiler does not provide this information. Custom pointer classes can be used to register pointers to a global pointer container, but then the problem is to identify which pointers are roots and which are members of objects, so as that only those pointers that are are truly root are registered as root pointers. Even if we managed somehow to register pointers to the actual memory areas they belong, the solution does not work with STL containers because the STL containers themselves do not use these special pointer classes. Another approach is possible that does not have these restrictions. Instead of scanning an object graph from the roots, an object graph can be scanned towards the roots. For example, if we have the object graph (R is a root reference, A and B are objects): R -> A - >B The traditional collector starts from R, then visits A and then B. But if we represent the graph like this: R <- A <- B We don't need to register the root reference anywhere: we can simply start from B, then visit A, then visit R: since R is a root, then A and B are reachable. The provided code implements this with two classes: 1) a class 'ptr_base' that represents a ptr with a link to an owner object: a) knows if it is a root class from the supplied owner object in its constructor: if no owner is given, the ptr is root. Otherwise, it is a member ptr. b) it registers itself to the object it points to. 2) a class 'object' which: a) contains a list of ptrs that points to that object. The list is intrusive, using boost::intrusive::list, for performance reasons. With these two classes, it is possible to traverse the graph of objects backwards, towards the roots: if an object is not accessible from a root ptr, then it can be collected. A class ptr<T> provides a typed ptr that is derived from class ptr_base. The cycles are broken like this: when an object is not accessible from roots and still has pointers pointing to it, it means there is a cycle, and therefore the list of pointers is cleared before deleting the object, thus breaking the cycle. The solution works with stl containers, because ptr<T> instances placed in STL containers are root pointers, and therefore the objects in the container are not collected until the container is deleted. The file contains an example of using an std::list to keep the objects around until the list is destroyed. The idea is not considered a panacea for all memory management problems. It is only complementary to shared ptrs and manual memory management.
Achilleas Margaritis wrote:
The trouble with shared ptrs is that cyclic references can not be reclaimed. The problem can be solved using weak pointers, but this approach does not scale well in big projects that evolve over time with different developers.
The scaling behavior is certainly of utmost importance. How does the runtime and memory behavior of the proposed solution scales when the object graph becomes huge? I think it would be great, if the proposed solution could be made to work. As you point out, there would be good reasons to use advanced memory management schemes that don't require weak pointers. However, "made to work" includes an acceptable amortized worst case bound for the runtime of the pointer/reference operations. I have a bit the impression that releasing the reference to an object deep down in the object graph might take O(N) operations, at least for the provided "prototype" implementation. I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed. I also have the impression that the provided "prototype" implementation can sometimes detect a cycle and conclude from this cycle that an object is collectable, even if the cycle still has a path to a root reference. But again, I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
The idea is not considered a panacea for all memory management problems. It is only complementary to shared ptrs and manual memory management.
Can you be more explicit about the "known" problems of your approach? Regards, Thomas
I think it would be great, if the proposed solution could be made to work. As you point out, there would be good reasons to use advanced memory management schemes that don't require weak pointers. However, "made to work" includes an acceptable amortized worst case bound for the runtime of the pointer/reference operations.
I have a bit the impression that releasing the reference to an object deep down in the object graph might take O(N) operations, at least for the provided "prototype" implementation. I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
You are correct. That is the reason why a proposed solution is 'lazy' disposal: the object is placed in a container and checked later for disposal. When checked like this, an object can be marked as reachable or unreachable(i.e. the result of the scanning can be cached), minimizing even further the number of operations required. The lazy disposal solution has roughly the same amortized complexity of the traditional garbage collector. In fact, I believe that the only difference between the backwards scanning (i.e. my solution, scanning from objects to roots) and the forward scanning algorithms are the same: in either case, the graph of objects is traversed and each node is visited once. That is, if the number of objects to be kept around is equal or higher than the number of objects that are unreachable. Perhaps there is a way to minimize the cost of the disposal algorithm: the recursive algorithm that checks if an object is collectable can also delete the object, if it finds that there is no path to a root ptr. Another solution that might be possible would be to cache the result of the collectable() function to a flag in the object, and then during release to use that instead of calling the collectable() function again. Another possible optimization is: if root ptrs are added to the front of the ptr list of each object, the path to the roots would be minimized. The list of pointers could also be sorted while the list of pointers is scanned: root pointers could be moved to the front, so as that the shortest path to roots is always the first to be checked. Finally, the algorithm 'collectable()' could return the number of steps to the root, from each path, and then optimize the list of ptrs according to that, while scanning the ptr list: shortest path goes first.
I also have the impression that the provided "prototype" implementation can sometimes detect a cycle and conclude from this cycle that an object is collectable, even if the cycle still has a path to a root reference. But again, I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
Can you be a little more specific? the provided example has many circles in it, yet all objects are collected. The function 'collectable()' stops and returns false only if there is a path to a root ptr. If there is a cycle, the function returns true, and therefore the algorithm continues until all paths are exhausted.
The idea is not considered a panacea for all memory management problems. It is only complementary to shared ptrs and manual memory management.
Can you be more explicit about the "known" problems of your approach?
Besides the obvious problem of scaling mentioned above, there might be some other issues: 1) it takes more memory. Each ptr becomes 16 bytes long. And each object gets an extra 12 bytes. 2) it may be difficult to make it thread safe.
I think it would be great, if the proposed solution could be made to work. As you point out, there would be good reasons to use advanced memory management schemes that don't require weak pointers. However, "made to work" includes an acceptable amortized worst case bound for the runtime of the pointer/reference operations.
I have a bit the impression that releasing the reference to an object deep down in the object graph might take O(N) operations, at least for the provided "prototype" implementation. I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
You are correct. That is the reason why a proposed solution is 'lazy' disposal: the object is placed in a container and checked later for disposal. When checked like this, an object can be marked as reachable or unreachable(i.e. the result of the scanning can be cached), minimizing even further the number of operations required. The lazy disposal solution has roughly the same amortized complexity of the traditional garbage collector. In fact, I believe that the only difference between the backwards scanning (i.e. my solution, scanning from objects to roots) and the forward scanning algorithms are the same: in either case, the graph of objects is traversed and each node is visited once. That is, if the number of objects to be kept around is equal or higher than the number of objects that are unreachable. Perhaps there is a way to minimize the cost of the disposal algorithm: the recursive algorithm that checks if an object is collectable can also delete the object, if it finds that there is no path to a root ptr. Another solution that might be possible would be to cache the result of the collectable() function to a flag in the object, and then during release to use that instead of calling the collectable() function again. Another possible optimization is: if root ptrs are added to the front of the ptr list of each object, the path to the roots would be minimized. The list of pointers could also be sorted while the list of pointers is scanned: root pointers could be moved to the front, so as that the shortest path to roots is always the first to be checked. Finally, the algorithm 'collectable()' could return the number of steps to the root, from each path, and then optimize the list of ptrs according to that, while scanning the ptr list: shortest path goes first.
I also have the impression that the provided "prototype" implementation can sometimes detect a cycle and conclude from this cycle that an object is collectable, even if the cycle still has a path to a root reference. But again, I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
Can you be a little more specific? the provided example has many circles in it, yet all objects are collected. The function 'collectable()' stops and returns false only if there is a path to a root ptr. If there is a cycle, the function returns true, and therefore the algorithm continues until all paths are exhausted.
The idea is not considered a panacea for all memory management problems. It is only complementary to shared ptrs and manual memory management.
Can you be more explicit about the "known" problems of your approach?
Besides the obvious problem of scaling mentioned above, there might be some other issues: 1) it takes more memory. Each ptr becomes 16 bytes long. And each object gets an extra 12 bytes. 2) it may be difficult to make it thread safe.
I also have the impression that the provided "prototype" implementation can sometimes detect a cycle and conclude from this cycle that an object is collectable, even if the cycle still has a path to a root reference. But again, I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
Can you be a little more specific? the provided example has many circles in it, yet all objects are collected.
The function 'collectable()' stops and returns false only if there is a path to a root ptr. If there is a cycle, the function returns true, and therefore the algorithm continues until all paths are exhausted.
OK, now I see it. The object that returns true when a cycle is detected will still visit all its parents (and return false if it finds a path to a root cell), because it is already in the loop over its parents somewhere up in the call chain. As I said "I might be wrong"...
I have a bit the impression that releasing the reference to an object deep down in the object graph might take O(N) operations, at least for the provided "prototype" implementation. I might be wrong, or it might simply be a bug in the "prototype" implementation that can easily be fixed.
You are correct. That is the reason why a proposed solution is 'lazy' disposal: the object is placed in a container and checked later for disposal. When checked like this, an object can be marked as reachable or unreachable(i.e. the result of the scanning can be cached), minimizing even further the number of operations required.
I guess that some sort of laziness is required to arrive at an acceptable amortized worst case bound for the runtime of the pointer/reference operations. So the question for me would be: "Is it possible to achieve an acceptable amortized worst case bound for runtime complexity of the pointer/reference operations". I have no problem if this costs additional memory and involves modification of this memory even for "read only" operations. The "checked later for disposal" that is proposed above doesn't look "automatic enough" to me, but I haven't yet tried to understand what exactly you are proposing as 'lazy' disposal.
Can you be more explicit about the "known" problems of your approach?
Besides the obvious problem of scaling mentioned above,
I would interpret this statement in the way that you think that it will be difficult to solve the scaling problem.
I guess that some sort of laziness is required to arrive at an acceptable amortized worst case bound for the runtime of the pointer/reference operations. So the question for me would be: "Is it possible to achieve an acceptable amortized worst case bound for runtime complexity of the pointer/reference operations". I have no problem if this costs additional memory and involves modification of this memory even for "read only" operations.
One 'truth' that can be said for this algorithm is that when an object is found collectable and deleted, there is no need to check for collectability in children nodes: they would have already been checked anyway.
The "checked later for disposal" that is proposed above doesn't look "automatic enough" to me, but I haven't yet tried to understand what exactly you are proposing as 'lazy' disposal.
I mean that the check if the object is collectable or not can be deferred to a later time...just like garbage collectors do.
I would interpret this statement in the way that you think that it will be difficult to solve the scaling problem.
Indeed. The scaling problem depends solely on the configuration of the graph of objects. The worst case is to have N objects pointing to all other objects, i.e. N objects having N-1 pointers to all other objects. I am not well versed into graph theory, so perhaps someone else can enlighten us if some sort of shortest path discovery algorithm exists that can be applied to this case. Perhaps some algorithm that applies weights over the paths of the graph? Another approach would be to optimize the graph while scanning it, as I mentioned earlier.
Achilleas Margaritis wrote:
I would interpret this statement in the way that you think that it will be difficult to solve the scaling problem.
Indeed.
The scaling problem depends solely on the configuration of the graph of objects. The worst case is to have N objects pointing to all other objects, i.e. N objects having N-1 pointers to all other objects.
I am not well versed into graph theory, so perhaps someone else can enlighten us if some sort of shortest path discovery algorithm exists that can be applied to this case. Perhaps some algorithm that applies weights over the paths of the graph?
This reminds me of the "Dynamic graph algorithms" To-Do item from the Boost Graph Library: http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/challenge.html The task at hand seems to be related to the "Dynamic Connectivity" problem. The given references seem to be from 1998 and 1999, but skimming over them gives hope that the problem is not as unsolvable as it seems at first glance: "The currently best theoretic bounds are achieved by a data structure invented by Henzinger and King [13] and improced by Henzinger and Thorup [14]. It achieves O(log n) worst-case deterministic query time and O(log^2 n) amortized expected update time ..." I haven't yet looked at your other proposed solutions, but perhaps I will do this later. Regards, Thomas
This reminds me of the "Dynamic graph algorithms" To-Do item from the Boost Graph Library:
http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/challenge.html
The task at hand seems to be related to the "Dynamic Connectivity" problem. The given references seem to be from 1998 and 1999, but skimming over them gives hope that the problem is not as unsolvable as it seems at first glance: "The currently best theoretic bounds are achieved by a data structure invented by Henzinger and King [13] and improced by Henzinger and Thorup [14]. It achieves O(log n) worst-case deterministic query time and O(log^2 n) amortized expected update time ..."
I haven't yet looked at your other proposed solutions, but perhaps I will do this later.
Thank you, I will check this out later.
This reminds me of the "Dynamic graph algorithms" To-Do item from the Boost Graph Library:
http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/challenge.html
The task at hand seems to be related to the "Dynamic Connectivity" problem. The given references seem to be from 1998 and 1999, but skimming over them gives hope that the problem is not as unsolvable as it seems at first glance: "The currently best theoretic bounds are achieved by a data structure invented by Henzinger and King [13] and improced by Henzinger and Thorup [14]. It achieves O(log n) worst-case deterministic query time and O(log^2 n) amortized expected update time ..."
I haven't yet looked at your other proposed solutions, but perhaps I will do this later.
Thank you, I will check this out later.
participants (3)
-
Achilleas Margaritis -
David Abrahams -
Thomas Klimpel