11 ms·

Boehm-Demers-Weiser conservative C/C++ Garbage Collector

132 points by swatson741 3y ago

torginus 3y ago
Ah the spectre of the 80s, most famously used by the ancient fork of Mono that Unity uses, leading to GC-pause induced stutters that have plagued gaming for over a decade. I'd estimate that the bad rap GC languages get can be traced back to this piece of code.
- pyeri 3y ago
  You don't need to go that far for GC's bad rep considering that excruciatingly slow Python can be found TODAY!
  - DarkNova6 3y ago
    But you must understand, Python is safe and C is difficult. Therefore, to be fast we need Python (fast development that is because nobody _really_ cares about performance (or maintainability)). If only more than two languages would exist!
    - h4ch1 3y ago
      > fast development that is because nobody _really_ cares about performance (or maintainability) This is either 1. missing a /s 2. delusion 3. bait
      - tmtvl 3y ago
        I believe it's 1, considering the statement 'If only more than two languages would exist!'. Granted, sarcasm doesn't transmit well in written text.
  - amelius 3y ago
    Python wasn't designed for speed.
  - torginus 3y ago
    Afaik (C)Python uses reference counting, it's slowness comes from the interpreter itself.
    - _flux 3y ago
      It uses also tracing GC to handle RC loops. 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.
    - kaba0 3y ago
      Ref counting is a GC-algorithm, and the slowest at that (especially with multi-core sync, but that’s not the case with python), as a tradeoff for less memory consumption.
  - adev_ 3y ago
    > You don't need to go that far for GC's bad rep considering that excruciatingly slow Python can be found TODAY! 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/fastest/python.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
- p_l 3y ago
  Mono is nowhere close to major use case of it, it has been succesfully deployed in maaaany projects. 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.
  - jstimpfle 3y ago
    How did GC visibly fix their issues? 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.
    - pjmlp 3y ago
      The deterministic myth only works out for basic types, see Herb Stutter CppCon 2015 talk on the matter, and how performance workarounds turn out a poor man's GC.
      - jstimpfle 3y ago
        What? RAII is totally deterministic, not sure what you want to contend here. CppCon 2015: Herb Sutter "Writing Good C++14... By Default": Not sure where I'm going to find my answer here. 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.
- mihaaly 3y ago
  I assume that real time computing should have used real time computing compatible techniques. But luckily those exposed to other than games and game development might feel less aversion towards GC, probably even the other way around.
- pjmlp 3y ago
  Another reason being that many people don't get GC theory, nor that because a language has some form of automatic resource management, does not mean the language doesn't offer other mechanisms.
- yxhuvud 3y ago
  Another big reason is the lack of value types in languages like Java. Modern languages with a GC tend to have those, and where it makes sense to use them they help, a lot.
  - amelius 3y ago
    What are "value types"?
    - greesil 3y ago
      In Java, primitives. int, boolean, float. Allocated on the stack, or the heap along with the object it is a part of.
    - jstimpfle 3y ago
      If you nest an object within another object you often want to embed the child directly in its parent, sharing the memory and avoiding the indirection that you get if you nest with a reference as is the typical approach with GC languages. Also embedding makes it clear that it's a 1:1 relation, i.e. non-optional, fixed identity etc. 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.
      - ghusbands 3y ago
        > 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?
        groestl 3y ago
        > 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.
- rbehrends 3y ago
  This needs some qualifications. 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 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).
  - cplusplusfellow 3y ago
    For all of the reasons you note above, this is why I've almost exclusively dealt with arena-style allocations of fixed-object-sizes when doing ultra low latency work.
    - iainctduncan 3y ago
- ack_complete 3y ago
  Sadly it was not just the GC, there were plenty of problems in Mono itself that adversely affected GC performance. 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.
itsphilos 3y ago
My experience with Cpp isn't that extensive, but what is the use-case of a garbage collector in this language? I always had the impression that with the well-defined lifetimes of objects, you wouldn't really create garbage to begin with, but I guess there are some use-cases I don't yet know about?
- FartyMcFarter 3y ago
  > what is the use-case of a garbage collector in this language? 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.
- pjmlp 3y ago
  Targeting .NET, hence C++/CLI, integration with Blueprints, hence Unreal C++.
- mike_hearn 3y ago
  It's pretty useful. Chrome uses one extensively for example (called Oilpan). So does Unreal Engine. GC in C++ is much more widely used than people realize. 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!
  - 3y ago
habibur 3y ago
in CPP you don't need GC. Use RAII. Objects only need a constructor, destructor and a copy-constructor for a very efficient reference counting GC that's almost impossible to leak. 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; and later during GC get the current stack address again and trace from old one to new. You also need to save the registers and can do it in a semi portable way using unix setjmp() longjmp() functions which save the register values into a structure that you can then later trace. There's also the issues of split stack that you need to keep into mind. But the positive thing is memory alignment ensures pointers are all 8 byte aligned, you only need to read address%8 values in between. It's a bit hackish regardless. 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.
- pjmlp 3y ago
  In theory, yes. 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.
  - mgaunard 3y ago
    I wouldn't call hazard pointers garbage collection. 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.
- rst 3y ago
  The RAII/ref-counting technique often works great, but not always. Cyclic structures are a problem -- so, if you've got, say, a global tree structure with bidirectional parent/child links, you'll need some kind of special-casing to make ref-counting clean up an entire abandoned subtree. A full GC does take care of cases like this.
shrubble 3y ago
Bjarne Stroustrup's view: https://www.stroustrup.com/bs_faq.html#garbage-collection https://www.stroustrup.com/bs_faq.html#garbage-collection
nickpsecurity 3y ago
I think a mix of methods are best. We can use non-GC methods for whatever is easiest to prove is safe. In Python, they then use reference counting by default. Then, a GC when that would be a problem. I also prefer when the GC let's me tell it to immediately delete something which it just checks incrementally. Then, performance-sensitive modules can be coded without GC's using tools like Meta's Infer which work on large modules. 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/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/immix/ [2] https://www4.cs.fau.de/Projects/JX/publications.html https://www4.cs.fau.de/Projects/JX/publications.html (It was in 'Beyond Address Spaces.') [3] https://dl.acm.org/doi/abs/10.1145/1029873.1029880 https://dl.acm.org/doi/abs/10.1145/1029873.1029880
truenorth 3y ago
Incremental alternatives to stop-the-world garbage collectors were well known over 30 years ago.
- mgaunard 3y ago
  The problem with the Boehm GC has always been that it's conservative. If it was something built into the language then you could do much better, but then that language wouldn't be C++.
NelsonMinar 3y ago
What I love about the Boehm collector is the hack that enables it to work in a language with no runtime typing like C. It literally guesses what's a pointer. In C pointers are basically integers but they're unusual numbers, often quite large, and you know the entire set of valid numbers if you control malloc(). Surprisingly this worked even in 32 bit architectures.
- chubot 3y ago
  I don't see that this is something to "love", and what you describe doesn't capture the full extent of the approximation. 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 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.
m4nu3l 3y ago
I once wrote a non-conservative generational GC for C++ just as an exercise, with the constraint that I could only use standard C++ (it was in C++17). 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.
- frutiger 3y ago
  Did you ever publish this library?
rurban 3y ago
I have a library which has an extremely slow free, around 2m for large files, because of unnaturally scattered allocation patterns, but this old conservative GC didn't help at all. It was about 40% slower with libgc. mimalloc was a bit better. Best would be an arena allocator without free, or at least a properly fast GC, like mps https://github.com/Ravenbrook/mps https://github.com/Ravenbrook/mps, but this would be too much work.
- CyberDildonics 3y ago
  If you have a program that takes 2 minutes to free allocations, that implies 100 million to 1 billion small allocations. An arena is not the answer, a normal data structure is (most likely a vector). I'm not sure an arena is ever really the answer, because it seems like a poor work around to multiple small allocations, which shouldn't happen in the first place. 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.
  - naasking 3y ago
    > An arena is not the answer, a normal data structure is (most likely a vector). I'm not sure an arena is ever really the answer, because it seems like a poor work around to multiple small allocations, which shouldn't happen in the first place. 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.
    - CyberDildonics 3y ago
      inlined into a vector 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.
Jeaye 3y ago
I have been using the Boehm-Demers-Weiser GC for jank [1], the native Clojure dialect on LLVM with C++ interop. Since jank is a Clojure dialect, and Clojure is built primarily on persistent, immutable data structures, there are potentially a lot of references to objects, potentially cyclical, across many threads, and there's a lot of garbage being churned. I originally started with reference counting and RAII, using boost::intrusive_ptr and an atomic count. The GC was actually 2x faster, in the sequence benchmark I was trying to optimize. 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. 1: https://jank-lang.org/ https://jank-lang.org/ 2: https://www.mmtk.io/code https://www.mmtk.io/code
- pharmakom 3y ago
  Immutable structures cannot be cyclical. Maybe I’m missing something?
  - nlitened 3y ago
    In Clojure, the data structures may usually contain references to mutable cells, which in turn may form cycles.
  - Jeaye 3y ago
    Exactly as nlitened mentioned, Clojure has a few difference reference types, which are boxes that hold pointers to more immutable values. The values within those boxes can be changed transactionally. This allows for cyclical references.
- mtlmtlmtlmtl 3y ago
  Just want to say, Never heard of Jank before and it looks awesome, great work!. 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 :)
dang 3y ago
Related. Others? A Garbage Collector for C and C++ - https://news.ycombinator.com/item?id=9862135 https://news.ycombinator.com/item?id=9862135 - July 2015 (73 comments)
gregfjohnson 3y ago
This thread brings to mind an issue I’ve wondered about: For hard real-time systems, do people use specialized CPU’s and hardware? Caches can introduce hard-to-predict timing issues. I’m sure there are other aspects of modern hardware that present similar problems; large pipelines? Speculative instruction execution? Does Intel Time-Coordinated Computing address some of these hardware issues? Are there embedded CPU’s from TI, Intel, AMD, etc. that are specifically designed to support predictable and understandable “lockstep” hard real-time time behavior?
- deschutes 3y ago
  It's an interesting question and one I'm unqualified to answer. From a brief survey I gather at least caching is enabled for some hard real time systems. The name of the game seems to be employing caches in ways that provably decrease worst case execution time. For example, ignoring associativity, if your task's worst case working set fits into a given cache level, you can reason that the task misses each line at most once. That's almost certainly a dramatic improvement in wcet over cache disabled. 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_CSUR15.pdf https://cs-people.bu.edu/rmancuso/files/papers/cache_survey_...
HarHarVeryFunny 3y ago
I guess garbage collection has it's uses, but it's very niche. Since C++11 (i.e 2011) (STL, unique_ptr, shared_ptr), any need for it in C++ has all but disappeared. For the most part you are using STL data structures, and if you need something custom then just use a class with a smart pointer member owner, and you get memory management for free (and a lot more performant than a garbage collector).
- Rochus 3y ago
  There are a lot of cases where unique and shared pointers are no good solution, and where a GC would help (e.g. when there is no clear ownership hierarchy but a lot of mutual dependencies between objects). And not to forget that smart pointers come with a non-negligible cost.
  - HarHarVeryFunny 3y ago
    shared_ptr essentially provides reference counted garbage collection. Sure there's a small overhead to smart pointers, but in 2024 it's a very odd application where you are compute bound and pointer dereferencing is the reason!! 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.
    - Rochus 3y ago
      > Sure there's a small overhead to smart pointers 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#issuecomment-1672960484 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/testcases/Are-we-fast-yet/Are-we-fast-yet_results_linux.pdf 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.
Animats 3y ago
> In our experience, the only examples we have found of a failure with the current collector, even in multi-threaded code, were contrived. 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 http://s3.amazonaws.com/nrbook.com/book_C210.html page 19.
einpoklum 3y ago
Related C++ Stackoverflow question/discussion: "Why Doesn't C++ have a garbage collector?" https://stackoverflow.com/q/147130/1593077 https://stackoverflow.com/q/147130/1593077 and my answer: https://stackoverflow.com/a/48046118/1593077 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."

132 points by swatson741 3y ago

Ah the spectre of the 80s, most famously used by the ancient fork of Mono that Unity uses, leading to GC-pause induced stutters that have plagued gaming for over a decade. I'd estimate that the bad rap GC languages get can be traced back to this piece of code.

pyeri 3y ago
You don't need to go that far for GC's bad rep considering that excruciatingly slow Python can be found TODAY!
- DarkNova6 3y ago
  But you must understand, Python is safe and C is difficult. Therefore, to be fast we need Python (fast development that is because nobody _really_ cares about performance (or maintainability)). If only more than two languages would exist!
  - h4ch1 3y ago
    > fast development that is because nobody _really_ cares about performance (or maintainability) This is either 1. missing a /s 2. delusion 3. bait
    - tmtvl 3y ago
      I believe it's 1, considering the statement 'If only more than two languages would exist!'. Granted, sarcasm doesn't transmit well in written text.
- amelius 3y ago
  Python wasn't designed for speed.
- torginus 3y ago
  Afaik (C)Python uses reference counting, it's slowness comes from the interpreter itself.
  - _flux 3y ago
    It uses also tracing GC to handle RC loops. 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.
  - kaba0 3y ago
    Ref counting is a GC-algorithm, and the slowest at that (especially with multi-core sync, but that’s not the case with python), as a tradeoff for less memory consumption.
- adev_ 3y ago
  > You don't need to go that far for GC's bad rep considering that excruciatingly slow Python can be found TODAY! 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/fastest/python.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
p_l 3y ago
Mono is nowhere close to major use case of it, it has been succesfully deployed in maaaany projects. 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.
- jstimpfle 3y ago
  How did GC visibly fix their issues? 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.
  - pjmlp 3y ago
    The deterministic myth only works out for basic types, see Herb Stutter CppCon 2015 talk on the matter, and how performance workarounds turn out a poor man's GC.
    - jstimpfle 3y ago
      What? RAII is totally deterministic, not sure what you want to contend here. CppCon 2015: Herb Sutter "Writing Good C++14... By Default": Not sure where I'm going to find my answer here. 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.
mihaaly 3y ago
I assume that real time computing should have used real time computing compatible techniques. But luckily those exposed to other than games and game development might feel less aversion towards GC, probably even the other way around.
pjmlp 3y ago
Another reason being that many people don't get GC theory, nor that because a language has some form of automatic resource management, does not mean the language doesn't offer other mechanisms.
yxhuvud 3y ago
Another big reason is the lack of value types in languages like Java. Modern languages with a GC tend to have those, and where it makes sense to use them they help, a lot.
- amelius 3y ago
  What are "value types"?
  - greesil 3y ago
    In Java, primitives. int, boolean, float. Allocated on the stack, or the heap along with the object it is a part of.
  - jstimpfle 3y ago
    If you nest an object within another object you often want to embed the child directly in its parent, sharing the memory and avoiding the indirection that you get if you nest with a reference as is the typical approach with GC languages. Also embedding makes it clear that it's a 1:1 relation, i.e. non-optional, fixed identity etc. 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.
    - ghusbands 3y ago
      > 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?
      - groestl 3y ago
        > 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.
rbehrends 3y ago
This needs some qualifications. 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 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).
- cplusplusfellow 3y ago
  For all of the reasons you note above, this is why I've almost exclusively dealt with arena-style allocations of fixed-object-sizes when doing ultra low latency work.
  - iainctduncan 3y ago
ack_complete 3y ago
Sadly it was not just the GC, there were plenty of problems in Mono itself that adversely affected GC performance. 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.

itsphilos 3y ago

My experience with Cpp isn't that extensive, but what is the use-case of a garbage collector in this language? I always had the impression that with the well-defined lifetimes of objects, you wouldn't really create garbage to begin with, but I guess there are some use-cases I don't yet know about?

FartyMcFarter 3y ago
> what is the use-case of a garbage collector in this language? 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.
pjmlp 3y ago
Targeting .NET, hence C++/CLI, integration with Blueprints, hence Unreal C++.
mike_hearn 3y ago
It's pretty useful. Chrome uses one extensively for example (called Oilpan). So does Unreal Engine. GC in C++ is much more widely used than people realize. 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!
- 3y ago

habibur 3y ago

in CPP you don't need GC. Use RAII. Objects only need a constructor, destructor and a copy-constructor for a very efficient reference counting GC that's almost impossible to leak. 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; and later during GC get the current stack address again and trace from old one to new. You also need to save the registers and can do it in a semi portable way using unix setjmp() longjmp() functions which save the register values into a structure that you can then later trace. There's also the issues of split stack that you need to keep into mind. But the positive thing is memory alignment ensures pointers are all 8 byte aligned, you only need to read address%8 values in between. It's a bit hackish regardless. 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.

pjmlp 3y ago
In theory, yes. 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.
- mgaunard 3y ago
  I wouldn't call hazard pointers garbage collection. 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.
rst 3y ago
The RAII/ref-counting technique often works great, but not always. Cyclic structures are a problem -- so, if you've got, say, a global tree structure with bidirectional parent/child links, you'll need some kind of special-casing to make ref-counting clean up an entire abandoned subtree. A full GC does take care of cases like this.

shrubble 3y ago

Bjarne Stroustrup's view: https://www.stroustrup.com/bs_faq.html#garbage-collection https://www.stroustrup.com/bs_faq.html#garbage-collection

nickpsecurity 3y ago

I think a mix of methods are best. We can use non-GC methods for whatever is easiest to prove is safe. In Python, they then use reference counting by default. Then, a GC when that would be a problem. I also prefer when the GC let's me tell it to immediately delete something which it just checks incrementally. Then, performance-sensitive modules can be coded without GC's using tools like Meta's Infer which work on large modules. 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/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/immix/ [2] https://www4.cs.fau.de/Projects/JX/publications.html https://www4.cs.fau.de/Projects/JX/publications.html (It was in 'Beyond Address Spaces.') [3] https://dl.acm.org/doi/abs/10.1145/1029873.1029880 https://dl.acm.org/doi/abs/10.1145/1029873.1029880

truenorth 3y ago

Incremental alternatives to stop-the-world garbage collectors were well known over 30 years ago.

mgaunard 3y ago
The problem with the Boehm GC has always been that it's conservative. If it was something built into the language then you could do much better, but then that language wouldn't be C++.

NelsonMinar 3y ago

What I love about the Boehm collector is the hack that enables it to work in a language with no runtime typing like C. It literally guesses what's a pointer. In C pointers are basically integers but they're unusual numbers, often quite large, and you know the entire set of valid numbers if you control malloc(). Surprisingly this worked even in 32 bit architectures.

chubot 3y ago
I don't see that this is something to "love", and what you describe doesn't capture the full extent of the approximation. 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 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.

m4nu3l 3y ago

I once wrote a non-conservative generational GC for C++ just as an exercise, with the constraint that I could only use standard C++ (it was in C++17). 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.

frutiger 3y ago
Did you ever publish this library?

rurban 3y ago

I have a library which has an extremely slow free, around 2m for large files, because of unnaturally scattered allocation patterns, but this old conservative GC didn't help at all. It was about 40% slower with libgc. mimalloc was a bit better. Best would be an arena allocator without free, or at least a properly fast GC, like mps https://github.com/Ravenbrook/mps https://github.com/Ravenbrook/mps, but this would be too much work.

CyberDildonics 3y ago
If you have a program that takes 2 minutes to free allocations, that implies 100 million to 1 billion small allocations. An arena is not the answer, a normal data structure is (most likely a vector). I'm not sure an arena is ever really the answer, because it seems like a poor work around to multiple small allocations, which shouldn't happen in the first place. 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.
- naasking 3y ago
  > An arena is not the answer, a normal data structure is (most likely a vector). I'm not sure an arena is ever really the answer, because it seems like a poor work around to multiple small allocations, which shouldn't happen in the first place. 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.
  - CyberDildonics 3y ago
    inlined into a vector 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.

Jeaye 3y ago

I have been using the Boehm-Demers-Weiser GC for jank [1], the native Clojure dialect on LLVM with C++ interop. Since jank is a Clojure dialect, and Clojure is built primarily on persistent, immutable data structures, there are potentially a lot of references to objects, potentially cyclical, across many threads, and there's a lot of garbage being churned. I originally started with reference counting and RAII, using boost::intrusive_ptr and an atomic count. The GC was actually 2x faster, in the sequence benchmark I was trying to optimize. 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. 1: https://jank-lang.org/ https://jank-lang.org/ 2: https://www.mmtk.io/code https://www.mmtk.io/code

pharmakom 3y ago
Immutable structures cannot be cyclical. Maybe I’m missing something?
- nlitened 3y ago
  In Clojure, the data structures may usually contain references to mutable cells, which in turn may form cycles.
- Jeaye 3y ago
  Exactly as nlitened mentioned, Clojure has a few difference reference types, which are boxes that hold pointers to more immutable values. The values within those boxes can be changed transactionally. This allows for cyclical references.
mtlmtlmtlmtl 3y ago
Just want to say, Never heard of Jank before and it looks awesome, great work!. 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 :)

dang 3y ago

Related. Others? A Garbage Collector for C and C++ - https://news.ycombinator.com/item?id=9862135 https://news.ycombinator.com/item?id=9862135 - July 2015 (73 comments)

gregfjohnson 3y ago

This thread brings to mind an issue I’ve wondered about: For hard real-time systems, do people use specialized CPU’s and hardware? Caches can introduce hard-to-predict timing issues. I’m sure there are other aspects of modern hardware that present similar problems; large pipelines? Speculative instruction execution? Does Intel Time-Coordinated Computing address some of these hardware issues? Are there embedded CPU’s from TI, Intel, AMD, etc. that are specifically designed to support predictable and understandable “lockstep” hard real-time time behavior?

deschutes 3y ago
It's an interesting question and one I'm unqualified to answer. From a brief survey I gather at least caching is enabled for some hard real time systems. The name of the game seems to be employing caches in ways that provably decrease worst case execution time. For example, ignoring associativity, if your task's worst case working set fits into a given cache level, you can reason that the task misses each line at most once. That's almost certainly a dramatic improvement in wcet over cache disabled. 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_CSUR15.pdf https://cs-people.bu.edu/rmancuso/files/papers/cache_survey_...

HarHarVeryFunny 3y ago

I guess garbage collection has it's uses, but it's very niche. Since C++11 (i.e 2011) (STL, unique_ptr, shared_ptr), any need for it in C++ has all but disappeared. For the most part you are using STL data structures, and if you need something custom then just use a class with a smart pointer member owner, and you get memory management for free (and a lot more performant than a garbage collector).

Rochus 3y ago
There are a lot of cases where unique and shared pointers are no good solution, and where a GC would help (e.g. when there is no clear ownership hierarchy but a lot of mutual dependencies between objects). And not to forget that smart pointers come with a non-negligible cost.
- HarHarVeryFunny 3y ago
  shared_ptr essentially provides reference counted garbage collection. Sure there's a small overhead to smart pointers, but in 2024 it's a very odd application where you are compute bound and pointer dereferencing is the reason!! 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.
  - Rochus 3y ago
    > Sure there's a small overhead to smart pointers 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#issuecomment-1672960484 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/testcases/Are-we-fast-yet/Are-we-fast-yet_results_linux.pdf 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.

Animats 3y ago

> In our experience, the only examples we have found of a failure with the current collector, even in multi-threaded code, were contrived. 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 http://s3.amazonaws.com/nrbook.com/book_C210.html page 19.

einpoklum 3y ago

Related C++ Stackoverflow question/discussion: "Why Doesn't C++ have a garbage collector?" https://stackoverflow.com/q/147130/1593077 https://stackoverflow.com/q/147130/1593077 and my answer: https://stackoverflow.com/a/48046118/1593077 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."