Why would this outperform malloc for multi-threaded programs? Is that a property of GCd programs in general?
Edit: That is, is it typical for GCd programs to outperform manually-memory managed programs in multi-threaded environments?
back
4 comments
You can often trade space complexity for time complexity and concurrency. Garbage collectors typically require integer multiples of the memory footprint of manual memory management to offset the higher intrinsic computational cost of garbage collection algorithms. While malloc() has much less work to do, the default malloc() is often not that fast and it is possible in principle to design a garbage collector that can leverage space complexity to beat the generic malloc().
The caveat is that properly engineered C/C++ hardly ever uses malloc() or similar to manage memory. Relative performance in real systems would be between a garbage collector and one of myriad not-malloc() mechanisms typical of C/C++ that are much faster and often safer than using malloc().
If you are among that subset of programmers that uses malloc() ubiquitously, an argument might be made that a garbage collector is a better choice if you have plenty of memory. However, this argument would be about safety; if you are using malloc() ubiquitously then you obviously do not care about performance prima facie.
> The caveat is that properly engineered C/C++ hardly ever uses malloc() or similar to manage memory.
"Properly engineered" probably isn't the right term. C/C++ code written for speed would not perform heap allocation in its main processing. However, this is true with garbage collected languages as well.
Removing allocation means removing an entire class of data management operations from your program regardless of the language's memory architecture. It's a general speed-optimizing programming style that is irrelevant to manual vs automatic GC.
Relative performance in "real systems" written for speed would be a manual memory management language without using malloc/free, vs GC language without using allocation. However, the more interesting case is comparing real systems which do perform runtime allocation; it's highly dependent on the particular program's characteristics, but GC systems can be both a lot faster and simpler architecturally.
> "Properly engineered" probably isn't the right term. C/C++ code written for speed would not perform heap allocation in its main processing. However, this is true with garbage collected languages as well.
Not just code written for speed. Stack allocation is easier. There's not much that can go wrong. Heap allocations on the other hand you have to be careful not to leak or free multiple times or free a wrong pointer. So after you've debugged one too many of these bugs, you learn to avoid heap allocations where possible just to make your own life easier.
(This is my experience with C, I don't have enough experience with C++ to know whether it sufficiently takes care of some of that complexity to the point where heap allocation becomes as easy as stack allocation.)
While you're right in theory, it's typically much less feasible to avoid heap allocations in garbage-collected languages. Systems programmers typically manually promote heap allocations to stack allocations in ways that common escape analysis algorithms cannot prove safe (for example, those involving higher order functions).
>However, this is true with garbage collected languages as well.
In theory - in practice trying to avoid GC in managed languages is like putting on a straightjacket, eg. JVM doesn't even have value types, and higher level languages - just forget about it :D
The closest I realistically got to this is C# and even then there are all sort of caveats because even if your code doesn't allocate it's a standard pattern to not care about allocation and stuff allocates all over the place and there are no tools to figure out what allocates and what doesn't from code so you just have to assume everything does unless you wrote it or read/profiled it.
Oberon, Oberon-2, Component Pascal, Modula-3, D, Eiffel all provide C++ like value types.
Arrays, records, objects can be stored on the global segment, stack or heap. So they stress the GC as much as new/malloc stress the C/C++ memory manager.
This is an argument I don't understand. It is exceedingly common for performance sensitive applications in GC environments not to allocate either, because quite simply allocating/deallocating in any environment is expensive.
Why in the world is it fair to compare C/C++ programs that don't allocate to Java/C# ones that do? Another way of saying this is if you are using new ubiquitously then you obviously do not care about performance prima facie.
At the end of the day GC'd versus manual memory debates seem to fall into 2 axis. Complexity vs correctness and total memory available vs concurrent access to said memory.
At this point in time the difference in performance between a C application and a Java one comes down to correctness and access to low level memory layout primitives, not GC vs manual memory.
I think the primary reason is an accident of history. There was a time where Java programmers were encouraged to not even think about allocation deallocation: "dont worry about it, we have it all covered, use it as freely as free love". The result of all that was a lot of bloated poorly performing software that paid no attention to how much allocations they were making. I still see the effects of that propaganda on many junior programmers. GC makes it safe, not free, and that message was never stressed as much it should have been.
The other reason is that languages that make you allocate explicitly with some burdensome syntax, that allocation is in your face, you cannot be unaware of it. Whereas in other languages someone may be blissfully unaware and still churn out pieces of usable software. The bite comes much later. On languages that were not designed around garbage collection, it is usually a whole lot harder to avoid allocation.
There were other factors at play during this time which roughly coincided with the Dot Come Boom/Bust. In those days it was ship or die, "money was no object" (unintentional pun) and Sun would be happy to spend people out of their perf well by adding more cpus and ram.
That and Java not having value types.
> This is an argument I don't understand. It is exceedingly common for performance sensitive applications in GC environments not to allocate either, because quite simply allocating/deallocating in any environment is expensive.
Is that possible? I thought all objects are heap allocated in Java?
Primitives aren't allocated. This is why we have `int` and `Integer`; Integer is a boxed int. Java has a fair amount of sugar around doing the change automagically.
Also escape analysis is a thing Java can do to avoid heap allocating objects in general: https://docs.oracle.com/javase/7/docs/technotes/guides/vm/pe...
Fun fact! Original Java, before they started adding autoboxing, had precisely one place which did heap allocation: the 'new' keyword (which is why it was a keyword). If you avoided the keyword, you could be sure you weren't using the heap.
...which meant you could run (a limited subset of) Java programs on very, very small devices. 8-bit microcontrollers. Such as Maxim's iButton devices, or smart cards.
My memory says that the standard is called kJava, but it seems to be ungoogleable these days, so I could be wrong (and Oracle ate all of Sun's documentation).
They are. So don't reallocate them. Just use mutable objects that can be reset and object pools. (This has its own obvious drawbacks.)
No this is bad advice in general! It causes the objects to permanently escape, with the knock-on that any objects stored in that object will also escape etc etc, and to move to the old generation. If you need objects, allocate and use them where you need them. This is more likely to allow scalar replacement, or at least more efficient collection while still in the young generation.
True, but object pools enables you to reuse objects, which in turn allows you to avoid or postpone GC (if done correctly).
But object pools prevent escape analysis and scalar replacement of objects, which wouldn't create garbage in the first place.
Malloc() is easy to write in multi-threaded environments. You can just have per-thread pools of allocable memory, which is what most multi-threaded mallocs do. Free() on the other hand isn't. Among other things, what do you do when you free an object? You can return the freed memory to the local pool of the thread that does the free() operation, but that can result in pathological behavior when, e.g. one thread consistently allocates objects while another frees them. In that case, a bunch of free memory accumulates in one thread. Production multi-threaded allocs have mechanisms to rebalance these per-thread pools, but that involves synchronization overhead.
If most objects die before a GC cycle, it can be faster to just stop all threads and reclaim that memory in bulk as Boehm does.
That seems independent of tracing GC versus manual memory management, though, doesn't it? jemalloc/tcmalloc could stop all threads and flush pools in bulk as well if it decided that it was faster to do so. (From looking at the code, jemalloc doesn't, but it could.)
More broadly, if batched deallocation is indeed faster, you can get that behavior in a manually memory-managed scenario. You aren't forced into prompt reclamation. It's just that prompt reclamation is usually faster for cache reasons and improves memory consumption, so malloc implementations take advantage of the opportunity.
Fans of GC claim that GC outperforms malloc() based on some studies that were done a long time ago. The argument is that repeated malloc/frees are less efficient than a bunch of GC allocs and then a single garbage collection.
The reality seems to be a bit different. In practice GC programs tend to use significantly more memory which can impact performance. And the trend towards low GC pause times costs additional CPU. Beyond that we're now using much larger multi gigabyte GC memory pools which can also lead to poor GC performance.
So overall people these days see lower performance with GC systems compared to malloc.
Many of the claims that GC outperforms manual memory management compare running dlmalloc to allocate all data with a well-tuned generational garbage collector on something like the Da Capo benchmark suite. Naturally, they find that the ability to get bump allocation in the nursery of a good generational GC ends up outperforming a malloc implementation that was never really designed for that kind of workload.
But the real question, in my mind, is whether a well-tuned systems-level program that uses stack, arena, and heap allocation with a good allocator like jemalloc ends up being better with a garbage collector. And it's really hard for me to see how that could possibly be the case. Performance-conscious systems programmers will use the stack as their nursery, gaining all the benefits of the nursery without the copying, tracing, or delayed reclamation. Modern mallocs like jemalloc or tcmalloc are incredibly good at minimizing fragmentation and satisfying requests quickly, using thread-local caches to avoid synchronization. Most of the time, the tenured generation needs the same bookkeeping that a modern malloc does, so you're not really gaining anything by using GC for that generation. And a GC always has some kind of mark or tracing phase (not to mention at least a write barrier if you want your pause times to be reasonable), which is pure overhead over manual memory management.
Yes, but in a language like Modula-3 you can have your "well-tuned systems-level program that uses stack, arena, and heap allocation with a good allocator", and still have a GC at your disposal.
Sadly HP/Compaq killed the Olivetti/Digital unit and Modula-3 died, but its ideas can still be applied in modern languages, assuming similar capabilities.
Please cite some evidence. As a GC fan, I'm interested in this question. (In my opinion, GC is more than worth the cost.)
They are only talking about slow, conservative, stop-the-world collectors there.
They have to scan the full heap. You shouldn't compare apples with oranges.
I find the methodology of the research to be solid, the collectors to be representative of the different approaches in the field and the conclusions to be consistent with the gut feeling from experience:
"With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%."
> In practice GC programs tend to use significantly more memory which can impact performance
In which language ?
There are GC enabled programming languages with global and stack static allocation, for example Oberon just to cite one, which was on top HN a few days ago.
Prove it.
That all depends on how you manually manage memory. Older versions of malloc performed poorly with frequent allocations.
Bohem GC allocates in large(ish) slabs, so it can manage many small objects more efficiently than OS malloc. Modern malloc replacements like jemalloc also do this for manual allocation.