OptionTypes.jl

[John Myles White]

At JuliaCon, I described the idea of using Option types instead of NAtype to make it easier to write type-stable code that interacts with NA’s. To help facilitate a debate about the utility of this approach, I just wrote up a minimal package that implements Option types: https://github.com/johnmyleswhite/OptionTypes.jl

Essentially, an Option type is a scalar version of a DataArray: it contains a value and a Boolean mask indicating whether that value is NA or not. Because Option types are parametric, they allow us to express the variants of NA that R has, such as a Float64 specific NA and an Int64 specific NA.

— John

[Júlio Hoffimann]

Dear John,

I'm joining the debate late, but the Boost C++ devs did make a good review of models for optional types and came up with a quite consistent API: http://www.boost.org/doc/libs/1_55_0/libs/optional/doc/html/boost_optional/development.html#boost_optional.development.the_models

Are you following their work? Don't you think Optional would be a better name for it?

Best,

Júlio.

[John Myles White]

Julia, for now I’m using names closer to those employed in Scala.

 — John

[John Myles White]

Also worth noting that our goals are somewhat different from Boost’s: we aren’t trying to express the notion of an uninitialized value, but rather than notion of a value whose unquestionably well-defined value is not known to the program. This is not quite the logic of things like Haskell’s Maybe, but we’re co-opting some of their terminology.

 — John

On Jul 31, 2014, at 7:28 AM, Júlio Hoffimann <julio.h...@gmail.com> wrote:

[Júlio Hoffimann]

As far as I remember, Haskell's Maybe is closer to Boost.Variant or discriminated unions in general.

Anyways, good to know about this effort.

Júlio.

[Stefan Karpinski]

This looks quite promising. The `get` interface looks like a very nice way to generically deal with missing values – provide a default or get an error. Automatic conversion of the default to the type of the Option value is particularly nice. This seems like it will be a pleasant and efficient API.

Minor question: how come the non-NA constructor for Option takes both the `na` and `value` arguments? Doesn't supplying a value imply that it's not NA while not supplying a value implies that it is NA?

[Harlan Harris]

John, how might this interact with DataArrays? This design, unlike DataArrays, requires that you use an entire byte to store the missingness, so it's not likely to be as fast if you're manipulating a lot of them. Is the intended use case here something sum(DataArray) yields Option{Float64}? 

[Júlio Hoffimann]

One suggestion is to have it named as the more intuitive Optional{T}.

Júlio.

[Spencer Russell]

This is really great stuff. I think that figuring this out and incorporating it into idiomatic Julia code would be a really great step forward in writing code that's fast AND safe.

I really liked your thoughts during JuliaCon regarding the difference between Epistemological missingness(Absence of knowledge of value, but value exists) and Ontological missingness (Value does not exist) [1]. Is there a reason that this Option type is better suited to cover the former, and not the latter?

Maybe a couple usage examples of OptionTypes would also help clarify the use cases you're shooting for.

[1]: https://github.com/JuliaCon/presentations/tree/ecfe2396010dad76f472a7eaacf4ada8523b65a1/RepresentingData

peace,

s

[Spencer Russell]

off-topic: John, do you have a reference for those different concepts of nothingness? It could come in handy for a bunch of the sensor data stuff I do for my research.

peace,

s

On Thu, Jul 31, 2014 at 11:35 AM, Spencer Russell <s...@mit.edu> wrote:

...

I really liked your thoughts during JuliaCon regarding the difference between Epistemological missingness(Absence of knowledge of value, but value exists) and Ontological missingness (Value does not exist) [1]. Is there a reason that this Option type is better suited to cover the former, and not the latter?

 

...

[1]: https://github.com/JuliaCon/presentations/tree/ecfe2396010dad76f472a7eaacf4ada8523b65a1/RepresentingData

[John Myles White]

You're right: the type I've implemented is not equivalent to Haskell's Maybe, which is a kind of Union type.

-- John

[John Myles White]

You're right: there's no reason to allow people to set the NA Boolean for options. In fact, I don't think I should expose the non-NA constructor at all, just the Some function.

Originally, that constructor was exposed because I was providing tools for working on Option types directly: doing arithmetic, for example, where the NA flag was being set appropriately.

But this minimal implementation is meant to provide a much more simplified wrapper than must be converted to a non-NA value as soon as possible.

 -- John

[John Myles White]

Harlan, I don't think your assumption about performance is necessarily correct: it's sometimes the case that you can get *better* performance by working with bytes rather than bits, since bytes are the primitive objects of computation. For that reason, I think the performance implications of using a full Bool are very sensitive to the exact computations being performed.

In general, I don't think the expansion of a BitArray bit into a Boolean is a big issue for most data analysis tasks. As evidence, I'd note that expanding a bit to a Bool is certainly not worse than the cost of translating a single byte from an ASCIIString or UTF8String object into a Char object when doing iteration over strings. If you think that decision for Base Julia is reasonable, I think the decision to use Option is also defensible for similar reasons.

As for integration into the current system, my thinking is that DataArrays would be changed so that OptionTypes would be generated whenever you attempt to access a scalar element of an AbstractDataArray. The following example shows how that might work:

function mean(a::AbstractDataArray, dropna::Boolean = false)
   sum, n = 0.0, 0
   if dropna
       for i in 1:length(a)
           o = a[i]
           if !isna(o)
               sum += get(o)
               n += 1
           end
       end
   else
       for i in 1:length(a)
           sum += get(o)
           n += 1
       end
   end
   return sum / n
end

One could also define this function so that it always returns an Option type, rather than a direct Float64 value.

For special types like Float64, you could even computes means while returning NaN's using the default values interface to `get`:

function mean{T <: FloatingPoint}(a::AbstractDataArray{T})
   sum, n = 0.0, 0
   for i in 1:length(a)
       sum += get(o, nan(T))
       n += 1
   end
   return sum / n
end

Unlike our current system, the use of OptionTypes would provide acceptable performance without requiring that users break abstraction barriers. This is the big gain: Option{T} exploits Julia's current type system / compiler to express the same ideas as NAtype does in an efficient way. Options wouldn't need to be boxed the way that our Union types currently are being boxed because their type could be easily inferred by the compiler.

If you're not familiar with the requirement for breaking our current abstraction barriers, note that indexing into a DataArray at the moment poisons the performance of every program you write, because the result has an uncertain type that the compiler doesn't know how to optimize. To work around this, you have to write code that effectively accesses the raw .na and .data fields of a DataArray. Simon's done some great work to make this easier to do, but I'm not sure that's the right direction for us to head in the long-run.

In general, I think an approach to missing data built on the combination of Option{T} and DataArray{T} provides an interface that's simple and consistent (everything happens in terms of isna/get) even if it's an interface that's somewhat unfamilar to R/Python folks. Most important to me is that using Option types efficiently doesn't require a deep understanding of Julia's type system, whereas our current abstractions require you to understand how to work around problems raised by Union types when programming for the current compiler. An Option type is basically a forcing function that says: "Julia is aggressively typed. If you want to work with a missing value of type T, you need to explicitly say how you're going to handle any missingness so that the system only interacts with values of type T."

I should note that I'm not very sure the use of Options is the right approach: Simon Kornblith has argued very persuasively for waiting for the compiler to improve its ability to handle tagged unions like those generated by indexing into DataArrays. My personal feeling is that it's easier to expose a simple abstraction that doesn't assume the compiler will change dramatically. This is based on my aesthetic sense that Julia's power comes from making optimizations transparent and explicit, rather than making the compiler smarter.

It's also worth noting that there are problems for which the use of Option types isn't very helpful: the computation of medians, for example, isn't defined in terms of scalars, so having a better abstraction for expressing missing scalars won't get us anywhere.

One other caveat is that I'm not providing an `unsafe_get` method, which means that the `isna` followed by `get` idiom I showed above does two checks when you could get away with only one. I still haven't figured out how I'd like to handle that issue.

So there's still a lot of design work needed, but I wanted to let people see how this interface could work were we to choose it.

 -- John

[John Myles White]

Julia, I think your naming suggestions will be more impactful if you're careful to describe your opinions in terms of your subjective preferences, rather than in terms of objective facts. Describing something as "more intuitive" isn't a very effective rhetorical strategy if others don't already share your intuitions. Rather than assert that X is more intuitive, it would be great to demonstrate why your preferred name could be more intuitive.

Just my two cents about effective argumentation strategies.

 -- John

[John Myles White]

The reason this type is meant to cover epistemological, rather than ontological, missingness is that epistemological missingness is the norm in statistics, not ontological missingness. Since that means we're breaking somewhat with the conventional programming use case for Options (which is ontological missingness), we might want to come up with a better name.

The e-mail I sent to Harlan has a few simple use cases. I'll write up some more later.

 

 -- John

[John Myles White]

I didn't have many good references for this, but the link that Julio brought up makes this distinction quite explicit: "A formally uninitialized optional object has conceptually no value at all and this situation can be tested at runtime."

http://www.boost.org/doc/libs/1_55_0/libs/optional/doc/html/boost_optional/development.html#boost_optional.development.the_models

 -- John

[Bob Nnamtrop]

What about naming it the Data{T} type instead of Option{T} (or Optional{T}). Seems to fit in the DataArray{T} theme better and gives me a better idea what it is from the name (at least once one knows about DataArrays).

Bob

[John Myles White]

Yeah, that's a good idea. I'd kind of like to call this something like Nullable since I'm not a huge fan of the name DataArray, but consistency is an important thing to maintain.

 -- John

[David Anthoff]

+1 for Nullable (I have a .Net background). Data{T} seems like a very generic name for a very specific concept. For people that have not read the doc and would come across code that used this construct, the name wouldn’t give the slightest hint what this might be about, whereas something like Nullable would probably point people at least in the right direction (also, much more googleable). I’m with your dislike for the name DataArray, again I think that is a generic name that doesn’t point people to what it might mean. Maybe better to rename DataArray to something like NullableArray? I guess the really nice syntax would just be that Array{Nullable{Float64}} would end up creating the same thing as a DataArray right now, but as far as I understand the type system that wouldn’t work, right?

 

Cheers, David

[Jacques Rioux]

Another +1 for Nullable type as opposed to Option type. 

Option type does not convey any specific meaning.

Jacques

[John Myles White]

Just to make sure everyone's on the same page: this concept's traditional name in CS is "Option" type. See http://en.wikipedia.org/wiki/Option_type for an example.

I'm totally happy to break with tradition on this, since there's also a strong tradition of referring to a similar construction as a "Nullable" type (as David Anthoff noted).

 -- John

[John Myles White]

Array{Nullable{Float64}} is very appealing, but it's not equivalent to DataArray{Float64} because of how things get stored in memory. I'd like to stick with DataArray{Float64} for a while, since it makes it easier to apply existing array functions. Getting rid of DataArray is very tempting, though.

 -- John

[Johan Sigfrids]

Would a Array{Nullable{Float64}} mean that you couldn't use OpenBLAS algorithms on the data because the bool value is laid out interleaved with the data?

[John Myles White]

Exactly. But we generally move over to Array{Float64} before calling OpenBLAS anyway, so that's not necessarily a fatal problem. Just something that needs to be approached with caution.

 -- John

[Simon Kornblith]

My previous comments on option types versus union types for DataArray indexing are here. To elaborate on John's summary above, my present views are:

• In many other language, including languages that are lower-level than Julia such as Rust, option types are union types and it's the compiler's job to make them fast. Making union types fast would simply mean that the presence of Union in the output of code_typed is no longer to be dreaded.
  
• The option type approach forces special handling of data that could potentially be missing but isn't, and this breaks generic code. I feel it is better if, once we know a datum is not missing, it has the same concrete type as if it were known to exist in advance.
• I'm not sure how missing data ought to fit into the type hierarchy, but neither the Union(NA, T) nor Option{T} approaches seem completely ideal.

Some more specific notes WRT performance:

• Storing option types in an Array{Option{T}} would require nearly twice as much memory as storing them in a DataArray in most cases. While a Bool is only 1 byte, there is additional padding needed for alignment. On x86_64 for types <= 64 bits the alignment is usually the size of the type.
• As long as option types live in registers and not in memory, they should consume no additional space as compared with scalar indexing into both the data and na arrays of a DataArray, as indexing into the na array would already require a register. There are, however, some cases where the BitArray representation of NAs can be exploited for performance. In John's example code for sum above with dropna = false above, the Option type approach would read every bit of the na array individually. It is faster to first check if any values are NA, which can be done 64 bits at a time, and throw an error if there are NAs or sum the values if not.
  
• There is other overhead related to DataArray indexing that needs to be addressed, notably that scalar indexing needs to be inlined (as well as isna and get, if we're using option types), and that accessing the data and na arrays currently incurs an undefined reference check.
  

Simon

[Jake Bolewski]

This is getting further afield but another point wrt performance is that the current design of data arrays is very amenable to accelerators such as gpus. This wouldn't improve performance for many operations but would be a huge performance gain in other instances if julia gains an alternative backend to target these devices.

[Diego Javier Zea]

I like the Sentinel value approach (but maybe because I don't know nothing about the Cons)

Pros

• Type-stable
  
• Imposes no indirection
  
• Directly use machine ops
  
• No additional memory requirements
  
• NaN already implements NA-like semantics
  
• Existing functions like + behave correctly
  

Cons

• Requires a sentinel value for every new type

In Julia is very easy to define by defining:

isna(x::MyType, MySentinelValues::Vector{MyType} ) = x in MySentinelValues

isna(x::MyType, MySentinelValue::MyType ) = x == MySentinelValue

isna(x::MyType) = isna( x , MySentinelValue )

• Potential binary incompatibility with other systems

I don't know about it. Are there problems in R because of this? What is the PANDAS approach to NA's? Is there some kind of general agreement?

• Vulnerable to compiler optimizations

I dont't know about it... Can we workin on that?

• NaN + NA != NA + NaN in some R builds

Is there any way to prevent it?

• Discards a potentially useful value

Is this a big problem? Is NaN doing the same, isn't it ?

Best,

[Stefan Karpinski]

Cons: not composable, makes basic arithmetic slow.

[John Myles White]

I think you're underestimating the difficulty of employing sentinel values. For example, what would be the sentinel values for basic types like Sets and Dicts?

No one disagrees with your assertion that, given sentinel values, you can easily define isna in terms of a containment check. This is the easy part of defining sentinel values. The hard part is deciding which values you’re going to use to define the vector MySentinelValues for every type.

 — John

[John Myles White]

To address Simon’s general points, which are really good reasons to avoid jumping on the Option{T} bandwagon too soon:

* I agree that most languages use tagged union types for Option{T} rather than a wrapper type that contains a Boolean value. It’s also totally true that many compilers are able to make those constructs more efficient than Julia currently does. But what we should expect from Julia in the coming years isn’t so clear to me. (And I personally think we need to settle on a solution for representing missing data that’s viable in a year rather than viable in five years.) This is an issue that I’d really like to have input on from Jeff, Keno, Jameson or someone else involved with the internals of the compiler. Getting input from the broader community is the main reason I wanted to put a demo of OptionTypes.jl out in front of other folks.

* I’m not clear how we could come to know that a datum is not missing without a resolution step that’s effectively equivalent to the get() function for Option{T}. I agree that the enforced use of get() means that you can’t hope to use generic functions like sum on collections of Option{T}. But I’m also not sure that’s such a bad thing: I think the easiest way to express to the compiler that you know that all of the entries of a DataArray are not NA is to convert the DataArray to a straight Array. But maybe you have other mechanisms for expressing this knowledge. Certainly my proposal to do conversions to Arrays isn’t the most elegant strategy. It’s just all that I’ve got so far.

* I kind of like the idea of Option{T} standing outside of the main type system in a kind of mirror type system. I’m less happy about Union(NA, T) being a super type of T, even though there are some good reasons that you’d like to view T as a specialization of Union(NA, T). But I agree that I don’t have a good feel about where missing data belongs in the type hierarchy. This is another question for which I’d love to get input from others.

In regard to Simon’s performance points:

* Yes, memory usage alone argues strongly for working with DataArray{T} rather than Array{Option{T}}.

* Exploting tricks that make operations like anyna() faster is another good argument for keeping DataArray{T} around.

* I’m not sure how to deal with inlining concerns or the undefined reference checks. Do you have ideas for improving this within DataArrays or do we need supporting changes in the compiler?

 — John

On Jul 31, 2014, at 4:49 PM, Simon Kornblith <si...@simonster.com> wrote:

My previous comments on option types versus union types for DataArray indexing are here. To elaborate on John's summary above, my present views are:

• In many other language, including languages that are lower-level than Julia such as Rust, option types are union types and it's the compiler's job to make them fast. Making union types fast would simply mean that the presence of Union in the output of code_typed is no longer to be dreaded.
  
• The option type approach forces special handling of data that could potentially be missing but isn't, and this breaks generic code. I feel it is better if, once we know a datum is not missing, it has the same concrete type as if it were known to exist in advance.
• I'm not sure how missing data ought to fit into the type hierarchy, but neither the Union(NA, T) nor Option{T} approaches seem completely ideal.

Some more specific notes WRT performance:

• Storing option types in an Array{Option{T}} would require nearly twice as much memory as storing them in a DataArray in most cases. While a Bool is only 1 byte, there is additional padding needed for alignment. On x86_64 for types <= 64 bits the alignment is usually the size of the type.

• As long as option types live in registers and not in memory, they should consume no additional space as compared with scalar indexing into both the data and na arrays of a DataArray, as indexing into the na array would already require a register. There are, however, some cases where the BitArray representation of NAs can be exploited for performance. In John's example code forsum above with dropna = false above, the Option type approach would read every bit of the naarray individually. It is faster to first check if any values are NA, which can be done 64 bits at a time, and throw an error if there are NAs or sum the values if not.
  

[Milan Bouchet-Valat]

Le jeudi 31 juillet 2014 à 21:19 -0700, John Myles White a écrit :

To address Simon’s general points, which are really good reasons to avoid jumping on the Option{T} bandwagon too soon:

* I agree that most languages use tagged union types for Option{T} rather than a wrapper type that contains a Boolean value. It’s also totally true that many compilers are able to make those constructs more efficient than Julia currently does. But what we should expect from Julia in the coming years isn’t so clear to me. (And I personally think we need to settle on a solution for representing missing data that’s viable in a year rather than viable in five years.) This is an issue that I’d really like to have input on from Jeff, Keno, Jameson or someone else involved with the internals of the compiler. Getting input from the broader community is the main reason I wanted to put a demo of OptionTypes.jl out in front of other folks.

* I’m not clear how we could come to know that a datum is not missing without a resolution step that’s effectively equivalent to the get() function for Option{T}. I agree that the enforced use of get() means that you can’t hope to use generic functions like sum on collections of Option{T}. But I’m also not sure that’s such a bad thing: I think the easiest way to express to the compiler that you know that all of the entries of a DataArray are not NA is to convert the DataArray to a straight Array. But maybe you have other mechanisms for expressing this knowledge. Certainly my proposal to do conversions to Arrays isn’t the most elegant strategy. It’s just all that I’ve got so far.

* I kind of like the idea of Option{T} standing outside of the main type system in a kind of mirror type system. I’m less happy about Union(NA, T) being a super type of T, even though there are some good reasons that you’d like to view T as a specialization of Union(NA, T). But I agree that I don’t have a good feel about where missing data belongs in the type hierarchy. This is another question for which I’d love to get input from others.

Either with Option{T} or with Union(NAtype, T), nullable types create a mirror type hierarchy. But in the latter case, there are bridges between the two hierarchies:
- horizontally, T <: Union(NAtype, T)
- vertically (in diagonal), T2 <: Union(NAtype, T1) when T2 <: T1

For example, for Real and Float64:

Real    <- Union(NAtype, Real)
 |        /    |
 |      /      |
 |    /        |
Float64 <- Union(NAtype, Float64)

I see this as a relatively nice definition of the type hierarchy for missing data.
Thus I agree with Simon that using a type union if possible would be better than a specific option type which would obscure the type hierarchy -- which is really essential in Julia. Let us see what people working on the compiler say.

But thanks for tackling this John, it's a very interesting investigation and it would be great to be able to handle missing data in a more Julian fashion!


Regards

[Milan Bouchet-Valat]

Le jeudi 31 juillet 2014 à 14:03 -0700, John Myles White a écrit :
> Exactly. But we generally move over to Array{Float64} before calling
> OpenBLAS anyway, so that's not necessarily a fatal problem. Just
> something that needs to be approached with caution.

Except that the current layout of DataArray allows passing the
underlying array to BLAS without any copy if no NAs are present. With
fast array views, it would also be possible to select a subset of the
DataArray where no NA appears, and pass it to BLAS without any copy. It
could even be modified in-place.

So the memory gain offered by DataArrays compared with arrays of option
types is not negligible if people need to do computations from such
data. (Whether this is common in practice remains to see. :-)


My two cents

[Milan Bouchet-Valat]

Le jeudi 31 juillet 2014 à 21:19 -0700, John Myles White a écrit :

To address Simon’s general points, which are really good reasons to avoid jumping on the Option{T} bandwagon too soon:

* I agree that most languages use tagged union types for Option{T} rather than a wrapper type that contains a Boolean value. It’s also totally true that many compilers are able to make those constructs more efficient than Julia currently does. But what we should expect from Julia in the coming years isn’t so clear to me. (And I personally think we need to settle on a solution for representing missing data that’s viable in a year rather than viable in five years.) This is an issue that I’d really like to have input on from Jeff, Keno, Jameson or someone else involved with the internals of the compiler. Getting input from the broader community is the main reason I wanted to put a demo of OptionTypes.jl out in front of other folks.

* I’m not clear how we could come to know that a datum is not missing without a resolution step that’s effectively equivalent to the get() function for Option{T}. I agree that the enforced use of get() means that you can’t hope to use generic functions like sum on collections of Option{T}. But I’m also not sure that’s such a bad thing: I think the easiest way to express to the compiler that you know that all of the entries of a DataArray are not NA is to convert the DataArray to a straight Array. But maybe you have other mechanisms for expressing this knowledge. Certainly my proposal to do conversions to Arrays isn’t the most elegant strategy. It’s just all that I’ve got so far.

* I kind of like the idea of Option{T} standing outside of the main type system in a kind of mirror type system. I’m less happy about Union(NA, T) being a super type of T, even though there are some good reasons that you’d like to view T as a specialization of Union(NA, T). But I agree that I don’t have a good feel about where missing data belongs in the type hierarchy. This is another question for which I’d love to get input from others.

In regard to Simon’s performance points:

* Yes, memory usage alone argues strongly for working with DataArray{T} rather than Array{Option{T}}.

* Exploting tricks that make operations like anyna() faster is another good argument for keeping DataArray{T} around.

* I’m not sure how to deal with inlining concerns or the undefined reference checks. Do you have ideas for improving this within DataArrays or do we need supporting changes in the compiler?

Actually it seems it would be possible to make Array{Union(NAtype, T)} more similar to and as efficient as DataArray{T}, by handling a few things in the compiler. This would create a generalization of DataArray to any kind of union type, which could be useful in other contexts. But more importantly, it would make missing values integrate seamlessly into Julia, getting rid of any hacks.

More specifically, the following features would need to be supported:
- a way of telling the compiler to store the data as two arrays of concrete types (here T and NAtype), instead of as an array of boxed values, so that:
    * efficient operations can be performed on the T values (by skipping the missing ones manually)
    * T values are stored as a dense array and can be converted to Array{T} without any copy or passed to BLAS when no missing values are present
   * NA values can be packed in a BitArray to save memory and make NA detection faster (see below)
- a fonction to check whether a given element of the array is of type T rather than of NAtype (generalization of isna())
- a fonction to check whether all elements of the array are of type T rather than of NAtype (generalization of anyna(), more efficient than calling the previous function on all elements thanks to the packing of NAs in a BitArray)
In this scheme, what is missing is how to allow the compiler to pack NAs in a BitArray. Somehow, NAtype would have to be defined as a 1-bit object. Maybe by making it an enum-like immutable with a 1-bit field inside it?

How does it sound?

[Simon Kornblith]

I've thought a bit about this, but it seems like it would be too much complexity in the compiler. Storing arrays as something besides contiguous elements and interaction between the codegen in C/C++ and the BitArray code in Julia both seem likely to be painful, although Jeff, Keno, and Jameson would know better than I. Additionally, this optimization (of storage of arrays of unions of a singleton type and a bits type) seems pretty specific to DataArrays, but the actual advantages in terms of performance and expressibility would be small or non-existent. (This is in contrast to optimizing storage/dispatch with union types, which could benefit a lot of code and is something a lot of languages do.) Finally, there are cases where it is useful to have direct access to the na BitArray chunks beyond anyna, e.g. pairwise summation and reductions across the first dimension.

Simon

[Keno Fischer]

It is possible to do generic compiler improvements for Union types
(Jameson had a branch at some point that did callsite splitting if we
inferred a Union type). However, I think the best way to go here is to
maintain the current separation of two arrays (one of the values one
for the NAs), but give an option type on access. The option type would
then most likely be in memory and wouldn't have much overhead. Please
let me know if there's anything specific I should explain how the
compiler will handle it, I admit I have only skimmed this thread.

[Jameson Nash]

I could (and probably will, someday) revive that commit. At the time, though, I seemed to find that it provided little performance benefit -- the gc cost of allocating boxes was far greater (for type uncertainty involving bitstypes) and the type dispatch wasn't as much of a performance impact as I had previously assumed. 

[Simon Kornblith]

Is there a reason we can't change the way unions of small bits types are represented, so that if we know something is a Union(Float64,NA) it can live in registers or on the stack instead of having to be heap allocated?

[Jeff Bezanson]

As usual, I agree with Keno :)

We could also implement optimizations for Union(Bits,OtherBits). In
theory this can be stack allocated along with a boolean flag that says
which one it is. However to take full advantage of this it seems you
need to generate lots of branches with code for each case. Possible
but tricky.

There is also a strong connection to the general
array-of-structs-to-struct-of-arrays optimization. It would not be
totally crazy to build this in to our object representation somehow,
or add hooks allowing customization of data representations, like
staged functions but for data instead of code.

[Tim Holy]

I also haven't read this thread carefully, but it does seem that in this case
one needs to automatically mutate code like this:

x = A[5]
if isa(x, BadType)
...
elseif isa(x, GoodType)
... # do something with x
end

into

dt = peektype(A, 5) # gets the type of A[5] without evaluating it
if dt <: BadType
...
elseif dt <: GoodType
x = A[5]
... # do something with x
end

so that dt can be type-stable.

--Tim

[Jameson Nash]

Nope -- that the right idea. Just pointing out that you get more value from improving the storage representation than from specializing union call sites

[Stefan Karpinski]

That also strikes me as the best approach for what it's worth – just use option/maybe/nullable for what you return when indexing into a DataArray but keep the DataArray storage as two separate arrays.

[John Myles White]

Thanks, everybody, for the input.

I’m going offline for the next week while camping in Oregon, but I’ll return to this project once I’m back.

 — John

[John Myles White]

Just wanted to come back to this thread now that I’m back from vacation. It sounds like the consensus of Jeff, Stefan, Keno and Jameson is that we’re better off working with an explicit Option{T} type than trying to get the compiler to handle Union(S, T) more efficiently.

If people are willing to accept that idea, I’d like to make the use of Option’s a priority for a release of DataArrays that would accompany Julia 0.4. There’s going to be a lot of changes to Julia’s core with that release, so it seems like the perfect time to make some breaking changes to JuliaData packages.

After thinking about the type hierarchy more, I’ve come to really like the interpretion of Option{T} as a 0-or-1 element container type. In that interpretation, Option{T} is to T exactly as Array{T} is to T, which is a relationship that has only horizontal links and no vertical links. I think that perspective simplifies things a lot, whie articulating the core issues involved with working with Option{T}.

For me, the main question is whether we want Option types to be a feature that’s shared by people who want to express NULL pointers (i.e. ontological missingness) or whether we want to customize things for statistical missingness (i.e. epistemological missingness). As it stands, OptionTypes.jl implements such a bare-bones version of missingness that it could be safely used for either purpose.

As for the naming debate, I think NullableTypes with a new type called Nullable{T} is the way to go.

 — John

On Aug 1, 2014, at 1:43 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

[Stefan Karpinski]

Sounds good. We could maybe include the Nullable type in Base and thus avoid the issue of what to call the module. If we need a module, how about Nullables? Although, I have to say that name makes me think of The Expendables.

[John Myles White]

Well, Facebook did just add stickers for The Expendables 3, so that might have been on my mind today.

Seems like there’s no need for a Nullables module if this goes into Base. The library is so minimal as is and I’m about to pull some functionality out of it that’s not really necessary.

 — John

On Aug 11, 2014, at 9:17 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

Sounds good. We could maybe include the Nullable type in Base and thus avoid the issue of what to call the module. If we need a module, how about Nullables? Although, I have to say that name makes me think of The Expendables.

<expendables.png>

[John Myles White]

Ok, I’ve cleaned this up and renamed it to NullableTypes.jl: https://github.com/johnmyleswhite/NullableTypes.jl

 — John

On Aug 11, 2014, at 9:17 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

Sounds good. We could maybe include the Nullable type in Base and thus avoid the issue of what to call the module. If we need a module, how about Nullables? Although, I have to say that name makes me think of The Expendables.

<expendables.png>

[Stefan Karpinski]

What's the deal with unsafe_get? Does that segfault if you try to access a null value reference value and give you random junk if you try to access an bits value?

[John Myles White]

Yup.

It’s unclear to me whether it should be included or not. It’s useful if you’ve already done an explicit isnull(x) check so that you can save a second check.

 — John

[Stefan Karpinski]

That seems like a really good candidate for improving the compiler to make sure that it can eliminate the second check.

[John Myles White]

Agreed. I included it to allow users to make clear what the compiler ought to do.

 — John