9 ms·
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 yo
by 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 agoAs 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 agoA 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 agoThat's why I said proportional.
- dumael 11y agoExcept 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 agoYou 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 agoYou 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 agoComparing 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 agoNot 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 agoI 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 agoGC 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.