4 ms·

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

by tines 3y ago

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).

flohofwoe 3y ago
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.
- eddd-ddde 3y ago
  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.
- widdershins 3y ago
  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.
  - soulbadguy 3y ago
    a good allocator could mitigate most of the allocation effects
    - flohofwoe 3y ago
      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).
      - soulbadguy 3y ago
        > Unlikely, because the allocator would need to know things only the compilers knows Such as ?
        flohofwoe 3y ago
        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.
  - gpderetta 3y ago
    I think parent meant transforming a vector<A+T> into vector<A>*vector<T>
- throwaway894345 3y ago
  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?
  - morelisp 3y ago
    > What does a "structure of arrays" look like as it pertains to sum types? https://news.ycombinator.com/item?id=36195425 https://news.ycombinator.com/item?id=36195425
- imtringued 3y ago
  Unfortunately, that isn't what cache unfriendly means. You're concerned about wasting memory bandwidth. Your array is trivial to prefetch.
  - flohofwoe 3y ago
    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.
- CodesInChaos 3y ago
  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.
- jackmott42 3y ago
  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.
- mikebenfield 3y ago
  > 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?
  - estebank 3y ago
    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]>), | ~~~~~~~~~~~~~~~~
    - chriskrycho 3y ago
      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.
deleted 3y ago
[deleted]

by tines 3y ago

flohofwoe 3y ago

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.

eddd-ddde 3y ago
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.
widdershins 3y ago
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.
- soulbadguy 3y ago
  a good allocator could mitigate most of the allocation effects
  - flohofwoe 3y ago
    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).
    - soulbadguy 3y ago
      > Unlikely, because the allocator would need to know things only the compilers knows Such as ?
      - flohofwoe 3y ago
        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.
- gpderetta 3y ago
  I think parent meant transforming a vector<A+T> into vector<A>*vector<T>
throwaway894345 3y ago
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?
- morelisp 3y ago
  > What does a "structure of arrays" look like as it pertains to sum types? https://news.ycombinator.com/item?id=36195425 https://news.ycombinator.com/item?id=36195425
imtringued 3y ago
Unfortunately, that isn't what cache unfriendly means. You're concerned about wasting memory bandwidth. Your array is trivial to prefetch.
- flohofwoe 3y ago
  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.
CodesInChaos 3y ago
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.
jackmott42 3y ago
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.
mikebenfield 3y ago
> 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?
- estebank 3y ago
  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]>), | ~~~~~~~~~~~~~~~~
  - chriskrycho 3y ago
    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.

deleted 3y ago

[deleted]