8 ms·

Is it time to stop using sentinel values for null / “NA” values? (2018)

52 points by greghn 3y ago

derbOac 3y ago
I think I'm following this but on the other end, I've often thought that there is a need for a NA class/type hierarchy, so the Arrow approach discussed in this piece might be too simple at some level? I'm being really loose and am unfamiliar with Arrow but it seems as if these kinds of discussions are useful but also maybe heavily language-dependent. E.g., how Julia, Python, R, Rust, or whatever interfaces with Arrow is also relevant. Treatment of null and missing data in the context of data science has rarely gotten the full consideration it probably warrants in design. Interesting read though.
- thriftwy 3y ago
  Arrow-based systems are also notorious for completely broken UIs/displaying of blank pages without missing a beat. You definitely do want some error reporting, however not in the form of SIGSEGV.
- ChrisRackauckas 3y ago
  Julia has language-level support for missing values (https://docs.julialang.org/en/v1/manual/missing/ https://docs.julialang.org/en/v1/manual/missing/) which acts like the solution here, but generally for any value that can be put in an array by doing `Union{Missing,T}`. The array type will automatically optimize by having a bitmap of represented values (for any singleton type this works, not just Missing). There were lots of pre-v1.0 design discussions on this vs sentinels, such as https://discourse.julialang.org/t/representing-nullable-values/4729 https://discourse.julialang.org/t/representing-nullable-valu... which can be dug up. The conclusion was more about the safety than performance, since sentinel values are fundamentally unsafe in generally since they can take a valid value and make it "special" (like in the blog post, minimum integer). Thus Julia has the following 3 choices: * Use `nothing`, which throws an error at each operation like `nothing + 1`. This requires `if x === nothing` handling everywhere, is the safest option, but is generally considered clunky for statistics use. As `nothing` is a singleton type, it has the same optimizations as what's mentioned in the blog post. * Use `missing`, which propagates, i.e. `missing + 1 === missing`. This allows for any `Union{Missing,T}` to use a scheme similar to the blog post: as `nothing` is a singleton type, it has the same optimizations as what's mentioned in the blog post. * Use a sentinel of your choice, risks known and dependent on the type. And you can build your stats libraries however you so choose, though JuliaStats has strongly gravitated towards the middle option as something close in ergonomics to R's NA but while having a bit more safety guarantees and generality.
  - derbOac 3y ago
    Interesting. I was familiar with Missing and nothing in Julia but had never really thought about other options from a safety angle. It makes sense though. I have run into issues where it would be nice to have some sort of missing type/class hierarchy though, in that the reason for missingness is coded somewhere and then how to represent that in those three categories gets complicated. At some level the different missing types get treated the same for many functions (such as your missing + 1 propagation example) but for other things not. Then you end up being tempted to use the third option which has its own issues. I suppose you could create another variable with type of missing information but then that also becomes complex quickly.
slicktux 3y ago
Low level programming at its finest…pretty cool performance gain!
- LorenPechtel 3y ago
  Yup, over the years I've had some pretty impressive gains from precalculating maps of various data items that are fundamentally bits and tend to be blocky in nature.
ryandrake 3y ago
I used to work with GPS mapping software, and the number of engineers who would lazily use "lat:0.0, lon:0.0" as a default or "invalid" location on Earth was... a little scary. When nuclear war breaks out, I am -not- going to want to be floating on a raft in the ocean off the coast of Africa at coordinates 0.0, 0.0 when the missiles fail and revert to their "default" target.
- mrighele 3y ago
  Funnily enough, that location is not empty (there is a buoy to mark it) and is aptly named "Null Island" [1] [1] https://en.wikipedia.org/wiki/Null_Island https://en.wikipedia.org/wiki/Null_Island
- NoboruWataya 3y ago
  When you think about it, we're somewhat fortunate that (0, 0) is in the literal middle of nowhere. You can pretty much always safely say that a reading of (0, 0) is a error (unless you're working with the weather buoy that's located there, I guess). If there was a major metropolis there things could get a lot more confusing.
  - jimktrains2 3y ago
    You mean like the house thats near the geographic center of the us and keep getting visits from the police because maxmind default to those coordinates for ip addresses. https://youtu.be/vh6zanS_epw https://youtu.be/vh6zanS_epw https://www.washingtonpost.com/news/morning-mix/wp/2016/08/10/lawsuit-how-a-quiet-kansas-home-wound-up-with-600-million-ip-addresses-and-a-world-of-trouble/ https://www.washingtonpost.com/news/morning-mix/wp/2016/08/1...
    - LorenPechtel 3y ago
      This isn't a null problem, but a precision problem. (And it's a lot more than just that one place, the same problem exists at many levels.) All location fixes inherently have a precision component and that routinely gets ignored. There's one tower that can reach the phone, the phone must be somewhere within the footprint of the tower. If the phone didn't supply more detailed info that's the only thing you can determine. The true area is the footprint but it gets reduced to a location and a precision--which maps it to a dot and a circle. A one-tower location fix will give a circle of uncertainty that extends off the visible map in most cases and humans ignore it. (The center of the US problem is a bit different but it's the same basic concept.) What I think they need to do is prohibit any system from showing the central dot (or any equivalent to that) when the precision is too low. Only render the zone of uncertainty and only at a map scale where you see the whole zone, attempting to zoom beyond that gets you a message that the location can't be determined more accurately, do not try to find the center of the zone.
deathanatos 3y ago
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.
cratermoon 3y ago
There's a design pattern, known alternately as Null Object or Special Case, related to this. The general goal is to eliminate the need to add checks for null/NA/sentinel and simply define valid behavior for these cases. Eliminating boundary checks both simplifies the code and improves performance.
jfengel 3y ago
There is no one solution to null. That's the point: "null" is the billion-dollar mistake because it solves so many different problems in exactly the same way. To fix it, you have to go back and reconsider what it means for your data to lack that value. Is it a different type of thing? Does it mean that the value must exist but isn't known? Does it mean that it's really some default value? Does it mean that there's an error but you're just trying to muddle along? Does it mean you could actually have zero or more of something? Does it mean it's uninitialized? You might try to solve any of these with a null. That's simple, but it does bad things to your type system. At least using sentinels makes it easier to reason about your type system, but if you're just using it as a "typed null" then you've just hidden the problem further. I find that the better you design your types to model the real problem domain, the less you need nulls or sentinels or other hacks. It all comes together naturally. Not always, but any time it doesn't, it's a smell.
- synthetigram 3y ago
  This is impractical a lot of the time. There are a class of problems where you want to put 2^N + 1 possible values in an N bit container, and it won't ever fit cleanly. Null is that 1 extra value that won't fit cleanly. Another case is an array based queue. It can be implemented with head+tail pointers, or size+offset. However, there will always be an ambiguity with either, because two words of memory aren't enough to represent all possible states of the queue.
taeric 3y ago
I'm a little curious if doing an equality comparison with self is the best way to determine something is NaN? I'm assuming that is as fast as any specific isNaN function available? I'm also assuming a nice thing about the bitmap approach is that it works for non float values? I recall hearing that Pascal had some good primitives for managing parallel arrays that were used like this. I can't remember the details, that well. Definitely feels related to the array of structures versus structure of arrays idea.

52 points by greghn 3y ago

I think I'm following this but on the other end, I've often thought that there is a need for a NA class/type hierarchy, so the Arrow approach discussed in this piece might be too simple at some level? I'm being really loose and am unfamiliar with Arrow but it seems as if these kinds of discussions are useful but also maybe heavily language-dependent. E.g., how Julia, Python, R, Rust, or whatever interfaces with Arrow is also relevant. Treatment of null and missing data in the context of data science has rarely gotten the full consideration it probably warrants in design. Interesting read though.

thriftwy 3y ago
Arrow-based systems are also notorious for completely broken UIs/displaying of blank pages without missing a beat. You definitely do want some error reporting, however not in the form of SIGSEGV.
ChrisRackauckas 3y ago
Julia has language-level support for missing values (https://docs.julialang.org/en/v1/manual/missing/ https://docs.julialang.org/en/v1/manual/missing/) which acts like the solution here, but generally for any value that can be put in an array by doing `Union{Missing,T}`. The array type will automatically optimize by having a bitmap of represented values (for any singleton type this works, not just Missing). There were lots of pre-v1.0 design discussions on this vs sentinels, such as https://discourse.julialang.org/t/representing-nullable-values/4729 https://discourse.julialang.org/t/representing-nullable-valu... which can be dug up. The conclusion was more about the safety than performance, since sentinel values are fundamentally unsafe in generally since they can take a valid value and make it "special" (like in the blog post, minimum integer). Thus Julia has the following 3 choices: * Use `nothing`, which throws an error at each operation like `nothing + 1`. This requires `if x === nothing` handling everywhere, is the safest option, but is generally considered clunky for statistics use. As `nothing` is a singleton type, it has the same optimizations as what's mentioned in the blog post. * Use `missing`, which propagates, i.e. `missing + 1 === missing`. This allows for any `Union{Missing,T}` to use a scheme similar to the blog post: as `nothing` is a singleton type, it has the same optimizations as what's mentioned in the blog post. * Use a sentinel of your choice, risks known and dependent on the type. And you can build your stats libraries however you so choose, though JuliaStats has strongly gravitated towards the middle option as something close in ergonomics to R's NA but while having a bit more safety guarantees and generality.
- derbOac 3y ago
  Interesting. I was familiar with Missing and nothing in Julia but had never really thought about other options from a safety angle. It makes sense though. I have run into issues where it would be nice to have some sort of missing type/class hierarchy though, in that the reason for missingness is coded somewhere and then how to represent that in those three categories gets complicated. At some level the different missing types get treated the same for many functions (such as your missing + 1 propagation example) but for other things not. Then you end up being tempted to use the third option which has its own issues. I suppose you could create another variable with type of missing information but then that also becomes complex quickly.

slicktux 3y ago

Low level programming at its finest…pretty cool performance gain!

LorenPechtel 3y ago
Yup, over the years I've had some pretty impressive gains from precalculating maps of various data items that are fundamentally bits and tend to be blocky in nature.

ryandrake 3y ago

I used to work with GPS mapping software, and the number of engineers who would lazily use "lat:0.0, lon:0.0" as a default or "invalid" location on Earth was... a little scary. When nuclear war breaks out, I am -not- going to want to be floating on a raft in the ocean off the coast of Africa at coordinates 0.0, 0.0 when the missiles fail and revert to their "default" target.

mrighele 3y ago
Funnily enough, that location is not empty (there is a buoy to mark it) and is aptly named "Null Island" [1] [1] https://en.wikipedia.org/wiki/Null_Island https://en.wikipedia.org/wiki/Null_Island
NoboruWataya 3y ago
When you think about it, we're somewhat fortunate that (0, 0) is in the literal middle of nowhere. You can pretty much always safely say that a reading of (0, 0) is a error (unless you're working with the weather buoy that's located there, I guess). If there was a major metropolis there things could get a lot more confusing.
- jimktrains2 3y ago
  You mean like the house thats near the geographic center of the us and keep getting visits from the police because maxmind default to those coordinates for ip addresses. https://youtu.be/vh6zanS_epw https://youtu.be/vh6zanS_epw https://www.washingtonpost.com/news/morning-mix/wp/2016/08/10/lawsuit-how-a-quiet-kansas-home-wound-up-with-600-million-ip-addresses-and-a-world-of-trouble/ https://www.washingtonpost.com/news/morning-mix/wp/2016/08/1...
  - LorenPechtel 3y ago
    This isn't a null problem, but a precision problem. (And it's a lot more than just that one place, the same problem exists at many levels.) All location fixes inherently have a precision component and that routinely gets ignored. There's one tower that can reach the phone, the phone must be somewhere within the footprint of the tower. If the phone didn't supply more detailed info that's the only thing you can determine. The true area is the footprint but it gets reduced to a location and a precision--which maps it to a dot and a circle. A one-tower location fix will give a circle of uncertainty that extends off the visible map in most cases and humans ignore it. (The center of the US problem is a bit different but it's the same basic concept.) What I think they need to do is prohibit any system from showing the central dot (or any equivalent to that) when the precision is too low. Only render the zone of uncertainty and only at a map scale where you see the whole zone, attempting to zoom beyond that gets you a message that the location can't be determined more accurately, do not try to find the center of the zone.

deathanatos 3y ago

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.

cratermoon 3y ago

There's a design pattern, known alternately as Null Object or Special Case, related to this. The general goal is to eliminate the need to add checks for null/NA/sentinel and simply define valid behavior for these cases. Eliminating boundary checks both simplifies the code and improves performance.

jfengel 3y ago

There is no one solution to null. That's the point: "null" is the billion-dollar mistake because it solves so many different problems in exactly the same way. To fix it, you have to go back and reconsider what it means for your data to lack that value. Is it a different type of thing? Does it mean that the value must exist but isn't known? Does it mean that it's really some default value? Does it mean that there's an error but you're just trying to muddle along? Does it mean you could actually have zero or more of something? Does it mean it's uninitialized? You might try to solve any of these with a null. That's simple, but it does bad things to your type system. At least using sentinels makes it easier to reason about your type system, but if you're just using it as a "typed null" then you've just hidden the problem further. I find that the better you design your types to model the real problem domain, the less you need nulls or sentinels or other hacks. It all comes together naturally. Not always, but any time it doesn't, it's a smell.

synthetigram 3y ago
This is impractical a lot of the time. There are a class of problems where you want to put 2^N + 1 possible values in an N bit container, and it won't ever fit cleanly. Null is that 1 extra value that won't fit cleanly. Another case is an array based queue. It can be implemented with head+tail pointers, or size+offset. However, there will always be an ambiguity with either, because two words of memory aren't enough to represent all possible states of the queue.

taeric 3y ago

I'm a little curious if doing an equality comparison with self is the best way to determine something is NaN? I'm assuming that is as fast as any specific isNaN function available? I'm also assuming a nice thing about the bitmap approach is that it works for non float values? I recall hearing that Pascal had some good primitives for managing parallel arrays that were used like this. I can't remember the details, that well. Definitely feels related to the array of structures versus structure of arrays idea.