Tuesday, December 7, 2010

Not Convinced

I want string support. The language needs a collector which doesn't run out of space during a rewrite. One manner of achieving that is going for reference counting. Other manners are just increasing the number of free heap space before a rewrite, or possibly even a try-and-retry implementation where a rewrite is just retried after a garbage collect if it ran out of heap space during rewriting.

Reference counting has some good properties like not using more memory than needed by the program, it gets rid of a factor 2.0 needed by stop-and-copy. Also, for future extensions, it is nice that it collects dead data immediately if coupled with references and finalizers attached to system resources. For example, you never keep files open longer than you need them.

Going for reference counting means:

  • A more difficult runtime where a count is held in the header of a node.
  • Implementing ALLOC, INCREF and DECREF operations. In the scheme I envision ALLOC becomes a call, INCREF a series of instructions, DECREF another call. Currently, ALLOC is just returning a pointer followed by an increment.
  • Major problems are throughput and memory fragmentation.
Question remains: Is a lot of calls plus INCREF/DECREF operations cheap enough?

(Great. Most current reference counting literature is on Java/C#. So far, RC in Java a low factor overhead, RC in C# makes the code go to a grinding halt. But there are both complex RC implementations for Java, by Bacon and Petrank, and C#, by Joisha, with claim good performance. Also, reference counting lisp?)


  1. It might be interesting to dig around for 1) RC overhead for functional languages vs. imperative languages, if such literature exists; and 2) low compiler overhead "stupid RC tricks" to elide incr/decr operations where possible and convenient.

  2. There is no clarity. Everyone seems to agree that RC has too much overhead until it is implemented to speed up -mostly generational- GC.

    I don't like any of the solutions at the moment.