Distilling the Real Cost of Production Garbage Collectors [pdf]
users.cecs.anu.edu.au
users.cecs.anu.edu.au
Haven't quite finished reading the paper yet, but it's interesting so far.
While they present a method that could be applied more widely, this paper is only analyzing current tracing GCs in OpenJDK (plus Epsilon GC). Would love to see future papers taking other GCs into account (e.g., various flavors of refcount GC).
Even better would be a way to compare vs methods of "manual" memory management (manual alloc/free, RAII/scope based alloc/free, arena allocation, etc.). Unfortunately, non-GC memory management is very application specific, so I'm not sure if a generalized analysis would be super useful.
I've personally found Rust to be a very difficult language to learn and become productive in.
In contrast, I was able to jump into Swift and become productive very quickly.
Swift isn't GC, but is reference counted. Reference cycles will lead to leaked memory.
So what's interesting is to know GC's overhead relative to what: Reference counted languages like Swift? Or languages like Rust?
More importantly: Is the overhead worth it? Developer time is valuable; thus leading to the critical question: What's cheaper, extra developer time or a more powerful computer?
GC is often an umbrella term that includes reference counting.
Almost all serious tracing GCs include some aspect of reference counting, and almost all serious reference counting GCs include some aspect of tracing.
With reference counting there are no pauses, and memory is reclaimed immediately. It allows for strongly coupling deallocation with resource cleanup. (The consequence is higher overhead maintaining counts, and leaked reference cycles.)
In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
Reference counting is widely considered one strategy of garbage collection (https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...). For that matter, some GCs that are primarily tracing also use ref counts for some portion of the heap, as an optimization (just as some primarily refcounting GCs also run a trace to clean up cycles).
Also, reference counting can certainly result in pauses, when large graphs of interconnected objects are reclaimed. On the upside, you know when a pause might happen. You still don't know for certain without explicitly keeping track of what is about to be freed, which would add additional overhead, and indeed may not be practical or even feasible.
You can't guarantee both of these properties at once, in the general case. Consider a very large tree of objects which are referenced through a single root node, and then that root node becomes eligible for reclamation. For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later.
Using pointers to make up a graph is a choice. It is a thing taught in CS classes, so it may feel comfortably familiar; that does not make it good. I never do.
There are lots of things you can do in GCed language to avoid allocations and avoid running the GC when it matters.
But the thing is, I can switch GC implementation according to my needs.
If throughput is my number 1 concern I can use ParalellGC, if not I can use ZGC. Or G1 if I want something in between (not sure if the paper picks up the huge drop in overhead of G1 in Java 18).
Region-based memory management is commonly used, for example, with per-frame heaps in games, or per-request heaps in servers; but in those cases memory is not reclaimed immediately. The MLKit implements Standard ML with regions instead of garbage collection, though recent versions also have GC.
In practice, manually memory managed languages always conflate memory and other resources. A File object is not just a block of memory, it's also a file descriptor, etc. So you have to run the destructors at the 'right' times and can't just toss the memory. In special cases where you control every allocation, sure, but often that isn't practical.
Also, though, it's very unusual to install an arena allocator as a replacement for malloc and (as a no-op) free — malloc has no way to specify which of possibly several arenas you want to allocate in, arena allocators suck at realloc, and writing an arena allocator that invokes malloc to get its arena is significantly easier than writing one that uses a variety of platform-specific calls depending on compilation options. Instead, you write your own arena allocation functions (h_alloc or apr_palloc or whatever), and then you invoke them explicitly, in your own code. Non-arena-aware library code will just keep invoking malloc as usual.
The case where you might end up with library code invoking your arena allocator is where you supply your allocator as an argument to something — like C++ STL containers or, again, APR pools, for example with apr_pool_create_ex. But that still doesn't mean you have to depend on the allocator to invoke finalizers — after all, the standard library operator new and operator delete don't invoke finalizers, instead relying on other finalizers (destructors) to invoke finalizers and then invoke operator free. That still works — your files still get closed — even if the "operator free" is a nop because you're allocating out of an arena. In that case you don't get the major benefit of arena allocation (fast constant-time reclamation of the whole arena), just the minor ones, no fragmentation and fast constant-time allocation.
A more useful strategy is often to attach your finalizers to the arena instead of allocations within it; in the case of apr_palloc you can do this by creating subpools with apr_pool_create and attaching cleanup functions to them with apr_pool_userdata_set.
Regardless, my claim was more restricted than the one you're arguing against. I claimed that arena allocation can guarantee both that there are no pauses and that memory is reclaimed immediately in this case, where you have an arbirarily large tree of objects that dies at a single point in time, and in many similar cases. This is what wgd was claiming was impossible in their second claim: "For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later." That claim is not true.
As far as I know, however, wgd's first and less general claim is true: there's no way to extend this region-based strategy even to the general case of immediate memory reclamation without losing the constant-time guarantee, much less the even more general case of immediate execution of arbitrary finalizers. (By contrast, reference counting can guarantee immediate memory reclamation and immediate execution of arbitrary finalizers, although at the cost of unbounded pauses, and not in the general case because it can't handle cycles.) Obviously you can't execute an unbounded number of finalizers in constant or even bounded time, or call close() on an unbounded number of file descriptors in constant or even bounded time.
But that doesn't mean you can't reclaim an unbounded number of memory allocations in constant time. You can, it's a useful thing to do, and people do it all the time. If you've fetched an URL from Apache today you've done it yourself, even if you didn't know it.
That's predictable and can be planned for: You can hold onto the reference until you get to a point where the pause is acceptable.
You can't do that in a garbage collected language, because you have no control over when the garbage collector will pause. (In theory your application can explicitly trigger a garbage collection, but in practice such behavior is discouraged.)
How are you reclaiming cycles with no pauses?
It smacks of poor discipline, or poor design.
(Also, in the sense of releasing a cycle, that would be pretty quick, since a typical RC implementation is just going to leak it. Its where a large graph resource graph is successfully ref-counted to 0 that can cause a pause, theoretically, although that's another case I've not seen.)
I'm not a fan of RC, myself. It's space-hungry, it creates unnecessary write traffic, it's unreliable (when you can have cycles), and it's slow. But there are lots of "not sound" and "not general" but "pragmatic" language implementations out there using it, without tracing. In practice, even.
I RC'd a thing in a program, five years back. The program had a linked list in it. Increments and decrements happened on a scale of minutes. I did not agonize over it.
For example, heap allocated closures for functions with non-local references create a cycle when a pointer to the closure is stored in a non-local environment.
You have to be aware that cycles can cause issues and you have to think about the impact of cycles on whatever you're doing.
I don't think this is a particularly fruitful line of discussion to strongly claim that cycles can just be avoided, or worse, that you're an idiot for having them. It's needlessly inflammatory.
Point is just that people get used to whatever they were directed to do for their CS class assignments, and get to thinking it is natural, and even unavoidable.
That something somebody is used to not thinking about is not actually necessary can be a novel and fruitful idea. The cheapest GC is always no GC at all.
> The cheapest GC is always no GC at all.
I kind of chuckle here because the Virgil compiler proves you manifestly right and wrong simultaneously; it's a fully GC'd, semi-functional language with a self-hosted compiler written entirely in the language. Incidentally, in a careful style that doesn't allocate a whole lot or create a lot of garbage. It chooses efficient, C-like data structures for IRs and doesn't waste a lot of time on Java-like armored classes because I am sick of wasting my life on that. It bootstraps in less than 200MB of memory, compiling the entire compiler at full optimization in a single whole program compilation. Because I made the dumbest, simplest Cheney moving GC, without even generations, it doesn't even have a write barrier. But because it only allocates 200MB, when bootstrapping it doesn't even GC once. It's basically a giant, single region that is thrown away at process exit, and the mutator doesn't pay the cost of a single write barrier. (And the funny thing is, GC wouldn't even find that much garbage, because only about half of the heap does actually die, primarily because it's mostly IR that is always reachable--it's a whole program compiler, after all). It's basically your mythical perfect GC just because it has enough memory and I am damn well in my rights to spend it as I have.
I'm going to time this thread out now because I'd rather continue not thinking about memory management until I cycle back on GC work, and I don't really see any evidence that you're listening. Besides, I've said it better with code and the machine seems to happily hum along to my music.
Same with GC. "Stop the world" may be a characteristic of a simple GC, but it's entirely possible to have GC that works by "coloring" objects.
> In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
You only need to implement IDisposable if you are dealing with unmanaged resources (ie. non-GC objects). But it's the same with C/C++: you have to call `free()` or `delete`; The difference is that managed resources are auto-released for you.
> With reference counting there are no pauses
You can still have pauses of arbitrary duration with ref counting. When the last reference to an object that is the sole owner of a large graph of other objects gets decremented, the entire object graph must be immediately deallocated. It's possible for a single dereference to trigger an unbounded amount of deallocation.
> and memory is reclaimed immediately.
Most production-quality ref counting implementations defer tracking references on the stack to minimize ref count churn. That significantly improves performance but it means you can no longer claim that the system always reclaims memory "immediately".
> In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
Managing non-memory resources is orthogonal to tracing versus ref counting. If you choose to tie a resource's lifetime to a piece of memory's lifetime then, yes, the memory manager's deallocation policy becomes user-visible.
I think you would get a lot out of reading "A Unified Theory of Garbage Collection".
Two things:
1. Unbounded may be technically true, but it's really not a hard problem to ensure that time-critical runtime deallocations either rarely happen or are simply never huge chains of objects that release each other. Source: Used C++ & boost::shared_ptr/boost::weak_ptr extensively in game development and never had unexpected jank due to deallocations.
2. There's no actual reason that the full deallocation needs to happen immediately in all reference counting implementations. If you have hard time or latency constraints you could queue up the actual dereferencing and ensure that you only dereference a certain number of objects per time period.
Yes, #2 changes some assumptions about when objects will be dereferenced; in C++ one might rely on guarantees that objects are immediately released along with associated resources. But if you go into a project knowing that it needed to support deferred reference counting, manually releasing critical resources is hardly the worst thing you'd need to do.
Sure, but now you're essentially in the same business as someone using a GC finds themselves where they are tuning the GC, using object pools, etc.
> There's no actual reason that the full deallocation needs to happen immediately in all reference counting implementations. If you have hard time or latency constraints you could queue up the actual dereferencing and ensure that you only dereference a certain number of objects per time period.
Yup, that's a common optimization. But now you have given up the property that destruction happens immediately and deterministically.
My overall point is that the benefits of ref counting are not without cost. There are trade-offs and as you make different ones to improve performance or latency, you quickly discover that your ref counting system starts to take on shades of tracing GC with both the benefits and downsides that that entails.
There's no "tuning of the GC" beyond that, though, unless you count linking in a faster multithreaded malloc library, which is another thing that I've tried.
What's problematic about Java in particular in relation to latency is that Java's libraries can be pointlessly wasteful with regard to allocating garbage. I found that a function that was supposed to call through to a system function that got the system time in milliseconds was somehow allocating an object and discarding it as part of the call. The function returned an integer.
I found this when my Android JNI (C++) app was getting janky because of GC pauses, and I traced the allocation to that function. I wrote a quick JNI function in C++ to call the system and return the integer directly, and the jank went away.
The best GC in the world won't make up for wasteful allocations, and some languages (or their ecosystems?) seem to encourage rampant allocations.
When people say "with reference counting there are no pauses", they are not talking about the bookkeeping cost of releasing the allocations when their last reference is dropped; they are talking about unrelated code (which might for instance be running a tight numerical loop with no allocation or deallocation at all) being arbitrarily stopped.
Also, it's misleading to call the amount of deallocation "unbounded". The amount of deallocation is precisely the size of the graph of objects being released at that point; no more, no less.
Still, it usually works out, especially when lowering peak memory increases performance on its own.
I'm not sure that you can claim that confidently. I have certainly seen many people laboring under the false assumption that ref counting systems always have bounded, small latency when that isn't the case. The latency may be much lower than various other tracing GC alternatives, but I think many people have a simplistic mental model that a ref count decrement only ever leads to a single object being freed.
There is an ah-ha moment when you point out that freeing an object decrements its outgoing references, which can in turn cause a cascade of frees.
> they are talking about unrelated code (which might for instance be running a tight numerical loop with no allocation or deallocation at all) being arbitrarily stopped.
Many GCs will never arbitrarily stop the program in a tight loop that isn't doing allocations, so there's nothing particularly unique about ref counting here.
> Also, it's misleading to call the amount of deallocation "unbounded". The amount of deallocation is precisely the size of the graph of objects being released at that point; no more, no less.
Sure, and a program can build object graphs of arbitrary size. That's what "unbounded" means: there is no pre-defined bound on it.
Something else people often don't realize is that malloc/free aren't instant. Why is de-referring a large object graph slow, well, mostly because free is slow. Why is free slow, because the internals of a malloc can be rather sophisticated. There is probably locking, there may be internal book-keeping like coalescing free regions inside the heap and so on.
If you look at modern GC benchmark workloads, they're often generating gigabytes of allocations per second. Good luck shoving that much work through a typical malloc! Big companies like Google have had to write their own mallocs for a good reason.
True, and the costs vary wildly and are deeply tied into the rest of the memory management strategy.
In a copying collector, free() is essentially free: It takes the same amount of time to free 1 object in the semispace as it does 1,000 objects in the same semispace.
Swift doesn't do this, if I understood what you meant properly. I suppose you might want to defer freeing some things to idle time but it's usually not a problem in my experience. I'm honestly surprised it always comes up.
There's "autorelease pools" in ObjC but they aren't used to move releasing to an idle time, rather it's to handle cases where nobody knows what the precise lifetime of the allocation is. Swift has a better ABI that doesn't have that issue.
I think Swift can take advantage of the fact that many values are purely stack allocated and don't touch the heap or ref counting system at all. It leans pretty heavily on structs and value types.
Other managed languages are more Java-esque in that basically every value is in principle heap allocated. In those, I think it's more valuable to defer ref counting stack references since there are many more of them and they tend to be frequently mutated.
That is why, as Apple decided to fix of their ARC optmizations, they had a talk at WWDC 2021 about ARC gotchas for code that will behave in a different way due to the new optimizations.
"ARC in Swift: Basics and beyond"
It's more like the old version of the optimizations were just heuristics (so they didn't work that well) and the new versions are formally proven, meaning they're more aggressive and found some memory safety holes in C/ObjC APIs.
Autorelease is a no-op when using automatic reference counting. (But it was a pretty cool concept back then.)
What you can't do is message autorelease yourself - although of course you can escape that pretty easily.
In rc/arc you can achieve the same by making release a no-op.
You can't achieve that with reference counting, with malloc/free, or with a non-copying tracing collector. You can achieve it with regions.
On the other hand, you may not need to. Allocating and initializing those objects took O(MN) time, so your program can't get an asymptotic speedup by deallocating them in O(1) time instead of O(MN) time. So it really depends on the constant factors, which nowadays depend strongly on things like cache miss rates and cache line sharing between cores.
While tracing is considered to have better throughput and reference counting to have a lower footprint, as the liked paper shows, they are really on a spectrum of techniques with different tradeoffs.
In strict computer science parlance, refcounting is a kind of GC, but to most people GC refers to "tracing GC" specifically. It's fairly pedantic.
> In a garbage collected language you need to explicitly release your resources.
I assume "resources" here must mean "non-memory resources"? Even still, GC can apply to any kind of resource, it's just most popularly applied to memory (you could have a GC for file handles, for example).
Also, so you know, the user you're replying to knows a thing or two about programming languages.
I don't know about the Java world but in Common Lisp GC there's no reference counting whatsoever.
I would bet my house that some implementation of Common Lisp somewhere has a GC that uses card marking, which is a form of reference counting.
So the question is whether one-off developer time is cheaper than SRE time for the useful lifetime of the service.
However, it gets worse for GC: depending on the application, developing for a GC can be much more difficult / expensive than manual memory management (or reference counting). The canonical examples are low latency (with SLAs on the order of a disk or network I/O, so 10-100 microseconds) and applications that need to use bounded memory.
On top of that, there are confounding factors that hurt the case for GC. I don't know of an imperarive GCed language with a reasonably expressive type system (all the JVM languages I know of use type erasure).
For experienced developers, rich type systems with actual runtime guarantees are a huge productivity boost.
Well, in those cases extra developer time is cheaper than a more powerful computer!
Will you get ROI building a stereotypical web application with manual memory management? Doubtful.
Edit:
> GC shifts human work from development time to deployment / ops time.
I've never had to tune a garbage collector in deployment. I've heard of other people having to do it; but I've never heard of anyone saying, "yes, I'm so happy I built my website with C++."
(Good luck calling malloc from Javascript, or debugging use-after-free issues when you're iterating quickly.)
Haskell with all code in the IO monad?
Like all good jokes, "Haskell is the world's best imperative language" contains a kernel of truth. The standard library contains rather interesting control structures that can exist only because IO actions are lazily evaluated values -- but you can also choose to ignore those for a more Java-like experience.
Well, we have no idea what you consider to be imperative and what you consider a reasonably expressive type system to be.
Not unless you're load testing in production. Source: have been both a developer and an SRE in the past (an actual SRE, at Google, running services that used both manual memory management and GC).
Now, often people do in fact load test in production but this isn't some intrinsic property of GC. Also as an ops guy at Google I had to track down a number of memory management errors/segfaults that only occurred in prod, which wouldn't have occurred in a GCd language. Often double-frees or use-after-frees that only occurred after very specific combinations of RPC responses or timeouts that corrupted the state machine trying to handle them. Not much fun.
Also, you should be aware that "SRE" as a job role is deeply weird and most companies don't do what Google and fast-follower firms do. In most companies, ops people are cheaper than developers. Google was historically pretty unusual in demanding ops people who also happened to have histories hacking UNIX kernels but that was:
a. Not consistent, even in the early days most SRE people had sysadmin backgrounds.
b. To some extent because you would sometimes have to do things like ... debug segfaults in production.
Frankly they struggled to keep devs in SRE. They were only able to do it for a long time because they were making job offers to SWEs conditional on them working in SRE for a few years. Don't want to do ops work? Tough, you don't get to work at Google at all then. The desirability factor of working at Google was higher than the dislike of doing ops, so, people would accept this offer (that's how I ended up there). But obviously this is only a viable strategy in rare cases. Most companies can't do that.
Final point - your ideas about JVM GC are quite out of date. Modern JVMs are much better at auto-tuning. You can still squeeze extra performance out by tweaking obscure knobs and you should definitely tweak the one master knob that tells it whether your job is latency or throughput sensitive (i.e. batch or interactive). But that takes a few seconds and then you're done.
I don't know of an imperarive GCed language with a reasonably expressive type system (all the JVM languages I know of use type erasure).
Type erasure and GC are orthogonal. C# has GC without type erasure.
Indeed, the fundamental question is whether the costs of automatic memory management (be it tracing GC or refcount GC) are "worth it".
But it's not always as simple as a monetary consideration, and even when it is, the monetary cost often involves way more than just dev time vs cost of computer (e.g., power, cooling, distributed cost over many end users, market applicability because of system requirements).
I'd be interested to hear where you experienced difficulty, specifically. `Rc<T>` is `Deref<T>`, so you should never have any problems calling borrowing APIs. Owning APIs require an explicit borrow-and-clone, but that's just two calls (`as_ref().clone()`).
Think of using something like a lambda to start a thread: You have to explicitly clone your Rc<Whatever> into another variable, and then use the second variable in your lambda. The compiler won't implicitly clone your RC<Whatever> for you.
IMO, it's one of the biggest drawbacks in Rust.
Let's take games as an example. You cannot say to users "Just buy more powerful compute/phone". And even if they would you may have literally millions of machines, due to having millions of users. In which case saving 1 dollar worth of machine per user is savings of millions which is worth a lot of developer time. Naturally you as a dev won't really be paying this, so the incentive is not directly there. But the incentive comes from people just not buying a game that runs like crap.
In these cases GC is nice and dandy at start but then you run into the inevitable "Why does my game stutter?", after which object pools are introduced and even then some annoying "leaks" may remain. If the amount of time had been used from the get go to actually think about memory management the whole issue could have been avoided.
Sometimes people argue as if they are, which is understandable because the overlap between semi-FP programming styles and GCd languages is fairly strong, and the FP world pushes immutable state as almost a matter of moral principle. If you tried to do functional programming with purely manual memory management you'd see high overheads too simply because there'd be so many small allocations and copies. In practice though, people tend to think harder about in-place mutation when they don't have a GC to clean up after them.
So, with a tracing GC, introducing an object pool will usually make your program slower, not faster. (This is not true with reference counting.)
I felt it was hard and exotic at first but now I feel it's quite logical: never free, and have a proper monitoring of your size per unit of information to size the heap right and you're done.
But then it also depends why you dont want GC, us it's because clients cannot tolerate a pause (we had a socket manager creating and releasing garbage that triggered one 50ms GC pause during the last 3 seconds of trading of a particularly crazy trading day and the client threatened to leave), but often they re tolerable if you just stay reasonable with your garbage.
The problem is not the collection in non critical applications, it's the garbage generation getting completely out of hand. In a C# application my team had to micro optimize because of covid-related explosive trading volume, we simply bought gigantic amount of RAM for our 200 users, only allowed GC if CPU was in low usage and run with 80GB memory usage at the end of the day for an order grid that could run with 5GB collected. That s another way: I wish Java 8 had an easier way to simply deactivate GC for us to run with hardware money.
For most people's applications this is totally fine. But, yeah, you can end up with a scenario where GC pauses are just totally unacceptable, or where you need absolutely predictable behaviour and then you might resort to radical things like what you're describing here and it starts to feel like you've just chosen the wrong tool for the job.
I say this as a person who wrote an RTB ad server in Java, many moons ago... and never would again.
Maybe Java had the wrong assumption and really should just have made C-string optional first class citizens or something.
One thing is sure though, our C++ colleagues in the algo team are so slow to deliver, so prone to crazy bugs, so wild and wizardy, so unable to onboard new joiners, they re getting replaced this year by... a brand new Java algo engine... So not sure what to think.
As for C++ - I do just that. All my servers are C++ and while I will not claim "bug free" I do not really remember when was the last time I've had memory related bug (alloc / boundary / use after free / etc). Modern C++ along with sanitizers helps greatly in this department. All fixed bugs were logical.
I did my share of Java development big while ago and got sick of trying to make it performant enough. In order for me to achieve the goal I've spent way more time caring about memory / resource related issues in Java than I would do in "dangerous languages. Granted it was high performance servers. Doing different type of task in Java could've cost way less aggravation.
In other shops, the notion of conducting trading in Java, GC'd or no, would get you laughed from the room. But Java coders certainly are cheaper.
The guys in London have nowhere near the volumes of APAC or the US. They can trade with excel if they want.
Just like using C or C++ hasn't taken away that some niche use cases still require coding in Assembly.
It isn't only Java, C#, F#, Haskell and OCaml are also tooling they reach for.
Problem with FPGA is that it s pointless to try to correct client mistakes or validate exchange regulation with it, so it's only for upstreams who have the whole chain clean, it's a slow transition.
Too bad it's finance :-)
I think there is a time threshold above which it defensibly is not, and another below which you would have to agree, but I am not sure of the values.
But your employers take home very large annual bonuses while contributing what, exactly, to society? If they and their sub-ms competitors did not do it, would anyone miss it? Suppose, e.g., trades did not register until 1000ms after entry?
Rhetorical questions.
I agree with this. Java promotes a profligate programming style where allocation (and reclamation) are considered free. (They aren't). This is baked into the JDK deeply. E.g. with standard APIs it is not even possible to parse an integer out of a string without allocating memory. Those are language and library design choices that have a huge confounding effect on trying to measure GC.
For example, I wrote the Avrora AVR emulator and sensor network simulator, which is one of the DaCapo benchmarks. It's a CPU emulator for very small devices and uses almost no standard JDK stuff in its core work. As such it allocates very little and has a pretty small heap. It often shows up weird (sometimes obnoxiously small or uninteresting) in papers that study memory management because it really isn't very Java-like in its behavior.
Not true anymore :)
https://docs.oracle.com/en/java/javase/17/docs/api/java.base...
I tried lobbying for threadrippers but... not easy to onboard a new CPU in a giga corporation :(
1. The cost of free(), which recursively includes the cost of free()ing all "substructures" (ex: linked list free(head) includes the cost of free()ing the entire linked list)
2. The cost of malloc()
Manual memory management has both malloc() and free(). While garbage-collection memory management removes free() entirely, and does everything with malloc() alone (with "malloc" having some kind of mechanism to automatically detect which bits of RAM are safe to re-allocate without free() to guide it).
These costs can be incredibly complicated to figure out (!!!). free()ing a 4MB linked-list for example, would flush out your L1 cache and L2 cache, as well as take up a significant chunk of your L3 cache.
There is also the issue of fragmentation: malloc() and free() are cheap when the program starts, but as the heap gets more and more confounded by malloc()/free() calls, future calls to malloc() and free() can get slower-and-slower.
So there's a degree of:
* "Housekeeping" -- anti-fragmentation mostly, sorting the free()'d pointers and regions into groups more easily malloc'd() in the future.
* Synchronization -- Having all your threads pull from the same pool of memory is easier to think about, but requires multi-threaded synchronization. For long-lasting free() (ex: freeing a 4MB linked list), this could have one thread slowing down other threads when they try to malloc or free themselves.
-----------
Finally, the application code grossly determines what is faster or slower. Many people assume manual memory management is faster, but consider the following example:
Lets say our application-data consists of 1MB of misc. data + 3999MBs of linked-list data (including the internal pointers). Lets also assume 4000MBs is when the garbage collector runs.
Manual memory management would malloc() the linked list until its of 3999MB size, then the free() call would traverse the entire 3999MB structure every time to find the "deletion" pointers.
In contrast, Garbage collection of malloc() the linked list to 3999MB. The free() doesn't exist, but the linked-list will be detected as "dead data" upon the next malloc() call (only the 1MB of misc. data is traversed).
As such: the garbage-collector will never "Traverse" the entire linked list. The garbage collector only traverses the "live data" whenever it runs (which might be the 1MB of misc. data... but if this misc. data is long lived, then a generational garbage collector won't even traverse that!!).
So really, garbage collectors are best when you have small amounts of live data, and large amounts of malloc() calls. In contrast, manual memory management is best when you have lots of live-data (especially "quickly moving" live data, such that the generational-heuristic doesn't help), and relatively little dead-data.
It's far below 10% now (thanks to the hard work of a lot of people), and Google actually gotten to the point where we chose to spend _more_ time in malloc to make overall efficiency higher.
I most typically choose 0% post start-up, with 0% fragmentation. For a different problem domain, I might choose differently.
No-GC could be used in cases where you are just transforming one list or whatever and you don’t need to keep around any references to older nodes. That’s an optimization which is used by a research language which focuses on effects (whatever its name was). But it does use GC (reference counting).
Then you have linear types and all of that. But the intent seems to be to want to complement regular functional programming, not to invent a new GC-less FP paradigm.
You claim that it is merely “cultural” makes it seem to me that you just want to throw some weird shade and that you don’t have any particular technical argument in mind.
If you delete a std::map taking up 4GB of RAM, the destructor will have to traverse all 4GBs to find all the pointers and return them to the heap.
nb if it used an arena allocator then it could simply not do anything on free as long as it was acceptable to reclaim the memory later.
Mark-and-sweep, as well as generational-collectors, walk through all references starting from the root of all variables. In college-level toy garbage collectors, you usually use 1-bit of the pointers to mark where your algorithm has been to (or not). EDIT: The top 16-bits of x86_64 systems are often ignored, because x86 CPUs (AMD Ryzen or Intel i7 / Xeons) only have 48-bit physical memory space, and are a common set of bits used for this "marking" process)
Its basically just a depth-first-search or breadth-first-search over the graph of memory pointers. Its pretty simple in concept, but lots of details depending on performance considerations.
Chandler Carruth has discouraged its use (Google talk 2014) because it’s a cache killer.
I wouldn’t use LinkedHashMap in Java unless I needed to preserve the order.
after learning about the costs associated with using malloc()/free(), then being exposed to long-term arena allocators, then being exposed to a "temporary storage" system like this, when people talk about garbage collection being absolutely necessary for developer productivity or whatever plus also a way of avoiding malloc()/free() costs, I can't help but wonder if anyone who promotes garbage collection as a borderline necessity has ever tried something like Temporary_Storage. I find it to be pretty wild that instead of figuring out better memory management models like this, we collectively decided to punt on the whole issue, declare it an unsolvable problem, and decide that increasingly complex garbage collection systems are the only way forward. with Temporary_Storage in place, you can do whatever small allocations you need at any point in time (parse an integer from a string, etc.), and you don't have to worry about free()ing the result, because it's taken care of for you, without Actually Being Garbage Collection.
this entirely solves both "1." and "2." above, without the uncertainty of not knowing when exactly the garbage created by the thing you're free()ing and all of its substructures will be cleaned up. instead, you know exactly when it's going to be cleaned up, once per frame at the end of the frame (or whenever you call reset_temporary_storage()).
everything below the line break above sounds crazy to me. why are your linked list nodes all being malloc()d randomly on the heap, instead of in an arena allocator that you can also just flush all at once that's what you want to do? why would you ever traverse a complex nested structure to free it all, when you could just free() the entire hunk of memory at once (or, if you're going to be reusing that chunk of memory, just reset the arena allocator pointer to the beginning)?
My example of 3999MBs of mallocs() followed by garbage collection is overly simplified. In the real world, if you knew such a common pattern existed, then you'd use a 3999MB vector/array instead. (or if a linked-list were really needed, perhaps Knuth's "Dancing Links" example is best).
--------
The issue is that the programmer nay not know the patterns of malloc/free for their code, and yet still wants O(1) performance for insertions / deletions to the middle of the chain. EX: the "Rope" data-structure for text editors is a glorified linked list. Each link has variable length, and represents a "cut" portion of the text that the user has entered. You can move the cursor and "insert" new text anywhere in the rope rather easily. For example, the sentence "This is a sample sentence" could be represented as: "Thi" -> "s is a sam" -> "ple sente" -> "nce".
If the user changes it to "This is a silly sample sentence", you'd split "s is a sam" into "s is a " -> "silly " -> "sam" ->...
"moving" the cursor left-or-right traverses the linked list. Since the "cursor" of the text-editor only exists in one location, its not very difficult to handle.
> when you could just free() the entire hunk of memory at once
In this rope example, you don't know which bits of the text will be free'able ahead of time. Only the human knows what parts they plan to delete.
I used C# before I learned C/C++ and it was great to muddle my way through things with garbage collection until it wasn't. then when I learned C & C++ it was like ok, malloc()/free()/new/delete all the things, sure. but there's plenty of middle ground between the two extremes that is often overlooked when it comes to memory management, in favor of "garbage collection, yes or no?"
Regardless it's good to know about arena allocation because it's one of many effective techniques in a toolbelt. If you find yourself writing a CLI utility in an unmanaged language, it's often simplest to just allocate and never deallocate, because the application will only run for a small amount of time and the OS will deallocate resources on app exit.
New/delete and RAII and malloc/free (be it either unique_ptr source/sink pattern or RAII pattern) are basically universal techniques, albeit at a performance cost.
There are many other strategies but they require more thought.
-------
Personally, I'm a big fan of vector + swap with the end, which covers most of my common needs.
When looking at linked structures: linked list, trees, and graphs... It's often common that your specific application has patterns that a more specific strategy (arena allocation, stack allocation/bump allocation) works out.
But there is also the chance it doesn't work out, and prototyping with generic methods (new/delete/RAII or garbage collection) is a good first step.
{
MyObject obj = new MyObject(); // Make an empty but non-null thing
... do stuff
obj = new MyObject("real data");
}
{
... do stuff
MyObject obj = new MyObject("real data");
}
Where applicable, this converts the run-time NullPointerException into a compile-time error if you're referencing the value of obj before you've initialized it, which is an improvement. By contrast, your suggested change converts the run-time NullPointerException into silently incorrect behavior, which seems strictly worse in any context I've ever seen.
You didn't say why your suggested change would be bad in C++, but I'm guessing you're thinking that it's because it would leak the initial empty object, which is true if you use a bare pointer. But in the more usual case where you just construct the empty object (as a "nested child object") in your stack frame
MyObject obj;
... do stuff
obj = MyObject("real data");
(There's also no leak in C++ if you use a smart pointer.)