Comment by celrod | Hacker News Reader

Comment by celrod | Hacker News Reader

The RCU use case is convincing, but my experience with GCs in other situations has been poor. To me, this reads more like an argument for bespoke memory management solutions being able to yield the best performance (I agree!), which is a totally different case from the more general static lifetimes generally outperforming dynamic lifetimes (especially when a tracing step is needed to determine liveness).

> Lies people believe... Calling free() gives the memory back to the OS.

I believe calling `free()` gives the memory back to the allocator, which is much better than giving it to the OS; syscalls are slow. Perhaps not immediately; mimalloc only makes frees available to future `malloc`s periodically.

Trying a simple benchmark where I allocate and then immediately `free` 800 bytes, 1 million times, and counting the number of unique pointers I get: glibc's malloc: 1 jemalloc: 1 mimalloc: 4 Julia's garbage collector: 62767

62767, at about 48 MiB, isn't that bad, but it still blows out my computer's L3 cache. Using a GC basically guarantees every new allocation is from RAM, rather than cache. This kills performance of any heavily allocating code; we don't care only about how fast memory management can work, but how quickly we can worth with what it gives us. I gave a benchmark in Julia showcasing this: https://discourse.julialang.org/t/blog-post-rust-vs-julia-in...

Malloc/free gives you a chance at staying hot, if your actual working memory is small enough.

Allocators like mimalloc are also designed (like the compacting GC) to have successive allocations be close together. The 4 unique pointers I got from mimalloc were 896 bytes apart.

My opinions might be less sour if I had more experience with compacting GCs, but I think GCs are just a vastly more complicated solution to the problem of safe memory management than something like Rust's borrow checker. Given that the complexity is foisted on the compiler and runtime developers, that's normally not so bad for users, and an acceptable tradeoff when writing code that isn't performance sensitive. Similarly, RAII with static lifetimes is also a reasonable tradeoff for code not important enough for more bespoke approaches. The articles example is evidently one of those deserving a more bespoke solution.

It's really not enough to just say that a GC gave you more pointers = it has worse cache locality. Compacting GC almost always has better cache utilization than malloc, because heap fragmentation over long-running programs will waste TLB cache entries and slack space between objects. A bump allocator from a compacting GC will give you a new pointer for each allocation because free doesn't reclaim the memory...but those allocations will be sequentially, and if you were in the case where you are churning through your heap and only ever touch the most recent object they will always be in cache still. Benchmarking the knock-on effects of allocators and GCs are insanely difficult and I'm very skeptical of basically any synthetic benchmarks like this.

I think the fact that it is complicated to reason about is precisely why systems developers don’t trust GC’s.

It’s far easier to write a threadsafe bump (slab) allocator than to locate and diagnose the code that someone wrote two years ago and, as of last week, started causing the GC to blow up the cache, contend on a lock, fragment the heap, add unbounded pauses, burn an extra cpu, etc, etc.

(Though, at this point, most mallocs are so good that the slab allocator loses anyway and there’s no need to bother.)

compaction really does help runtimes alot. but I'm not sure how much it really has to do with line level locality. in general we don't try to batch related objects together except in a coarse form by generation.

I think the measurable benefit comes from page level savings, both reducing the number of trips to the kernel to get zeroes pages, and from reduced pressure on the tlb.

but I have definitely seen numbers like 20% on some workloads for turning on compaction

> in general we don't try to batch related objects together except in a coarse form by generation.

It greatly depends on the GC algorithm, right? Copying collectors naturally bunch up related objects (though of course, in which order is less well defined, if one object has multiple pointers to others).

FWIW, that synthetic benchmark was reflective of some real world code we were deploying. Using malloc/free for one function led to something like a 2x performance improvement of the whole program.

I think it's important to differentiate between malloc implementations/algorithms, just like it's important to differentiate between GCs. E.g., mimalloc "shards" size classes into pages, with separate free lists per page. This way, subsequent allocations are all from the same page. Freeing does not free eagerly; only if the entire page is freed, or if we hit a new allocation and the page is empty, then it can hit a periodic slow path to do deferred work. https://www.microsoft.com/en-us/research/uploads/prod/2019/0...

Good malloc implementations can also employ techniques to avoid fragmentation. It's unfortunate that the defaults are bad.

But I confess, compacting GCs and profiling the effects of heap fragmentation (especially over time in long running programs) are both things I lack experience in. Microbenchmarks are unlikely to capture that accurately.

If we are talking long running multithreaded processes, then libc malloc have issues that isn't even fragmentation. There are many workloads when it seems to forget to return whole empty pages and just accumulate allocated areas despite them being totally empty.

> Compacting GC almost always has better cache utilization than malloc

...only if you put each object into its own heap allocation, which is a dumb thing to do in manual memory management. Typically you'd group many related objects of the same type tightly packed into the same allocation and loop over them in sequence to make proper use of prefetching.

The programmer will always have a better idea how objects are going to be used compared to an automatic memory management solution, and even with a GC it makes a lot of sense to use arrays of value types for better memory layout control.

The post explains why this works in the RCU context, why it sucks in general, and then just writes it off and ignores it.

> At this point, some folks fire back with non-arguments about how this isn’t “real” garbage collection. Like, uh, because you manually mark the garbage!

Yeah. People's concerns are that the process of figuring out what memory is not longer used is inefficient and non-deterministic relative to simply telling the allocator when you're done with a resource. I've never met someone who's been concerned with deferring deallocation.

Sure traversing the whole live set is rare and we've spent 30 years tweaking GC algorithms to make them better, and now they're practically sentient. However this statement either willfully or unintentionally writes off the thing people actually have an issue with. If you run into GC issues in your services you have to bring in a shaman to tweak things here and there hoping it sends the angry spirits back to the shadow realm.

If you're just marking the garbage and being notified when it's no longer used, that entire process is gone.

Yes, it can be very fast to allocate memory in a GC. This ignores the cost of marking and compaction that actually need to be amortized in to get a fair comparison.

The other big issue people have with GC is that in general it requires significantly more memory than manual memory management to achieve equivalent performance. And you have to have a bunch of extra CPU power to throw at redundantly checking if things are still referenced over and over. And you have to be okay with a bunch of extra memory copies for optimistic compaction.

Finally the post criticizes manual memory management (Rust's Arc/Rc) as being necessary when you have unclear lifetimes - but ignores that you basically build the exact same infrastructure in GC'd languages to close external resources as you can't rely on finalizers ever being called.

Anyways this has been beaten to death for the last 20-30 years and this article doesn't seem to bring anything new to the table besides ignoring the legitimate concerns of a GC using memes, which is fine because memes are fun IMO.

The correct answer is exactly what you say - there is no general correct answer. You use the tool appropriate to the job to meet the design constraints of the system.

> I've never met someone who's been concerned with deferring deallocation.

Realtime audio processing (instruments and effects), where malloc/free can never be called on the realtime audio thread. Deallocations have to be deferred.

If it matters for realtime audio, I cannot imagine that it would not matter for twitch games as well.

In non-GC languages the audio thread can be kept running even when changing audio plugins, as long as allocations and deallocations are not performed on the audio thread.

Realtime audio synthesis is possible in .net; but no memory allocations can occur anywhere in the entire realtime audio process. It is possible to write allocation-free message queues between a UI process and a realtime process. If allocations do occur in the realtime audio process, the realtime thread has to be suspended at some point in order to grab object references on the stack of the realtime thread -- a process that can take 2ms or more in .net GCs (which is more than enough to case audio dropouts).[1]

Many of the systems I have seen that need to be deterministic and fast but still need to allocate will use pool allocators or slab allocators. The edge cases mean that malloc/free is not in the conversation. I suppose that pre-allocating objects and deferring deallocation would also work, but that seems roughly equivalent to pool allocation.

The null allocator is the fastest allocator, though!

Yes. Lots of pool allocators as well. :-)

The principle application is making changes to Audio plugin chains without stopping the real-time audio thread. The new chain has to be pre-allocated, and the old chain has to be sent off-thread to get deallocated on a deferred basis. You can't pool-allocate a VST or an LV2 audio plugin.

Data subscriptions (Audio VU data and control port values) also use a similar deferred deallocation scheme. Doing so allows use of mutexes and shared ptrs in dependent non-realtime data structures.

That would suggest expensive destructors. It makes a lot of sense to put the destructor on a helper thread.

> > I've never met someone who's been concerned with deferring deallocation.

> Realtime audio processing (instruments and effects), where malloc/free can never be called on the realtime audio thread. Deallocations have to be deferred.

I think you misunderstood GP, they are saying “I’ve never met someone who thinks deferred deallocation is a bad thing”, ie. you’re agreeing with them.

This makes no sense to me. In a generational GC gen-0 is more likely than not to be cached — and that’s where the ‘churn’ is. Outside of that, any longer lived allocations are by definition not easy to control cache-wise.

Locality is one of the big wins for GCs, the only issue I’m aware of is the ‘stop the world’ mark/sweep (yes, I know modern GCs have a background thread — but you still get stop-the-world events afaik)

Modern collectors have stop-the-world pause times in the millisecond range (aiming for less), even for very large heaps. Allocating threads may also incur allocation stalls, also in the millisecond range. However, these collectors need additional barriers in the application, and the concurrently running collector competes with the application for resources even if the application is not paused. Meaningful comparisons are difficult.

The problem is not only how long the pause takes but also the fact it pauses all the things. In manual memory management even if you have to spend some time in allocation / deallocation, it affects only the allocating thread. A thread that doesn’t allocate doesn’t pause.

With current concurrent collectors, the stop-the-world pauses are so short that they approach the pause times processes encounter for other reasons on untuned systems.

But I meant something else: it's not always clear whether low-pause collectors are a win. A totally made-up example: Is it worthwhile to add 2ms processing time to every request to avoid that every 7 to 10 minutes, there is a 20% chance that there is a garbage collection that delays all requests currently in flight by 40ms?

How much more memory bandwidth does that require?

> I believe calling `free()` gives the memory back to the allocator, which is much better than giving it to the OS

Having to deal with memory fragmentation in long running servers is no fun at all, especially internal fragmentation of pages maintained by slab allocators.

this is not a very common problem, but it is a hard one to deal with.

Fragmentation rarely wastes more than 20% memory and 50% is extremely unlikely. But with tracing GC you’re often wasting 4-5x right from the start. Maybe it’s not called fragmentation, but the room needed for the GC to run efficiently is also waste. Plus all the headers in the objects to keep the marking flags also addup.

If cache usage is that major of a concern, arena allocation works just as well as it does with manual memory allocation. Thankfully there aren't too many areas where garbage collection has to compete with such conveniently contrived examples.

>> My opinions might be less sour if I had more experience with compacting GCs

I have quite a bit of experience with the GC in .NET. For projects that deal with large data structures, the GC is something that you are always thinking about though it's behavior is conceptually transparent. I think I would ultimately prefer a more explicit approach.

free() gives back memory to your local POSIX. :)

Reply on news.ycombinator.com