3 ms·
When talking about Garbage Collection they claim that "Even languages with highly optimized garbage collectors can’t match the performance of non-GC’d languages
by rwmj 8y ago
When talking about Garbage Collection they claim that "Even languages with highly optimized garbage collectors can’t match the performance of non-GC’d languages" and link to this paper: http://greenlab.di.uminho.pt/wp-content/uploads/2017/09/paperSLE.pdf http://greenlab.di.uminho.pt/wp-content/uploads/2017/09/pape... However I cannot see where this paper supports the assertion (although Rust comes out well).
The particular problem is that malloc/free is not free of charge. Different allocators have complex internal implementations, plus you lose easy sharing of complex structures and compaction. So if you're using a GC you probably program in a different way, eg using more shared immutable structures, exploiting the advantages of GC.
Edit: A bit later they brush off this old favourite for GC-haters: https://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf https://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf claiming that GC requires 5x as much memory. The problem with this paper is it assumes that malloc/free is cost-free and instantaneous, and that your programmer always calls free at the exact moment that the memory is no longer needed, both of which are extremely unrealistic.
- whyever 8y ago> that your programmer always calls free at the exact moment that the memory is no longer needed I think this is not so unrealistic if you use RAII.
- naasking 8y agoEven then. There's nothing stopping you from placing a loop in the same scope as an object that's not used in or after the loop.
- pjmlp 8y agoHerb Sutter has a nice talk about how RAII can cause stack overflows or stop-the-world pauses if used badly. https://www.youtube.com/watch?v=JfmTagWcqoE https://www.youtube.com/watch?v=JfmTagWcqoE
- mrec 8y agoAgreed. I suspect a more useful distinction would be "...can't match the performance of languages that facilitate stack allocation" - the main advantage comes from locality of reference rather than tighter heap management. There's a separate point that could be made about the memory headroom needed for GC to work well, but (sadly) I don't think many people think of memory-efficiency as a performance metric these days. I'm not sure about your > So if you're using a GC you probably program in a different way, eg using more shared immutable structures This is definitely not the case for mainstream GC languages like Java, which have truly awful support for immutability, to the point of having to write a separate type if you want it.
- rwmj 8y agoAgreed about Java. However in OCaml or Haskell it allows elegant immutable tree structures with maximal sharing between versions.
- SilasX 8y agoSorry if OT, but the nand2tetris course really brought the benefits of stack vs heap allocation into stark relief. As part of the course, you have to implement a compiler and OS, including malloc/free [1]. You can see how local variables just push something onto the stack, which is a small number of CPU instructions, while malloc is a big function, each step of which translates into many instructions, and which also has to deal with iterating through a data structure to find a big enough block. Part 8: Implementing the virtual machine, where you do stack allocation/calls: https://www.nand2tetris.org/project08 https://www.nand2tetris.org/project08 Part 12: Implementing the OS, where you add the malloc/free utilities (Memory.jack): https://www.nand2tetris.org/project12 https://www.nand2tetris.org/project12 [1] It calls them alloc and deAlloc in the course.
- deleted 8y ago[deleted]
- jasode 8y ago>The particular problem is that malloc/free is not free of charge. [...] The problem with this paper is it assumes that malloc/free is cost-free and instantaneous, I think I get that you're trying to explain how GC overhead is overstated and malloc()/free() is understated but your angle about "malloc not being free of charge" it isn't really the evidence you want to use. As analogy, we can see that a Lamborghini is faster than a Hyundai. Let's say we state that the performance comparison is flawed because it it still takes the Lamborghini a non-zero amount of time to accelerate to 60 mph (or 100 km/hr) and Lamborghini is still consuming gasoline. While the cost datapoints are true, it still doesn't change the macro observation that the Hyundai is slower. Also, you're misrepresenting the 2nd paper you cited. The authors do mention "overhead" of malloc. They do not assume that malloc is "cost-free" on page 4: >3.2 malloc Overhead - When using allocators implemented in C, the oracular memory manager invokes allocation and deallocation functions through the Jikes VM SysCall foreign function call interface. While not free, these calls do not incur as much overhead as JNI invocations. Their total cost is just 11 instructions: six loads and stores, three registerto-register moves, one load-immediate, and one jump. This cost is similar to that of invoking memory operations in C and C++, where malloc and free are functions defined in an external library (e.g., libc.so). In other words, even if malloc/free is not instantaneous and not cost-free, it can still be faster than GC. Neither paper's conclusions depend on malloc/free taking zero amounts of time or zero cpu instructions. If the papers are flawed, you have to explain it using different logic.
- pjmlp 8y agoYet several companies on the tourism world circuit happen to use semi-automatic gear boxes that outperform any human driving with manual, so much for the typical car comparisasions.
- vardump 8y ago> >3.2 malloc Overhead - When using allocators implemented in C... That's not even about malloc overhead, it's about the overhead of just calling C malloc. So actual malloc overhead is on top of that. Malloc and free have pretty unpredictable runtime over time, once a lot of allocations and deallocations have been performed. That's why you don't use either in latency sensitive code, like with realtime requirements. > In other words, even if malloc/free is not instantaneous and not cost-free, it can still be faster than GC. Whoah, faster than GC in what regard? GC will probably win the throughput race, or average latency. Manual allocation will likely win the jitter race, lower latency standard deviation. (I write low level code in C/C++, including kernel drivers and bare metal firmware with hard realtime requirements. Hopefully in the future in Rust or some other memory and concurrency safe language.)
- pjmlp 8y agoAlso another point is that even GC languages do happen to support value types, stack, global memory allocation, manual memory management in unsafe code and memory slices. So putting all on the same bag doesn't work quite well.
- rbehrends 8y agoThis can be easily illustrated using this example [1], which uses both the Boehm GC (v8.0.2) and jemalloc (v5.0.1), directly installed via Homebrew, as well as the system malloc on macOS to implement the binary trees benchmark from the benchmark game. The benchmark keeps a large live set and allocates aggressively, making it an unattractive scenario for many GCs. The Boehm GC is being run with the following four distinct configurations: - Four marker threads in parallel, trading CPU time for wall clock time and lower pause times. - Single-threaded marking. - GC disabled, all memory is freed explicitly. - Incremental collection (using virtual memory). The results, run on a Macbook Pro with a six core 2.6 GHz Core i7: $ make benchmark DEPTH=21 # jemalloc explicit malloc()/free() /usr/bin/time ./btree-jemalloc 21 >/dev/null 17.53 real 17.40 user 0.11 sys # Boehm GC with four parallel marker threads GC_MARKERS=4 /usr/bin/time ./btree-gc 21 >/dev/null 8.50 real 10.87 user 0.09 sys # Boehm GC with single-threaded marking GC_MARKERS=1 /usr/bin/time ./btree-gc 21 >/dev/null 10.40 real 10.33 user 0.05 sys # Boehm GC with explicit deallocation GC_MARKERS=1 /usr/bin/time ./btree-gc-free 21 >/dev/null 11.75 real 11.70 user 0.04 sys # Boehm GC with incremental collection (single-threaded) /usr/bin/time ./btree-gc-inc 21 >/dev/null 18.39 real 16.40 user 5.11 sys # System malloc()/free() /usr/bin/time ./btree-sysmalloc 21 >/dev/null 64.43 real 63.69 user 0.71 sys Obviously, one should not read too much into this, as this is a very specific scenario with its own very specific allocation behavior that will not match other use cases. And one can speed up this specific example easily with a specialized allocator (as all allocations have the same size and predictable lifetime). Plus, different GCs make different tradeoffs, and so do general purpose manual allocators. But for throughput at least, the worries about GC overhead tend to be exaggerated. In practice, any language with proper value types will also spend only a fairly small fraction on allocation and garbage collection, so overhead becomes less of a problem. [1] https://gist.github.com/rbehrends/528fc713c24195b1c8aefda074b281ec https://gist.github.com/rbehrends/528fc713c24195b1c8aefda074...