Skip to content
No description, website, or topics provided.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
papers
tests
README.md
concurrent.js
fuzz.js
index.js
package.json
synchronous.js
test.js

README.md

A repository to fiddle around with pure automatic reference counting.

After the paper "A Pure Reference Counting Garbage Collector" by David F. Bacon et al.

Considerations

TL;DR If you can break it, please do.

The concurrent algorithm, as described in the paper, does not work as-is. It misses that in MarkGray, each T is reachable from S as well, which isn't recursively taken into account by the else clause that is responsible to decrement CRC of each object reachable from within the graph. Also, unlike its synchronous variant, the concurrent Scan routine recursively recolors nodes already marked white to black, preventing them from being collected. Hence, patches applied here are as follows:

 MarkGray(S)
   if (color(S) != gray)
     color(S) = gray
     CRC(S) = RC(S)
     for T in children(S)
       MarkGray(T)
-  else if (CRC(S) > 0)
-    CRC(S) = CRC(S) - 1
+      if (CRC(T) > 0)
+        CRC(T) = CRC(T) - 1

 Scan(S)
-  if (color(S) == gray and CRC(S) == 0)
-    color(S) = white
-    for T in children(S)
-      Scan(T)
-  else
-    ScanBlack(s)
+  if (color(S) == gray)
+    if (CRC(S) > 0)
+      ScanBlack(s)
+    else
+      color(S) = white
+      for T in children(S)
+        Scan(T)

Apart from that, the prototypical acyclic detection in this implementation differs from the assumptions made in the paper, in that all nodes that cannot directly or indirectly reference their own kind are considered acyclic, which a static compiler can prove. The underlying assumption is that if an acyclic parent's RC is decremented and the parent is in turn released, the RC of each child is decremented, leading to the cyclic child to be considered as a possible root anyway.

You can’t perform that action at this time.