<p>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.</p>
<p>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?</p>

<memory-management>
If garbage collection always sacrifice performance in multi-threaded languages, then how do some languages approch this problem?
CC BY-SA 4.0
2024-02-07T02:53:04.163Z
There are various garbage collection algorithms (such as the [train algorithm](https://wiki.c2.com/?TheTrainAlgorithm)) that are more suited to minmizing stalls.
Chris Dodd
CC BY-SA 4.0
2024-02-07T03:26:38.657Z
Not enough for a full answer, but have a look at the OCaml 5 multicore garbage collector: https://kcsrk.info/multicore/gc/2017/07/06/multicore-ocaml-gc/
blueberry
CC BY-SA 4.0
2024-02-07T09:24:36.237Z
This is a very broad question without a single answer.  Probably the most important optimisation is generational garbage collection.  Beyond that, the overhead of tracing may be less than you think, because it is amortised and may enable more efficient (time-efficient and cache-efficient) allocation strategies than piecemeal allocation.  If you are interested in gc implementation I recommend reading the gc handbook.
Moonchild
CC BY-SA 4.0
2024-02-07T11:10:35.813Z
@Moonchild If asking the best strategy, then that'd be too broad a question. I've clarified that I want to know how the specific 3 languages I've enumerated approach the problem.
DannyNiu
CC BY-SA 4.0
2024-02-07T13:00:38.473Z
"I want to know how the specific 3 languages I've enumerated approach the problem" – They don't. They leave it up to the implementation. None of the three specific languages you mentioned require garbage collection, and none of them even mention it in their specifications. It is perfectly legal to implement either Java or C# without GC.
Jörg W Mittag
CC BY-SA 4.0
2024-02-07T13:09:03.907Z
The memory model of Swift is carefully designed such that Swift can be implemented without needing a tracing collector, it can be implemented using Reference Counting, and all existing industrial-strength, production-ready mainstream implementations of Swift do.
Jörg W Mittag
CC BY-SA 4.0
2024-02-07T20:12:35.940Z
State-of-the-art garbage collectors, e.g. in JVM, use virtual memory to establish barriers so that collection/tracing can happen concurrently with running the threads/mutators.  The barriers interrupt a thread when it uses something that the gc has altered (i.e. moved) or previously scanned, giving the gc a chance to fix something for that thread.
Erik Eidt
CC BY-SA 4.0
2024-02-07T21:05:22.807Z
@JörgWMittag Reminds me of the original Lisp Machine garbage collector: Reboot every day or so. The OS was probably unstable enough that it took care of that for you automatically.
Barmar
CC BY-SA 4.0
2024-02-07T21:10:44.447Z
@Barmar: For a shell language that might very well be a valid strategy. Scripts only have a short lifetime, and most objects they manipulate are provided by the host and their lifetime is independent of the script. So, the garbage will just be released by the OS when the process exits.
Jörg W Mittag
CC BY-SA 4.0
2024-02-08T01:05:14.763Z
@JörgWMittag I hate to be contradictory but I think you'll find that every version of the C# specification mentions garbage collection literally on page one of the spec. The spec does not *require* any specific garbage collection regime in a conforming implementation. But C# was specifically designed for runtimes that have GCs.
Eric Lippert
CC BY-SA 4.0
2024-02-08T01:08:30.223Z
@JörgWMittag: The tenth line of the current version of the spec is "*The language, and implementations thereof, should provide support for software engineering principles such as strong type checking, array bounds checking, detection of attempts to use uninitialized variables, and automatic garbage collection.*"
Eric Lippert
CC BY-SA 4.0
2024-02-08T01:24:08.387Z
@ErikEidt virtual memory is not generally used for gc barriers.  it is too coarse and faults are too slow
Moonchild
CC BY-SA 4.0
2024-02-08T04:12:12.980Z
@JörgWMittag: The Java spec also discusses GC requirements on page one, and goes on to describe the interactions between the GC and finalization semantics and type unloading semantics. I'm not sure where you're getting this idea that the specs do not discuss collection.
Eric Lippert
CC BY-SA 4.0
2024-02-08T04:18:12.953Z
@JörgWMittag: And I just checked the swift specification, which has a whole section on how its GC works; it refers to it as "automatic reference counting" rather than "garbage collection", but an ARC is a garbage collector.
Eric Lippert
<blockquote>
<p>Mark-and-Sweep garbage collection need to work over the graph of all objects in the process.</p>
</blockquote>
<p>It does not! Generational GC works over the graph of all objects in a <em>generation</em>. 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.</p>
<blockquote>
<p>and would stall threads to make the operation safe with regard to threads</p>
</blockquote>
<p>There are clever things you can do to avoid stop-the-world collections, but generally we just live with the tax.</p>
<blockquote>
<p>I can think of no way to work around this and make it efficient.</p>
</blockquote>
<p>&quot;Efficiency&quot; 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 &quot;work&quot; and &quot;cost&quot;.</p>
<p>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.</p>
<blockquote>
<p>But how are some system/application-programming languages solving it?</p>
</blockquote>
<p>I once asked a gardener at Oxford how they got their lawn so nice.  &quot;Rake the dew off every morning, mow it once a week, run a lawn roller over it once a month, for 400 years&quot;.  You too can have a great lawn; start today.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2024-02-08T01:17:12.000Z
2024-02-08T04:32:50.970Z
2024-02-08T04:32:50.970Z
Eric Lippert
CC BY-SA 4.0
2024-02-08T16:13:50.690Z
Reminds me of a meme where one guy asks another how he wrote such good code, and he replies, "it's not my code." Standing on the shoulders of giants.
Seggan
CC BY-SA 4.0
2024-02-09T01:33:03.257Z
@Seggan: That reminds me of the Peter Sellers movie where he asks the hotel manager "does your dog bite?" and the manager says "no", and then the dog bites him and he says "I thought you said your dog does not bite!" "That sir, is not my dog."
Eric Lippert
<p>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</p>
<ol>
<li>keep as many values as possible off the heap (immutable data generally can be moved to stack or registers by a sufficiently smart compiler)</li>
<li>multithreaded gc so the pauses are shorter</li>
<li>use a concurrent gc where most of the gc time isn't done inside the lock.</li>
<li>atomic reference counting.</li>
</ol>

CC BY-SA 4.0
2024-02-07T17:31:21.970Z
2024-02-07T17:31:21.970Z
Oscar Smith
<p>You can have a fully concurrent GC that does not stop the mutator threads at all. Look at the <a href="https://github.com/pebal/sgcl" rel="nofollow noreferrer">SGCL</a> for C++.</p>
<p>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.</p>

CC BY-SA 4.0
2024-02-16T09:13:49.620Z
2024-02-16T13:28:33.603Z
2024-02-16T13:28:33.603Z
Pebal
CC BY-SA 4.0
2024-02-16T09:52:03.040Z
Please disclose your affiliation to the linked library as per [the help center](https://langdev.stackexchange.com/help/promotion).
MisterMiyagi
CC BY-SA 4.0
2024-02-16T10:44:18.603Z
I do not hide my affiliation to this library. I also don't understand what significance it has for the topic. It is just an example of an implementation of a non-blocking GC algorithm.
Pebal
CC BY-SA 4.0
2024-02-16T11:04:56.997Z
I don't mind a self-promoting answer as long as they solve, or demonstrate their idea of solving said problems. My questions for you here are: do you intend to and are capable of maintain your library for long-term? is your library in alpha, beta, golden-master, or production status?
DannyNiu
CC BY-SA 4.0
2024-02-16T11:16:32.957Z
This library was created to test whether it is possible to implement an efficient, fully non-blocking GC. Its status is "it seems to work", I treat it as a testing ground.
Pebal
CC BY-SA 4.0
2024-02-16T11:58:20.450Z
Your code is a 2.6k line of monologue (well-beyond my self-claimed ~300 optimum), can you provide a sketch of how you view and approach the problem?
DannyNiu
CC BY-SA 4.0
2024-02-16T13:29:05.157Z
I edited my post.
Pebal
<p>Technically speaking, garbage collection is a feature of the runtime environment, not the <em>language</em>.  As for specifics:</p>
<ul>
<li><a href="https://learn.microsoft.com/en-us/dotnet/standard/garbage-collection/fundamentals" rel="noreferrer">The Microsoft Common Language Runtime (CLR)</a> <a href="https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html" rel="noreferrer">and Java Virtual Machine</a> 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.</li>
<li>Swift is different, basic its memory management around <a href="https://docs.swift.org/swift-book/documentation/the-swift-programming-language/automaticreferencecounting/" rel="noreferrer">automatic reference counting</a>.</li>
<li><a href="https://devguide.python.org/internals/garbage-collector/" rel="noreferrer">CPython uses a hybrid approach</a>, relying mainly on reference counting, but with an additional garbage collector to detect the cyclic garbage that reference counting does not.</li>
</ul>
<blockquote>
<p>Mark-and-Sweep garbage collection...would stall threads to make the operation safe with regard to threads.</p>
</blockquote>
<p>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.</p>
<p>One popular optimization (if you can call it that) is <a href="https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13203" rel="noreferrer">the null garbage collector</a>.  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.</p>

CC BY-SA 4.0
2024-02-08T01:32:59.980Z
2024-02-08T01:32:59.980Z
dan04
CC BY-SA 4.0
2024-02-08T03:23:31.507Z
Appreciations for mentioning CPython, it's such good a thinking out of the box.
DannyNiu
CC BY-SA 4.0
2024-02-08T04:22:40.027Z
The null collector is particularly useful in conjunction with process-based concurrency. A trick we used at FB in previous instances of the Hack compiler was to farm program analysis of some subset of files out to as many processes as the physical hardware had processors. Since each process (we hope) did only a relatively small amount of work, we simply turned the GC off for those processes and let the OS deal with it.
Eric Lippert
CC BY-SA 4.0
2024-02-08T04:24:04.990Z
(Not all analysis tasks were amenable to this partitioning scheme and some compiler processes did start running out of memory as the codebase grew. Preventing that looming disaster was a whole other story. :) )
Eric Lippert
CC BY-SA 4.0
2024-02-08T16:50:33.640Z
One amusing use of the null garbage collector was [in a guided missile](https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98125), which was simply designed to explode before it ran out of memory.
dan04
# If garbage collection always sacrifice performance in multi-threaded languages, then how do some languages approch this problem?
Posted by: username_0 on 2024-02-07
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?
**Tags:** memory-management
> **Comments:**
> **username_1**: There are various garbage collection algorithms (such as the [train algorithm](https://wiki.c2.com/?TheTrainAlgorithm)) that are more suited to minmizing stalls.  
> **username_2**: Not enough for a full answer, but have a look at the OCaml 5 multicore garbage collector: https://kcsrk.info/multicore/gc/2017/07/06/multicore-ocaml-gc/  
> **username_3**: This is a very broad question without a single answer.  Probably the most important optimisation is generational garbage collection.  Beyond that, the overhead of tracing may be less than you think, because it is amortised and may enable more efficient (time-efficient and cache-efficient) allocation strategies than piecemeal allocation.  If you are interested in gc implementation I recommend reading the gc handbook.  
> **username_0**: @Moonchild If asking the best strategy, then that'd be too broad a question. I've clarified that I want to know how the specific 3 languages I've enumerated approach the problem.  
> **username_4**: "I want to know how the specific 3 languages I've enumerated approach the problem" – They don't. They leave it up to the implementation. None of the three specific languages you mentioned require garbage collection, and none of them even mention it in their specifications. It is perfectly legal to implement either Java or C# without GC.  
> **username_4**: The memory model of Swift is carefully designed such that Swift can be implemented without needing a tracing collector, it can be implemented using Reference Counting, and all existing industrial-strength, production-ready mainstream implementations of Swift do.  
> **username_5**: State-of-the-art garbage collectors, e.g. in JVM, use virtual memory to establish barriers so that collection/tracing can happen concurrently with running the threads/mutators.  The barriers interrupt a thread when it uses something that the gc has altered (i.e. moved) or previously scanned, giving the gc a chance to fix something for that thread.  
> **username_6**: @JörgWMittag Reminds me of the original Lisp Machine garbage collector: Reboot every day or so. The OS was probably unstable enough that it took care of that for you automatically.  
> **username_4**: @Barmar: For a shell language that might very well be a valid strategy. Scripts only have a short lifetime, and most objects they manipulate are provided by the host and their lifetime is independent of the script. So, the garbage will just be released by the OS when the process exits.  
> **username_7**: @JörgWMittag I hate to be contradictory but I think you'll find that every version of the C# specification mentions garbage collection literally on page one of the spec. The spec does not *require* any specific garbage collection regime in a conforming implementation. But C# was specifically designed for runtimes that have GCs.  
> **username_7**: @JörgWMittag: The tenth line of the current version of the spec is "*The language, and implementations thereof, should provide support for software engineering principles such as strong type checking, array bounds checking, detection of attempts to use uninitialized variables, and automatic garbage collection.*"  
> **username_3**: @ErikEidt virtual memory is not generally used for gc barriers.  it is too coarse and faults are too slow  
> **username_7**: @JörgWMittag: The Java spec also discusses GC requirements on page one, and goes on to describe the interactions between the GC and finalization semantics and type unloading semantics. I'm not sure where you're getting this idea that the specs do not discuss collection.  
> **username_7**: @JörgWMittag: And I just checked the swift specification, which has a whole section on how its GC works; it refers to it as "automatic reference counting" rather than "garbage collection", but an ARC is a garbage collector.  
---
## 4 answers
### Answer by username_12 on 2024-02-08. Score: 5 | Accepted answer
Technically speaking, garbage collection is a feature of the runtime environment, not the *language*. As for specifics:

* [The Microsoft Common Language Runtime (CLR)](https://learn.microsoft.com/en-us/dotnet/standard/garbage-collection/fundamentals) [and Java Virtual Machine](https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html) 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](https://docs.swift.org/swift-book/documentation/the-swift-programming-language/automaticreferencecounting/).
* [CPython uses a hybrid approach](https://devguide.python.org/internals/garbage-collector/), 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](https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13203). 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.
> **Comments:**
> **username_0** (2024-02-08): Appreciations for mentioning CPython, it's such good a thinking out of the box.  
> **username_7** (2024-02-08): The null collector is particularly useful in conjunction with process-based concurrency. A trick we used at FB in previous instances of the Hack compiler was to farm program analysis of some subset of files out to as many processes as the physical hardware had processors. Since each process (we hope) did only a relatively small amount of work, we simply turned the GC off for those processes and let the OS deal with it.  
> **username_7** (2024-02-08): (Not all analysis tasks were amenable to this partitioning scheme and some compiler processes did start running out of memory as the codebase grew. Preventing that looming disaster was a whole other story. :) )  
> **username_12** (2024-02-08): One amusing use of the null garbage collector was [in a guided missile](https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98125), which was simply designed to explode before it ran out of memory.  
---
### Answer by username_7 on 2024-02-08. Score: 12
> 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.
> **Comments:**
> **username_8** (2024-02-08): Reminds me of a meme where one guy asks another how he wrote such good code, and he replies, "it's not my code." Standing on the shoulders of giants.  
> **username_7** (2024-02-09): @Seggan: That reminds me of the Peter Sellers movie where he asks the hotel manager "does your dog bite?" and the manager says "no", and then the dog bites him and he says "I thought you said your dog does not bite!" "That sir, is not my dog."  
---
### Answer by username_9 on 2024-02-07. Score: 1
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 by username_10 on 2024-02-16. Score: 0
You can have a fully concurrent GC that does not stop the mutator threads at all. Look at the [SGCL](https://github.com/pebal/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.
> **Comments:**
> **username_11** (2024-02-16): Please disclose your affiliation to the linked library as per [the help center](https://langdev.stackexchange.com/help/promotion).  
> **username_10** (2024-02-16): I do not hide my affiliation to this library. I also don't understand what significance it has for the topic. It is just an example of an implementation of a non-blocking GC algorithm.  
> **username_0** (2024-02-16): I don't mind a self-promoting answer as long as they solve, or demonstrate their idea of solving said problems. My questions for you here are: do you intend to and are capable of maintain your library for long-term? is your library in alpha, beta, golden-master, or production status?  
> **username_10** (2024-02-16): This library was created to test whether it is possible to implement an efficient, fully non-blocking GC. Its status is "it seems to work", I treat it as a testing ground.  
> **username_0** (2024-02-16): Your code is a 2.6k line of monologue (well-beyond my self-claimed ~300 optimum), can you provide a sketch of how you view and approach the problem?  
> **username_10** (2024-02-16): I edited my post.  
---
