Boehm-Demers-Weiser conservative C/C++ Garbage Collector
hboehm.info
hboehm.info
At this point, jank is generally several times faster than the equivalent Clojure JVM code. I'm sure there are better GCs out there, in terms of performance, and I have my eye on MMTK [2] for a future upgrade, but the fact that remains is this: the Boehm GC is stupid simple to integrate and it's surprisingly fast. Compare it to MPS, MMTK, and others and both the documentation and the actual dev work required are worlds apart.
For a project which needs a GC but doesn't need to pick the absolute fastest one first, it seems like the best option, based on my research and my experience.
As more of a CL guy who's dabbled in Clojure but found it a bit too slow(but conversely I also miss the Clojure's data structures and transactional state in CL; multithread programming really isn't CLs strong suit, for obvious historical reasons), this might reinvigorate me. I may sit down one day soon and churn out some AOC or something in Jank just to get a feel.
Cheers :)
Check it out, join our Slack, and stay tuned. jank's still under heavy development right now, and not ready for AOC this year, but it's getting close. The blog is the best way to watch the progress: https://jank-lang.org/blog/
Thanks for taking the time to comment!
On the compiler and tooling itself, I have some open issues here: https://github.com/jank-lang/jank/issues
The vast majority of it is heavy C++ work, though. Outside of that, the biggest gains will come from time spent on packaging, distribution, and testing on various platforms.
And if none of that sounds interesting or applicable, don't worry. Just be sure to join the Slack channel and hang out with us. :)
What scared me off of Boehm GC is that there a bazillion config options -- e.g. it requires tuning and blacklisting to avoid memory leaks -- and probably even correctness because register scanning isn't portable.
The codebase is large and a bit scary, and there are seemingly lots of ways to use it poorly. People kept saying it's "drop in", but that seems like a myth.
At least personally it doesn't seem like the kind of thing I want to debug.
The opinions on Boehm generally seem very split -- a bunch of bad stories resulting in ripping it out of the codebase, and also people who think it's surprisingly good, and codebases that have used it for a very long time.
I think the Nix evaluator uses it and is carrying around patches, and Guile Scheme uses it. Though I think there is some desire to move away from it in both cases. But again people have used it for a very long time, which isn't nothing!
---
e.g. https://www.hboehm.info/gc/gcdescr.html
Recent versions of the collector use an approximate best fit algorithm by keeping free lists for several large block sizes. The actual implementation of GC_allochblk is significantly complicated by black-listing issues (see below).
...
The collector implements black-listing of pages, as described in Boehm, ``Space Efficient Conservative Collection'', PLDI '93, also available here.
During the mark phase, the collector tracks ``near misses'', i.e. attempts to follow a ``pointer'' to just outside the garbage-collected heap, or to a currently unallocated page inside the heap. Pages that have been the targets of such near misses are likely to be the targets of misidentified ``pointers'' in the future. To minimize the future damage caused by such misidentifications they will be allocated only to small pointerfree objects.
The collector understands two different kinds of black-listing. A page may be black listed for interior pointer references (GC_add_to_black_list_stack), if it was the target of a near miss from a location that requires interior pointer recognition, e.g. the stack, or the heap if GC_all_interior_pointers is set. In this case, we also avoid allocating large blocks that include this page.
I don't doubt it caused all sorts of problems too. It's just an interesting reminder that sometimes a really wacky hack can be pretty useful.
Certainly not but it wasn't particularly hard to implement either, I managed to do it with some simple inline assembly. Here's my programming language's register spilling code:
https://github.com/lone-lang/lone/blob/master/architecture/x...
https://github.com/lone-lang/lone/blob/master/architecture/a...
I assume everything must be properly aligned to work. Interestingly, it uses jmpbuf to spill the registers. There's also a compiler builtin to get the current stack frame which can be used to obtain the stack root if called at the beginning of the program. Really neat, and educational.
I'd estimate that the bad rap GC languages get can be traced back to this piece of code.
If only more than two languages would exist!
This is either
1. missing a /s
2. delusion
3. bait
I guess doing it this way allows to have mostly deterministic collection (that is then just an implementation feature, not language semantics) while needing the actual tracing GC to not be that efficient, as it presumably needs to be executed less rarely.
To be fair, the GC is probably the last reason of Python speed problems.
Many languages also designed with GC performs significantly better than python in term of raw performance [^1].
The extremely dynamic nature of python associated with its reference semantics are probably significantly more to blame here.
[^1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
C++ crazies denigrating GC even when it visibly fixed their issues, or maybe especially when it did, was a phenomenon since 1990. Even when code with Boehm GC ran faster - and most importantly, didn't crash all the time.
Manually managed code doesn't crash all the time. It probably crashed way more in the 90s. There is an art to writing manually managed code that is maintainable and fast, sure, and it doesn't involve malloc() and free(). And then there is RAII, automating lots of the work.
The C++ crazies are AFAICS still most everywhere where there is lots of temporary objects and serious requirements on throughput & latency. There are frameworks and languages that support garbage collection that get used in this space too, but I don't know how much can be inferred from that.
Seems like C and C++ guys are constantly looking for ways to automate their garbage cleanup.
And seems like GC guys are constantly looking for ways to fix their web-of-objects memory layout, and to prevent GC from ruining their performance. Plus, GC isn't deterministic, it mostly works for memory but otherwise you'll see _lots_ of manual cleanup code (not making use of the GC), and it always feels a bit tricky with the GC still being part of the game. Not that I take a huge issue with C-like cleanup code -- I think RAII can be tricky too because it's hard to "read" what happens, and I often prefer the manual cleanup code. But compared to GC, at least RAII is deterministic.
Anyway, for complex state that must be cleaned up, maybe flushed before etc., you'll always find a lot of manual cleanup code, or otherwise find code with lots of random problems, often unreported. That is true both for GC languages as well as C++ and other languages with RAII or RAII-likes.
The talk is "Leak-Freedom in C++", 2016 actually, https://youtu.be/JfmTagWcqoE?si=MY1JnWyybh5K8I8-
An optimization that coroutines rely upon as means to remove the abstractions of their execution.
I can't imagine what LTO should have to do with that either, but if there's any substance here please enlighten me.
The order in which destructors get called is well defined (and generally useful insofar as it's the reverse order of construction). Can't you just accept a simple argument? I'm not even a huge fan of RAII, but it has its uses.
Similarly, the construction/destruction order for std::tuple elements is not well defined.
Granted, that's implementation defined behavior, which is technically deterministic on a single compiler.
I suppose the destruction of whatever the expressions constructed still happens in reverse order of construction.
But either way I might not even care, I'm aware that at the level of a single statement the execution sequences aren't much defined, so I rarely put more than one mutating thing per expression, or otherwise I'm sure that I don't care about the order -- I could live with any sequence as well as totally parallel execution.
Example: buf[i++] = 5 has 2 mutating sub-expressions, but I know it's not messing up anything. I don't care whether i gets incremented before 5 gets assigned or the other way around.
> and how performance workarounds turn out a poor man's GC.
If you need performance then it doesn't matter if it is a "poor mans GC", what matters is that it meets the space/time requirements, most general purpose GC tend to care about neither.
Sometimes you can't do that though because you have certain constraints on the execution order of whatever routines you need to run. This is completely independent of whether you use manual cleanup or GC or RAII, however with GC it is weird/hard/impossible to synchronize the GC with the non-cleanup code.
I had a AAA project hitting 30ms pauses in free() implementation by platform vendor for quite popular gaming platform in 2016. Ofc it is anecdata but having actual deadlines from implementations is really hard. I had to replace malloc/free implementation like 3 month before ship date to avoid the issue.
Of course, you can also do manual allocations if you really wanted to, but - with the changes in the language since C++11 - you just don't have the motivation to do it.
AFAICT few GC languages allow you to do this, basically you have to buy into indirection and end up with webs of objects.
This is quite cache unfriendly, but the bigger issue for me is that it makes the code less clear and requires additional complexities since you can't just jump from a child to its parent by subtracting an offset from its address.
Wait, so you're saying that code that subtracts an offset from a child node to get to a parent node is clearer and less complex than alternatives?
Parent made me laugh out loud on this.
The same approach works for lists and a variety of other data structures.
You can get from the abstract link node to the containing struct with a macro: CONTAINER_OF(ptr, containertype, membername). It's easy to use and unlikely to get it wrong.
How do you get from the child to the parent in, say Java? And how do you tell that a child is never swapped out?
How do you copy an object that holds, say 4 vec4, vec4 being a struct that itself 4 holds floats? With value types, say in C, it's 1 memcpy and you're done.
Many other languages also have newer/different approaches to solve some of these problems, be they subclassing, generics, macros (often safe ones), JITs, or other. They mostly cannot do this as efficiently, but that seems less like a clarity/complexity concern and more like a low-level-programming concern.
> How do you get from the child to the parent in, say Java?
In Java, you do indeed have to embed mutual pointers and just be careful. As a C user, you must be used to being careful. Even C#, which does allow structs, doesn't have references-to-members that can be turned into references-to-owners. The aforementioned language features like subclassing (for lists) and generics can help.
> How do you copy an object that holds, say 4 vec4, vec4 being a struct that itself 4 holds floats?
Copying structs as a block works fine in Rust, C++ and C#, along with many other languages. Again, Java is a little more limited in this regard, though I believe they are working on adding value types.
I see literally a subtraction operation versus a huge memory safe language framework set up over the same machine, plus a whole lot more user facing surface level source code, just to achieve the same thing.
In the message I originally replied to, I guess it's only the "since you can't ..." part that I really object to, as it's never going to be clearer to use &(par->child) and CONTAINER_OF(ch, some_type, child) than to use par.child and ch.parent.
Java's mistake was ignoring them, as its was designed as set-top box programming language as Oak, pivoted to applets, and then pushed all over the place.
Might be interpreted as older languages with GC did not had value types, which is bluntly false, going back to 1970's.
My remark was to make clear this isn't something new and modern, rather a design mistake in languages like Java, that is now trying really hard to fix it, while others designed after it (like C#), thankfully didn't follow the same trap.
How modern a 2001 language (C#), using ideas from Mesa/Cedar (1985), is an exercise in the semantics of "modern".
Ok, but you included Common Lisp in your list, which doesn't really have value types. (E.g. you cannot make an unboxed array of structs.)
As if me mis-remembering Common Lisp capabilities, invalidates the rest regarding "modern" GC languages.
Here is an array of structs in Oberon, 1987,
TYPE
Point = RECORD
x, y : INTEGER
END;
Triagle = RECORD
v1, v2, v3: Point
END;
Data = ARRAY 100 OF Triagle; (* static sized *)
DynData = ARRAY OF Triagle; (* dynamically sized *)
VAR
dynData : DynData; (* Allocated via NEW(dynData, elems)*)There's a little bit of irony here in how you react to people picking at details in your own posts, when your original post is precisely the same kind of pedantry!
The above problem is about latency of stop the world collectors in a domain that requires extremely low latency. And if you think that stop the world collections are representative of garbage collection as a whole (i.e. the "bad rap"), this is just not being up to the state of the art. (It's just that generational/incremental collection is hard to impossible without having support for write barriers/read barriers/snapshotting on the compiler or hardware side, which makes that a practical no-go for a language that was never designed to have GC support.)
But in terms of throughput, the BDW GC actually performs pretty well, competitive with or beating malloc()/free() libraries. This is plenty enough for a number of applications, especially when it comes to batch processing. In fact, even the stop the world latency is (combined with parallel marking) plenty good enough for a number of types of regular GUI applications, where you don't have the fairly extreme latency requirements of standard video games.
It is also worth noting that manual deallocation (especially via RAII) isn't a panacea for latency, as that is just as prone to large pauses due to cascading deletes [1].
[1] While in theory you can do that lazily, in this case you're losing timeliness of deletion and may actually have worse worst case latency than a modern GC that can stagger its work to have bounded pause times. The benefit of RAII is that you may be able to plan these deletions, but even that can be surprisingly difficult at times, requiring extra management to keep data structures alive longer than normal. [2]
[2] Note that lazily deleting objects in RC to avoid pause times is not necessarily the answer; for one thing, you're introducing much of the complexity associated with incremental GC again (especially having to do X amount of deallocation work for each allocation), or risking considerable space overhead. https://dl.acm.org/doi/abs/10.1145/964001.964019 It also remains a difficult challenge when you're dealing with objects that aren't of bounded size (e.g. large arrays).
iain
I don't know what your domain is, but the domains I'm familiar with (especially hard real-time) deal with the underlying constraints by way of restricting how you write programs. A side effect of these restrictions is that you generally avoid use constructs that give rise to cascading deletes. But ultimately, having to deal with these restrictions is suboptimal.
I remember a talk by Gil Tene (CTO and co-founder of Azul Systems) about how the problem with writing real-time Java was that it historically required you to write non-idiomatic Java code, which came at a serious cost to reuse and where he argued that one of the benefits of Azul's GC was that you could write (mostly) idiomatic Java and still have GC noise be less than OS noise.
There is of course the actual problem that the stricter your latency requirements are, the fewer GCs actually meet them. Plenty of modern off the shelf GCs meet typical soft real time requirements, but the harder your real time requirements get, the fewer implementations actually meet them (and are increasingly more expensive).
I'll also add that depending on how strict your latency requirements are, off the shelf allocators may not meet them, either, even for a single malloc() (though there are allocators that offer hard upper bounds for allocation costs, such as TLSF).
It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem.
The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go.
I suppose you could write special shared_ptr / unique_ptr that supported address mutation but you’d need a compiler flag to check for an object’s address being taken… but to some degree the destructor paradigm renders a lot of this moot.
Yes, that's why I wrote about support "on the compiler or hardware side" (i.e. MMUs). That said, while this might work in theory, the BDW GC does have support for it, and in practice it doesn't actually work well. Throughput suffers and pause times can actually get worse.
By the way, another alternative way of having incremental collection without compiler support is to use fork() for snapshotting (there's an option in D for that), but that has its own issues, of course.
> The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go.
No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection.
FWIW they are orthogonal
Cascading deletes are rare in practice, and if anything they are inherent to deterministic deletion, which is often a desirable property. When they're possible, one can often use arena allocation to avoid the issue altogether since arenas are managed as a single allocation.
This is true, but it's absent especially in C. Of course, as long as you can intercept writes and/or reads through pointers, you are good to go in principle. However, that solution may not be efficient.
> Cascading deletes are rare in practice
An array of objects (e.g. std::vector<std::string>) already has unbounded deallocation cost. People mostly think of tree-like structures here, but such structures only add the risk of stack blowout to the lack of an upper bound. But in principle, any container that does not have a size limit can give rise to unbounded pause times.
A significant one was a problem in the way that the Mono C# compiler generated foreach loops, which caused it to allocate an object for the enumerator that the regular .NET compiler was able to avoid. This caused foreach() to produce unnecessary garbage and resulted in a lot of Unity developers writing manual for() indexing loops instead of a more straightforward foreach() loop.
Another problem was a bug in the Mono standard library where one of the array containers -- I forget whether it was ArrayList or List<T> -- would fail to clear elements at the end on removals. This was innocuous for arithmetic types, but for reference types it would result in hidden entries in unused capacity holding onto stale references. In some cases this caused rather large trees of objects to persist unnecessarily, pinned invisibly by containers that had already been deleted from or were even empty.
Maybe that time is coming from something even more ridiculous like scanning an entire linked list to find each element, but if you can open up that library there are without a doubt terrible memory allocation techniques that should never happen going on.
The only way I can make sense of this claim is if you're saying the items he needs to operate on should be inlined into a vector. But that's basically just an arena.
I'm not sure what this means.
My point was that a vector is like an arena but better in practicality because if someone is 'allocating' from an arena, they are then storing that pointer somewhere. In a vector you can store the index somewhere, but you have the much better option of looping through everything and dealing with it contiguously instead of dealing with each element in some isolated way.
Also a lot of arena implementations are basically linked lists inside a vector and freeing up the memory means jumping around in memory while dereferencing the pointers to unwind the individual allocations. The advantage is that you can free individual cells of the arena, but the cost of allowing that fragmentation is high. It's much better to avoid that and with hundreds of millions of elements it's likely that the data should be dealt with by just allocating huge chunks of memory and looping through them.
It means the structure storage is contained within the vector storage and you return an index, just as if it were an arena.
The problem is that such an approach can only allocate a homogenous set of types and sizes.
> Also a lot of arena implementations are basically linked lists inside a vector and freeing up the memory means jumping around in memory
That's not an arena. The whole point of an arena is deallocation of all elements allocated from that arena is a constant time bulk operation.
I've seen both, you can use empty cells to link to the next empty cell and the head pointer to link to the first empty cell in the chain so that the cells can be arbitrarily freed, but the option is always there to do what you said and do a single bulk deallocation of the actual heap memory allocation instead of dealing with individual cells.
My point in all this is the same thing you have been implying. There aren't many differences in techniques so when people are talking about 'arena allocators' most of the time they should just be using a vector.
It worked based on a template type I called "gc_ptr<T>". So you could create one of these with the function template "make_gc(...)". This was the only way you could allocate a new garbage-collected object.
"make_gc" would check if a type descriptor for the type was already initialized and if not it would allocate a new one. It would then set a thread_local with the descriptor and the address of the current object being created.
Then it would call the object constructor. If the type being instantiated had gc_ptr members, these would be initialized by their constructor. The gc_ptr constructor would, in turn, check the descriptor of the parent object and add a record to it representing the member. The record would store the member offset calculated from its address and the one of the parent object.
Garbage-collected objects would also use reference counting for gc_ptr(s) on the stack or inside objects that were not garbage-collected. It's easy to know if a gc_ptr is being constructed inside a garbage-collected object or not: If it is, then the code is also executing inside make_gc, so I just need a thread_local flag.
For the mark and sweep, I would use an atomic flag to mark the GC as running. If the flag was set, then all gc_ptr would stop the thread (by waiting on a mutex) as soon as some code would try to swap/reassign them. This means that code that didn't touch them would be kept running during garbage collection.
I would start marking objects from those allocated in the custom arena I used that had a reference count different from zero.
I wanted to add containers that could allocate contiguous GC'ed objects by wrapping the standard containers but never finished that. GC'ed containers of gc_ptr(s) just worked fine.
I just re-ran the benchmarks I wrote to compare it against the Boehm-Demser-Weiser GC. It is quite faster in doing the mark-and-sweep (up to an order of magnitude faster with thousands of objects and a bit less than 100 MBs of GC'ed memory in total).
However, because of the atomic check, it was slower in swapping pointers by roughly an order of magnitude.
I never used it in any project.
I once found a real incompatibilty. This collector assumes that a pointer to a block must point to somewhere in the block, or, in later versions, at least somewhere really close.
The original Numerical Recipes in C was a conversion of Numerical Recipes in FORTRAN. FORTRAN arrays start at 1. So, NR in C had an array allocator which returned an array address computed such that subscripts starting at 1 would work.[1] If you allocated a 100x100 array of 4-byte f32 values, the array address would be offset downward by (100+1)*4 bytes. That would not look like a pointer to the array to the garbage collector.
By the third edition, in 1986, the Numerical Recipes people had converted to C++, dropped FORTRAN array compatibility, and the problem went away.
[1] http://s3.amazonaws.com/nrbook.com/book_C210.html page 19.
Same as other languages.
> I always had the impression that with the well-defined lifetimes of objects, you wouldn't really create garbage to begin with
There's no well defined lifetime of objects when it comes to dynamic allocation. For example, if you allocate something with the new keyword, there are no language guarantees that this won't leak memory.
The problem is that big programs in the real world often don't have well defined lifetimes for everything. The idea that everything in your app can have its lifetime worked out in advance isn't true when you're modelling the world (a world), or lifetimes are controlled by other people (e.g. website authors).
Generally what you see is that these apps start out trying to do manual memory management, decide it's too difficult to do reliably at scale, and switch to a conservatively GCd heap with a custom collector or Boehm.
Note that Rust doesn't fix this problem. Rust just encodes the assumption of pre-known lifetimes much more strongly in the language. If you're not in such a domain then you have to fall back to refcounting, which is (a) slow and (b) easy to get wrong such that you leak anyway. Early versions of Rust used refcounting for everything and iirc they found anywhere between 10-15% of the resulting binaries was refcounting instructions!
Do you happen to have a citation for this? I don’t remember ever hearing about it, but it’s possible this was before my time, as I started in the smart pointers era.
https://news.ycombinator.com/item?id=5691684
The Rust compiler does this. Even so, 19% of the binary size in rustc is adjusting reference counts.
I am not exaggerating this. One-fifth of the code in the binary is sitting there wasted adjusting reference counts. This is much of the reason we're moving to tracing garbage collection.
It's interesting how many strategies Rust tried before settling on linear types.
Rust doesn’t actually have linear types. I’m not sure what Rust’s types are called (affine?), but linear types are the “must be consumed” (can’t leak) types, and Rust doesn’t have any support for this.
Rust’s guarantee is that you MUST NOT use an object after dropping it. Linear types would add the additional requirement that you MUST drop the object.
(I completely forgot I wrote that and also I'm mildly embarrassed at how I used to write back then.) :)
But yeah, at this point Rust’s niche is a competitor to c/c++ and in that world implicit recounting doesn’t have a lot of traction and people favor explicit gc and “manual” resource management (RAII mechanisms like drop and destructors are ok).
Due to the nature of web engine workloads migrating objects to being GC'd isn't performance negative (as most people would expect). With care it can often end up performance positive.
There are a few tricks that Oilpan can apply. Concurrent tracing helps a lot (e.g. instead of incrementing/decrementing refs, you can trace on a different thread), in addition when destructing objects, the destructors typically become trivial meaning the object can just be dropped from memory. Both these free up main thread time. (The tradeoff with concurrent tracing is that you need atomic barriers when assigning pointers which needs care).
This is on top of the safey improvements you gain from being GC'd vs. smart pointers, etc.
One major tradeoff that UAF bugs become more difficult to fix, as you are just accessing objects which "should" be dead.
Are you referring to access through a raw pointer after ownership has been dropped and then garbage collection is non deterministic?
No - basically objects sometimes have some state of when they are "destroyed", e.g. an Element detached from the DOM tree[1]. Other parts of the codebase might have references to these objects, and previously accessing them after they destroyed would be a UAF. Now its just a bug. This is good! Its not a security bug anymore! However much harder to determine what is happening as it isn't a hard crash.
[1] This isn't a real case, just an example.
Swift is probably a better baseline.
It was probably right for that language at that time, but I don't see it as being a generalizable decision.
Swift and ObjC have plenty of optimizations for reference counting that go beyond "Elide unless there's an ownership change".
Well, modern idiomatic Rust only uses Arc/Rc on the few objects where it's needed, so the overhead of reference count adjustment is so tiny as to never show up. You typically only see reference count traffic be expensive when either (a) everything is reference counted, as in ancient Rust; or (b) on super-inefficient implementations of reference counting, as in COM where AddRef() and Release() are virtual calls.
Even outside of writing languages on top of C++, if you're using something like immer, for persistent immutable data structures in C++ (as jank does), it has memory policies for reference counting or garbage collection. This is because immutable data generally results in more garbage, even when transients are used for the most pathological cases. That garbage is the trade off for knowing your values will never be mutated in place. The huge win of that is complete thread safety for reading those values, as well as complete trust on reproducibility/purity and trivial memoization.
"Why Doesn't C++ have a garbage collector?" https://stackoverflow.com/q/147130/1593077
and my answer: https://stackoverflow.com/a/48046118/1593077
... which develos Bjarne's classic quote:
"I don't like garbage. I don't like littering. My ideal is to eliminate the need for a garbage collector by not producing any garbage. That is now possible."
For the GC component, there's two options I'd like to see more exploration of. One is a modern, concurrent GC to reduce the pauses people here are worried about. Immix [1] is an interesting design I remember.
The other option is a runtime supporting multiple, app-specific GC's without much tuning. JX OS was the first variation of that I saw. I just stumbled on this other paper. So, we have a global, memory manager divided up into chunks managed differently across apps or components.
[1] https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/immix/
[2] https://www4.cs.fau.de/Projects/JX/publications.html (It was in 'Beyond Address Spaces.')
In C you can construct your hackish tracing GC yourself. For root objects save the stack address at the beginning of main() by saving the address of a dummy stack variable.
int dummy=0;
void* stack_head=&dummy;
I built a few apps using the above technique but now am more comfortable with old styled manual memory management. Valgrind will tell you exactly which line you allocated memory that leaked.
In practice if you care about performance, one ends up creating a pseudo GC like Herb Sutter has shown on his CppCon talk about deferred _ptr, or why hazardous pointers are coming to C++26.
Then there is the point RAII handles have to be written in exception safe way, also be movable if used as part of other data structures.
Also, I don't think that's necessarily as critical as you suggest. I've been working with performance-critical software for many years and never saw a strong need for general-purpose concurrent reclamation techniques.
Worst case execution time with pipelining should be similarly measurable given a worst case execution (which seems in any case necessary to demonstrate a bound on the task, even in a lockstep system).
See https://cs-people.bu.edu/rmancuso/files/papers/cache_survey_...
Garbage collection has an overhead too of course, since there is a major cost to discovering what can be freed, while the cost of doing this with smart pointers is zero.
Not so small, and it has the potential to significantly speed down an application when not used wisely. Here are e.g. some measurements where the programmer used C++11 and did everything with smart pointers: https://github.com/smarr/are-we-fast-yet/issues/80#issuecomm.... There was a speed down between factor 2 and 10 compared with the bare-bone C++98 implementation. Also remember that smart pointers create memory leaks when used with circular references, and there is an additional memory allocation involved with each smart pointer.
> Garbage collection has an overhead too of course
The Boehm GC is surprisingly efficient. See e.g. these measurements: https://github.com/rochus-keller/Oberon/blob/master/testcase.... The same benchmark suite as above is compared with different versions of Mono (using the generational GC) and the C code (using Boehm GC) generated with my Oberon compiler. The latter only is 20% slower than the native C++98 version, and still twice as fast as Mono 5.
If you need zero overhead memory management then garbage collection isn't going to be the answer either - you need application specific arena allocators, reuse pools, etc. You seem to be focusing on a very odd set of performance requirements where the overhead of garbage collection is just right, C++ too inefficient, and the need to go full custom not needed.
It's a standardized benchmark suite used to compare different languages, thus focusing on similarity and comparability of the implementation. It's especially suited to compare GC and non-GC implementations.
Run-time cost for GC can be minimized, if not completely obviated, by having the collector run on a processor other than those allocated for system use. One such example of this strategy is the JVM Concurrent Mark Sweep[0] GC algorithm.
0 - https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gc...
Not really. This is a straw man argument.
Having large graph of object with mutual dependencies represented as references to each other is almost all the time a code smell and a problem of design.
It is terrible for cache locality, terrible for memory fragmentation and will bring even the best GC on its knees.
The way to handle that is to use Entity Component System [^1] or a SOA structue with indexes.
In fact every mature game engine or serious Graph Representation library (which are specially design to deal with these cases) will do exactly that.
Of course it can also be done without a GC.
> is almost all the time a problem of design
There are even cases where this design is unavoidable to solve the problem.
At least one situation where GC can greatly simplify C++ logic is when implementing lock-free collections. Having a GC available is not a requirement, however, as witnessed by Boost.Lockfree[0].
As others have pointed out, the smart pointer types you identified can be employed in may situations, but are not a universal replacement for all memory management concerns.
0 - https://www.boost.org/doc/libs/1_53_0/doc/html/lockfree.html
A Garbage Collector for C and C++ - https://news.ycombinator.com/item?id=9862135 - July 2015 (73 comments)
If it was something built into the language then you could do much better, but then that language wouldn't be C++.