4

If all data types are made non-recursive using tricks like a table of node IDs linking to data and data uses only other node IDs to form a graph, then can all memory be managed using just Reference Counting?

Furthermore is it possible to express a immutable list with the standard set of Haskell-like functions for the list in a language like C++ and guarantee no memory leaks using only reference counting?

3

Reference counting requires you to be more aware of object lifetimes. When creating a graph in a reference counting environment, you would create a parent object that owns all nodes in the graph. If the nodes in the graph have some concept of direction, then references from the top to the bottom can also be strong references. However, undirected connections or backlinks need to be weak refs that do not increment the reference counting. This is fine, since the graph-owning object ensures all nodes live long enough. This doesn't even need reference counting: C++- or Rust-style lifetime management is sufficient.

This prevents memory leaks in the sense that all nodes managed through this graph are eventually deallocated (when the whole graph is deallocated). However, if any particular node in the graph is not referenced by other nodes, it will still stay alive. Of course, that might be intentional (not all graphs are connected graphs). You also cannot remove a node from this graph, unless you sweep all nodes to make sure it isn't referenced. This means you are essentially re-implementing your own GC.

(Proper memory management is needed to ensure memory safety: that data cannot be referenced if it was deallocated.)

Even outside of mathematical graphs, such owning collections are actually quite common in many practical problems. E.g. with the repository pattern, the repository would own all entities that it manages. Other code only borrows references to each entity. Relations between entities do not need to use strong refs.

So while reference counting is an acceptable solution to nearly all memory management problems (the exceptions being relations with unclear ownership, or the need to remove unreferenced nodes), the technique has a number of significant drawbacks:

  • Reference counting requires more memory, since you have to store the refcount somewhere. This becomes notable overhead when the things you are counting are very small.
  • Reference counts have to be updated atomically. This means that you either can't share objects between threads, or have to use comparatively expensive thread-safe updates.
  • Reference counting results in unnecessarily many writes. This makes caching more difficult.
  • While reference counting may be deterministic, it does impose a continuous overhead. A pause-the-world GC algorithm will need less time total = better amortized performance.
  • A compacting GC can further improve performance by making all allocations very cheap.

In reality, the only reasons to use reference counting instead of GC are:

  • Prejudices such as “GC is too {slow, complicated}”
  • Unawareness of GC research
  • Unsuitability of compile-time lifetime management as in C++, Rust.
  • Real-time systems where GC pauses are unacceptable
  • Memory-constrained systems (GC is more expensive when it has to run more often)
  • Reference counting enables deterministic destruction/RAII (e.g. Perl)
  • 3
    GC can be slow when in a memory-constrained environment. When you have to do a sweep (even Gen-0) on almost every allocation, you're going to slow way down. If you're writing a mobile app that naturally holds a lot of memory (eg. a video editor), then you might be right up against the memory limit the whole time. (sealedabstract.com/rants/why-mobile-web-apps-are-slow the section headed "All about garbage collectors") – Andrew Oct 31 '16 at 18:39
  • 1
    @AndrewPiliser That is a very good point (and a quite interesting article, thanks :-) ). Things have gotten a bit better since 2013, I think, but mobile development isn't my focus (though I have yet to see a web app that's user-friendly and non-jittery on my phone) – amon Oct 31 '16 at 19:46
3

You will still have to keep track of which nodes of your graph are reachable. This could be done with a sequence of "live node" collections ordered by "generation", where as part of construction of new nodes you store what is reachable from that node, and then when you drop a generation the reference counting will collect them.

This is however basically re-implementing an "eagerly evaluating" generational GC, where it does the collection work as things are allocated, rather than before they are destroyed.

Once you have your immutable graph, you also have your immutable list (as a restricted case).

  • okmij.org/ftp/Haskell/regions.html . This page seems to suggest there is an alternative to GC and manual memory management. But I can't seem to work out an implementation in C++ for managing memory using monadic regions. – clinux Oct 31 '16 at 12:06
  • 1
    That seems to be a different way of saying what I was trying to say. Region <=> generation. My point is that it has to be tracked somewhere – Caleth Oct 31 '16 at 12:27
2

If all data types are made non-recursive using tricks like a table of node IDs linking to data and data uses only other node IDs to form a graph, then can all memory be managed using just Reference Counting?

Moving from pointers as references to ID-based references doesn't change the problem. In fact it can make it worse!

The properties of immutable data are pretty strong, and even with recursive data types, immutable data suppresses pointer reference cycles, because an old object/data could not have known a future created object reference when it was created (thus it can't reference future objects) and also cannot later be changed to reference a new object. Therefore, immutable data is always directed and acyclic with respect to pointer-based references.

However, using ID's or names as a referencing mechanism, an immutable object can be created that references future immutable object, which references the old immutable object, and thus, using names for references instead of pointers, we can create cycles with immutable data.


Furthermore is it possible to express a immutable list with the standard set of Haskell-like functions for the list in a language like C++ and guarantee no memory leaks using only reference counting?

A singly linked list, yes. However, for a doubly linked list: A doubly linked list is a recursive data type that also creates cycles with pointer-based references.

Simple or naive reference counting would fail to release any nodes of the list, if the list as a whole became unreferenced. The only way to collect the items would be to delete each and every one from the list.

Smart reference counting would be required to handle that, which is to say that the various references need to be differentiated, as @amon describes, say, as strong vs. weak. The strong ones count and the weak ones don't. Some systems attempt strong vs. weak differentiation at runtime, dynamically and automatically; other systems tag the references at compile time via the type system; some mix the two.

Have a look at Objective C and Swift, they use Automatic Reference Counting (automatic as compiler-supplied assistance) for their memory management. Also note problematic areas for ARC, especially around closures.


And yet still, in garbage collected languages, like Java and C#, we easily and commonly "leak" memory. All you need is a long lived collection or data structure that grows over time but isn't properly shrunk over time. This is a slightly different notion of memory leak, but has the same effect in that if the program runs long enough, it will run out of memory. This can even happen in functional languages that enforce immutable data, say like Erlang.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.