5 ms·

https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/ https://www.infoq.com/presentations/Null-References-The-Bill... It's

https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/ https://www.infoq.com/presentations/Null-References-The-Bill... It's just another variant of that: having INT32_MIN is just as bad: these things inevitably end up unrepresented in the typesystem, someone writes a naïve function over that, and suddenly your "nulls" are being summed or computed on, particularly when they're rare in the dataset, or at least in the one the coder tested with. (Even in SQL, where it's a separate value — NULL — it's still an awfully weak type system, so sanity is by no means assured.) Give me must-be-explicitly-handled Option<T>. (So, I'd argue that even if there were a performance loss, in most cases, the gain in correctness is the right tradeoff.)

richardjam73 3y ago
I was under the impression that this article was talking about how to store nulls in memory not their usage. An Option type still needs to store either the value or the None value, which takes up the same space as having a Null value.
morelisp 3y ago
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.
    - 3y ago
- 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.
jmull 3y ago
I think you're conflating different things. This is about how to represent a null values in memory (for a columnar data structure), not how null values are expressed and accessed in a particular language's type system. However null values are represented in memory, you'd want an appropriate language binding/reppresentation.
- deathanatos 3y ago
  Yes, but only from a strictly theoretical view. One influences the other, and in particular, one makes the other much more difficult. Representing "INT32_MIN is None" in, e.g., Rust, is possible, but it's much more troublesome. I'd need something like Option<ASpecialI32>, where that inner type excludes the sentinel. Cf. representing "all i32s are valid, plus there's a None value", that's just Option<i32>. And in practice, if someone has an odd sentinel value like that in the data format, library authors tend to be lazy and not take the time to do that wrapping; instead, they just expose the i32 directly, maybe Option<i32>, and sharp edges abound around the sentinel. (That is, the data format — a sentient value — encourages buggy code. And that is the billion dollar mistake: that a nullptr pretends to be a pointer, while it is not, and gets swept up in the same operations.)
  - Dylan16807 3y ago
    What's the memory representation of an Option<> then? Do you want to add 4 bytes to each value to hold the tag? Even if you do that, a lazy author might still provide raw access to the ints.
cratermoon 3y ago
However, if you define a "null" number as 0, the summation works fine. Division by 0 can still fail, and that's good because the naïve coder will get a result like NaN or, in some languages, undefined behavior, alerting them to the problem.
- arthurjj 3y ago
  >the summation works fine This is only true if that summation is not used or compared anywhere else which isn't usually the case. For example if in sql you are reporting the SUM(column_A)/ SUM(column_B) and one column can be null without the other one being null you're likely reporting the wrong number
  - cratermoon 3y ago
    So you're saying if you don't consistently use the same value to represent the value, you get incorrect results?
msla 3y ago
How do I represent an Option<Int> in a CSV file?
- smcin 3y ago
  I assume you mean the Scala type Option<Int>, and that's an integer type which can be NaN, right?
  - msla 3y ago
    No, I only used Option<Int> because the person I replied to did, and I don't expect them to know what Maybe Int means.
- deathanatos 3y ago
  I mean … CSV hasn't a notion of Option, or Int, so you'd have to define your own. But you don't have to use what the article calls a "sentinel value" (i.e., you don't have to dedicate -2489391827 as "null") to do it: simply "null" for None/Null/Nothing, and the integer for Some(<int>) / Just int would work.
- icedchai 3y ago
  An empty string could be interpreted as a null integer. Now how do you do that with a string? If you have to ask these questions, CSV is probably not the right format.

richardjam73 3y ago

I was under the impression that this article was talking about how to store nulls in memory not their usage. An Option type still needs to store either the value or the None value, which takes up the same space as having a Null value.

morelisp 3y ago

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.
  - 3y ago
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.

jmull 3y ago

I think you're conflating different things. This is about how to represent a null values in memory (for a columnar data structure), not how null values are expressed and accessed in a particular language's type system. However null values are represented in memory, you'd want an appropriate language binding/reppresentation.

deathanatos 3y ago
Yes, but only from a strictly theoretical view. One influences the other, and in particular, one makes the other much more difficult. Representing "INT32_MIN is None" in, e.g., Rust, is possible, but it's much more troublesome. I'd need something like Option<ASpecialI32>, where that inner type excludes the sentinel. Cf. representing "all i32s are valid, plus there's a None value", that's just Option<i32>. And in practice, if someone has an odd sentinel value like that in the data format, library authors tend to be lazy and not take the time to do that wrapping; instead, they just expose the i32 directly, maybe Option<i32>, and sharp edges abound around the sentinel. (That is, the data format — a sentient value — encourages buggy code. And that is the billion dollar mistake: that a nullptr pretends to be a pointer, while it is not, and gets swept up in the same operations.)
- Dylan16807 3y ago
  What's the memory representation of an Option<> then? Do you want to add 4 bytes to each value to hold the tag? Even if you do that, a lazy author might still provide raw access to the ints.

cratermoon 3y ago

However, if you define a "null" number as 0, the summation works fine. Division by 0 can still fail, and that's good because the naïve coder will get a result like NaN or, in some languages, undefined behavior, alerting them to the problem.

arthurjj 3y ago
>the summation works fine This is only true if that summation is not used or compared anywhere else which isn't usually the case. For example if in sql you are reporting the SUM(column_A)/ SUM(column_B) and one column can be null without the other one being null you're likely reporting the wrong number
- cratermoon 3y ago
  So you're saying if you don't consistently use the same value to represent the value, you get incorrect results?

msla 3y ago

How do I represent an Option<Int> in a CSV file?

smcin 3y ago
I assume you mean the Scala type Option<Int>, and that's an integer type which can be NaN, right?
- msla 3y ago
  No, I only used Option<Int> because the person I replied to did, and I don't expect them to know what Maybe Int means.
deathanatos 3y ago
I mean … CSV hasn't a notion of Option, or Int, so you'd have to define your own. But you don't have to use what the article calls a "sentinel value" (i.e., you don't have to dedicate -2489391827 as "null") to do it: simply "null" for None/Null/Nothing, and the integer for Some(<int>) / Just int would work.
icedchai 3y ago
An empty string could be interpreted as a null integer. Now how do you do that with a string? If you have to ask these questions, CSV is probably not the right format.