7 ms·

Having worked with all sorts of GCs in the past, I basically stopped using them altogether some years ago in favor of manual memory management. I have to say, i

Having worked with all sorts of GCs in the past, I basically stopped using them altogether some years ago in favor of manual memory management. I have to say, it's been liberating and so much easier to write performant code since I know what memory I need instead of relying on the computer to guess (and giving the computer hints as to how to guess). I have no doubt that GC research and systems is making good forward progress, but I can't imagine myself using them again.

pron 11y ago
I love GCs. They give you better memory throughput (in exchange for more footprint and higher latency, although latency can be made rather low), and they let you build and use very scalable concurrent data structures. On large machines with lots of cores and lots of RAM, they let you work with large, in-memory data sets very efficiently.
- duaneb 11y ago
  As with everything in engineering, this is a tradeoff. Not all access patterns work well with mark-and-sweep (or equivalent full traversal patterns). In particular, without needing to release or allocate memory, a GC pass wastes cycles. Furthermore, data structures must be compatible with the GC: traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running. Generational garbage collection helps this, but for large numbers of pointers, you're going to see performance decrease unless at some point you move the pointers out of collection contention--think an allocation pool to reduce the depth of traversal early. I believe google just released a library to help with this, though the semantics are specific enough you could easily make your problems much worse. GC is never a flat win.
  - pron 11y ago
    > traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running. That's not quite how it works. Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking). I do agree there are tradeoffs, but they're much more nuanced than that. There is certainly a footprint tradeoff, and there is a latency tradeoff (that can be mitigated).
    - vitalyd 11y ago
      A card in the card table covers more than one object, so the entire dirty card needs to be scanned. Card marks only help with old->young references, and stack based roots still need to be visited each time, irrespective of what happened in the last collection.
      - pron 11y ago
        That's why I said proportional.
      - dumael 11y ago
        Except card marking (this region of the heap was changed) is only one way of flagging changes. It's entire possible to instead record the address of objects unconditionally and then flag them as they are visiting during a generation.
        vitalyd 11y ago
        You could but it's likely to perform worse for common case. Where are you going to record the addresses? How are you going to size that buffer? Card table is fixed size, and doesn't care whether you're using compressed pointers or full blown word sized ones. Cards also benefit from cache locality if recording objects in the same card. Marking a card clean is dirt cheap, and incremental cleaning is cheaper than removing entries individually from an exact buffer. The downside to card marking is the impreciseness but with java being very reference heavy, I don't know how much that is a problem. Secondary problem is false sharing of memory when multiple mutators write in there; Hotspot, e.g. has a special flag to enable conditional marking, but it's not on by default.
    - duaneb 11y ago
      > Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking). True. I was just trying to make the point that GC comes with complexity cost, and this should be considered—it's not "free" for an arbitrary algorithm.
- banachtarski 11y ago
  You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. Having lots of cores and lots of RAM just means you can eat the cost more easily. It just means you can afford to let the VM do the work instead of the programmer. Also, no matter how much RAM you have, cache sizes are more or less the same, and cache line misses hurt.
  - pron 11y ago
    > You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They are much, much (much) faster than malloc/free. They do however increase the frequency of young-gen so they have an indirect cost. When it comes to throughput (i.e. total time the application spends doing memory management), modern GCs handily beat malloc/free. What you can do, however, with manual memory management is all sorts of arena allocations, but then you have to be careful when sharing pointers (Rust helps with that). Then there's the question of concurrent data structures, that are very, very hard to do well without a GC. > cache line misses hurt. What does that have to do with GCs? If anything, copying GCs bring related objects together, so the prefetcher can help. What affects cache misses (in Java) is the lack of arrays-of-structs, which is scheduled to be fixed, with the addition of value types, in Java 10.
    - banachtarski 11y ago
      Comparing to malloc and free directly isn't very useful because that's pretty much the worst way to manage memory. Aside from memory arenas, you can just pool memory or preallocate too. I think concurrent data structures have very niche usage in practice (compared to say, a thread safe system). >> cache line misses hurt. > What does that have to do with GCs? Everything. Sure you can use a copying GC and hope related objects go together. I tell the compiler to lump them together and exploit the prefetcher wherever possible.
- Dewie3 11y ago
  Not to mention that you get to hire performance engineers. People may have overestimated their utility (that they are good for less things then commonly thought). Maybe not to the degree that the stereotypical C/++ would believe, but still an overestimation. Maybe we just need to use more abstractions in the middle between manual and fully automatic memory management, like region-based memory management (just an example).
  - pcwalton 11y ago
    I think the solution is to use the right memory management tool for the job. pron is right that GC can be helpful for concurrent data structures (where the non-GC approach, hazard pointers, is basically just a GC), for instance. GC is also great when your objects have truly dynamic lifetime, such as open files in Unix from the kernel's point of view. But GC for all data tends to be overkill when your goal is to maximize performance: a pure number-crunching workload like a triangle rasterizer has no need for GC, since the memory management is so trivial that it's better for the programmer to manually specify it (and, ideally, have the compiler check that) than for the program to spend cycles figuring it out at runtime. So, in my view, the best memory management discipline is a flexible one that allows the choice between automatic and manual memory management on a case-by-case basis.
    - vitalyd 11y ago
      GC does help with ABA style concurrent problems, and it also simplifies the places where you simply don't care (slow/uncommon paths). But concurrent data structures are a special case, and likely, not always the best anyway since even though they scale much better than locks, with enough writers and cores, the cache coherence traffic is going to swamp the application. I do agree with the flexibility comment. A hybrid environment where you can pick and choose the mem mgmt strategy (and, very important, not pay in perf for things you're not using) would be great.
      - pron 11y ago
        > GC does help with ABA style concurrent problems I wasn't just referring to that. GC helps with pretty much any concurrent data structure, lock-free or not. For example, read-write locks don't scale too well (certainly no beyond the core count we're quickly coming up against on servers), and GC enables easy optimistic locking.
bd_at_rivenhill 11y ago
I think we will start to see less use of GCs in mobile going forward, especially now that Apple has deprecated GC in favor of automatic reference counting. The issues caused by the interaction between the memory hierarchy and the fragmentation that is naturally introduced by GC are difficult to measure, but nevertheless an important component of performance.
- pjmlp 11y ago
  Lets not forget they did that, because they failed to produce a stable working GC for Objective-C.
  - Drdrdrq 11y ago
    Lets not forget Java failed to produce that too, they just dont seem to care. :)
    - pjmlp 11y ago
      I didn't notice that JVM's GC do segfault all the time, with erratic behaviour depending on the libraries being linked.
  - vitalyd 11y ago
    A performant GC for mobile is inherently a much harder problem than for servers.
- banachtarski 11y ago
  Reference counting is still not the same as manual memory management, and there is a heavy cost to reference counting as well. Reference counting trades throughput for latency relative to a garbage collected runtime.
pjmlp 11y ago
Manual memory management only works in small teams with highly skilled developers, and even then there is a reason why so many CVE exploits are related to memory corruption. Even those highly skilled developers aren't failure prof.
- duaneb 11y ago
  Manual memory management (i.e. not GC) is a little disingenuous because it implies that it's entirely manual. In fact, there are many patterns (e.g. RAII) which make "brain dead" manual memory management possible. I'm not necessarily arguing this is a great way to go for a new team, but there are manual memory management strategies that can definitely scale. Among other things, it's not the only type of resource that needs managing, and GC only handles memory.
  - banachtarski 11y ago
    Agreed. Sometimes, you don't even need RAII. You just let the stack unwind :) But yes, RAII can make it pretty braindead (which is good)
    - TheLoneWolfling 11y ago
      Or arena allocation - which, by the way, is something I wish was more supported in mainstream languages
    - PopeOfNope 11y ago
      Do you have any book suggestions for learning modern C++ memory management techniques? I'm beginning to think maybe it's time to fill that gap in my programming knowledge.
      - banachtarski 11y ago
        Hmm, modern C++ memory management is not entirely different from before. You have std::unique_ptr which is a game changer. I recommend just learning the language itself well. The C++ Primer (latest edition) plus Effective Modern C++ would be a good start. Also, read that doc floating around about everything a programmer needs to know about memory.

pron 11y ago

I love GCs. They give you better memory throughput (in exchange for more footprint and higher latency, although latency can be made rather low), and they let you build and use very scalable concurrent data structures. On large machines with lots of cores and lots of RAM, they let you work with large, in-memory data sets very efficiently.

duaneb 11y ago
As with everything in engineering, this is a tradeoff. Not all access patterns work well with mark-and-sweep (or equivalent full traversal patterns). In particular, without needing to release or allocate memory, a GC pass wastes cycles. Furthermore, data structures must be compatible with the GC: traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running. Generational garbage collection helps this, but for large numbers of pointers, you're going to see performance decrease unless at some point you move the pointers out of collection contention--think an allocation pool to reduce the depth of traversal early. I believe google just released a library to help with this, though the semantics are specific enough you could easily make your problems much worse. GC is never a flat win.
- pron 11y ago
  > traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running. That's not quite how it works. Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking). I do agree there are tradeoffs, but they're much more nuanced than that. There is certainly a footprint tradeoff, and there is a latency tradeoff (that can be mitigated).
  - vitalyd 11y ago
    A card in the card table covers more than one object, so the entire dirty card needs to be scanned. Card marks only help with old->young references, and stack based roots still need to be visited each time, irrespective of what happened in the last collection.
    - pron 11y ago
      That's why I said proportional.
    - dumael 11y ago
      Except card marking (this region of the heap was changed) is only one way of flagging changes. It's entire possible to instead record the address of objects unconditionally and then flag them as they are visiting during a generation.
      - vitalyd 11y ago
        You could but it's likely to perform worse for common case. Where are you going to record the addresses? How are you going to size that buffer? Card table is fixed size, and doesn't care whether you're using compressed pointers or full blown word sized ones. Cards also benefit from cache locality if recording objects in the same card. Marking a card clean is dirt cheap, and incremental cleaning is cheaper than removing entries individually from an exact buffer. The downside to card marking is the impreciseness but with java being very reference heavy, I don't know how much that is a problem. Secondary problem is false sharing of memory when multiple mutators write in there; Hotspot, e.g. has a special flag to enable conditional marking, but it's not on by default.
  - duaneb 11y ago
    > Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking). True. I was just trying to make the point that GC comes with complexity cost, and this should be considered—it's not "free" for an arbitrary algorithm.
banachtarski 11y ago
You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. Having lots of cores and lots of RAM just means you can eat the cost more easily. It just means you can afford to let the VM do the work instead of the programmer. Also, no matter how much RAM you have, cache sizes are more or less the same, and cache line misses hurt.
- pron 11y ago
  > You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They are much, much (much) faster than malloc/free. They do however increase the frequency of young-gen so they have an indirect cost. When it comes to throughput (i.e. total time the application spends doing memory management), modern GCs handily beat malloc/free. What you can do, however, with manual memory management is all sorts of arena allocations, but then you have to be careful when sharing pointers (Rust helps with that). Then there's the question of concurrent data structures, that are very, very hard to do well without a GC. > cache line misses hurt. What does that have to do with GCs? If anything, copying GCs bring related objects together, so the prefetcher can help. What affects cache misses (in Java) is the lack of arrays-of-structs, which is scheduled to be fixed, with the addition of value types, in Java 10.
  - banachtarski 11y ago
    Comparing to malloc and free directly isn't very useful because that's pretty much the worst way to manage memory. Aside from memory arenas, you can just pool memory or preallocate too. I think concurrent data structures have very niche usage in practice (compared to say, a thread safe system). >> cache line misses hurt. > What does that have to do with GCs? Everything. Sure you can use a copying GC and hope related objects go together. I tell the compiler to lump them together and exploit the prefetcher wherever possible.
Dewie3 11y ago
Not to mention that you get to hire performance engineers. People may have overestimated their utility (that they are good for less things then commonly thought). Maybe not to the degree that the stereotypical C/++ would believe, but still an overestimation. Maybe we just need to use more abstractions in the middle between manual and fully automatic memory management, like region-based memory management (just an example).
- pcwalton 11y ago
  I think the solution is to use the right memory management tool for the job. pron is right that GC can be helpful for concurrent data structures (where the non-GC approach, hazard pointers, is basically just a GC), for instance. GC is also great when your objects have truly dynamic lifetime, such as open files in Unix from the kernel's point of view. But GC for all data tends to be overkill when your goal is to maximize performance: a pure number-crunching workload like a triangle rasterizer has no need for GC, since the memory management is so trivial that it's better for the programmer to manually specify it (and, ideally, have the compiler check that) than for the program to spend cycles figuring it out at runtime. So, in my view, the best memory management discipline is a flexible one that allows the choice between automatic and manual memory management on a case-by-case basis.
  - vitalyd 11y ago
    GC does help with ABA style concurrent problems, and it also simplifies the places where you simply don't care (slow/uncommon paths). But concurrent data structures are a special case, and likely, not always the best anyway since even though they scale much better than locks, with enough writers and cores, the cache coherence traffic is going to swamp the application. I do agree with the flexibility comment. A hybrid environment where you can pick and choose the mem mgmt strategy (and, very important, not pay in perf for things you're not using) would be great.
    - pron 11y ago
      > GC does help with ABA style concurrent problems I wasn't just referring to that. GC helps with pretty much any concurrent data structure, lock-free or not. For example, read-write locks don't scale too well (certainly no beyond the core count we're quickly coming up against on servers), and GC enables easy optimistic locking.

bd_at_rivenhill 11y ago

I think we will start to see less use of GCs in mobile going forward, especially now that Apple has deprecated GC in favor of automatic reference counting. The issues caused by the interaction between the memory hierarchy and the fragmentation that is naturally introduced by GC are difficult to measure, but nevertheless an important component of performance.

pjmlp 11y ago
Lets not forget they did that, because they failed to produce a stable working GC for Objective-C.
- Drdrdrq 11y ago
  Lets not forget Java failed to produce that too, they just dont seem to care. :)
  - pjmlp 11y ago
    I didn't notice that JVM's GC do segfault all the time, with erratic behaviour depending on the libraries being linked.
- vitalyd 11y ago
  A performant GC for mobile is inherently a much harder problem than for servers.
banachtarski 11y ago
Reference counting is still not the same as manual memory management, and there is a heavy cost to reference counting as well. Reference counting trades throughput for latency relative to a garbage collected runtime.

pjmlp 11y ago

Manual memory management only works in small teams with highly skilled developers, and even then there is a reason why so many CVE exploits are related to memory corruption. Even those highly skilled developers aren't failure prof.

duaneb 11y ago
Manual memory management (i.e. not GC) is a little disingenuous because it implies that it's entirely manual. In fact, there are many patterns (e.g. RAII) which make "brain dead" manual memory management possible. I'm not necessarily arguing this is a great way to go for a new team, but there are manual memory management strategies that can definitely scale. Among other things, it's not the only type of resource that needs managing, and GC only handles memory.
- banachtarski 11y ago
  Agreed. Sometimes, you don't even need RAII. You just let the stack unwind :) But yes, RAII can make it pretty braindead (which is good)
  - TheLoneWolfling 11y ago
    Or arena allocation - which, by the way, is something I wish was more supported in mainstream languages
  - PopeOfNope 11y ago
    Do you have any book suggestions for learning modern C++ memory management techniques? I'm beginning to think maybe it's time to fill that gap in my programming knowledge.
    - banachtarski 11y ago
      Hmm, modern C++ memory management is not entirely different from before. You have std::unique_ptr which is a game changer. I recommend just learning the language itself well. The C++ Primer (latest edition) plus Effective Modern C++ would be a good start. Also, read that doc floating around about everything a programmer needs to know about memory.