[HN Gopher] Is it time to stop using sentinel values for null / ...
___________________________________________________________________
Is it time to stop using sentinel values for null / "NA" values?
(2018)
Author : greghn
Score : 49 points
Date : 2023-06-05 12:44 UTC (10 hours ago)
(HTM) web link (wesmckinney.com)
(TXT) w3m dump (wesmckinney.com)
| jfengel wrote:
| 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 wrote:
| 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.
| ryandrake wrote:
| 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.
| NoboruWataya wrote:
| 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 wrote:
| 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://www.washingtonpost.com/news/morning-
| mix/wp/2016/08/1...
| LorenPechtel wrote:
| 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.
| remram wrote:
| In that vein, more recently when users asked ChatGPT for its
| phone number it would consistently give them a specific
| journalist's number:
| https://twitter.com/DaveLeeBBG/status/1626288109339176962
| HPsquared wrote:
| In the vein of Douglas Adams you could open "the restaurant in
| the centre of the world". Probably won't get many customers,
| but you might end up with an enormous number of misdirected
| parcels.
| mrighele wrote:
| 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
| cratermoon wrote:
| 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.
| derbOac wrote:
| 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.
| ChrisRackauckas wrote:
| Julia has language-level support for missing values
| (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-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 wrote:
| 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.
| thriftwy wrote:
| 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.
| taeric wrote:
| 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.
| slicktux wrote:
| Low level programming at its finest...pretty cool performance
| gain!
| LorenPechtel wrote:
| 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.
| deathanatos wrote:
| 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 naive 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 wrote:
| 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 wrote:
| 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 wrote:
| > Most mainstream languages conflate memory layout and type
| definitions
|
| for example?
| morelisp wrote:
| 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/
|
| - This is somewhat the raison d'etre for Jai, if it ever
| gets released.
| marcosdumay wrote:
| 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 wrote:
| I said conflated, not made formally identical.
| zabzonk wrote:
| > C++ would be the obvious poster child
|
| to make it obvious, post some code.
| morelisp wrote:
| https://www.boost.org/doc/libs/1_34_1/boost/optional/opti
| ona... bool m_initialized ;
| storage_type m_storage ;
| zabzonk wrote:
| ok, now explain how this " conflate memory layout and
| type definitions"
| Dylan16807 wrote:
| 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.)
| gpderetta wrote:
| 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.
| weinzierl wrote:
| The discriminant will be optimized away if possible you end
| up with a sentinel but no performance hit.
| morelisp wrote:
| 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.
| jmull wrote:
| 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 wrote:
| 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 wrote:
| 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.
| msla wrote:
| How do I represent an Option<Int> in a CSV file?
| smcin wrote:
| I assume you mean the Scala type Option<Int>, and that's an
| integer type which can be NaN, right?
| msla wrote:
| 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 wrote:
| 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 wrote:
| 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.
| cratermoon wrote:
| 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 naive coder will get a result like NaN or, in some
| languages, undefined behavior, alerting them to the problem.
| arthurjj wrote:
| >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 wrote:
| So you're saying if you don't consistently use the same
| value to represent the value, you get incorrect results?
___________________________________________________________________
(page generated 2023-06-05 23:04 UTC)