5 ms·

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 mos

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.

avar 10y ago
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?
- Kutta 10y ago
  malloc and free are indeed far more expensive than allocation in a runtime system with copying GC.
- rwmj 10y ago
  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.
chaotic-good 10y ago
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).
- weberc2 10y ago
  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).
bitwize 10y ago
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.
- pjmlp 10y ago
  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.
ThatGeoGuy 10y ago
> 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 http://dl.acm.org/citation.cfm?doid=214448.214454
- belovedeagle 10y ago
  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
- deleted 10y ago
  [deleted]
walkingolof 10y ago
>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.
nice_byte 10y ago
> 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.
- pjmlp 10y ago
  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.
  - nice_byte 10y ago
    agreed, but that doesn't affect performance (i was responding to grandparent's performance argument).
- lomnakkus 10y ago
  > 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.
  - 10y ago
stevefolta 10y ago
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).

avar 10y ago

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?

Kutta 10y ago
malloc and free are indeed far more expensive than allocation in a runtime system with copying GC.
rwmj 10y ago
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.

chaotic-good 10y ago

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

weberc2 10y ago
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).

bitwize 10y ago

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.

pjmlp 10y ago
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.

ThatGeoGuy 10y ago

> 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 http://dl.acm.org/citation.cfm?doid=214448.214454

belovedeagle 10y ago
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
deleted 10y ago
[deleted]

walkingolof 10y ago

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

nice_byte 10y ago

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

pjmlp 10y ago
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.
- nice_byte 10y ago
  agreed, but that doesn't affect performance (i was responding to grandparent's performance argument).
lomnakkus 10y ago
> 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.
- 10y ago

stevefolta 10y ago

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