Hacker News Reader

Comment by tines | Hacker News Reader

This is a huge deal, I find it so difficult to choose a language that doesn't have sum types and destructuring via pattern matching for the kinds of projects I like to work on (compiler/interpreter implementation).

View on HN

IMHO the one downside with sum types in a performance-oriented systems programming language (or as I prefer to call them 'tagged unions' because that makes it clearer how they actually look like in memory) is that they are inherently cache-unfriendly, because they always take up as much space as the largest wrapped type (plus 8 bytes for the tag). When you have an array of those you need to be aware of the potential 'waste' between array items.

(now of course an automatic transformation into a structure-of-arrays would be pretty cool, I actually wonder what Zig's MultiArrayList does with tagged unions).

PS: in general I agree though, for instance in Typescript they are fantastic, but there I usually don't care much about memory layout and performance.

That depends on the sizes of the objects. If the objects in the union are generally small, cache coherence is better than if you have polymorphic objects allocated on the heap.

a good allocator could mitigate most of the allocation effects

Unlikely, because the allocator would need to know things only the compilers knows, and the compiler in turn needs to know how the allocator lays out the data in memory?

Some of that could probably be solved with comptime code (like Zig's MultiArrayList container I mentioned above).

> Unlikely, because the allocator would need to know things only the compilers knows

Such as ?

Such a 'smart allocator' can't just work with a size and alignment, it also needs to know the internal structure of objects so that it can arrange them differently (maybe to remove padding bytes, maybe to turn arrays-of-structs into structs-of-arrays. And in turn the compiler needs to know how the 'allocator' has rearranged things in order to generate the code which accesses the data.

I also wasn't thinking about moving parts of a struct out into heap allocations, I think in most situations that would be worse than having to deal with padding. Instead at least have the programmer think about how the internal memory layout of sum types might affect performance in specific situations instead of just using them everywhere and in mass because they are convenient.

I think parent meant transforming a vector<A+T> into vector<A>*vector<T>

What's the alternative to sum types? What does a "structure of arrays" look like as it pertains to sum types? Are the arrays sparse or dense (and how is either going to be better for cache coherence)? Where does the tag live? In its own array?

> What does a "structure of arrays" look like as it pertains to sum types?

https://news.ycombinator.com/item?id=36195425

If you are dealing with always-same-type arrays then you can express so as a sum type of arrays, not an array of sum types.

Unfortunately, that isn't what cache unfriendly means. You're concerned about wasting memory bandwidth. Your array is trivial to prefetch.

AFAIK the prefetcher doesn't help much if it's mainly busy with prefetching padding bytes of the 'inactive' unions (and I think even a smart prefetcher would at least always load whole cache lines which could be packed with active data instead). Of course that's also a bandwidth problem, you're wasting bandwidth loading data into the cache which then is ignored.

The overhead isn't always 8 bytes. When the type uses the naive representation, the overhead will generally match the alignment. For example an Option<u8> occupies 2 bytes, 1 of which is for the tag.

And if the type has some illegal values, these can sometimes be used to discriminate the type. When that's possible, the union will have the same size as the largest underlying type with no overhead for a tag. For example Option<&T> matches the size of &T, since it uses the illegal null value to represent None.

Rust sum types do not take up that much extra space, in fact often the overhead is completely compiled away. Lots of hard work to keep the wasted memory to a minimum, and they are not pointers, so there isn't an extra memory hop or anything.

> plus 8 bytes for the tag

The tag can often be stored inline in the data, so doesn't necessarily require extra space.

> because they always take up as much space as the largest wrapped type

Yeah... but what's the alternative?

The alternative would be for Rust to generate machine code for the following

    enum Foo {
        Bar,
        Qux([i32; 1024]),
    }

as if the user had written

    enum Foo {
        Bar,
        Qux(Box<[i32; 1024]>),
    }

I don't think it's a good idea to do that kind of silent transformation, instead teach the developer about their options. That way the application's performance doesn't suddenly shift after changing a few parts of unrelated code that accidentally causes some threshold to be crossed that changes the performance characteristics of binary being produced.

Today, clippy does what I think is the right thing: it teaches the user

  warning: large size difference between variants
   --> src/main.rs:1:1
    |
  1 | / enum Foo {
  2 | |     Bar,
    | |     --- the second-largest variant carries no data at all
  3 | |     Qux([i32; 1024]),
    | |     ---------------- the largest variant contains at least 4096 bytes
  4 | | }
    | |_^ the entire enum is at least 4100 bytes
    |
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#large_enum_variant
    = note: `#[warn(clippy::large_enum_variant)]` on by default
  help: consider boxing the large fields to reduce the total size of the enum
    |
  3 |     Qux(Box<[i32; 1024]>),
    |         ~~~~~~~~~~~~~~~~

When you combine this with rust-analyzer's hints for the sizes of items, it makes it much easier to spot this kind of stuff and resolve it automatically while developing, too.

Reply on news.ycombinator.com