News for hackers. Stuff that matters.
Re:Why Rust helps even if you have to use a lot of `unsafe` by flohofwoe on Wednesday August 02, 2023 @11:01AM (#36971844)
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.

Re:Why Rust helps even if you have to use a lot of `unsafe` by eddd-ddde on Wednesday August 02, 2023 @11:40AM (#36972413)
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.
Re:Why Rust helps even if you have to use a lot of `unsafe` by widdershins on Wednesday August 02, 2023 @11:13AM (#36971994)
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.
Re:Why Rust helps even if you have to use a lot of `unsafe` by soulbadguy on Wednesday August 02, 2023 @11:46AM (#36972495)
a good allocator could mitigate most of the allocation effects
Re:Why Rust helps even if you have to use a lot of `unsafe` by flohofwoe on Wednesday August 02, 2023 @12:24PM (#36973067)
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).

Re:Why Rust helps even if you have to use a lot of `unsafe` by soulbadguy on Wednesday August 02, 2023 @08:49PM (#36979921)
> Unlikely, because the allocator would need to know things only the compilers knows

Such as ?

Re:Why Rust helps even if you have to use a lot of `unsafe` by flohofwoe on Thursday August 03, 2023 @02:38AM (#36982177)
The 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, that would be worse. Instead think about whether a sum type is actually necessary, even if it is convenient.

Re:Why Rust helps even if you have to use a lot of `unsafe` by gpderetta on Wednesday August 02, 2023 @11:50AM (#36972547)
I think parent meant transforming a vector<A+T> into vector<A>*vector<T>
Re:Why Rust helps even if you have to use a lot of `unsafe` by throwaway894345 on Wednesday August 02, 2023 @11:39AM (#36972394)
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?
Re:Why Rust helps even if you have to use a lot of `unsafe` by morelisp on Wednesday August 02, 2023 @01:50PM (#36974328)
> What does a "structure of arrays" look like as it pertains to sum types?

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

Re:Why Rust helps even if you have to use a lot of `unsafe` by imtringued on Wednesday August 02, 2023 @12:04PM (#36972756)
Unfortunately, that isn't what cache unfriendly means. You're concerned about wasting memory bandwidth. Your array is trivial to prefetch.
Re:Why Rust helps even if you have to use a lot of `unsafe` by flohofwoe on Wednesday August 02, 2023 @12:14PM (#36972910)
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.
Re:Why Rust helps even if you have to use a lot of `unsafe` by CodesInChaos on Wednesday August 02, 2023 @12:21PM (#36973026)
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> costs 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. For example Option<&T> matches the size of &T, since it uses the illegal null value to represent None.

Re:Why Rust helps even if you have to use a lot of `unsafe` by jackmott42 on Wednesday August 02, 2023 @12:32PM (#36973195)
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.
Re:Why Rust helps even if you have to use a lot of `unsafe` by mikebenfield on Wednesday August 02, 2023 @12:59PM (#36973564)
> 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?

Re:Why Rust helps even if you have to use a lot of `unsafe` by estebank on Wednesday August 02, 2023 @01:25PM (#36973941)
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]>),
    |         ~~~~~~~~~~~~~~~~
Re:Why Rust helps even if you have to use a lot of `unsafe` by chriskrycho on Wednesday August 02, 2023 @02:00PM (#36974500)
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.