12 ms·

Most mainstream languages conflate memory layout and type definitions so your Option<T> is going to be implemented internally with worse-than-sentinel-values an

Most mainstream languages conflate memory layout and type definitions so your Option<T> is going to be implemented internally with worse-than-sentinel-values and take an even larger performance hit.

zabzonk 3y ago
> Most mainstream languages conflate memory layout and type definitions for example?
- morelisp 3y ago
  C++ would be the obvious poster child. It might be more instructive to list some exceptions: - As described elsewhere in this thread, Julia is able to optimize Array<Option<X>> internally into a bitfield and a tightly-packed array of X - Rust can use knowledge of a type's valid values to optimize Option<T> into something the same size of T for common T (pointers, arrays, etc, also notably I think user-defined enums which aren't exhaustive of their value space) - but as far as I know it cannot do what Julia does, you need to reach for e.g. https://docs.rs/vec-option/latest/vec_option/ https://docs.rs/vec-option/latest/vec_option/ - This is somewhat the raison d'etre for Jai, if it ever gets released.
  - zabzonk 3y ago
    > C++ would be the obvious poster child to make it obvious, post some code.
    - morelisp 3y ago
      https://www.boost.org/doc/libs/1_34_1/boost/optional/optional.hpp https://www.boost.org/doc/libs/1_34_1/boost/optional/optiona... bool m_initialized ; storage_type m_storage ;
      - zabzonk 3y ago
        ok, now explain how this " conflate memory layout and type definitions"
        Dylan16807 3y ago
        It sticks a bool onto each value, directly attached in memory layout, taking up a byte plus padding bytes, multiplied by how many values you have. (The compiler is allowed to improve this, but it won't.)
        morelisp 3y ago
        The compiler is only vaguely allowed to do this by general "as if" rules; in practice there are so many formal constraints on field layout I don't think it could do better even with the world's most brilliant optimizer. It would need to behave "as if" if the two fields are laid out next to each other, in address-ascending order, with nothing but padding in between.
      - gpderetta 3y ago
        Boost and std optional do not do it, but you can write your optional type that take advantage of the properties of T for optimal storage via traits. FWIW, we have had this discussion a few months ago on HN.
  - marcosdumay 3y ago
    C and C++ do really not do that, and programing as if the memory structure is equivalent to the type structure is an undefined behavior factory that will turn your program into a mine field. But those languages are very good at pretending they mix the two concepts.
    - morelisp 3y ago
      I said conflated, not made formally identical.
weinzierl 3y ago
The discriminant will be optimized away if possible you end up with a sentinel but no performance hit.
- morelisp 3y ago
  Not sure how you come to this conclusion - the sentinel is a performance hit. If you're lucky enough to be working in a language and with the blessed types where it figures out a good sentinel for you, you're still paying the sentinel cost, just not any more than that.
  - weinzierl 3y ago
    The discriminant is certainly the bigger performance hit, converting to a sentinel when possible is the best we can do. So I don't se how it would be classified as performance hit at all when essentially this is what we couldn't hand code any better.
    - morelisp 3y ago
      > converting to a sentinel when possible is the best we can do. Did you, uh, do the thing I can't ask if you did on HN? Because it's entirely about how to get better performance than sentinel values by specially structuring your discriminant.
      - weinzierl 3y ago
        EDIT: Ah, I think I understand where this went wrong. I was answering from my comment thread and did not see your other comments, especially the one where you explained how Julia handles this case. I did not know about that. I'm sorry, I didn't mean to berate you I just was under the wrong impression you said what you said because you were not aware of Rusts discriminant elision. My apologies. ORIGINAL: Not sure what you mean, so I'll try again. An Option<T> in Rust should occupy the size of T plus the size of a discriminant. On a 64-bit machine for example an Option<i32> will take up 8 bytes. Four bytes for the i32 and four bytes (including alignment) for the discriminant. A 100% increase in space is clearly a performance hit. If, however, T is a non-nullable type, the Rust compiler is smart enough to use this null value as a sentinel and you end up with an Option<T> that only takes up the size of T. So, for example, both a &i32 and an Option<i32> will take 8 bytes, no difference, zero waste.

Most mainstream languages conflate memory layout and type definitions so your Option<T> is going to be implemented internally with worse-than-sentinel-values and take an even larger performance hit.

zabzonk 3y ago

> Most mainstream languages conflate memory layout and type definitions for example?

morelisp 3y ago
C++ would be the obvious poster child. It might be more instructive to list some exceptions: - As described elsewhere in this thread, Julia is able to optimize Array<Option<X>> internally into a bitfield and a tightly-packed array of X - Rust can use knowledge of a type's valid values to optimize Option<T> into something the same size of T for common T (pointers, arrays, etc, also notably I think user-defined enums which aren't exhaustive of their value space) - but as far as I know it cannot do what Julia does, you need to reach for e.g. https://docs.rs/vec-option/latest/vec_option/ https://docs.rs/vec-option/latest/vec_option/ - This is somewhat the raison d'etre for Jai, if it ever gets released.
- zabzonk 3y ago
  > C++ would be the obvious poster child to make it obvious, post some code.
  - morelisp 3y ago
    https://www.boost.org/doc/libs/1_34_1/boost/optional/optional.hpp https://www.boost.org/doc/libs/1_34_1/boost/optional/optiona... bool m_initialized ; storage_type m_storage ;
    - zabzonk 3y ago
      ok, now explain how this " conflate memory layout and type definitions"
      - Dylan16807 3y ago
        It sticks a bool onto each value, directly attached in memory layout, taking up a byte plus padding bytes, multiplied by how many values you have. (The compiler is allowed to improve this, but it won't.)
        morelisp 3y ago
        The compiler is only vaguely allowed to do this by general "as if" rules; in practice there are so many formal constraints on field layout I don't think it could do better even with the world's most brilliant optimizer. It would need to behave "as if" if the two fields are laid out next to each other, in address-ascending order, with nothing but padding in between.
    - gpderetta 3y ago
      Boost and std optional do not do it, but you can write your optional type that take advantage of the properties of T for optimal storage via traits. FWIW, we have had this discussion a few months ago on HN.
- marcosdumay 3y ago
  C and C++ do really not do that, and programing as if the memory structure is equivalent to the type structure is an undefined behavior factory that will turn your program into a mine field. But those languages are very good at pretending they mix the two concepts.
  - morelisp 3y ago
    I said conflated, not made formally identical.

weinzierl 3y ago

The discriminant will be optimized away if possible you end up with a sentinel but no performance hit.

morelisp 3y ago
Not sure how you come to this conclusion - the sentinel is a performance hit. If you're lucky enough to be working in a language and with the blessed types where it figures out a good sentinel for you, you're still paying the sentinel cost, just not any more than that.
- weinzierl 3y ago
  The discriminant is certainly the bigger performance hit, converting to a sentinel when possible is the best we can do. So I don't se how it would be classified as performance hit at all when essentially this is what we couldn't hand code any better.
  - morelisp 3y ago
    > converting to a sentinel when possible is the best we can do. Did you, uh, do the thing I can't ask if you did on HN? Because it's entirely about how to get better performance than sentinel values by specially structuring your discriminant.
    - weinzierl 3y ago
      EDIT: Ah, I think I understand where this went wrong. I was answering from my comment thread and did not see your other comments, especially the one where you explained how Julia handles this case. I did not know about that. I'm sorry, I didn't mean to berate you I just was under the wrong impression you said what you said because you were not aware of Rusts discriminant elision. My apologies. ORIGINAL: Not sure what you mean, so I'll try again. An Option<T> in Rust should occupy the size of T plus the size of a discriminant. On a 64-bit machine for example an Option<i32> will take up 8 bytes. Four bytes for the i32 and four bytes (including alignment) for the discriminant. A 100% increase in space is clearly a performance hit. If, however, T is a non-nullable type, the Rust compiler is smart enough to use this null value as a sentinel and you end up with an Option<T> that only takes up the size of T. So, for example, both a &i32 and an Option<i32> will take 8 bytes, no difference, zero waste.