6 ms·

> This is where `Option` or `Optional` types shine. They force you to unwrap the nilable value at compile time, and are zero-cost abstractions. They aren't zer

> This is where `Option` or `Optional` types shine. They force you to unwrap the nilable value at compile time, and are zero-cost abstractions. They aren't zero-cost abstractions in most languages. Every unwrap() potentially results in a dynamic check, even if one isn't necessary. There are a number of ways you could extend a type system to track the potential cases of sum types, which would help alleviate this cost.

webkike 9y ago
Option types for references need be no more expensive than a null pointer check, and I believe this is how they are implemented in Rust. If a dynamic check is not necessary, then you simply do not use an Option type.
- cwzwarich 9y ago
  In C/C++, you quite often end up in situations when some other condition implies that a pointer is nonnull. In Rust, the equivalent code with Option would require an unnecessary dynamic check.
  - webkike 9y ago
    That's just a problem with ordering. If a condition implies a non null pointer then a non null pointer can imply the condition as well. This is true unless the condition being false does not guarantee a null pointer, in which case the condition is not useful. If some condition implies multiple non null pointers then the option type can be defined on a tuple of references
    - tomsmeding 9y ago
      > in which case the condition is not useful I contest. The reason for the condition need not be only to indicate whether the other value isn't null; if it was, you could just remove the condition and check nullity. In fact, unless there is either a case where the condition is true and the pointer is null or a case where the condition is false and the pointer is non-null, the condition is useless because checking the pointer would've been enough. Consider the following silly example, where we have a function f(Conductor *c, bool isDriving, Train *t) with the guarantees that c != NULL, and isDriving==true => t!=NULL. Note that the case isDriving==false does not imply t==NULL; indeed, c could just be waiting for the signal to start driving.
      - webkike 9y ago
        isDriving remains connected to t. Specifying an Option reference for t allows you to convey two pieces of information: if None, that isDriving is false and you do not care about t, and if Some, you have train t
      - dbaupp 9y ago
        One can express the states more clearly with a slightly upgraded Option/Optional/Maybe, i.e. a full sum-type/enum. For instance, that function could be, in Rust syntax (but the same thing works in Haskell, OCaml, Swift, ...): enum ConductorTask { Nothing, Waiting(Train), Driving(Train) } fn f(c: Conductor, task: ConductorTask) I think this says everything that your text says, but in a way the compiler understands and can assist the programmer with. Alternatively, since isDriving only makes sense when there's a train, t could be Option<(bool, Train)>, i.e. an optional train along with a boolean for if it's being driven or not.
        cwzwarich 9y ago
        An Option type in Rust forces a particular memory layout by requiring the components to be contiguous, which might not be what you want if you are doing low-level optimizations of data layout.
        jjnoakes 9y ago
        So put a ref or a box in your optional.
        dbaupp 9y ago
        I don't think adding indirection is what the parent was thinking of. It's more like storing the Option<T> Some vs. None bit in its own separate bitvector along with a packed vector of Ts. This layout, due to padding, may be significantly less memory than alternating bool, T like a vector of Option<T>s gives, but it still retains properties like contiguous layout and minimal allocation/indirection.
        9y ago
  - lmm 9y ago
    Put the condition in the type. If you truly know that the pointer is nonnull, you can explain how you know to the compiler.
  - twic 9y ago
    If, after inlining and so on, the compiler can prove that the condition implies the non-null/Some case, then the check can be optimised away. If it can't, then the version without the check is potentially unsafe, and the check is not unnecessary.
dbaupp 9y ago
I think in practice it isn't a higher cost: a lot of code in languages with nullable pointers also has a pile of unnecessary dynamic checks (e.g. checking arguments aren't null).
- qznc 9y ago
  Exceptions (implemented zero-cost style) are truly zero cost. No dynamic checks as long as no exception is thrown.
  - lmm 9y ago
    Exceptions aren't zero-cost either: they require you to be able to unwind the stack, so you have to keep the frame pointer and have one fewer general-purpose register to work with.
    - cwzwarich 9y ago
      You actually don't need the frame pointer to unwind the stack. DWARF frame info allows the compiler to specify tables that describe the stack layout at every program point, and this can be used to perform unwinding. Another reason why exceptions aren't zero-cost in practice is that compilers need to model the exceptional control-flow, and they usualy don't do a great job in this situation and miss a lot of potential optimizations.
  - dbaupp 9y ago
    The cost being compared here is the 'if x.is_none()' or 'if x == null' check, not what happens after it.

webkike 9y ago

Option types for references need be no more expensive than a null pointer check, and I believe this is how they are implemented in Rust. If a dynamic check is not necessary, then you simply do not use an Option type.

cwzwarich 9y ago
In C/C++, you quite often end up in situations when some other condition implies that a pointer is nonnull. In Rust, the equivalent code with Option would require an unnecessary dynamic check.
- webkike 9y ago
  That's just a problem with ordering. If a condition implies a non null pointer then a non null pointer can imply the condition as well. This is true unless the condition being false does not guarantee a null pointer, in which case the condition is not useful. If some condition implies multiple non null pointers then the option type can be defined on a tuple of references
  - tomsmeding 9y ago
    > in which case the condition is not useful I contest. The reason for the condition need not be only to indicate whether the other value isn't null; if it was, you could just remove the condition and check nullity. In fact, unless there is either a case where the condition is true and the pointer is null or a case where the condition is false and the pointer is non-null, the condition is useless because checking the pointer would've been enough. Consider the following silly example, where we have a function f(Conductor *c, bool isDriving, Train *t) with the guarantees that c != NULL, and isDriving==true => t!=NULL. Note that the case isDriving==false does not imply t==NULL; indeed, c could just be waiting for the signal to start driving.
    - webkike 9y ago
      isDriving remains connected to t. Specifying an Option reference for t allows you to convey two pieces of information: if None, that isDriving is false and you do not care about t, and if Some, you have train t
    - dbaupp 9y ago
      One can express the states more clearly with a slightly upgraded Option/Optional/Maybe, i.e. a full sum-type/enum. For instance, that function could be, in Rust syntax (but the same thing works in Haskell, OCaml, Swift, ...): enum ConductorTask { Nothing, Waiting(Train), Driving(Train) } fn f(c: Conductor, task: ConductorTask) I think this says everything that your text says, but in a way the compiler understands and can assist the programmer with. Alternatively, since isDriving only makes sense when there's a train, t could be Option<(bool, Train)>, i.e. an optional train along with a boolean for if it's being driven or not.
      - cwzwarich 9y ago
        An Option type in Rust forces a particular memory layout by requiring the components to be contiguous, which might not be what you want if you are doing low-level optimizations of data layout.
        jjnoakes 9y ago
        So put a ref or a box in your optional.
        dbaupp 9y ago
        I don't think adding indirection is what the parent was thinking of. It's more like storing the Option<T> Some vs. None bit in its own separate bitvector along with a packed vector of Ts. This layout, due to padding, may be significantly less memory than alternating bool, T like a vector of Option<T>s gives, but it still retains properties like contiguous layout and minimal allocation/indirection.
        9y ago
- lmm 9y ago
  Put the condition in the type. If you truly know that the pointer is nonnull, you can explain how you know to the compiler.
- twic 9y ago
  If, after inlining and so on, the compiler can prove that the condition implies the non-null/Some case, then the check can be optimised away. If it can't, then the version without the check is potentially unsafe, and the check is not unnecessary.

dbaupp 9y ago

I think in practice it isn't a higher cost: a lot of code in languages with nullable pointers also has a pile of unnecessary dynamic checks (e.g. checking arguments aren't null).

qznc 9y ago
Exceptions (implemented zero-cost style) are truly zero cost. No dynamic checks as long as no exception is thrown.
- lmm 9y ago
  Exceptions aren't zero-cost either: they require you to be able to unwind the stack, so you have to keep the frame pointer and have one fewer general-purpose register to work with.
  - cwzwarich 9y ago
    You actually don't need the frame pointer to unwind the stack. DWARF frame info allows the compiler to specify tables that describe the stack layout at every program point, and this can be used to perform unwinding. Another reason why exceptions aren't zero-cost in practice is that compilers need to model the exceptional control-flow, and they usualy don't do a great job in this situation and miss a lot of potential optimizations.
- dbaupp 9y ago
  The cost being compared here is the 'if x.is_none()' or 'if x == null' check, not what happens after it.