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.
It was written by Maoni Stephens, the architect of .NET's garbage collection.
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 easier.
> 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.
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.
One solution is to forbid recursive data types - e.g., require every struct type to only reference types that have already been defined. I can't think of any languages that do this.
Another solution is to make things immutable (like Erlang), or "as-if" immutable (like Koka), which guarantees that data can only point to things that have already been defined, preventing cycles.* Erlang uses this to simplify generational collection - because old data can't point to young data, it doesn't need a card table or anything like that.
I think it's perfectly possible to have a general purpose language without cycles: you can just use integer indices into an array instead of pointers if you want cyclic data structures. This is common in Rust, when people want to avoid the overhead of reference counting, but don't want to use unsafe code.
* A hidden assumption here is that the language is eagerly evaluated. There are languages like Haskell that have immutability and cyclic data structures.
Even with cyclic relationships between types, immutability makes cycles within instances difficult (without laziness anyway). A syntax tree would be a good example.
Yes, and the nice thing about doing it with immutability is you can still have recursive types to build linked lists, trees, and/or dags. From there you can build hash-array-mapped-tries, finger-trees, and so on, giving you friendly dict/list or JSON style data structures.
Yes, either is sufficient, I think.
Edit: I think the common idea with both solutions is that our objects have some weak order (the order in which their types were defined, and the time at which the object was created, respectively), and objects are only allowed to point to objects strictly less than them in this order.
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.
On any one object you can just follow the references to see if you get back to the same object. Not super efficient as you’d have to do it for each reference as it is set.
But if it was a simple scripting language and you needed that constraint, it’s relativity easy to implement.
Like Rust if it has no Rc?
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.
When I play around with changing various GCs for Java (via Clojure), then I always setup benchmarks measuring what kind of thing I want to improve, run all GCs via that benchmark to chose which to use for that service/project and call it a day. There is a lot of theorizing and navel-gazing around GCs it seems to me, and in the end it is the results that count so setup some way to measure, find the differences then move on from there :)
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.
On the context of .NET runtime, as missing from the title.
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.
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 easier.
> 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.
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.
One solution is to forbid recursive data types - e.g., require every struct type to only reference types that have already been defined. I can't think of any languages that do this.
Another solution is to make things immutable (like Erlang), or "as-if" immutable (like Koka), which guarantees that data can only point to things that have already been defined, preventing cycles.* Erlang uses this to simplify generational collection - because old data can't point to young data, it doesn't need a card table or anything like that.
I think it's perfectly possible to have a general purpose language without cycles: you can just use integer indices into an array instead of pointers if you want cyclic data structures. This is common in Rust, when people want to avoid the overhead of reference counting, but don't want to use unsafe code.
* A hidden assumption here is that the language is eagerly evaluated. There are languages like Haskell that have immutability and cyclic data structures.
Even with cyclic relationships between types, immutability makes cycles within instances difficult (without laziness anyway). A syntax tree would be a good example.
Yes, and the nice thing about doing it with immutability is you can still have recursive types to build linked lists, trees, and/or dags. From there you can build hash-array-mapped-tries, finger-trees, and so on, giving you friendly dict/list or JSON style data structures.
Yes, either is sufficient, I think.
Edit: I think the common idea with both solutions is that our objects have some weak order (the order in which their types were defined, and the time at which the object was created, respectively), and objects are only allowed to point to objects strictly less than them in this order.
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
On any one object you can just follow the references to see if you get back to the same object. Not super efficient as you’d have to do it for each reference as it is set.
But if it was a simple scripting language and you needed that constraint, it’s relativity easy to implement.
Like Rust if it has no Rc?
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.
When I play around with changing various GCs for Java (via Clojure), then I always setup benchmarks measuring what kind of thing I want to improve, run all GCs via that benchmark to chose which to use for that service/project and call it a day. There is a lot of theorizing and navel-gazing around GCs it seems to me, and in the end it is the results that count so setup some way to measure, find the differences then move on from there :)
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.
On the context of .NET runtime, as missing from the title.