I'd estimate that the bad rap GC languages get can be traced back to this piece of code.
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).
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.
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).
iain
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!
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?
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.
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.
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.
> 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.
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.
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.
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/...
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.
If only more than two languages would exist!
This is either
1. missing a /s
2. delusion
3. bait
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.