A Tour of Safe Tracing GC Designs in Rust • Hacker News Board

Re: A Tour of Safe Tracing GC Designs in Rust

#31

Post by saurik » Sat, Jun 19, 2021, 6:07 PM UTC

tialaramex wrote: post #15

saurik wrote: post #6

Earlier quoted context omitted.

The concept of what a pointer "is" is somewhat language-dependent, particularly as people finally attempt to mitigate the waste of moving to 64-bit by using tagged pointers (which maybe could try to be modelled in LLVM also, but I think you will rapidly realize that LLVM just isn't modeling a lot of things that affect scanning).

> particularly as people finally attempt to mitigate the waste of moving to 64-bit by using tagged pointers It's very fraught to try to "mitigate the waste" at the top of the pointer. Everybody involved is clear that what you're doing there is saving up pain for yourself because periodically more of those "wasted" bits become significant and each time that happens if you've been using them now you've incurred a maint…

The longer I stare at your comment the deeper the feeling that you are hung up on a semantic issue feels. While the intermediate states I went through were maybe a bit more interestingly-explanatory with respect to specific techniques, the final state I landed in is simply: "if you only used the bottom single bit to tag that the entire value is a value instead of a pointer, that alone mitigates the waste of moving to 64-bits by having fewer indirect allocations".

Re: A Tour of Safe Tracing GC Designs in Rust

#32

Post by _flux » Sat, Jun 19, 2021, 6:08 PM UTC

pjmlp wrote: post #16

_flux wrote: post #11

Earlier quoted context omitted.

Tracing GC is troublesome for any non-memory resource, such as network connection or file handle, due to its untimely release, but otherwise I actually agree: reference counting is a GC mechanism—not a very good one, but it's the only one I'm aware of that works both for memory and resources. I would enjoy someone test a model where the type system guarantees (or at least lets you detect the situation) that you canno…

Not when the language also supports value types and region allocators (e.g. IDispose in .NET). You can even turn it into RAII proper, by turning into a compilation error not handling those interfaces properly. Again with .NET, there are SafeHandles as well, alongside the MarshalInterop APIs. This is nothing new actually, Mesa/Cedar for Xerox PARC used reference counting with a cycle collector, while other descendent…

I must be missing something. How is it possible to precisely collect a resource with tracing GC? And if you need to update counters when you make duplicates of object references, you are not using a tracing GC where the benefits are the cheap duplication of object references, cheap allocations and cheap (batched) releases, but the downside is not being able to precisely and automatically do it when the value is available for collection.

Seems to me it is impossible to have both automatic precise release of a resources and collection-based GC?

As I understand it, even the documentation for IDisposable in .NET says as much at https://docs.microsoft.com/en-us/dotnet/api/system.idisposab...:

> The primary use of this interface is to release unmanaged resources. The garbage collector automatically releases the memory allocated to a managed object when that object is no longer used. However, it is not possible to predict when garbage collection will occur. Furthermore, the garbage collector has no knowledge of unmanaged resources such as window handles, or open files and streams.

> Use the Dispose method of this interface to explicitly release unmanaged resources in conjunction with the garbage collector. The consumer of an object can call this method when the object is no longer needed.

So this is the interface you can use to explicitly release a resource, because the GC gets around to it only later at some unspecified time.

About SafeHandle it says at https://docs.microsoft.com/en-us/dotnet/api/system.runtime.i...:

> The SafeHandle class provides critical finalization of handle resources, preventing handles from being reclaimed prematurely by garbage collection and from being recycled by Windows to reference unintended unmanaged objects.

Doesn't seem it's at all helpful for automatic precise release of resources.

Re: A Tour of Safe Tracing GC Designs in Rust

#33

Post by celeritascelery » Sat, Jun 19, 2021, 6:35 PM UTC

For me, the most interesting one is Josephine[1]. This allows tracking of stack roots, doesn't limit the time when GC can run, and takes advantage of rust's affine type system. However I have to say the API feels fairly clunky, with the need to root everything before mutation and the need to pass context objects to every method.

[1] https://github.com/asajeffrey/josephine

Re: A Tour of Safe Tracing GC Designs in Rust

#34

Post by duped » Sat, Jun 19, 2021, 6:38 PM UTC

joppy wrote: post #5

amelius wrote: post #4

Wouldn't it make more sense to have garbage collectors at the level of LLVM? That way, you could have direct access to all the pointers in a program without jumping through the language's hoops. And other languages could benefit from it too.

Yes, it makes total sense for the garbage collector to be tightly coupled to the memory allocation system, which is also tightly coupled to code generation (as is done in the case of various high-performance managed languages: Java, C#, Haskell, …). I remember hearing a talk a few years ago about a system of the kind you’re talking about - a kind of “managed language” micro-core that ran alongside LLVM so that it cou…

That sounds a lot like Graal

Re: A Tour of Safe Tracing GC Designs in Rust

#35

Post by zozbot234 » Sat, Jun 19, 2021, 6:51 PM UTC

_flux wrote: post #32

pjmlp wrote: post #16

Earlier quoted context omitted.

Not when the language also supports value types and region allocators (e.g. IDispose in .NET). You can even turn it into RAII proper, by turning into a compilation error not handling those interfaces properly. Again with .NET, there are SafeHandles as well, alongside the MarshalInterop APIs. This is nothing new actually, Mesa/Cedar for Xerox PARC used reference counting with a cycle collector, while other descendent…

I must be missing something. How is it possible to precisely collect a resource with tracing GC? And if you need to update counters when you make duplicates of object references, you are not using a tracing GC where the benefits are the cheap duplication of object references, cheap allocations and cheap (batched) releases, but the downside is not being able to precisely and automatically do it when the value is avail…

> the benefits are the cheap duplication of object references, cheap allocations and cheap (batched) releases, but the downside is not being able to precisely and automatically do it when the value is available for collection.

Note that you don't need GC to reap these benefits, if desired. You can allocate an arena and do secondary allocations inside it, then deallocate everything in a single operation. Arena deallocation is not timely or precise, but it does happen deterministically.

Re: A Tour of Safe Tracing GC Designs in Rust

#36

Post by _flux » Sat, Jun 19, 2021, 7:31 PM UTC

zozbot234 wrote: post #35

_flux wrote: post #32

Earlier quoted context omitted.

I must be missing something. How is it possible to precisely collect a resource with tracing GC? And if you need to update counters when you make duplicates of object references, you are not using a tracing GC where the benefits are the cheap duplication of object references, cheap allocations and cheap (batched) releases, but the downside is not being able to precisely and automatically do it when the value is avail…

> the benefits are the cheap duplication of object references, cheap allocations and cheap (batched) releases, but the downside is not being able to precisely and automatically do it when the value is available for collection. Note that you don't need GC to reap these benefits, if desired. You can allocate an arena and do secondary allocations inside it, then deallocate everything in a single operation. Arena dealloc…

True, but GC gives those benefits automatically, compared to a naive program doing e.g. RC-based memory management.

And there is of course the question of safety; should you release an arena too early, you may have introduced a bug. Worse: it might not crash immediately.

There is actually some work for doing arena management automatically, called region inference: http://www.mlton.org/Regions

But the way I see it, it's just a way to make memory management even more efficient; it's not about precise release of resources, and indeed not all programs can be expressed so that releases can happen only in batches of an arena (assuming those arenas themselves aren't dynamically managed, which certainly is a valid strategy as well, but manual).

Re: A Tour of Safe Tracing GC Designs in Rust

#37

Post by zozbot234 » Sat, Jun 19, 2021, 7:35 PM UTC

_flux wrote: post #36

zozbot234 wrote: post #35

Earlier quoted context omitted.

> the benefits are the cheap duplication of object references, cheap allocations and cheap (batched) releases, but the downside is not being able to precisely and automatically do it when the value is available for collection. Note that you don't need GC to reap these benefits, if desired. You can allocate an arena and do secondary allocations inside it, then deallocate everything in a single operation. Arena dealloc…

True, but GC gives those benefits automatically, compared to a naive program doing e.g. RC-based memory management. And there is of course the question of safety; should you release an arena too early, you may have introduced a bug. Worse: it might not crash immediately. There is actually some work for doing arena management automatically, called region inference: http://www.mlton.org/Regions But the way I see it, it…

> should you release an arena too early, you may have introduced a bug.

A memory safe programmming language will detect any such bugs and reject the program. This is not hard, it's a clean application of existing lifetime checks.

Re: A Tour of Safe Tracing GC Designs in Rust

#38

Post by vlovich123 » Sat, Jun 19, 2021, 8:07 PM UTC

celeritascelery wrote: post #29

devit wrote: post #27

Earlier quoted context omitted.

Of course competent programmers using the top K bits of the pointer would make sure that the kernel and memory allocator operate so that they don't allocate memory outside a (64 - K)-bit address space, regardless of what the CPU supports (e.g. Linux mmap as one would expect won't allocate beyond 2^48 unless explicitly requested). And obviously any intelligent CPU architect, if they make a CPU that masks the upper bit…

> Of course competent programmers ... And obviously any intelligent CPU architect Interesting to see the future is so "obvious" to you. You are correct however, that this is not a problem at the present because no architecture uses more then 48-bits of address space in practice. And since this is such a common practice now, there will have to allowances made in the future for when the address space is expanded.

As a sibling to you noted, Ice Lake has bumped this from 48 bits to 57 bits to support 5-level paging [1]. So the "in practice" appears to already by out of date. This was known publicly as early as 2017 (albeit this is the first I've heard of it).

That being said, I don't know why the increase from 256TB to 128PB is at all useful but it's enabled in my Arch Linux kernel on a 32GB laptop, so clearly adopted by the broader ecosystem even outside whatever niche use-case it's for.

That being said, the kernel maintains backward compatability by restricting the allocation address space it hands out by default. Userspace needs to explicitly ask for the higher bits [2], so it's probably OK to just continue as-is assuming the 48-bit limit in practice.

[1] https://en.wikipedia.org/wiki/Intel_5-level_paging

[2] https://www.kernel.org/doc/html/latest/x86/x86_64/5level-pag....

Re: A Tour of Safe Tracing GC Designs in Rust

#39

Post by _flux » Sat, Jun 19, 2021, 8:11 PM UTC

zozbot234 wrote: post #37

_flux wrote: post #36

Earlier quoted context omitted.

True, but GC gives those benefits automatically, compared to a naive program doing e.g. RC-based memory management. And there is of course the question of safety; should you release an arena too early, you may have introduced a bug. Worse: it might not crash immediately. There is actually some work for doing arena management automatically, called region inference: http://www.mlton.org/Regions But the way I see it, it…

> should you release an arena too early, you may have introduced a bug. A memory safe programmming language will detect any such bugs and reject the program. This is not hard, it's a clean application of existing lifetime checks.

So are there some languages that do it? I'm sure the devil is in the details.

Re: A Tour of Safe Tracing GC Designs in Rust

#40

Post by zozbot234 » Sat, Jun 19, 2021, 8:14 PM UTC

devit wrote: post #27

celeritascelery wrote: post #24

Earlier quoted context omitted.

Until the virtual address space gets so big that there are no bits left at the top that are "free". As soon as you have a 64 bit virtual address space, pointer tagging the top bits no longer works. Your program is now broken on the new CPU.

Of course competent programmers using the top K bits of the pointer would make sure that the kernel and memory allocator operate so that they don't allocate memory outside a (64 - K)-bit address space, regardless of what the CPU supports (e.g. Linux mmap as one would expect won't allocate beyond 2^48 unless explicitly requested). And obviously any intelligent CPU architect, if they make a CPU that masks the upper bit…

> And obviously any intelligent CPU architect, if they make a CPU that masks the upper bits, they would make the number of bits that gets masked configurable per-process

x86-64 does this by requiring all accesses to be correctly sign-extended, which means that valid virtual addresses are unique and there is full forward compatibility even with an extended virtual address space. The "number of bits that get masked" is a pure system/ABI concern, the CPU support only defines a maximum.