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?
Non-Recursive data types = No need for garbage collection?
theory
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 researchUnsuitability of compile-time lifetime management as in C++, Rust.Real-time systems where GC pauses are unacceptableMemory-constrained systems (GC is more expensive when it has to run more often)Reference counting enables deterministic destruction/RAII (e.g. Perl)