JuliaLang/julia — pull request #6437 by timholy (2014-04-06 12:58:49+00:00)
Title: WIP: Add Cartesian product iteration. Fixes #1917

This is a WIP because `next` is not currently being inlined, and consequently this has a massive performance hit.
```
function sumloop{T}(A::AbstractArray{T,2}, iter)
s = zero(typeof(one(T)+one(T)))
for k = 1:iter
for i2 = 1:size(A,2)
for i1 = 1:size(A,1)
s += A[i1,i2]
end
end
end
s
end

function sumiter{T}(A::AbstractArray{T}, iter)
s = zero(typeof(one(T)+one(T)))
for k = 1:iter
for I = eachindex(A)
s += A[I...]
end
end
s
end

A = rand(500,500);

julia> @time sumloop(A, 100)
elapsed time: 0.048933864 seconds (64 bytes allocated)
1.2497917273335826e7

julia> @time sumiter(A, 100)
elapsed time: 4.077510313 seconds (2400008064 bytes allocated)
1.2497917273335826e7
```

```
julia> code_typed(sumiter, (typeof(A), Int))
1-element Array{Any,1}:
:($(Expr(:lambda, {:A,:iter}, {{:s,:#s39,:#s38,:#s37,:k,:#s36,:#s35,:#s34,:I,:_var0,:_var1,:_var2,:_var3,:_var4,:_var5,:_var6},{{:A,Array{Float64,2},0},{:iter,Int64,0},{:s,Float64,2},{:#s39,UnitRange{Int64},18},{:#s38,Int64,2},{:#s37,(Int64,Int64),18},{:k,Int64,18},{:#s36,SizeIterator{2},18},{:#s35,(Int64,Int64),2},{:#s34,((Int64,Int64),(Int64,Int64)),18},{:I,(Int64,Int64),18},{:_var0,Int64,18},{:_var1,Bool,18},{:_var2,(Int64,Int64),18},{:_var3,Float64,18},{:_var4,Bool,18},{:_var5,Int64,18},{:_var6,Int64,18}},{}}, :(begin # /tmp/iteration.jl, line 14:
s = 0.0 # line 15:
_var0 = top(getfield)(Intrinsics,:select_value)(top(sle_int)(1,iter::Int64)::Bool,iter::Int64,top(box)(Int64,top(sub_int)(1,1))::Int64)::Int64
#s39 = $(Expr(:new, UnitRange{Int64}, 1, :(_var0::Int64)))::UnitRange{Int64}
#s38 = top(getfield)(#s39::UnitRange{Int64},:start)::Int64
_var1 = #s38::Int64 === top(box)(Int64,top(add_int)(top(getfield)(#s39::UnitRange{Int64},:stop)::Int64,1))::Int64::Bool
unless top(box)(Bool,top(not_int)(_var1::Bool))::Bool goto 1
2:
_var5 = #s38::Int64
_var6 = top(box)(Int64,top(add_int)(#s38::Int64,1))::Int64
k = _var5::Int64
#s38 = _var6::Int64 # line 16:
_var2 = top(tuple)(arraysize(A::Array{Float64,2},1)::Int64,arraysize(A::Array{Float64,2},2)::Int64)::(Int64,Int64)
#s36 = $(Expr(:new, SizeIterator{2}, :(convert_tuple((Int64,Int64),_var2::(Int64,Int64),convert)::(Int64,Int64))))::SizeIterator{2}
#s35 = top(tuple)(1,1)::(Int64,Int64)
unless top(box)(Bool,top(not_int)(top(slt_int)(tupleref(top(getfield)(#s36::SizeIterator{2},:I)::(Int64,Int64),2)::Int64,tupleref(#s35::(Int64,Int64),2)::Int64)::Bool))::Bool goto 5
6:
#s34 = top(next)(#s36::SizeIterator{2},#s35::(Int64,Int64))::((Int64,Int64),(Int64,Int64))
I = top(tupleref)(#s34::((Int64,Int64),(Int64,Int64)),1)::(Int64,Int64)
#s35 = top(tupleref)(#s34::((Int64,Int64),(Int64,Int64)),2)::(Int64,Int64) # line 17:
_var3 = arrayref(A::Array{Float64,2},top(tupleref)(I::(Int64,Int64),1)::Int64,top(tupleref)(I::(Int64,Int64),2)::Int64)::Float64
s = top(box)(Float64,top(add_float)(s::Float64,_var3::Float64))::Float64
7:
unless top(box)(Bool,top(not_int)(top(box)(Bool,top(not_int)(top(slt_int)(tupleref(top(getfield)(#s36::SizeIterator{2},:I)::(Int64,Int64),2)::Int64,tupleref(#s35::(Int64,Int64),2)::Int64)::Bool))::Bool))::Bool goto 6
5:
4:
3:
_var4 = #s38::Int64 === top(box)(Int64,top(add_int)(top(getfield)(#s39::UnitRange{Int64},:stop)::Int64,1))::Int64::Bool
unless top(box)(Bool,top(not_int)(top(box)(Bool,top(not_int)(_var4::Bool))::Bool))::Bool goto 2
1:
0: # line 20:
return s::Float64
end::Float64))))
```

I'm aware that most of the performance hit comes from not eliding tuples in places where we ideally could. But once that problem gets solved, we'll have to face the next performance problem that stems more specifically from the lack of inlining. (Heck, we were worried about #5469, and compared to inlining the increment operation, moving the placement of `state += 1` is _peanuts_.) So we'll need to fix the inlining anyway, and it neatly sidesteps the (harder?) problem of tuple elision in this particular case.

Once the problems are fixed we can expect to be within a small factor of manually-coded (or Cartesian-coded) loops. See discussion in #3796.