Hacker News Reader

Comment by raphaelj | Hacker News Reader

A generational GC is way more efficient than `std::shared_ptr`. `std::shared_ptr` is implementing a reference counting garbage collection, which is like the most inefficient way of implementing a GC.

FYI: - Allocating memory in a generational GC is as fast as allocating something on the stack. It's basically changing the value in a register. It's order of magnitude faster than calling `malloc()`. - A generational garbage collection is slower than freeing a stack frame, but has a lower per item overhead than calling `free()`.

tl;dr: for most programs, generational GCs are the fastest at allocating dynamic memory.

View on HN

Yeah, but all that efficiency in allocation is paid for on the back end when all threads using the same heap grind to a screeching halt to do GC. Real world applications (incl. web apps at scale) do not need to perform allocations fast. They do need to run within strict space and time constraints. Value semantics and smart pointers guarantee these constraints. GC does not.

GC doesn't preclude value semantics or lack deterministic release of resources, not all languages are Java.

Also not all GC algorithms imply stop the world.

Regarding RC, it still is a GC algorithm, and Herb Sutter had a nice presentation where he shown how a cascade release of resources with RC algorithms can lead to indeterministic release time and worse, stack overflow.

> A generational GC is way more efficient than `std::shared_ptr`

that's true, but it's also a moot point because std::shared_ptr is almost never the semantics you want. You want std::unique_ptr.

Also, you can get away without allocating memory dynamically in a lot of cases (thus not incurring overhead of malloc).

After C++11 and Rust I'm starting to think garbage collection is holding us back from doing research into better approaches to automatic memory management.

The main problem with std::shared_ptr as a library type, is not being able to forbid developers to call get() or pass a reference or pointer to it.

agreed, but that doesn't affect performance (i was responding to grandparent's performance argument).

> that's true, but it's also a moot point because std::shared_ptr is almost never the semantics you want. You want std::unique_ptr.

unique_ptr still has the malloc()/free()[1] overhead, I'm assuming the parent poster just misspoke. One major issue with shared_ptr (which unique_ptr doesn't have) is that it must work properly when different threads have different shared_ptr's (copies of each other) pointing to the same object. This adds overhead.

> Also, you can get away without allocating memory dynamically in a lot of cases (thus not incurring overhead of malloc).

Ok, but we're specifically talking about GC and RC here, so I don't see why you'd bring that up.

> After C++11 and Rust I'm starting to think garbage collection is holding us back from doing research into better approaches to automatic memory management.

GC literally is automatic memory management. (And as others have pointed out, so RC is a form of GC.)

Also, there's lots and lots of research into various different ways of doing automatic memory management.

[1] Alright, they don't literally use malloc/free, but you know what I mean.

> Ok, but we're specifically talking about GC and RC here, so I don't see why you'd bring that up.

well, my point was, in garbage-collected languages you don't have the option to never even engage the garbage collector by creating variables on the stack, while in languages like C++ you can avoid the overhead of malloc/free by using stack variables.

> GC literally is automatic memory management.

It is, but there are other approaches to automatic memory management that don't introduce another entity that does stuff to your program at runtime. C++'s smart pointers is one such approach, see also Automatic Reference Counting and Rust's borrow checking. I wish there was more research done into compile-time techniques to prevent resource leaks.

> well, my point was, in garbage-collected languages you don't have the option to never even engage the garbage collector by creating variables on the stack, while in languages like C++ you can avoid the overhead of malloc/free by using stack variables.

Oh, I see. I can see what you mean, but there are solid techniques for avoiding GC in e.g. JVM-based langauges -- for an example see e.g. Disruptor/Aeron.

I'll happily grant that it's a problem that it can be quite hard to see if you're actually avoiding GC when using these patterns. It'd be interesting if there were a "@no-gc" annotation which could enforce such patterns on the source code. (So, essentially you'd have a compile-time "GC by default, but you can opt-out and the compiler will tell you when you violate that". One can dream.)

Calling malloc is not that expensive if you're using jemalloc or any other modern allocator. And with generational GC allocation is not just a register increment because Java has mandatory object initialization and all objects will be pushed to 2nd gen heap eventually. std::shared_ptr is quite fast when been used correctly (no excessive sharing between threads and no abusing).

Not all languages have Java's constraints, and "using something correctly" necessarily implies a cognitive cost, which might is probably less than the cognitive cost of optimizing around a GC, but worse than not optimizing at all (which is often appropriate for the majority of code paths through most applications).

Because calling malloc() & free() is expensive? That's just an implementation detail of your reference-counting GC or malloc(). You can also just pre-allocate memory in batches which makes allocation just changing a pointer to some pre-allocated memory.

Many reference based GC's do that, e.g. perl. Or have I entirely misunderstood your comment?

malloc and free are indeed far more expensive than allocation in a runtime system with copying GC.

One problem amongst several with allocating memory in batches (or using a pool allocation scheme) is that you end up making poor use of the cache. After a while you have a lot of free memory mixed up with the used memory in your pool (see the article - the generational hypothesis), but because it's spread out a lot of that unused memory gets loaded into cache lines when accessing the memory which is still being used.

Having said all that, pool allocators can work really well for certain workloads, especially client-server stuff. Apache uses a pool allocator for serving requests. Pool allocators also fit well with languages like C/C++, but that's just because those languages are very poorly suited to GC, there are much better designed languages which integrate better with modern GC.

> A generational garbage collection is slower than freeing a stack frame, but has a lower per item overhead than calling `free()`.

Almost, but not always. The Cheney on the MTA [1] paper describes a generational GC where the first generation is the stack. So for collections on the first generation, collection is equivalent to clearing a stack frame.

[1] http://dl.acm.org/citation.cfm?doid=214448.214454

I don't think you quite understand the problem... The cost isn't in literally freeing objects but in doing the mark/{sweep,copy}. So Cheney's collection is not equivalent to decrementing the stack pointer.

The only special things about the stack per se are a) arena[0] allocation and b) special ISA and OS support. When people say "stack allocation" the important points are (a) as well as c) static lifetime analysis. These are different concepts: Rust, for example, achieves (c) on the heap as well as the native stack.

[0] I.e., three-pointer, although for the stack the OS manages at least one of them

Your conclusion may be correct, but you're confusing "generational" GC with "copying" GC. There can be generational GCs that use freelists (eg. Boehm) and copying GCs that are not generational (I think the first copying GC for Smalltalk was like that).

>It's order of magnitude faster than calling `malloc()`

That depends on the underlying heap, Microsoft Low Fragmentation Heap is very fast for example.

The big plus with reference counting is that you (can) get a very attractive scoped release of resources.

Reply on news.ycombinator.com