printing ApplyArray(*, A...) has exponential cost

[putianyi889]

julia> @time show(ApplyArray(*, [ones(10,10) for k in 1:6]...))
[100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 
100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0; 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0 100000.0]  1.060463 seconds (1.30 M allocations: 38.767 MiB, 1.97% gc time)

julia> @time show(ApplyArray(*, [ones(10,10) for k in 1:7]...))
[1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6; 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6 1.0e6]  8.158341 seconds (12.56 M allocations: 353.813 MiB, 1.54% gc time)  

julia> @time show(ApplyArray(*, [ones(10,10) for k in 1:8]...))
[1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7] 76.525859 seconds (125.37 M allocations: 3.429 GiB, 1.37% gc time)

However, getindex is fast

julia> @time show(ApplyArray(*, [ones(10,10) for k in 1:8]...)[:,:])
[1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7; 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7 1.0e7]  0.815893 seconds (569.25 k allocations: 37.234 MiB, 3.19% gc time)

[putianyi889]

potentially related #255

[putianyi889]

The cost is cut by 90% after #261, however the exponential growth is still not solved.

[dlfivefifty]

Note if we want to support many operators we should add support for vector arguments eg ApplyArray(*, [A1,…,An])

but removing the need for ApplyStyle seems like a first step

[putianyi889]

How do you resolve the ambiguity of ApplyArray(*, [A1,…,An])? since the vector could potentially be the only argument.

Maybe add a new type of ReduceArray which mimics reduce?

[dlfivefifty]

That probably won’t be the actual constructor. Note args is usually a Tuple but I think will accept a Vector already.

Reduce doesn’t return an array does it?

[putianyi889]

julia> reduce(+, [ones(5,5) for k in 1:10])
5×5 Matrix{Float64}:
 10.0  10.0  10.0  10.0  10.0
 10.0  10.0  10.0  10.0  10.0
 10.0  10.0  10.0  10.0  10.0
 10.0  10.0  10.0  10.0  10.0
 10.0  10.0  10.0  10.0  10.0

[dlfivefifty]

In that case you want to support ApplyArray(reduce, +, A)

[putianyi889]

the same argument could also apply to broadcast, considering ApplyArray(broadcast, +, A) instead of BroadcastArray(+, A)