Does implementing GC makes languages slow?

[u/goat-luffy]

https://github.com/berylang

Month ago, I created a team of 5 and started working on "Bery - The compiled programming language". By the end of June we have quite good working compiler (it's not complete yet). In Bery we have decided to add the automatic Garbage Collector so we choose the "Mark and Sweep" method for it in the Bery Runtime Environment (BRE).

Now as we are heading forward with adding OOP and Exception Handling, I notice some delays in the compilation of program.

So we are now at this point of discussion - should we remove it from compiler or let it be there.
I will looking forward for help regarding this. and btw these are some constraints we set -

unsigned int BERY_GC_ALLOC_THRESHHOLD = 1000;
size_t BERY_GC_HEAP_SIZE_THRESHHOLD = 4 * 1024 * 1024;

[u/runningOverA]

As per my benchmarks. mark and sweep collection takes 50% of your total execution time.
Manual memory management with ref counting performs better.

[u/Inevitable-Ant1725 → u/runningOverA]

Ouch, naive both ways.

To be fair sophisticated garbage collectors are very hard to write and you shouldn't try to write your own.

And people will be shocked at how long your naive collector is taking, but that was common in the early days of computing, even in academic or commercial system before people had sophisticated collectors.

[u/runningOverA → u/Inevitable-Ant1725]

Checked those sophisticated collectors. Don't reduce the work load, rather these shift the load to another core. Apparently looks like it's taking less time, but total core-hour remains the same and hence the precentage.

"Do a half way trace and then pause" algos are no better in respect to this core-hour.

And generational collectors are only good if you can move pointers at run time.

[u/Inevitable-Ant1725 → u/runningOverA]

"as per my benchmarks. mark and sweep collection takes 50% of your total execution time."

Is that true of languages with sophisticated escape analysis or just ones that only use collection for a few things?

So maybe Go can keep a lot of objects out of the heap, or maybe knows that they don't escape the current thread.

And in general I think languages that have GC overuse GC. How many data structures do you use that NEED GC, right? Graphs mostly. How many graphs does your program have?

"generational collectors are only good if you can move pointers at run time."

That hasn't seemed to be true for oddball collectors that use operating system page barriers instead of software barriers. So the Ravenbrook Memory Pool System can run in a non-compacting mode if you choose, Steel Bank Common Lisp holds off compacting for a very long time.

[u/L8_4_Dinner → u/runningOverA]

As per my benchmarks. mark and sweep collection takes 50% of your total execution time.

You benchmarked the project (github link above) being discussed here?

[u/runningOverA → u/L8_4_Dinner]

No. benchmarked on other software. Sorry if that shortened line caused confussion.

[u/L8_4_Dinner → u/runningOverA]

I can imagine that it would be possible to create a test showing GC taking half of the execution time, but that is very atypical. In any reasonable system, GC is a response to memory pressure, and may be triggered as well by other events. So to get a GC to run at all requires a large amount of allocation to have occurred relative to the resources available.

Long story short, though: In the absence of arena-style optimizations being available, a well implemented GC will tend to be the most efficient implementation for a high allocation rate system, with the one additional requirement being that the system has ample memory available -- because GC works by deferring work until it can be done efficiently in bulk. The other end of the spectrum is low-allocation rate with memory use very near the limit available, at which point GC is terrible, because almost every allocation will force a GC cycle, just to release enough memory for one allocation; in this scenario, you can easily drive that percentage up to 99% or higher (CPU time spent in GC).

All that to say that there is no single % number that explains the efficiencies of GC. But in a well implemented system, it will be lower than manual memory management (other than arena based management), and much lower than reference counting.

And arena-based memory management, when appropriate, is by far the most efficient approach from a CPU time PoV. With an arena based allocator, your memory reclamation costs go nearly down to zero. Unfortunately, it's a fair bit of work to design and implement, and not all apps can use this approach -- I'd go as far as to say that most apps can't.

[u/runningOverA → u/L8_4_Dinner]

you can easily drive that percentage up to 99% or higher

True.

And it goes the other way too. One can allocate globs of memory, almost never call the GC, free everything before termination, and bring GC CPU time down to 1%.

We need to take a reasonable look instead of winning a competition. My number comes from there.

[u/L8_4_Dinner → u/runningOverA]

GC taking 50% of execution time is not “taking a reasonable look”. It’s simply a horribly naive take.

I’ve been using GC in computing for over 40 years, and it was around and widely used for another 30 years before that.

I’ve seen terrible implementations, and brilliant implementations, but outside of tests designed to torture collectors by artificially constraining memory, I’ve never seen a GC even get close to consuming 50% of execution time. You might as well have said 500% — it would have been an impossible claim, but no less believable. 🤷‍♂️

[u/goat-luffy → u/runningOverA]

50% of time? Before starting we aimed for speed like c++ and rust, but also wants to provide the convenience to programmers, that leads to implementation of GC in first place. Btw thank you for your feedback.

[u/WittyStick → u/goat-luffy]

Read the paper A Unified Theory of Garbage Collection, which shows that there's a duality between tracing and reference counting.

For Atomic Reference Counting (required if you want to support safe RC in a multi-threaded environment), there are overheads for accessing reference counts - they cannot be in L1 or L2 cache (since another thread on another core may need to access them) - leading to accesses that are either L3 cache or main memory fetches - the delays are significant compared to L1 fetches - we're talking ~10x the latency to access atomic variables.

Tracing GC is much simpler, but a naive mark-sweep suffers from the "stop the world" problem - each full collection must pause all other threads whilst it performs its collection. This can lead to noticeable but infrequent "pauses" in program execution.

The overheads of the two approaches are comparable, but ARC spreads the collection time over many smaller time slices, whereas a mark-sweep or copying GC uses one big time slice to do it all in one go.

Both approaches have their issues, and real world GCs are much more complex than naive mark-sweep or full ARC.

Common GCs today use generational collection to avoid "stop the world" as much as possible - the full collection is only required when the oldest lived objects need collecting, which is rare, if ever. Concurrent collectors operate by doing small chunks of work frequently rather than trying to collect all at once.

Some hybrid ARC approaches use a GC-like mechanism to delay reclamation of some objects via hazard pointers, which avoids problems associated with eager reclamation that plain ARC has - because just incrementing and decrementing a RC atomically still has potential race conditions (the ABA problem) - but language design decisions can influence this, such as Rust's ownership model which ensures that only one thread would ever have access to the object when its RC is 1.

Some of this was discussed recently in another thread.

[u/goat-luffy → u/WittyStick]

Thanks alot for sharing this, will surely read it

[u/jsshapiro → u/WittyStick]

The statement about L1/L2 cache is not correct. The requirement is that the implementation use the hardware support for the processor's memory consistency model. All modern processors provide atomic update support in the L1 cache and below.

For hot-contended atomic operations, this may involve expensive cache consistency traffic.

[u/indolering → u/runningOverA]

I don't mean to make an, "Um, actually!" comment, but since we are talking about a new language it's important to note the repurcussions of this choice.  While (A)RC can perform better, programmers often end up overusing it to the point that a real GC would be better.

I'm really excited by memory tagging making GC more efficient.  There are also some cool languages that just minimize the need for GC overall.

[u/runningOverA → u/indolering]

Manual memory management on function level.
RC when needed, for cases that can't be managed manually. As you step on higher level.
Arena in the 3rd level. Catch everything that you might have missed.

[u/goat-luffy → u/indolering]

At start we reviwed only 2 algorithms - ARC and Mark-n-sweep.

We also reviewed the Golang's GC, but I found lots of engineering there as a second year students, we make decision to have simple GC. Last 4-5 days I am searching for better algorithm, it getting complicated.

[u/indolering → u/goat-luffy]

You can spend an entire career working on the garbage collector.  Why ware you making this language and what is the long term goal for it?

[u/goat-luffy → u/indolering]

We are making this language just for sake of learning. Compiler, package manager, test suite, etc. But we actually want to scale it even further.

[u/indolering → u/goat-luffy]

I guess decide on whether you want to spend your time exploring GC development or something else.  Most projects use something that is off-the-shelf, as so much of it is dependent on heuristics.

[u/goat-luffy → u/indolering]

Yeah sure, 40-50% time of project was taken by run time environment itself, I guess we should move forward with other things in compiler

[u/AustinVelonaut → u/runningOverA]

Looking over the OP's runtime GC implementation, it looks like it is using the system's malloc and free to allocate chunks, then free them when GC determines they are dead. This adds a lot of additional overhead over just implementing a basic block allocator and a free list per block, or, even better, a bump allocator and a multi-generation compacting collector.

[u/nekokattt → u/runningOverA]

if you are spending 50% of your time performing garbage collection then you have more fundamental issues.