Talk:XPCOMGC: Difference between revisions

From MozillaWiki
Jump to navigation Jump to search
(move to Ynvich GC)
 
Line 1: Line 1:
I may have idea how to turn tamarin into an exact incremental GC framework, easy for managing XPCOM.
Ynvich's garbage collection scheme was here. I moved it to [[Ynvich GC]]. --[[User:Jorend|jorendorff]] 05:47, 15 October 2007 (PDT)
 
In short, the idea is to replace ''colored states'' in mark stage with an ''exact reference count of ALL root parents'' (not just immediate as in XPCOM refcount) which is permanently keeped in sync with dependency list.
 
==Concept comparison==
Let's compare XPCOM refcount (XPCOM), the present MMgc idea (MMgc), and the proposed idea (XPgc - Cross Platform gc):
<table width="100%">
<tr>
<th>Parameter \ Version</th><th>XPCOM</th><th>MMgc</th><th>XPgc</th></tr>
<tr> <td>'''Inter-object Relations'''</td></tr>
<tr> <td>how stored</td>
<td>ignored</td>
<td>saved in a table</td>
<td>saved in a table</td></tr>
<tr> <td>when changed</td>
<td>--</td>
<td>in a write barrier</td>
<td>in a write barrier</td></tr>
<tr> <td>'''Object GC-status'''</td></tr>
<tr> <td>mechanism</td>
<td>immediate refcount</td>
<td>white/grey/black</td>
<td>full refcount</td>
<tr> <td>when updated</td>
<td>in a write barrier</td>
<td>during mark stage</td>
<td>in a write barrier</td>
<tr> <td>when applied</td>
<td>in a write barrier</td>
<td>during sweep stage</td>
<td>both variants possible</td></tr>
</table>
 
==Details==
Several more issues need to be addressed:
* refcount cycles;
* what is the number of parents;
* multiple inheritance.
 
===Dealing with Cycles===
When we traverse dependency table in a write barrier, we will keep a list of visited nodes in a temporary structure. If the same node is hit second or more time, it will be ignored.
 
===Fast Calculation of Full Refcount===
We will increase/decrease refcount of the node and all child nodes by the refcount of the parent node.
 
===Multuple Inheritance===
Object nodes should be identified by the beginning of their address space. This is guaranteed if we cast object to (void *) from one of its methods ('''Visitor''' design pattern). This must be done two times: for the parent and for the child.
 
It can be done like that:
* '''nsISupports''' is changed
    -unsigned int AddRef();
    +unsigned int AddRef(void *parent);
    -unsigned int Release();
    +unsigned int Release(void *parent);
 
* '''GC''' has something like this
    unsigned int Add(void *parent, void *child);
    unsigned int Remove(void *parent, void *child);
 
* parent calls:
    child->AddRef(this);
    child->Release(this);
 
* child calls:
  unsigned int
  nsFoo::AddRef(void *parent)
  {
    return mGC->Add(parent, this);
  }
 
If type-safety is mandatory, (void *) casts may be replaced with (GCObject *) casts or the like.
 
==Functional Comparison==
Let's again compare XPCOM refcount (XPCOM), the present MMgc idea (MMgc), and the proposed idea (XPgc - Cross Platform gc):
<table width="100%">
<tr>
<th>Parameter \ Version</th><th>XPCOM</th><th>MMgc</th><th>XPgc</th></tr>
<tr> <td>write barrier cost (add)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1) on demand</td></tr>
<tr> <td>write barrier cost (remove)</td>
<td>O(M), M = (changes)</td>
<td>O(1)</td>
<td>O(1)</td></tr>
<tr> <td>mark stage cost</td>
<td>--</td>
<td>O(N), N = (all)</td>
<td>O(M ln N), M = (changes), N = (all)</td></tr>
<tr> <td>sweep misses</td>
<td>leaks on cycle</td>
<td>conservative leaks</td>
<td>safe</td></tr>
<tr> <td>sweep starvation</td>
<td>absent</td>
<td>possible</td>
<td>absent on demand</td></tr>
</table>
 
This table shows that three solutions are not worse or better, they are different. '''Refcount''' is great for design which is free of cycles, '''MMgc''' and '''XPgc''' allows to postpone processing, and '''XPgc''' is better when only a subset changes states between collection cycles.
 
In addition, '''XPgc''' allows to do collection incrementally without additional cost.
 
==Comments==
===Storing dependencies===
We must use an efficient data structure (btree most likely) to actually achieve that O (M ln N) performance. We can use in-memory sqlite tables to handle this in the beginning.
 
===Interface===
Looks like it is possible to have C interface to this GC:
* callback '''Sweep''';
* Add(void *, void *, void (void *));
* Remove(void *, void *, void (void *)).
 
C interface will allow to use XPgc not only from C++, but also from other languges like Java and Python.
[[User:Ynvich|Ynvich]] 03:38, 15 October 2007 (PDT)

Latest revision as of 12:47, 15 October 2007

Ynvich's garbage collection scheme was here. I moved it to Ynvich GC. --jorendorff 05:47, 15 October 2007 (PDT)

Retrieved from "https://wiki.allizom.org/index.php?title=Talk:XPCOMGC&oldid=71100"