Optimized memory layout for Coproducts

[joonazan]

Instead of nesting enums, the new representation explicitly has one tag and nested unions. The nested unions only take up as much space as the largest variant of the coproduct, unlike the old representation, which was optimized very poorly by the compiler.

For example the below line takes 120 bytes on frunk 0.4 but only 16 bytes with my implementation. If I change the tag from usize to u32 it drops to 8 bytes. This raises the question whether it is possible to dynamically choose a good tag size. It is probably not worth the complexity, though, as I suspect that tags larger than u16 aren't practical simply because the data structure's size would slow down compilation too much.

Coprod! {u8, u8, u8, u8, u32, u8, u8, u8, u8, u8, u8, u8, u8, u8, u8, u8, u32, u8, u8, u8, u8, u8, u8, u8, u8, u8, u8, u8, u32, u8, u8, u8, u8, u8, u8, u8};

The code passes all tests but it is still quite messy and some of the old Coproduct's API like Ord and Eq is still missing.

I also need to name the current Coproduct LeakingCoproduct and put it in yet another wrapper that has a custom Drop implementation. That, or make Coproduct only take values that are Copy.

[joonazan]

I think I understand the design space of this change relatively well now.

Instead of Coproduct, there needs to be Coproduct and CopyableCoproduct, which are otherwise identical but Coproduct is Drop and CopyableCoproduct is Copy.

The trait bounds may have to get uglier (as seen in my current code). The problem is that I have traits implemented on UntaggedCoproduct and I can not figure out how to make Coproduct<Untagged>: Trait2 imply Untagged: Trait1.

Some unsafe is necessary because that is the only way to use unions.

Do you think this is good for frunk, or should I rather make this a separate coproduct library?

[ExpHP]

Hmmm. This is a tough one.

@lloydmeta, would it be correct to say that "no usage of unsafe" is one of the design goals of Frunk?

I've always seen frunk as the kind of library that shows what's possible with type-level programming in rust, even if it is not necessarily the best implementation.

All of this said, there's no mistaking that the current size of Coproducts is... well, a little obscene. I don't like to think that our advice to people can only be "don't use frunk's Coproduct." Improving the size of Coproduct could also improve the performance of Generic for people who are using that. These could potentially serve as arguments for making such a change to frunk.

[joonazan]

The README implies that no unsafe is a goal of frunk. That most likely loses performance elsewhere as well, so using unsafe and having a worse API just to improve performance seems like a bad fit for frunk. The only counterargument I can think of is that the huge proc macros generated by frunk can be seen as somewhat dangerous, though not in the same way as unsafe.

Anyway, I'm glad that frunk exists because otherwise I wouldn't have figured out that the data structure implemented in this PR is possible in Rust. It is good to have an easy to understand implementation that shows what is possible in Rust. My version of coproducts is not as easy to understand, as it uses the same construction as the safe version on the type level but the actual implementation has to be wildly unsafe.

My use case is that I've written a subset of an algebraic effect library (stable and no unsafe btw) and seen a more fully featured one that uses frunk's Coproduct. I want to try using algebraic effects really heavily, but that requires that they are very cheap.

[ExpHP]

Interesting. Yeah an effect system library definitely sounds like the kind of thing that needs this. Funny, though, I would've expected them to require some concept of "minimal common superset" (which unfortunately is also a huge technical challenge in rust).

(Edit: oh hah! That issue is apparently from the effing-mad author! Guess that adds up! XD)

Anyways, best of luck with that!

[lloydmeta]

Thanks for sending this PR; I can only imagine the amount of hair pulling needed to make it work to this point !

I agree that no unsafe usage is a (implied) goal of frunk: a lot of the type-level craziness/machinery was put in place specifically to avoid unsafe (I imagine transmogrification is doable to an extent with unsafe, in a much less type-levely way).

I feel like maybe optimizing Coproduct’s runtime size is something that we can/only hope the compiler will one day do for us.

should I rather make this a separate coproduct library?

This sounds like a good idea; if needed, maybe users can convert too/from Frunk Coproducts if there are implementations they want to use.

[joonazan]

I made the standalone version. Still missing some features; I'll add them as needed. I think this PR can be closed now.

I will also make a PR for using my library in effing-mad sometime soon. I haven't used my own library much yet, so that will hopefully be a better test.

@ExpHP I looked into computing the union of two coproducts. It is currently impossible but most of it is pretty straightforward. The impossible part is behaving differently when two types are equal vs when they are not.

Type comparison is easy via the specialization feature, which is unfortunately currently unsound. I think this use case would be sound as it doesn't involve lifetimes but who knows.

Alternatively one could assign compile-time natural numbers to all types that go into the coproduct.

[ExpHP]

Type comparison is easy via the specialization feature, which is unfortunately currently unsound. I think this use case would be sound as it doesn't involve lifetimes but who knows.

As far as I am aware, the current plans to implement a sound subset of specialization explicitly forbid any attempt to specialize on type equality, because this can be used to equate lifetimes.

[ExpHP]

I think this PR can be closed now.

Sure.