Base DataFrame on NamedTuple

[nalimilan]

Now that NamedTuple is in Julia Base (on 0.7), we should use it in DataFrames. A possible approach which has been discussed on Slack would be to define a new TypedDataFrame{C<:NamedTuple} <: AbstractDataFrame type, which would just wrap a NamedTuple, and include information regarding the column names and types in its type parameter C. Then DataFrame would be a convenience type wrapping a TypedDataFrame object, with the advantages that 1) columns can be added/removed/renamed, and 2) functions do not need to be compiled for each combination of column types when it doesn't improve performance. TypedDataFrame would be useful to improve performance where the user provides a custom function operating on each row (notably groupby), as specialization is essential for performance in that case.

I have experimented this approach in the nl/typed branch, using the NamedTuples.jl package (since I used Julia 0.6 at first). It's mostly working (and passes some tests), but lots of fixes are needed to pass all tests. In particular, I originally removed the Index type since I thought NamedTuple could replace it (hence the sym_colinds and int_colinds attempts), but I'm not sure that's possible since we sometimes need to convert symbols to integer indices and vice-versa (cf. #1305). Handling of duplicate column names need to be improved (rebased on top of #1308).

@bkamins This touches areas you improved recently, and I'm not sure I'll be able to find the time to finish this right now. To avoid stepping on each other's toes (since this is required to implement the getindex improvements you've mentioned), if you want to take this up just let me know.

[quinnj]

but I'm not sure that's possible since we sometimes need to convert symbols to integer indices and vice-versa

Can't you just rely on the fact that getfield(::NamedTuple, i) works w/ i being a Symbol or Integer? What are the cases where you actually need to convert between?

[nalimilan]

Can't you just rely on the fact that getfield(::NamedTuple, i) works w/ i being a Symbol or Integer? What are the cases where you actually need to convert between?

The way the code is currently written, we sometimes need to convert all indices from either symbols or integers to a common representation since the function accepts both, and we don't want to write it twice. The lookup operation should be fast, so unless NamedTuple can provide us some way of doing it, we have to keep a dictionary mapping names to indices.

[quinnj]

Wait, are talking about cases where the user is providing both symbols and integers? Why even allow that? It seems totally reasonable to just say, use symbols, or use integers, but you can't mix both.

[nalimilan]

No, I mean that functions allow passing either symbols or integer, but internally they work with only one type of index. For example, that's the case of the stack/unstack functions. Maybe they could be refactored to support both without any conversion, but for now that's not how they work.

[bkamins]

@nalimilan I would help - but because of the size of the PR we have to discuss how to work with it.

I would start with the performance - this relates to the question if it is worth to switch to NamedTuples. This again has several layers. Let me start with the most basic one (I do not want to start too many topics at the same time).

Field access in NamedTuple using Symbol has O(n) complexity. Similarly checking if field is present (haskey) or field index (this can be verified using Base.fieldindex).

This means that we get type stability of the return value of the function:
https://github.com/JuliaData/DataFrames.jl/compare/nl/typed#diff-ba2bdc24748beed6a8c4e5b45ab5d644R266

at the cost of performance. To give you the scale. Accessing column of DataFrame with Symbol that is 1000th column is 100x slower using NamedTuple implementation than using current Dict implementation (still both operations are reasonably fast - we would get into problems if we created DataFrames having millions of columns - which is not unthinkable, but not a common use case).

If we accept this penalty then we do not need internal Index as we can use Base.fieldindex to get the index (just we have to check with Julia core what are the plans for this function as it is currently not exported).

[nalimilan]

The interest of using NamedTuple is mainly to get type-stability regarding the columns, which is essential in particular for groupby. In that case, the cost of resolving the name of the column is only paid once, then on each iteration the compiler should optimize out that lookup and turn it into a simpler getindex call on the corresponding column vector.

In general, the cost of looking up a column should never be significant in the computing time, or the code is not designed correctly. Indeed for efficient operation you really need to work directly with column vectors.

That said, it's always good to make an operation as efficient as possible, so I think we should keep Index if it really makes a performance difference when accessing a data frame column for reasonably-sized data frames. I'd say "reasonable" can go up to a few thousand columns, probably not more than that. When you say "to give you the scale", do you mean these are roughly the numbers you obtained with benchmarking? That would sound quite large indeed.

[bkamins]

OK. I have done some more careful tests - earlier I was mixing different things when timing.
I use @time to get realistic user experience.

Conclusions:

• In global scope access to NamedTuple is slower than to DataFrame (this problem should not be significant inside a function as probably this can be optimized by the compiler);
• Construction of NamedTuple on 0.6.2 is prohibitively slow (not an issue in the long term);
• Construction of NamedTuple on 0.7 is slow, it seems that complexity is O(n^2), but I have not investigated it in detail; but for small DataFrames it should be acceptable.

As a comment I think we should target the performance up to 100 000 number of columns, as those are the numbers of explanatory variables you can meet in practice in modeling in analytical data set. But this judgement is conditional on target audience of DataFrames package - in particular how it should be positioned against JuliaDB (for what usage scenarios which package should be recommended). I am not 100% clear about this.

Benchmark results below:

On 0.6.2:

julia> using NamedTuples
julia> using DataFrames
julia> cnames = [Symbol(string("a", i)) for i in 1:5000];
julia> columns = [[1] for i in 1:5000];
julia> @time C = eval(:(@NT($(cnames...)))){map(typeof, columns)...};
  1.756493 seconds (284.89 k allocations: 14.464 MiB, 0.47% gc time)
julia> @time nt = C(columns...);
 26.728015 seconds (1.99 M allocations: 105.869 MiB, 0.16% gc time)
julia> @time df = DataFrame(columns, cnames)
  0.889981 seconds (479.70 k allocations: 25.268 MiB, 0.82% gc time)
julia> # additionally check direct Dict lookup times
julia> z = Dict{Symbol,Vector{Int}}()
Dict{Symbol,Array{Int64,1}} with 0 entries
julia> for i in 1:5000 z[cnames[i]] = columns[i] end
julia> @time for i in 1:10^6 nt[:a5000] end;
  2.774900 seconds (11 allocations: 912 bytes)
julia> @time for i in 1:10^6 df[:a5000] end;
  0.077999 seconds (1.00 M allocations: 15.260 MiB, 3.94% gc time)
julia> @time for i in 1:10^6 z[:a5000] end;
  0.049605 seconds (32 allocations: 2.141 KiB)

On 0.7:

julia> @time nt = NamedTuple{(cnames...,)}((columns...,));
  3.819478 seconds (590.83 k allocations: 30.013 MiB, 0.23% gc time)

but for 20000 columns (which is not unthinkable):

julia> @time nt = NamedTuple{(cnames...,)}((columns...,));
 49.894595 seconds (2.40 M allocations: 157.249 MiB, 0.17% gc time)

The same on 0.6.2 is probably unacceptable:

julia> cnames = [Symbol(string("a", i)) for i in 1:20000];

julia> columns = [[1] for i in 1:20000];

julia> @time C = eval(:(@NT($(cnames...)))){map(typeof, columns)...};
 19.307509 seconds (898.39 k allocations: 44.163 MiB, 0.10% gc time)

julia> @time nt = C(columns...);
492.488972 seconds (7.32 M allocations: 392.716 MiB, 0.04% gc time)

[nalimilan]

Don't worry about 0.6.2, we already have enough work on our plate. Also, note that most of the time is only needed the first time the type is created, i.e. the first time a table with specific column names and types is encountered. The second call is very fast.

[bkamins]

I know, but the problem with DataFrame is that the chance to encounter the same name-type combination is very low.
Actually maybe it is possible to speedup the construction of large named tuples in Base - do you know who would be best to ask?

As a side note - your current proposed implementation is for 0.6.2 and will not work on 0.7.

[nalimilan]

I know, but the problem with DataFrame is that the chance to encounter the same name-type combination is very low.

Yes. But 3 seconds for 5000 columns isn't too bad, anyway with that many columns many operations are going to be slow. For 500 columns it's already much more reasonable.

Actually maybe it is possible to speedup the construction of large named tuples in Base - do you know who would be best to ask?

The best person is probably Jeff, I can ask him on Slack.

As a side note - your current proposed implementation is for 0.6.2 and will not work on 0.7.

Yes, unfortunately I started working on that before NamedTuple was merged in Base. But it would be OK to stop using NamedTuples.jl and require 0.7.

[nalimilan]

BTW, Jameson says we'd better not use NamedTuple at all for TypedDataFrame, and instead store of tuple of column names and a tuple of column types as two type parameters. I haven't investigated this yet, but he pointed at an example implementation similar to NamedTuple at https://github.com/bramtayl/Keys.jl/blob/master/src/Keys.jl.

NamedTuple would then only be used to pass a row in the public API (#1337).

[davidanthoff]

@nalimilan Did Jameson say why that would be a better option? Just curios. Or is that discussion somewhere in the open so that I can read up on it?

[ararslan]

Did Jameson say why that would be a better option?

Not really