If garbage collection always sacrifice performance in multi-threaded languages, then how do some languages approch this problem?

Question

Mark-and-Sweep garbage collection need to work over the graph of all objects in the process, and would stall threads to make the operation safe with regard to threads. I can think of no way to work around this and make it efficient.

But how are some system/application-programming languages solving it? The specific question I'm asking is, how do (the reference implementation, or if the details're not available, the secondary open-source implementation), Microsoft C#, Sun/Oracle Java, and Apple Swift, these 3 languages approach the problem?

Answer 1

Technically speaking, garbage collection is a feature of the runtime environment, not the language. As for specifics:

• The Microsoft Common Language Runtime (CLR) and Java Virtual Machine both divide their heaps into “generations”, based on the idea that most objects will be small and short-lived, and can be allocated and collected independently of long-lived objects. This removes the need “to work over the graph of all objects in the process”, since most of the time only the most recent generation will be collected.
• Swift is different, basic its memory management around automatic reference counting.
• CPython uses a hybrid approach, relying mainly on reference counting, but with an additional garbage collector to detect the cyclic garbage that reference counting does not.

Mark-and-Sweep garbage collection...would stall threads to make the operation safe with regard to threads.

This is a common problem. Some runtimes let you choose different GC algorithms, or fine-tune parameters like the heap size or number of GC threads, but ultimately, programmers of GC-ed languages have just learned to live with the occasional GC pauses.

One popular optimization (if you can call it that) is the null garbage collector. That is, if your program never actually allocates more memory than your computer has, then its legal to simply never collect the garbage, and just leave it to the OS to free the process's memory when it exits.

Answer 2

Mark-and-Sweep garbage collection need to work over the graph of all objects in the process.

It does not! Generational GC works over the graph of all objects in a generation. Objects that survive one generation are promoted to the next, which is GC'd less often. You therefore get fast reclamation of short-lived temporaries, and infrequent scans of long-lived objects.

and would stall threads to make the operation safe with regard to threads

There are clever things you can do to avoid stop-the-world collections, but generally we just live with the tax.

I can think of no way to work around this and make it efficient.

"Efficiency" is work done divided by cost, so before you spend a lot of time thinking about ways to improve efficiency, start by defining what your metrics are for "work" and "cost".

Mark-and-sweep GCs are efficient enough for the vast majority of business processes; in cases where collection stalls are frequent enough to exceed user-focused performance budgets, my usual advice is to start by reducing collection pressure via pooling or other strategies. We did a lot of that when building the Roslyn C# compiler.

But how are some system/application-programming languages solving it?

I once asked a gardener at Oxford how they got their lawn so nice. "Rake the dew off every morning, mow it once a week, run a lawn roller over it once a month, for 400 years". You too can have a great lawn; start today.

The .NET GC is one of the most heavily tuned pieces of software on the planet. Patrick Dussud did a great job in the initial performance tuning and there has been literally two decades of a team of experts continuing to tweak it.

You solve this performance problem the same way you solve all foundational subsystem performance problems. (1) think about performance of foundational subsystems up front, during design, (2) hire industry leading experts (3) measure measure measure measure measure.... (4) make careful changes designed to achieve particular goals, (5) go back to step 3. Do that for 20 years and you too will have a great GC.

Answer 3

The basic answer is that solving this is hard and a balancing act between different priorities. the other part of the answer is that it's not just garbage collection that suffers in multithreaded environments. manual memory management gets a lot harder also. Some of the strategies to consider are

1. keep as many values as possible off the heap (immutable data generally can be moved to stack or registers by a sufficiently smart compiler)
2. multithreaded gc so the pauses are shorter
3. use a concurrent gc where most of the gc time isn't done inside the lock.
4. atomic reference counting.

Answer 4

You can have a fully concurrent GC that does not stop the mutator threads at all. Look at the SGCL for C++.

A variation of the three-color mark and sweep algorithm was used. The GC engine work in a separate thread. Separate stacks are created for pointers so that the mutator thread does not have to be stopped while the GC scans its stack. Simple atomic write barriers allow mutator to modify pointers while GC marks live objects.