This is a very neat proof of concept that the problem is solvable entirely in safe rust. Obviously the ergonomics suffer, but its an interesting datapoint, and one can hope that future rust developments will mitigate some of the papercuts
It's quite unfortunate that traced references has to be wrapped in Gc<>, as this means that your types are bound to a GC allocator (right? Maybe I'm wrong!). It also means that trying out a GC is a pain, as you're stuck first doing the rewrite of your types. The necessity of Trace is another burden, but probably an unavoidable one.
In this example, you wrap Gc types in Option, I think that having the Gc type be nullable instead would be an interesting experiment. Having to introduce a lot of places that branch both puts more into the instruction cache, and adds more places that the branch predictor has to track. Besides, you can always add in missing checks if you know that you have a sparse subgraph somewhere. Total potential micro optimization, but it's a bit of fun :-).
I also like how this shows how freelists are a smidge less efficient in safe Rust, as compared to unsafe Rust. In this solution, we have to encode the tag for the discriminated union, this is unnecessary! The unoccupied slots forms its own separate list, and so you know that you will always have unoccupied slots as long as you trace along that path. I assume that that will add up to the maximum alignment of bytes, as arrays need to be well-aligned? So, probably 8 extra bytes per element (you're storing stuff that probably references other stuff).
I think it should be possible to get rid of the Option tag without introducing any unsafe code by changing index in Gc from u32 to std::num::NonZero<u32>.
I found this while looking for a solution for more easily removing some unsafe code from a library that does a lot of C FFI. I didn't end up going with it though, for now I'm taking an approach of mapping valid pointers that I return to the caller and then validating that pointers passed to my library functions are in that valid mapping (and then also using that valid mapping to contain some additional information that doesn't fit in the ABI of the structs that the pointers are for that I use to safely do validation. So e.g., I can store the range of some other valid member pointers as a normal safe rust reference and then index into it with member pointers on the struct, completely avoiding unsafe code despite having this FFI boundary (obviously the FFI boundary itself is still unsafe, but I can take this ugly C struct with a bunch of raw pointers and handle it safely)).
This is a very neat proof of concept that the problem is solvable entirely in safe rust. Obviously the ergonomics suffer, but its an interesting datapoint, and one can hope that future rust developments will mitigate some of the papercuts
It's quite unfortunate that traced references has to be wrapped in Gc<>, as this means that your types are bound to a GC allocator (right? Maybe I'm wrong!). It also means that trying out a GC is a pain, as you're stuck first doing the rewrite of your types. The necessity of Trace is another burden, but probably an unavoidable one.
In this example, you wrap Gc types in Option, I think that having the Gc type be nullable instead would be an interesting experiment. Having to introduce a lot of places that branch both puts more into the instruction cache, and adds more places that the branch predictor has to track. Besides, you can always add in missing checks if you know that you have a sparse subgraph somewhere. Total potential micro optimization, but it's a bit of fun :-).
I also like how this shows how freelists are a smidge less efficient in safe Rust, as compared to unsafe Rust. In this solution, we have to encode the tag for the discriminated union, this is unnecessary! The unoccupied slots forms its own separate list, and so you know that you will always have unoccupied slots as long as you trace along that path. I assume that that will add up to the maximum alignment of bytes, as arrays need to be well-aligned? So, probably 8 extra bytes per element (you're storing stuff that probably references other stuff).
I think it should be possible to get rid of the Option tag without introducing any unsafe code by changing index in Gc from u32 to std::num::NonZero<u32>.
I found this while looking for a solution for more easily removing some unsafe code from a library that does a lot of C FFI. I didn't end up going with it though, for now I'm taking an approach of mapping valid pointers that I return to the caller and then validating that pointers passed to my library functions are in that valid mapping (and then also using that valid mapping to contain some additional information that doesn't fit in the ABI of the structs that the pointers are for that I use to safely do validation. So e.g., I can store the range of some other valid member pointers as a normal safe rust reference and then index into it with member pointers on the struct, completely avoiding unsafe code despite having this FFI boundary (obviously the FFI boundary itself is still unsafe, but I can take this ugly C struct with a bunch of raw pointers and handle it safely)).