Ridiculous idea: types from the future

Internals & Design
1

I’ve been thinking about a pattern that often comes up when I write Julia code. I frequently find myself creating a vector and then appending elements to that vector within a loop. But that raises the question of how to declare the element type of the vector. Let’s be concrete. Suppose I have a function f(i) and I want to call it multiple times and collect the results. I can do the following:

results = []
for i in 1:10
  push!(results, f(i))
end

but this makes results a Vector{Any}, which is sub-optimal. If the return type of f(i) is obvious, then I can use it in my declaration:

results = T[]
for...
end

but often times that return type is not obvious, or is just heavily parameterized and tedious to type out. If I still want a concretely-typed results vector, then I can try to manually invoke Core.inference, but that’s not exported and can be tedious, since it requires deriving the types of the inputs to f() myself.

There’s another option, which is to use the comprehension syntax:

[f(i) for i in 1:10]

which is perfect for loops with short bodies but less convenient if the loop body is complex.

What I actually want (I think), is to be able to do something like:

results = <future T>[]
for i in 1:10 
  push!(results, f(i)::<future T>)
end

where <future T> is a type that has to be figured out based on the type inference of f(i) later in the function (thus, in the “future” (not in the world-age sense, though)).

So, my question is: is this possible? Clearly if the inferred type of f(i) depends on the type of results, then the answer is no. But if the type of f(i) is independent of results, then it should at least be computable. In a sense, this is just a matter of trying to save the user from having to manually invoke inference.

Anyway, this is all just fairly wild speculation, but I’m curious if others have found themselves wanting something similar or if there’s a way to get what I want without changing Julia itself.

5 Likes
2

You can always use map with a do block:

results = map(1:10) do i
   ....
end

The map function already implements the type-narrowing deduction you want. It uses Julia’s type inference as an optimization, but works even when type-inference fails.

17 Likes
3

What if you need to build two result arrays in the loop?

4

If there’s only one unknown type, you could

other_vector = Vector{KnownType}
results = map(1:10) do i
  other_vector[i] = f_other()
  f_res()
end

I’ve thought before that it would be cool if functions that returned tuples could somehow be broadcast or mapped into two output vectors, instead of just a vector of tuples.
I don’t know any way of doing that.

It’s also a slow function:

julia> @benchmark Core.Inference.return_type(exp, (Float64,))
BenchmarkTools.Trial: 
  memory estimate:  560 bytes
  allocs estimate:  12
  --------------
  minimum time:     6.315 μs (0.00% GC)
  median time:      6.576 μs (0.00% GC)
  mean time:        6.805 μs (2.00% GC)
  maximum time:     1.395 ms (97.65% GC)
  --------------
  samples:          10000
  evals/sample:     5

Hundreds of times slower than actually just evaluating this particular function:

julia> @benchmark exp(4.3)
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     18.644 ns (0.00% GC)
  median time:      18.645 ns (0.00% GC)
  mean time:        18.836 ns (0.00% GC)
  maximum time:     41.621 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     997

So I think I would evaluate the function once, and then dispatch on that before proceeding and iterating over the remainder of the iterable.
Another option similar to what rdelts does in the first place:

results = [f(1)]
for i in 2:10
  push!(results, f(i))
end
5

If the result type of f varies, it is no option to determine the element type of the result array in advance.
I propose, to use an array with most general type as a buffer, and convert to an array of the most specific element type according to the actual sequence of results afterwards.

julia> results = []
0-element Array{Any,1}
julia> for i in 1:10
         push!(results, rand() < 0.5 ? 42 : 1.0)
       end
julia> collect(promote(results...))
10-element Array{Float64,1}:
  1.0
 42.0
  1.0
...

whereas

julia> map(x -> rand() < 0.5 ? 42 : 1.0, 1:10)
10-element Array{Real,1}:
  1.0
 42  
  1.0
 42  
...
6

Another approach with an own ArrayBuffer type, which accumulates the promoted result type:

julia> mutable struct ArrayBuffer{T}
           a::Array{T}
           et::Type
           ArrayBuffer{T}() where T = new(T[], Union{})
       end

julia> function Base.push!(buf::ArrayBuffer, x)
           buf.et = promote_type(buf.et, typeof(x))
           push!(buf.a, x)
        end

julia> get_result(buf::ArrayBuffer) = (buf.et).(buf.a)
get_result (generic function with 1 method)

julia> buf = ArrayBuffer{Any}()
ArrayBuffer{Any}(Any[], Void)
julia> for i in 1:10
         push!(buf, rand() < 0.5 ? 42 : 1.0)
       end
julia> buf
ArrayBuffer{Any}(Any[1.0, 1.0, 42, 1.0, 42, 1.0, 1.0, 1.0, 42, 42], Float64)

julia> get_result(buf)
10-element Array{Float64,1}:
  1.0
  1.0
 42.
...
1 Like
7

Thanks for the replies everyone! In particular, the map() suggestion from @stevengj solves my particular case quite nicely (although for more complex looping operations it might not work as well).

For comparison, I’ve implemented a few of the options:

julia> using Base.Test

julia> f(i) = i * 5.0
f (generic function with 1 method)

julia> function f_comprehension()
           [f(i) for i in 1:10]
       end
f_comprehension (generic function with 1 method)

julia> function f_map()
           map(1:10) do i
               f(i)
           end
       end
f_map (generic function with 1 method)

julia> function f_inference()
           T = Core.Inference.return_type(f, (Int,))
           result = T[]
           for i in 1:10
               push!(result, f(i))
           end
           result
       end
f_inference (generic function with 1 method)

julia> mutable struct ArrayBuffer{T}
          a::Array{T}
          et::Type
          ArrayBuffer{T}() where T = new(T[], Union{})
       end

julia> function Base.push!(buf::ArrayBuffer, x)
          buf.et = promote_type(buf.et, typeof(x))
          push!(buf.a, x)
       end

julia> get_result(buf::ArrayBuffer) = (buf.et).(buf.a)
get_result (generic function with 1 method)

julia> function f_arraybuf()
           buf = ArrayBuffer{Any}()
           for i in 1:10
               push!(buf, f(i))
           end
           get_result(buf)
       end
f_arraybuf (generic function with 1 method)

julia> @assert f_comprehension() == f_map() == f_inference() == f_arraybuf()

julia> @inferred f_comprehension();

julia> @inferred f_map();

julia> @inferred f_inference();
ERROR: return type Array{Float64,1} does not match inferred return type Array{_,1} where _
Stacktrace:
 [1] error(::String) at ./error.jl:21

julia> @inferred f_arraybuf()
ERROR: return type Array{Float64,1} does not match inferred return type Any
Stacktrace:
 [1] error(::String) at ./error.jl:21

julia> using BenchmarkTools

julia> @btime f_comprehension();
  43.632 ns (1 allocation: 160 bytes)

julia> @btime f_map();
  46.965 ns (1 allocation: 160 bytes)

julia> @btime f_inference();
  6.660 μs (25 allocations: 1.02 KiB)

julia> @btime f_arraybuf();
  99.434 μs (67 allocations: 2.59 KiB)

So the map and comprehension versions are inferable and fast, while the versions that rely on run-time promotion or inference are not (not totally surprising, but I actually hoped that Core.Inference.return_type() could have been run at compile-time more like a Base.@pure function). But I think all of these are useful suggestions for particular cases (in particular, the ArrayBuffer example could be very useful if the resulting array is passed to a function rather than being returned).

8

The implementation of map is actually the opposite of this, if I remember correctly. Even if inference returns Any, it optimizes for the common case where all the elements are actually the same type by allocating the array based on the type of the first element. As it goes along, it reallocates and copies the array to a wider type if it encounters an element of a different type.

9

I thought, the missing type-stability of f was the problem. I am not surprised to see strong performance advantages for the built-in comprehension and map solutions.

10

The “built-in” map function is implemented purely in Julia. There is nothing to stop user code from attaining the same performance, except for the fact that the implementation is admittedly rather subtle.

(map actually calls collect on a generator, and the core of the implementation is in Base.collect_to!.)

11

I see the difference! With “built” in I meant, optimized code by experienced implementers.
I also see, why map returns an Array{Real,1}, while get_result returns a more specific Array{Float64} in my example.

Would it be an improvement of collect_to! to use promote_type instead of typejoin?

12

The last parameter should be Tuple{Int}. At runtime, it sometimes (sort of accidentally) accepts a tuple, but it only infers the latter syntax. This isn’t usually recommended, since map is a better API, and currently the preferred way to interact with Core.Inference.return_type (when necessary) is via promote_op (Update of Jameson's "common parametric method patterns" by mauro3 · Pull Request #23245 · JuliaLang/julia · GitHub)

1 Like
13

Thanks! Good to know.

For completeness, here are the fixed versions of my earlier inference example:

julia> function f_inference_2()
           T = Core.Inference.return_type(f, Tuple{Int})
           result = T[]
           for i in 1:10
               push!(result, f(i))
           end
           result
       end

julia> @inferred(f_inference_2());

julia> @btime f_inference_2();
  215.081 ns (4 allocations: 352 bytes)

julia> function f_promote_op()
           T = Base.promote_op(f, Int)
           result = T[]
           for i in 1:10
               push!(result, f(i))
           end
           result
       end

julia> @inferred(f_promote_op());

julia> @btime f_promote_op();
  171.147 ns (4 allocations: 352 bytes)
14

It seems that you could wrap material in a generated function to end up with a function customized for whatever type comes along during execution. In fact, now that I’ve gotten into generated functions, I have to say that that ability is one of my favorite parts of Julia. Would this not work for your case?

16

I am missing the feature as well. In my use case, it is a simple assembly of a covariance matrix with given floating point precision:

function pairwise(cov, X)
  n = size(X, 2)
  C = Array{???}(n, n)
  for j=1:n, i=1:n # naive loop for this example
    C[i,j] = cov(X[:,i], X[:,j])
  end
  C
end

What I will do is define a function result_type(cov, X) to infer the type, similar to what is done in the Distances.jl package. It would be great though if we could just type something like Array{?}(n, n) before the loop and have it figured out automatically. C++11 introduced similar functionality under the name of auto and decltype: Placeholder type specifiers (since C++11) - cppreference.com

17

As a note, sometimes (often) you can use a comprehension to achieve the same effect. Although if the iteration body is too big it might not be so pretty. In the given example it might work well though.

1 Like
18

Comprehensions work nicely when the shape of the array is “full”. In the case of covariance, I would like to exploit the symmetry and loop only in entries that aren’t redundant.