http://researcher.watson.ibm.com/researcher/files/us-bacon/B...
Takes time proportional the live set times the number of GC runs that happen while the objects are alive. In other words, the longer the objects live, the more GC runs have to scan that object (assuming there is enough activity to trigger the GC), and the worse GC looks.
Moving the work to another core doesn't really change my statement.
Aside: I wonder if it's feasible to switch to reference counting for the oldest generation? That would move the problem back to deallocation. I'm not sure if that's a good trade-off, but it would be interesting.
But generational GCs do improve massively on this problem.
This can also trivially be done in other languages. Atomically append your pointer to a queue of "large things that need to be freed" and move on as though you had actually called free.
Within a particularly time sensitive loop you can even opt to place pointers into a preallocated array locally. Then once per loop iteration swap that array with the thread handling the deallocations for you. It eats up a bit of CPU time but can significantly reduce latency.
Consider this code
{
Window a;
ClickHandler* b = new ClickHandler(&a);
delete b;
}
That being said, it seems like most cases where such an approach is worthwhile involve large nested data structures that involve lots of pointer chasing to traverse. All cases I've encountered so far were bulk stores that didn't involve actively interacting with external objects.
Not to say that it's not worth it to learn manual memory management as well, but it is important not to think that GCs are a fancy modern tool, and that greybeards would never touch one. There were greybeards using punch cards and programming in a GC language, with output printed out on paper.
That doesn't seem to make intuitive sense. A GC has the same problem.
A garbage collector has to traverse the data structure in a similar way to determine whether it (and it's embedded keys and values) are part of the live set or not, and to invoke finalizers. You're beginning your comparison after the mark step, which isn't a fair assessment since what Rust is doing is akin both both the mark and sweep phases.
The only way to drop an extensively nested structure like this any faster than traversing it would be an arena allocator, and forgetting about the entire arena.
The difference between a GC and this kind of memory management is that the GC does the traversal later, at some point, non-deterministically. Rust allows you to decide between deallocating it in place, immediately, or deferring it to a different thread.
A generational/compacting collector traverses pointers from the live roots, and copies everything it finds to the start of its memory space, and then declares the rest unused. If there is 1GB of unused memory, it's irrelevant. Only the things that can be reached are even examined.
As I said, this has the opposite problem. When the live set becomes huge, this can drag performance. When the live set is small, it doesn't matter how much garbage it produces, performance is fast.
> Objects with finalizers (those that have a non-trivial finalize() method) have significant overhead compared to objects without finalizers, and should be used sparingly. Finalizeable objects are both slower to allocate and slower to collect. At allocation time, the JVM must register any finalizeable objects with the garbage collector, and (at least in the HotSpot JVM implementation) finalizeable objects must follow a slower allocation path than most other objects. Similarly, finalizeable objects are slower to collect, too. It takes at least two garbage collection cycles (in the best case) before a finalizeable object can be reclaimed, and the garbage collector has to do extra work to invoke the finalizer. [1]
Sure, you're technically correct that if the objects all had finalizers that did the same thing as C++ destructors, it would be equivalent, but because of the existence of a GC we don't have to do any work for most objects. A GC is equivalent to an arena allocator in this sense.
Another point is the C++/Rust pattern of each object recursively freeing the objects it owns presumably leads to slower deallocation, because in the general case it involves pointer following and non-local access.
[1] https://www.ibm.com/developerworks/java/library/j-jtp01274/i...
[1]: https://docs.oracle.com/en/java/javase/14/docs/api/java.base...
No, C++ destructors are used for finalizers, not memory management.
Memory deallocation is a particular use case for finalizers which is avoided when performance is a concern.
> Another point is the C++/Rust pattern of each object recursively freeing the objects it owns presumably leads to slower deallocation, because in the general case it involves pointer following and non-local access.
No, a program that does pointer chasing and has to deallocate many small allocations is badly designed. If you are going to do that, using a GC language would be much better.
In the original comment I may have overstated this. I was ignoring the other uses of destructors because the context of the discussion was memory management. But memory management is a huge portion of what destructors do in C++. Consider a vector of strings (`vector<string>`). The destructor deallocates the memory for all the strings, then deallocates the memory for the vector.
> No, a program that does pointer chasing and has to deallocate many small allocations is badly designed. If you are going to do that, using a GC language would be much better.
How do you deallocate all of the nodes in a binary tree? As far as I can tell, you either have to pointer chase or use a custom allocation strategy. At some point with the second option, you're basically creating an ad-hoc garbage collector.
But I think we may be in vigorous agreement here, since my comment was about the general tradeoff between garbage collection and tracing data structures. I was trying to defend the original assertion that with tracing, "freeing the structure takes time proportional to the number of pointers in the structure it has to chase" while "garbage collection [or at least copy collection] takes time proportional to the live set".
A vector (or binary tree as you mentioned later) of heap allocated elements in a performance critical path is a likely candidate to be redesigned if possible.
> As far as I can tell, you either have to pointer chase or use a custom allocation strategy. At some point with the second option, you're basically creating an ad-hoc garbage collector.
A custom, ad-hoc strategy is the way to go if you need them dynamically allocated and performance at the same time, yeah.
I wouldn't call that a GC, though. A GC usually refers to a global solution.
> But I think we may be in vigorous agreement here
Sounds like it!
It is debatable whether using it is good or bad design, but at least the C++ std lib does offer a data structure which requires exactly this kind of deallocation: std::list and std::forward_list. And, given the cache characteristics of array VS linked list implementations, I would guess that most uses of std::list occur for huge lists that get written to often, as that seems to be the only case where the big-O advantage of list inster/delete would actually materialize into any performance benefit over a std::vector.
If the finalizers do something stupid like resurrect the object, have the runtime system notify someone with the authority to go beat the programmer with a stick.
Do you happen to offer beat the programmer with a stick as a service?
I was fooling with a cycle-collected reference counter for Rust for a while, but eventually gave up because of the difficulty in handling finalizers.
The JVM is notable in this regard. And thus, most classes that compile to Java bytecode offer no-finalizer semantics.
The biggest difference I know of is that the 'holds-resources' property does not propagate automatically like it does in C++. It's not that hard to always remember to call using(file = new File()) [...]. However, it's much easier to forget that you have a File field in your class which you initialize in the constructor, and so your class must itself be declared IDisposable/AutoCloseable etc.
Yes, but in practice tracing in a tracing GC is done concurrently and with the help of GC barriers that don't require synchronization and so are generally cheaper than the common mechanisms for reference-counting GC.
> and to invoke finalizers
As others have said, finalizers are very uncommon and, in fact, have been deprecated in Java.
Note that the problem appears in a different place: if your large structure is actually not garbage, then every GC pass will have to scan it to see what other objects it is keeping alive.
Isn't that incompatible with RAII though?
EDIT: and then I noticed that you mentioned RAII... Right, if the object own some sort of resources that doesn't apply.
Of course this is all somewhat tangential to the original topic of generational GCs, where the RAII idiom also has significant negative impacts. The performance characteristics would otherwise be O(n) based on the live set and thus similar to an arena allocator in terms of the ability to dispose of an arbitrarily large number of objects efficiently.
RAII is the only use case I was speaking of there. Way back up thread the original post I responded to was talking about arena allocators in comparison to a generational GC and finalizers. The point is that a generational GC doesn't handle finalizers well, but neither does an arena allocator!
> A garbage collector has to traverse the data structure in a similar way to determine whether it (and it's embedded keys and values) are part of the live set or not, and to invoke finalizers.
All garbage collectors start from live objects and only scan those. Then, whatever objects they have not scanned get collected. In copying collectors (like most generational ones), this means that garbage is never touched.
In the mark-and-sweep algorithms, the mark phase still never touches the unreachable objects. However, the sweep phase does need to return those objects to the free list, so it will have to walk them. It will still not do it the same way as malloc/free, as it can walk the heap in order and free unmarked objects as it encounters them, no need to follow pointers, so it may still have better cache performance.
Finalizers introduce extra difficulty, but still the behavior is fundamentally different. What usually happens is that objects which have finalizers are usually remembered in a special list which acts as a GC root itself. When they are only reachable from that list, they get marked so that the finalize will run (usually on a special Finalizer thread). When the Finalizer is finished, and assuming the object was not resurrected, they get removed from the Finalizer list, and now they are not reachable from anywhere at all, so the next GC will finally clean them up. Usually, there is also some API for user code to mark a Finalizable object as 'finalized', which essentially removed it from the Finalizer list early and allows it to be collected as normal, without going through the above process.
And yes, having a large number of finalizable objects in your memory is usually considered a very bad idea. Generally, they are only recommended as a fail-safe measure: you are supposed to do explicit cleaning, but as a fail-safe, to avoid your program crashing in production if a connection or file leak was missed, you also have the Finalizer to throw buckets of water out of your boat (but you should really notice that it is happening and plug that leak, rather then relying on the bucketeer).
Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount of memory collected is unimportant.
It's actually a lot to be said for rust that the ownership system lets you transfer freeing responsibility off-thread safely and cheaply in order to not have it block the critical path.
But overall, there's nothing really unexpected here, if you're familiar with memory management.