Hacker News Reader

Comment by username223 | Hacker News Reader

> In a future blog post, I’ll describe how Nullable works in greater detail.

This is the part that interests me. If you're not using sentinel values like NaN, then it seems like you're left with pointers (terrible) or tags and tag tests (also pretty bad). If Julia can't use the processor's SIMD instructions (or the GPU in the near future), it's not suitable for inner loops. Do you special-case "Nullable{Double}" to use NaN as its "NA" value?

View on HN

Thankfully, the solution paths you're enumerating aren't the only viable solutions to the problem of representing missing values. Because Julia has value types (called immutables) and because Julia can compile functions based on their input arguments' types so that the functions don't need to do any run-time tag checking, a Nullable{Float64} value can be stored using at most 16 bytes -- 8 bytes for a Boolean flag indicating whether a value is present or not and 8 bytes for the actual 64-bit floating point value. The latter 8 bytes can store arbitrary bits if the Boolean flag is set to indicate that the Float64 value is missing.

If you're interested in the details of how Nullable{T} works, you can start with http://github.com/JuliaLang/julia/pull/8152 and then read through Julia's compiler code to understand how immutables are represented in memory and how functions that employ them are compiled to machine code.

UPDATE: Looking back at my answer, I should make clear that, when you want to work with SIMD or GPU operations, one can (and we will) use a representation of arrays of Nullable objects that places the values and the Boolean flags into two separate arrays. The values array is then identical to a normal 64-bit floating point array and allows all of the same operations. Setting the Boolean flags appropriately requires a bit more work. (How much work is strongly dependent on the exact computation being performed.)

Yikes. While this sidesteps some of the issues in the other approaches, it also doubles your memory usage and halves your potential SIMD performance. Maybe this is better than the downsides of the alternatives, but as someone working on optimizing large and slow R code with C++ extensions speaking to someone who is trying to replace R with something better, this seems like a choice that may haunt you in the future. If you can, I'd keep your options open for a "Structure of Arrays" approach or "buddy bitmap" that keeps your data contiguous and compact.

We'll keep re-evaluating this over time, but I'm currently not sure it's that serious a problem. For many numerically intensive computations, you'll want to move over to a pure array of 64-bit floating point values before the long-running computation begins, at which point you can adopt NaN == NA semantics if appropriate. I believe the solution I outlined in my updated comment above may already describe the buddy bitmap solution you're referring to. It certainly describes a solution that I would refer to as a struct-of-arrays.

Thanks for the informative reply.

> ... when you want to work with SIMD or GPU operations, one can (and we will) use a representation of arrays of Nullable objects that places the values and the Boolean flags into two separate arrays.

"When" is pretty much "always" with arrays. Trusting a sufficiently smart compiler and runtime to get rid of the tag checks makes me nervous, though. This optimization needs to be user-predictable and/or -controllable to be truly useful. If only compiler gurus can understand when slow, tag-checking, scalar loops will be replaced with fast SIMD code, something has gone wrong.

We will probably be pushing people very heavily towards always using specialized arrays for working with nullable objects.

I'm a little surprised by your comment about sufficiently smart compilers, since Julia seems to have taken the exact opposite approach to compiler design. The language is systematically designed to require little intelligence from the compiler. Being able to safely drop tag checks inside of a function's body seems like a fairly simple part of the language's design, since the type of all inputs to a function and all function-local variables are, in general, easily knowable as invariants before a function call even begins evaluating.

Reply on news.ycombinator.com