Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fundamentals of garbage collection (2023)

learn.microsoft.com

Post reply on HN
Print view View original

11–20 of 34 posts

Re: Fundamentals of garbage collection (2023)

#11

Post by bob1029 »

ozim wrote: post #8

Question: does anyone run "Server GC" for the ASP.NET applications? There is bunch of people copy pasting documentation to SO "explaining" server GC. I am running bunch of .NET stuff in VMs and never set "Server GC" and never ran into issues with default but also not sure if it is worth testing out. I guess it does not matter much if you are running in containers but I am running on VMs in IIS.

Server GC is a tradeoff between latency and throughput. It makes a ton of sense for a web server where a small additional overhead of a few milliseconds on some responses won't matter.

Workstation GC is what you want when latency is critical. This is what you'd use if you were developing a UI or game engine.

I've seen workstation GC stay in the microsecond region when strategically executing GC.Collect at allocation batch boundaries.

Re: Fundamentals of garbage collection (2023)

#12

Post by andreamonaco »

BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

Hello, I'm writing an implementation of the Common Lisp language that uses an enhanced reference counting algorithm (that I've taken from literature) that detects and handles cycles. Performance seems okay, though I still haven't tried large programs.

https://savannah.nongnu.org/p/alisp

Re: Fundamentals of garbage collection (2023)

#13

Post by n_plus_1_acc »

BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

Like Rust if it has no Rc?

Re: Fundamentals of garbage collection (2023)

#14

Post by Metalnem »

I recently re-read this article and can confirm that it's excellent—not just this specific page, but all the other sections under "Garbage Collection" as well.

If you want to dive deeper into memory performance analysis in .NET, this is another must-read: https://github.com/Maoni0/mem-doc/blob/master/doc/.NETMemory...

It was written by Maoni Stephens, the architect of .NET's garbage collection.

Re: Fundamentals of garbage collection (2023)

#15

Post by Someone »

BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

> I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way

In general, I think that cannot be done, but if one restricts what programs can do, solutions exist.

A simple way to do it is by requiring all references “pointing out of” an object to be set the moment the object is created, and be immutable afterwards (that’s what Lisp cons (https://en.wikipedia.org/wiki/Cons) does. Without setf or similar, lisp code cannot create cycles)

That disallows quite a ome code that modifies structures without introducing cycles, but still allows for quite some code to work.

One could also store an ‘age’ field with each object and check, when a reference is updated in an object, that it points to an object that is older than the one being modified. That gives some more leeway, at the price of using more (a lot more, in code using small objects) memory.

Another idea is to add a bit to each object “there are no cycles containing this object”, and have the runtime clear that when it no longer can guarantee that (edit: unfortunately, maintaining that invariant can be very costly. Whenever code does foo.field = bar, with both foo and bar known to be not part of a cycle, you still have to do a search through all objects reachable from bar to check whether a cycle was created and, if so, clear that bit in all objects in the cycle(s). That makes this idea impractical)

If, as I suspect happens in programming languages which are “mostly immutable”, there are many objects for which that flag stays set, that can significantly speed up checking for the creation of cycles.

Re: Fundamentals of garbage collection (2023)

#16

Post by zozbot234 »

andreamonaco wrote: post #12
BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

Hello, I'm writing an implementation of the Common Lisp language that uses an enhanced reference counting algorithm (that I've taken from literature) that detects and handles cycles. Performance seems okay, though I still haven't tried large programs. https://savannah.nongnu.org/p/alisp

A somewhat different approach was recently proposed here: https://news.ycombinator.com/item?id=44319427 but it seems to have non-trivial overhead. (Still very much worthwhile, given the potential advantages of deterministic cycle collection.) The paper you reference is quite a bit older so it would of course be interesting to do a proper comparison.

Re: Fundamentals of garbage collection (2023)

#17

Post by Lariscus »

ozim wrote: post #8

Question: does anyone run "Server GC" for the ASP.NET applications? There is bunch of people copy pasting documentation to SO "explaining" server GC. I am running bunch of .NET stuff in VMs and never set "Server GC" and never ran into issues with default but also not sure if it is worth testing out. I guess it does not matter much if you are running in containers but I am running on VMs in IIS.

Server GC is the default garbage collector for Asp.net Core.

> https://github.com/dotnet/AspNetCore.Docs/blob/main/aspnetco...

Re: Fundamentals of garbage collection (2023)

#18

Post by jlouis »

BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

You can make a programming language where cycles are impossible. Erlang is a prime example.

Region inference is another strategy in this space. It can limit the need for full-blown garbage collection in many cases, but also comes with its own set of added trade-offs.

Reference counting is just a different kind of garbage collection, really. It acts like a dual construction to a tracing GC in many cases. If you start optimizing both, you tend to converge to the same ideas over time. Refcounting isn't void of e.g. latency problems either: if I have a long linked list and snip the last pointer, then we have to collect all of that list. That's going to take O(n) time in the size of the list. For that reason, you'd have to delay collecting the large list right away, which means you are converging toward a tracing GC that can work simultaneously with the mutator. See e.g., Go's garbage collector.

Re: Fundamentals of garbage collection (2023)

#19

Post by zozbot234 »

jlouis wrote: post #18
BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

You can make a programming language where cycles are impossible. Erlang is a prime example. Region inference is another strategy in this space. It can limit the need for full-blown garbage collection in many cases, but also comes with its own set of added trade-offs. Reference counting is just a different kind of garbage collection, really. It acts like a dual construction to a tracing GC in many cases. If you start…

> latency problems either: if I have a long linked list and snip the last pointer, then we have to collect all of that list. That's going to take O(n) time in the size of the list. For that reason, you'd have to delay collecting the large list right away

These latency issues are inherent to deterministic destruction, which is an often desirable feature otherwise; they have little to do with reference counting itself. In principle, they can be addressed by "parking" objects for which delayed disposal is non-problematic onto a separate, lower-priority task.

Re: Fundamentals of garbage collection (2023)

#20

Post by andreamonaco »

zozbot234 wrote: post #16
andreamonaco wrote: post #12

Earlier quoted context omitted.

Hello, I'm writing an implementation of the Common Lisp language that uses an enhanced reference counting algorithm (that I've taken from literature) that detects and handles cycles. Performance seems okay, though I still haven't tried large programs. https://savannah.nongnu.org/p/alisp

A somewhat different approach was recently proposed here: https://news.ycombinator.com/item?id=44319427 but it seems to have non-trivial overhead. (Still very much worthwhile, given the potential advantages of deterministic cycle collection.) The paper you reference is quite a bit older so it would of course be interesting to do a proper comparison.

I'll look at that. About performance: people in practice have always favored GC, so I think there's a lot to be discovered in optimization of reference counting algorithms, including concurrent traversal (which is easier because each node has local info in the form of refcounts and flags) and maybe detection of problematic worse-case graphs
Post reply on HN