Hacker News Reader

Comment by chowells | Hacker News Reader

I said generational/compacting collector. You're talking about a mark and sweep collector.

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.

View on HN

How are finalizers invoked if the structure isn't traversed? Would it just be optimized away none of the objects have finalizers? Hence my suggestion about the area allocators being a better point of comparison.

My understanding is that finalizers are special cased for a generational GC, have a tendency to introduce significant overhead, and (as with any GC scheme) generally run at unpredictable times. My impression is that RAII idioms are strongly discouraged in conjunction with most GC ecosystems.

Actually, RAII idioms are generally encouraged, but finalizers are not. For the rare few classes that hold resources in GC languages, the Resource is usually Acquired at Initialization as well, and released in a special method (IDisposable.Dispose() in C#, AutoCloseable.Close() in Java). There is also usually some special syntax for automatically calling this syntax when the object exits some scope, though that scope usually has to be declared by the user (using(), try-with-resources, with() in Python etc.).

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.

This is a really good point. I had completely overlooked various deterministic resource cleanup idioms as being equivalent to RAII in all but name.

Many languages allow a class to avoid declaring a finalized, for just this reason.

The JVM is notable in this regard. And thus, most classes that compile to Java bytecode offer no-finalizer semantics.

Java is an example of a language with a generational copy collector by default. Most objects in Java don't have a finalizer, since after all the main point of, for example, destructors in C++ is to make sure you don't leak memory, which the GC solves. But when the `finalize` method is used is causes significant overhead.

> 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...

Which is why finalizers in Java have been officially deprecated [1] and might be removed altogether in a future release.

[1]: https://docs.oracle.com/en/java/javase/14/docs/api/java.base...

Unfortunately, the alternative they recommend (Cleaner) only exists since Java 9, so it cannot be used by libraries that wish to remain compatible with Java 8 (which, in my experience, is most or all of them; so far, I haven't seen any Java library which has dropped compatibility with Java 8, and many only recently dropped compatibility with Java 6 or 7).

The actual alternative is PhantomReference, which exists since ancient times. Cleaner simply provides safe way to use PhantomReferences, which are rather tricky to use (by Java standards).

Destructors in C++ aren't just for making sure you leak memory. They are used for many lifetime controlled things such as: 1. general resource cleanup (file handle, database connection, etc.) using RAII (Resource Aquisition Is Initialization); 2. tracing function entry/exit.

Apparently, that doesn't work in Rust: https://news.ycombinator.com/item?id=23363647

It does work in rust. you just cannot rely on Drop for memory-safety. If you mem::forget a struct that holds onto some other resource then all that means is that you're committing that resource to the lifetime of the process. We usually call that a leak but it can be intentional.

By that argument, it doesn't work in C++ either because std::unique_ptr::release() exists.

In the JVM the equivalent to RAII is implemented with try-with-resource/Autocloseable instead.

In my experience, try-with-resources is inferior to RAII, since it's very easy to forget (that is, it's very easy to do "Foo x = bar();" instead of "try (Foo x = bar()) { ... }"), leading to resource leaks. More than once I have added a finalizer to an AutoCloseable class just to warn loudly if close() hasn't been called; unfortunately, there's no way that I know of to suppress the finalizer once close() is called, so the GC still has to do all the work to call the finalizer even when the class was used correctly.

> after all the main point of, for example, destructors in C++ is to make sure you don't leak memory, which the GC solves

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.

> 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.

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.

> No, C++ destructors are used for finalizers, not memory management.

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".

> Consider a vector of strings (`vector<string>`). The destructor deallocates the memory for all the strings, then deallocates the memory for the vector.

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!

Maintain a collection of objects with finalizers associated with the generation; when an object is moved out of the generation, move the finalizer record with it. Then, just before the generation is discarded, run the finalizers.

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.

Interestingly for the Rust GC I'm working both Drop and finalizers will be supported.

Do you happen to offer beat the programmer with a stick as a service?

Unfortunately, no, but you are going to need it.

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.

Even mark-and-sweep collectors only mark starting from GC roots, they don't mark through unreachable objects.

Reply on news.ycombinator.com