Julia: Sum of large-ish tuple of arrays leads to StackOverFlowError

[dmeklund]

Reproducing

Calculating the sum of a sufficiently large NTuple containing numeric arrays leads to a StackOverFlowError. The breaking point seems to be somewhere around ~1,000 items in the tuple.

julia> datavals = ntuple(i->[3.0, 4.0], 1600);
julia> sum(datavals)
Internal error: encountered unexpected error in runtime:
StackOverflowError()
...

The stacktrace goes on for quite some time, with the repeating bit:

abstract_call_method at ./compiler/abstractinterpretation.jl:404                                                                 
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:101                                                             
abstract_call_known at ./compiler/abstractinterpretation.jl:873                                                                  
abstract_call at ./compiler/abstractinterpretation.jl:895                                                                        
abstract_apply at ./compiler/abstractinterpretation.jl:604                                                                       
abstract_call_known at ./compiler/abstractinterpretation.jl:673                                                                  
abstract_call at ./compiler/abstractinterpretation.jl:895                                                                        
abstract_call at ./compiler/abstractinterpretation.jl:880
abstract_eval at ./compiler/abstractinterpretation.jl:974
typeinf_local at ./compiler/abstractinterpretation.jl:1227
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1283
typeinf at ./compiler/typeinfer.jl:12

Version info

julia> versioninfo()
Julia Version 1.4.0
Commit b8e9a9ecc6 (2020-03-21 16:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: AMD Ryzen Threadripper 1950X 16-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, znver1)

[Micket]

https://github.com/JuliaLang/julia/blob/master/base/tuple.jl#L396
would need a specialization for very large tuples, just like isless, hash does:
https://github.com/JuliaLang/julia/blob/master/base/tuple.jl#L369
else, the recursion will blow the stack.

using Base: sum
const Any16{N} = Tuple{Any,Any,Any,Any,Any,Any,Any,Any,
                       Any,Any,Any,Any,Any,Any,Any,Any,Vararg{Any,N}}

function sum(x::Any16)
    s = x[1]
    for i in 2:length(x)
        s += x[i]
    end
    return s
end

datavals = ntuple(i->[3.0, 4.0], 1600)
sum(datavals)

2-element Array{Float64,1}:
 4800.0
 6400.0

[dmeklund]

Should using long tuples like this be considered an anti-pattern? The original code that triggered this investigation was actually attempting to do the equivalent of broadcast(+, datavals...) to handle both arrays and scalars, which wouldn't be resolved by this fix, at which point it feels like whack-a-mole trying to fix these issues. I've worked around it for now with an explicit loop for my use case.

[Micket]

I was going to suggest that as well; there shouldn't be a reason to have huge tuples in general, the existence of the tuple itself should eventually explode the stack (I think? I'm not sure how Julia handles them), but then I saw there already was such implementations for hash, isless, so why not also sum and prod.

Though, this isn't actually limited to tuples at all, the problem is occurs for everything that touches
+(A::Array, Bs::Array...) in Base.

The scalar version works fine, as it is specialized to a loop for large arrays;

scalars = [3.0 for i in 1:1600];
a = +(scalars...)

while

arrays = [[3.0, 4.0] for i in 1:1600];
b = +(arrays...)

explodes the stack.

So, this operation lands us here:
https://github.com/JuliaLang/julia/blob/12acd694e096b878ebca539b03c85828191556ad/base/arraymath.jl#L43
Though, digging into subleties and recursive definitions of broadcast* functions is a bit over my head.

[mcabbott]

It's my understanding that huge tuples are discouraged, they are for (human-readable) argument lists of functions, and dealing with dimensions of arrays (which fit in memory). Length 16 isn't a hard cutoff but is a guideline.

If datavals is something like an array (an object perfectly happy to have length 1000), then broadcast(+, datavals...) should probably be reduce(+, datavals) or something.

Nevertheless I don't see why more guardrails like sum(x::Any16) would hurt. Although I also don't understand the comments nearby in the linked file.

[dmeklund]

The reduce concept is what I'm looking for, but it doesn't work with + because of the need for broadcasting. For context, I have a set of structs that are being converted into anonymous functions, and then returning an anonymous function that applies some function (in this case +) to the results. However some of those anonymous functions return scalar values like 1.0 while others return an array of the same shape as the input, something like [1.0, 2.0]. So the original code which triggers the stack overflow looks like:

convertToFunction(expr::NAryAddition, var::Variable) = x -> broadcast(+, (convertToFunction(item, var)(x) for item in expr.elements)...)

The workaround I have now does an explicit loop instead:

convertToFunction(expr::NAryAddition, var::Variable) = begin
    x -> begin
        result = 0.0
        for item in expr.elements
            result = result .+ convertToFunction(item, var)(x)
        end
        result
    end
end

Though now that I'm writing it out I might be better off customizing my "scalar functions" to do the work of broadcasting themselves since they know the shape of the input and could simply return [1.0, 1.0] instead of 1.0.

It seems what I was really looking for is something like suggested here: https://discourse.julialang.org/t/is-there-something-like-broadcast-mapreduce/6076/14

The "sum of large tuple" was my attempt at an MWE for the stack overflow.

[mcabbott]

You can also reduce with a broadcasted function, like reduce((x,y) -> x .+ y, [1:2, 3:4, pi, ones(2)]) == .+([1:2, 3:4, pi, ones(2)]...).

[JeffBezanson]

The biggest problem here is splatting large things. Nothing whose size is proportional to the amount of data you have should be splatted, and we should follow that internally as well (which we sometimes have to guess, but in the case of sum it's pretty clear). Having large tuples isn't a problem in itself, but can put you in greater danger of stack overflows or excessive code unrolling.