Borrow Checking, RC, GC, and the Eleven () Other Memory Safety Approaches
verdagon.dev
verdagon.dev
Two fundamental characteristics of garbage collection (in pretty much every programmer's experience) are that (a) it can handle cycles (read: more general programs), and (b) it does not provide hard performance guarantees in the general case. Reference counting is literally the opposite, and that's exactly what people love about it.
Sure it does. One hard guarantee in that case is that freeing M objects (out of N total that are alive) takes O(M) time. (Another is that you can access all the other objects in parallel without any impact. Etc.)
Cheney's algorithm gives you O(N-M) time which really is in the same order of time complexity.
No, it's not. M could be 1 and N could be a million. The entire point of O(M) is that it's independent of N.
[0] https://www.sciencedirect.com/science/article/abs/pii/002001...
> if you have a million objects and need to release all of them except 1
That literally only happens at most 1 time for each allocation during its lifetime. But the GC can still waste its time traversing that object a billion times before then, despite nobody adding or removing references to it. Whereas RC would only touch each allocation when you're actually doing something to the object.
It's like arguing for wasting several decades of your life, just to make sure your funeral is quick...
Also, generations are a thing, so no need to "waste several decades of your life". And why is that metaphor applicable anyhow? Why not something like "stop constantly opening and closing the warehouse door during the work, and reinventorize it once a year instead of making a note every time you take something out of it or put something back in it" instead?
Anyway, thanks for you time and exchange.
Is this a rebuttal? How? You have a million live objects, you just want to free 1 object, and this awesome GC accesses O(1 million) objects, and that's somehow comparable to refcounting's O(1)?
> You're also ignoring the work to actually free which is generally slightly super linear
That's like arguing that everyone who claims binary search is O(log n) is "ignoring" the fact that page-table traversals and/or bit-complexity "actually" make it O((log n)^2).
It's "ignored" because the performance of the underlying system is entirely beside the point being made about the comparison of 2 algorithms on top of it. You analyze an algorithm based on the number of calls to the APIs provided to it, which in this case would be mmap/munmap (or VirtualAlloc/VirtualFree, or whatever), and you assume each of those operations takes constant time, unless specified otherwise. It doesn't make sense to dig into the underlying system, especially when nobody has specified what the underlying system is to begin with.
“O(M) guarantee” and “you can access all the other objects in parallel” are valid points, but they come with caviats that to utilize the first, one must know how many objects will be freed, and to utilize the second, one must know that two objects are not reachable from each other, which is not always the case e.g. objs=find(scene,criteria)
(Obviously you are aware of that. This comment is meant to inform other readers and prevent further idealisation of RC)
No -- unless I'm misunderstanding you(?), this is incorrect. The following pseudocode (I'll just use Python syntax for simplicity) has no idea how many objects are being deleted:
while True:
print("[Progress] Deleting: " + node.name)
prev = node
node = next(node)
del prev # Assume this happens M times
With GC, the user can see random arbitrarily-long stutters, depending on the shape of the rest of the object graph, and the phase of the moon.
With RC, you can rely on the user seeing your progress indicators consistently... without knowing or caring what M was.
> to utilize “you can access all the other objects in parallel”, one must know that two objects are not reachable from each other, which is not always the case e.g. objs=find(scene,criteria)
Again, this is false, and (subtly) misses the point.
The claim wasn't "you can access all objects in parallel". That's not true in any system, be it GC or RC.
The claim is "you can still access some objects in parallel" with RC. The crucial difference here is that, under a GC, all threads are at risk of getting throttled because of each other arbitrarily. They simply cannot do any work (at least, nothing that allocates/frees memory) without getting throttled or interrupted at the whim of the GC.
What does that mean? How is that helpful for the user to know you've free-d 56,789 objects so far if he doesn't know if there's 60k in total or 600k?
> The crucial difference here is that, under a GC, all threads are at risk of getting throttled because of each other arbitrarily. They simply cannot do any work (at least, nothing that allocates/frees memory) without getting throttled or interrupted at the whim of the GC.
And that's also the case for all thread which share the same RC-d object. They will all be throttled when the memory is freed.
The biggest benefit of RC is how it seamlessly interact with native code, that's why it's a great fit for languages like Obj-C and Swift or Rust (opt-in), but in terms of performance, be it latency or throughput, it's not a particularly good option (the trade off it makes is comparable to copying GC but with higher max latency than copying GC and even lower throughput, and doesn't have fast allocation and memory compaction as a side benefit).
I was thinking of a lot of cases where RC is being used as a general solution for lifetime management with automatic refcounting; but most objects have a well-known lifetime with their refcount being 1 95% of the time. And another 4% have their refcount bump up to 2 briefly when they're temporarily shared, or transferred to a new owner (think returning a shared_ptr<>).
But, yeah, the "genuinely shared" case - either the 1% in the scenario above, or when RC is only being used for objects with complex lifetimes - is definitely a significant use-case I overlooked.
But, also, if your point is that defragmentation is a selling point... I mean, the last time I saw someone who moved from RC to GC because of defragmentation was... never? Probably because you can just solve it by throwing money at it and buying more memory to permanently solve the problem. Whereas people go in the other direction all the time... probably because you can't just perpetually throw more money at the problem and make compute time go N times faster.
You never saw anyone move from RC to GC, because there are very few high performance pure RC implemenations to make them a first option anyway, and in most cases that requires a rewrite in another language.
Isn't that an implementation detail of the GC itself? For example this RC algorithm [1] (which detects cycles) can be implemented by tracking free and potentially free objects in their own special structure that can be evaluated incrementally.
Second, what you seem to consider to be fundamental characteristics of tracing GC and RC is not in fact so fundamental.
For starters, RC absolutely can handle cycles (e.g. through trial deletion). Such implementations may be difficult or impossible to implement as pure library solutions, but there is nothing that says it can't be done. The most prominent example of a programming language that uses such an approach is probably Python.
Nor does the claim that tracing GC cannot provide hard performance guarantees in the general case (while RC does) hold up under closer examination. Leaving aside the problem that it's already non-trivial to provide hard real time performance guarantees for malloc()/free() and ignoring the issue of cascading deletions, it doesn't hold under the more relaxed assumptions discussed downthread.
For starters, we have such predictability only for the single-threaded case, not for arbitrary multi-threaded situations. And even in the single-threaded case, there are real use cases where predicting performance becomes functionally intractable. Examples are implementations of binary decision diagrams or certain persistent data structures, where the presence of shared subgraphs of arbitrary size make predicting performance of individual deallocations impractical.
In contrast, in the single-threaded case we can absolutely bound individual operations of a tracing GC by either a constant or (in the case of arbitrarily sized allocations) make them linear in the number of bytes allocated (e.g. Baker's treadmill).
What is true is that in the absence of cycles, (naive) reference counting will free memory at the earliest opportunity, which is not something we can say for tracing GC.
I'll put it on my list, thanks for the recommendation, but it really has no impact on my point (see next point).
> because I think you're misunderstanding the claim (plus, it is a very good paper)
Note: I wasn't criticizing the paper. I was criticizing the comment, which claimed "it’s better" to view these as special cases.
If it's not obvious what I mean, here's an analogy: it's the difference between having a great paper that reduces ~everything to category theory, vs. claiming "it's better" for the audience I'm talking to to view everything in terms of category theory. I can be impressed by the former while still vehemently disagreeing with the latter.
> For starters, RC absolutely can handle cycles (e.g. through trial deletion).
"Can handle" is quite the hedge. You "can" walk across the continent too, but at what cost?
> The most prominent example of a programming language that uses such an approach is probably Python.
You're saying Python uses RC to handle reference cycles, and doesn't need a GC for that? If so please ask them to update the documentation, because right now it specifically says "you can disable the collector if you are sure your program does not create reference cycles". https://docs.python.org/3/library/gc.html
> [...] hard real time [...]
Nobody said "real time". I just said "hard guarantee".
I didn't assume you were. My note about it being a good paper was just a general "this is worth reading" recommendation.
> "Can handle" is quite the hedge. You "can" walk across the continent too, but at what cost?
It's not a hedge. You claimed that (tracing) GC can handle cycles, while RC was "the opposite", which I read to mean that you believe it cannot.
While we are at it, let's go through the basics of trial deletion.
Trial deletion first looks at possible candidates for objects involved in a cycle (in the original algorithm, those were objects whose RC got decremented without reaching zero). Then, you do a recursive decrement of their children's (and their children's children's, and so forth) reference counts.
Unlike with regular reference counting decrements, you visit children even if the reference count doesn't reach zero. The net result is that reference counts are reduced only along internal paths, but that objects that are still reachable from external paths have reference counts > 0 after that.
Thus, any object with a reference count of zero after this step must be part of an internal cycle and can be deleted. All other objects have their original reference counts restored.
Because trial deletion operates on reference counts differently, it's not something that you can easily implement as a library, which is why you don't see it much except when a language implementation chooses to go with reference counting over a tracing GC.
> You're saying Python uses RC to handle reference cycles, and doesn't need a GC for that? If so please ask them to update the documentation, because right now it specifically says "you can disable the collector if you are sure your program does not create reference cycles". https://docs.python.org/3/library/gc.html
This is a terminology thing. Python uses a variant (generational) trial deletion approach [1]. It's not a traditional tracing GC, and it's also not inaccurate, because GC can mean more than using a traditional tracing GC.
> Nobody said "real time". I just said "hard guarantee".
I was not sure what you meant, so I answered both, as you may have noticed.
[1] https://github.com/python/cpython/blob/796b3fb28057948ea5b98...
AFAIK it's how you get memory safety in missile guidance software: you just have to put enough RAM on the board so it never run out of memory before the end of its flight.
Edit: TFA just talks about that in the “never free”
>I was once working with a customer who was producing on-board software for a missile. In my analysis of the code, I pointed out that they had a number of problems with storage leaks. Imagine my surprise when the customers chief software engineer said "Of course it leaks". He went on to point out that they had calculated the amount of memory the application would leak in the total possible flight time for the missile and then doubled that number. They added this much additional memory to the hardware to "support" the leaks. Since the missile will explode when it hits its target or at the end of its flight, the ultimate in garbage collection is performed without programmer intervention.
Right. I've occasionally thought about that for Rust, as a way to do back references. You can have an Rc owning an object, which can own another object, which can have a weak RC reference back to the original. This allows you to find an object's owner when needed, so you can do inheritance-like things when you need to. The single-ownership and dangling-pointer checks are made at run time and will panic if they fail.
Now, the question is, can you statically check access behavior and determine that those panics will never occur? If you can, you can eliminate the reference counts and checks. That looks 1) possible, and 2) a PhD thesis sized problem.
https://doc.rust-lang.org/std/collections/struct.LinkedList....
> NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.
https://docs.rs/petgraph 78 M downloads
Rust prevents data races, so I'm not sure what this is referring to.
A region's model is described as:
> Pony's iso keyword: an iso'd object (and its contents) are only reachable from your pointer; nobody else points at that object or anything the object contains [...] we can "temporarily open" an isolated subgraph for a given scope, and afterward it would still be properly isolated.
In Rust, AFAIR, one gets a mutable reference to an object, and the borrower can independently operate on its fields (subgraphs), while the root mutable reference can't be accessed from anything else other than the borrower.
It is an interesting APL successor I was planning to learn after getting current projects out of the way.
Damn pattern recognition, the logo looks almost the same if you squint!
you allocate and must / are extending its lifetime all the time or else it frees itself! very predictable behaviour of memory collection.
you get pointer and keep it allocated by "extending" its lifecycle.