Garbage collecting seems to get solved in each new release of Go and Java, apparently.
The only other stable release that had any change to the GC worthy of mention in the release notes was 1.3, which was a minor change.
The only possible way to interpret your statement as true, would be if "get solved" meant ANY change or bug fix was applied to the GC. Which is a statement that would apply to so much code (not just the GC) that it would make the statement completely meaningless.
I wonder when we'll see a further GC update that trades latency for throughput...
The problem seems to be that no matter how you tweak GC, you will always have a class of program that it performs terribly for (and it seems to impact a large group of programs, never just some obscure corner case). So I suspect that this latest GC tweak will have unexpected results on some other class of program, leading to another tweak, and so on...
For casual use, most programs can treat GC like magic, but if you are doing serious work in a language with GC, then you should learn about the GC's characteristics. That bit of due diligence and up front design effort is still often going to be tons cheaper than doing the manual memory management.
Reducing latency in exchange for throughput is the right decision for the vast majority of programs that will be written in Go. It was already a very attractive language for writing a multiplayer game server, so long as I didn't have very large heaps. (Even so, I can still support 150-250 players and 10's of thousands of entities.) With the "tweak," that limitation is much relaxed.
Calling shenanigans. No it's not, unless the person doing the manual solution is a novice.
What GC often gets you is a program that doesn't crash but instead has performance problems, but these are often more easily profiled and found and less severe than a crash. (Manual memory management isn't immune from the same performance problems in any case.)
In other words, GC gets you to "Step 1 -- Get it Correct" faster so you can play with running code faster. The cost/benefit may not fit your situation. In that case, use a different tool.
(The page limit was 4. Organizers only raised it to 6 after seeing submitted papers.)
I can also confirm the “bit of due diligence” part, and the fact that it's cheaper that the aggravation of not having memory management at all. In the example that I can contribute to the discussion, the due diligence amounted to two more short articles: http://cristal.inria.fr/~doligez/publications/cuoq-doligez-m... and http://blog.frama-c.com/public/unmarshal.pdf
The solution to unclear or shared ownership is generally reference counting. There's a reason why shared_ptr is called that.
Reference counting is a form of automated memory management which can easily be integrated and used in a manually-managed system, and can be used for a specific subset of the in-memory structures (again see shared_ptr). Not so for more complex garbage collection systems which tend to interact badly with manual or ownership-based memory management. Putting the lie to your assertion that the only way to implement sharing in a non-GC language is "gratuitous copying".
That's just a pipe dream. I say this having spent inordinate amounts of time trying to tune myriad parameters in JVM GC for large heap systems without ultimate success. What it always comes down to is, how much extra physical RAM you're willing to burn to get some sort of predictable and acceptable pauses for GC. It's usually an unacceptable amount.
In the context of games, and other ones as well, I think there's too much attention paid to pushing the envelope and not enough to how much awesome can be had for what is readily available.
Patient: Doctor, it hurts when I do this!
Doctor: Don't do that!
Possibly, divide your heap into smaller pieces with their own GC? Restructure your system, such that most of your heap is persistent and exempt from GC? I don't know the details of the system you're trying to build, of course. It sounds interesting and challenging.
That's the common recommendation. (resisting calling it "pat answer"). Suffice it to say, this is not always possible. Apart from all the business related issues with rewriting a complex system from scratch, breaking up a large shared memory system into smaller, communicating processes multiplies both the software complexity (roughly by O(N^2) where N is the number of new components created) as well as hardware requirements in it's own right -- think of all the overhead of marshalling/demarshalling, communication latencies, thread managements, increased missed cache-hits because of fragmenting that nice giant cache you were hosting in that big JVM heap.
And on top of that, manual memory management is not free. I maintain a simple but high-throughput C++ server at Google, and tcmalloc is never less than 10-15% of our profiles.
Don't get me wrong, I'm not saying that Go is faster than C++ or ever will be. I'm just trying to counter the notion that "GC is expensive, manual memory management is near zero runtime cost."
But the very important difference here is that in your case you have a choice and it is possible to optimize the cost away and to otherwise control the characteristics of wheyou pay this cost. In GC systems it is never possible to do this completely. You can only sort of kind of try to prevent GC. It's not just a difference in magnitude, it's a categorical difference.
Of course we do not use std::string.
The first answer at https://www.quora.com/Is-tcmalloc-stable-enough-for-producti... (by Keith Adams) is completely consistent with what I've seen. Rust went with jemalloc for some reason too.
The CLR has also done a lot of GC work to enable concurrent GC, thread-local heaps, and "zero pause" (in reality extremely low constant time pauses).
The only way to avoid paying the cost for managing memory is to allocate everything you need once and never release it.
I always thought that malloc was further from free with GC :P
Go being one of them.
Others, Oberon family of languages, Modula-3, D, Eiffel and even .NET to a certain extent.
Having managed heap doesn't mean other allocation types aren't available.
It's not an either/or choice though, picking malloc or GC. There is a whole spectrum of allocation styles you can do that might be better for a particular application. For example, a server could use per-request memory pools, which effectively can turn related mallocs into a 'move the pointer forward' operation and the whole lot can be free()d together.
I'm not saying GC is worthless. I just have a distaste for GC because it doesn't truly deliver on the promise of removing worries about memory management. You still pay the cost and can be tripped up by nasty GC performance. Even worse, the garbage collector behaviour can change between language versions and a well-tested application can suddenly hit dire performance problems. Once you have to consider GC problems, IMO you might well be better off doing old fashioned app-controlled memory allocation.
which is usually for short lived objects only, and in a non-GC world these get put on the stack anyway.
This GC update in Go already trades latency for throughput, because of the added write barrier.
There is no free lunch in GC. Most features that reduce latency reduce throughput. For example, Azul C4 has lower throughput than HotSpot's GC does.
First, the code was rewritten from C to Go. Second, the GC was made precise, which is a major improvement to a GC.
The GC was not made truly concurrent however, and short pause times were not addressed either. These concerns are addressed in the 1.5 release.
The trade-off in 1.5 is to eliminate pause times for slightly worse throughput. For the programs Go is written to handle, this trade-off is probably fine.
I don't even see a mention of parallelism in that PDF. There's probably a lot of room left to squeeze out performance for Go.
Java has expanded into the big data space in recent years and underpins Hadoop, Spark, HBase, Cassandra etc where they are dealing with heap sizes up to 1TB. The previous GC algorithms are fine for smaller heaps (<32GB) but they needed something for bigger ones hence the introduction of G1GC.
Go is very much just trying to get their foundation GC perfected.
Also, a lot of performance can be gained be re-using frequently-allocated short-lived objects' memory, rather than freeing them without special treatment.
GC could actually be really useful in C++ or Rust for postponing the destruction of many small objects and doing it in one big sweep instead.
I've seen this claim before, but I've never understood it. You could add delayed reclamation to your system malloc if it actually helped things: just replace free() with a function that adds to a free list but doesn't actually recycle the memory. That wouldn't require more than a couple of writes and a TLS lookup.
I suspect that the reason why mallocs don't do this is that there's little benefit compared to just recycling the memory right away. Prompt reclamation is actually really nice for cache reasons, and adding memory blocks to a free list is what free's fast path does in the first place.
Now that's not to say that GC wouldn't be useful in C++ or Rust. I think what a GC would be useful for is for lock-free data structures and long-lived structures with dynamic lifetimes, especially ones shared between threads, to eliminate reference counting traffic. But for short-lived objects, if you have any sort of mark phase, you've already lost. Fundamentally, it's really hard to beat a system that precomputes the object lifetimes at compile time—which is what manual memory management is—with a dynamic system that has to compute them at runtime.
E.g. see "Safe and Efficient hybrid memory management for Java."
http://dl.acm.org/citation.cfm?id=2754185&CFID=694525936&CFT...
A GC with compactation gives you bump pointer allocation though. No need to traverse free lists. With malloc you potentially have short-lived and long-lived interspersed with each other, creating lots of holes/fragmentation.
> That wouldn't require more than a couple of writes and a TLS lookup.
While you can just null a reference with a single, unfenced write to something that's probably in your L1 cache already. Plus thread-local lists to avoid contention. Complexity grows quickly. It's not exactly free lunch.
You only get bump pointer allocation in the nursery, not in the tenured generation (unless you want an inefficient tenured generation). In a manually-managed system, short-lived objects usually aren't going to be allocated on the heap at all—they're on the stack. Even for the few that are allocated on the heap, the way free lists work does a great job of keeping them in cache.
Fragmentation really isn't much of a problem anymore with modern mallocs like jemalloc and tcmalloc.
> While you can just null a reference with a single, unfenced write to something that's probably in your L1 cache already. Plus thread-local lists to avoid contention.
I have a hard time believing that the cost of a TLS lookup and a couple of writes per freed object is more expensive than a Cheney scan for objects in the nursery.
This paper describes how it is possible if you are happy to throw a lot of memory at the problem:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49....
Section 3 is titled "Explicit freeing is more expensive".
That's not universally true; e.g. V8 can and does allocate pretenured objects in the old generation with bump-pointer allocation.
Here is a very stable one for C and C++:
But Boehm-Weiser's GC can parallelize marking, and store and restore the sweep phase for lower latencies, i.e. in incremental mode. http://www.hboehm.info/gc/gcdescr.html
Better GC's, Mark & Compact and Copying as used in more mature languages, are still on the horizon for Go. (If you go for larger heaps and more speed). I see it at just 30% done yet. Go controls its ABI, so it can easily use better GC's in the future.
http://jayconrod.com/posts/55/a-tour-of-v8-garbage-collectio... gives a good overview of good GC techniques, championed in earlier lisps and functional languages.
A GC still has those same delays when freeing a large object graph (assuming that large object graph is in the tenured generation). They're just sometimes incrementalized or done in a background thread. Your malloc implementation could do that too. If this were actually much of a problem, batched deallocation APIs that work on a background thread could be easily added to (or layered on top of!) the popular modern mallocs.
> Also, a lot of performance can be gained be re-using frequently-allocated short-lived objects' memory, rather than freeing them without special treatment.
Your malloc is already doing this, if it's any good. free is usually implemented with a free list.
Of course, I was just making an argument against 'immediately deallocating is always the best strategy'. It's clear that malloc()/free() could implement the same behaviour.
free is usually implemented with a free list.
Sorry, I was a bit vague: I was referring to moving garbage collectors, where one of the motivations was to be more performant with a lot of short-lived objects.
Best modern one might be Azul Systems' Vega Machines:
http://www.azulsystems.com/products/vega/overview
The LISP and Vega machines just try to solve the problem at its core. Works pretty well when you do that. The modern systems try to solve these hard problems on architectures, OS's, and apps that inherently suck at them. That's a difficult problem that requires constant attention by very smart people. Whole Ph.D.'s worth of effort were spent on getting this far with GC's.
- Reference counting/mark and sweep
- Throughput/latency
- RAII/GC
We present a formulation of the two algorithms that shows that
they are in fact duals of each other. Intuitively, the difference is that
tracing operates on live objects, or “matter”, while reference counting
operates on dead objects, or “anti-matter”.So you are going to have programs using 1PB of RAM across the cluster?