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.

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.

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.

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.

[1] https://en.wikipedia.org/wiki/Null_Island

https://youtu.be/vh6zanS_epw

https://www.washingtonpost.com/news/morning-mix/wp/2016/08/1...

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.

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.)

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.

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.

for example?

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.

to make it obvious, post some code.

    bool m_initialized ;
    storage_type m_storage ;

FWIW, we have had this discussion a few months ago on HN.

(The compiler is allowed to improve this, but it won't.)

But those languages are very good at pretending they mix the two concepts.

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.

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.)

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

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.

Now how do you do that with a string? If you have to ask these questions, CSV is probably not the right format.

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.

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.

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.