search

willow-ahrens / Finch.jl

Sparse tensors in Julia and more! Datastructure-driven array programing language.
http://willowahrens.io/Finch.jl/
MIT License
157 stars 15 forks source link

Error in eager mode when adding two Tensors #481

Closed mtsokol closed 5 months ago

mtsokol commented 5 months ago

Hi @willow-ahrens!

While trying to run some benchmarks I came across such issue:

Code for bug repro:

using Finch

r = fsprand(1, 10, 10, 0.01)
r_tns = Tensor(Dense(Dense(Dense(Element(0.0)))), r)
r_tns + r_tns  # fails

Error log:

ERROR: RewriteTools.RuleRewriteError(query(~a, ~b) => if b.kind !== reformat && b.kind !== table
        #= /Users/mateusz/JuliaProjects/Finch.jl/src/interface/compute.jl:205 =#
        query(a, reformat(immediate(suitable_storage(b, bindings)), b))
    end, query(alias(A2), mapjoin(immediate(+), reorder(relabel(alias(A1), field(i3), field(i7), field(i8)), field(i7), field(i8)), reorder(relabel(alias(A0), field(i0), field(i7), field(i8)), field(i7), field(i8)))))
Stacktrace:
  [1] (::RewriteTools.Rule{…})(term::Finch.FinchLogic.LogicNode)
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/rule.jl:151
  [2] (::RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{…}})(x::Finch.FinchLogic.LogicNode)
    @ RewriteTools.Rewriters ~/.julia/packages/RewriteTools/ncmWH/src/rewriters.jl:122
  [3] iterate
    @ ./generator.jl:47 [inlined]
  [4] collect_to!(dest::Vector{Nothing}, itr::Base.Generator{Vector{…}, RewriteTools.Rewriters.Postwalk{…}}, offs::Int64, st::Int64)
    @ Base ./array.jl:892
  [5] collect_to_with_first!(dest::Vector{…}, v1::Nothing, itr::Base.Generator{…}, st::Int64)
    @ Base ./array.jl:870
  [6] _collect(c::Vector{…}, itr::Base.Generator{…}, ::Base.EltypeUnknown, isz::Base.HasShape{…})
    @ Base ./array.jl:864
  [7] collect_similar(cont::Vector{Finch.FinchLogic.LogicNode}, itr::Base.Generator{Vector{…}, RewriteTools.Rewriters.Postwalk{…}})
    @ Base ./array.jl:763
  [8] map(f::RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{…}}, A::Vector{Finch.FinchLogic.LogicNode})
    @ Base ./abstractarray.jl:3285
  [9] (::RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{…}})(x::Finch.FinchLogic.LogicNode)
    @ RewriteTools.Rewriters ~/.julia/packages/RewriteTools/ncmWH/src/rewriters.jl:120
 [10] (::RewriteTools.Rewriters.Rewrite)(x::Finch.FinchLogic.LogicNode)
    @ RewriteTools.Rewriters ~/.julia/packages/RewriteTools/ncmWH/src/rewriters.jl:38
 [11] compute_impl(args::Tuple{Finch.LazyTensor{Any, 3}}, ctx::Finch.DefaultOptimizer)
    @ Finch ~/JuliaProjects/Finch.jl/src/interface/compute.jl:392
 [12] compute(arg::Finch.LazyTensor{Any, 3}; ctx::Finch.DefaultOptimizer)
    @ Finch ~/JuliaProjects/Finch.jl/src/interface/compute.jl:368
 [13] copy
    @ ~/JuliaProjects/Finch.jl/src/interface/eager.jl:30 [inlined]
 [14] materialize
    @ ~/JuliaProjects/Finch.jl/src/interface/eager.jl:22 [inlined]
 [15] map
    @ ~/JuliaProjects/Finch.jl/src/interface/eager.jl:44 [inlined]
 [16] +(::Tensor{DenseLevel{Int64, DenseLevel{Int64, DenseLevel{…}}}}, ::Tensor{DenseLevel{Int64, DenseLevel{Int64, DenseLevel{…}}}})
    @ Finch ~/JuliaProjects/Finch.jl/src/interface/eager.jl:76
 [17] top-level scope
    @ REPL[4]:1

caused by: MethodError: no method matching isless(::Int64, ::Nothing)

Closest candidates are:
  isless(::Missing, ::Any)
   @ Base missing.jl:87
  isless(::Any, ::Missing)
   @ Base missing.jl:88
  isless(::Int64, ::Limit)
   @ Finch ~/JuliaProjects/Finch.jl/src/util/limits.jl:188
  ...
willow-ahrens commented 5 months ago

I forget what error this is, but we see it a lot in Finch and I'd like to make it more descriptive

willow-ahrens commented 5 months ago

When you see a "RewriteError", it just means that an error occurred during rewriting. Usually, another error get's printed after that says what actually went wrong. The second stacktrace in this case is:

Stacktrace:
  [1] lt(o::Base.Order.ForwardOrdering, a::Int64, b::Nothing)
    @ Base.Order ./ordering.jl:117
  [2] lt(o::Base.Order.By{Finch.var"#1822#1825"{Finch.FinchLogic.LogicNode}, Base.Order.ForwardOrdering}, a::Finch.FinchLogic.LogicNode, b::Finch.FinchLogic.LogicNode)
    @ Base.Order ./ordering.jl:119
  [3] lt
    @ ./ordering.jl:125 [inlined]
  [4] _sort!(v::Vector{Int64}, ::Base.Sort.InsertionSortAlg, o::Base.Order.Perm{Base.Order.By{Finch.var"#1822#1825"{…}, Base.Order.ForwardOrdering}, SubArray{Finch.FinchLogic.LogicNode, 1, Vector{…}, Tuple{…}, true}}, kw::@NamedTuple{scratch::Nothing, lo::Int64, hi::Int64})
    @ Base.Sort ./sort.jl:785
  [5] _sort!(v::Vector{Int64}, a::Base.Sort.Small{10, Base.Sort.InsertionSortAlg, Base.Sort.IEEEFloatOptimization{…}}, o::Base.Order.Perm{Base.Order.By{…}, SubArray{…}}, kw::@NamedTuple{scratch::Nothing, lo::Int64, hi::Int64})
    @ Base.Sort ./sort.jl:750
  [6] _sort!
    @ ./sort.jl:697 [inlined]
  [7] _sort!
    @ ./sort.jl:636 [inlined]
  [8] #sort!#28
    @ ./sort.jl:1463 [inlined]
  [9] sort!
    @ ./sort.jl:1456 [inlined]
 [10] #_sortperm#33
    @ ./sort.jl:1664 [inlined]
 [11] _sortperm
    @ ./sort.jl:1651 [inlined]
 [12] #sortperm#32
    @ ./sort.jl:1648 [inlined]
 [13] (::Finch.SuitableRep)(ex::Finch.FinchLogic.LogicNode)
    @ Finch ~/Projects/Finch.jl/src/interface/compute.jl:233
 [14] iterate
    @ ./generator.jl:47 [inlined]
 [15] _collect(c::SubArray{Finch.FinchLogic.LogicNode, 1, Vector{Finch.FinchLogic.LogicNode}, Tuple{UnitRange{…}}, true}, itr::Base.Generator{SubArray{Finch.FinchLogic.LogicNode, 1, Vector{…}, Tuple{…}, true}, Finch.SuitableRep}, ::Base.EltypeUnknown, isz::Base.HasShape{1})
    @ Base ./array.jl:854
 [16] collect_similar
    @ ./array.jl:763 [inlined]
 [17] map(f::Finch.SuitableRep, A::SubArray{Finch.FinchLogic.LogicNode, 1, Vector{Finch.FinchLogic.LogicNode}, Tuple{UnitRange{Int64}}, true})
    @ Base ./abstractarray.jl:3285
 [18] (::Finch.SuitableRep)(ex::Finch.FinchLogic.LogicNode)
    @ Finch ~/Projects/Finch.jl/src/interface/compute.jl:224
 [19] suitable_storage(ex::Finch.FinchLogic.LogicNode, bindings::Dict{Finch.FinchLogic.LogicNode, Finch.FinchLogic.LogicNode})
    @ Finch ~/Projects/Finch.jl/src/interface/compute.jl:213
 [20] macro expansion
    @ ~/Projects/Finch.jl/src/interface/compute.jl:205 [inlined]
 [21] (::Finch.var"#1819#1820"{Dict{Finch.FinchLogic.LogicNode, Finch.FinchLogic.LogicNode}})(__MATCHES__::Base.ImmutableDict{Symbol, Any})
    @ Finch ~/.julia/packages/RewriteTools/ncmWH/src/rule.jl:312
 [22] success
    @ ~/.julia/packages/RewriteTools/ncmWH/src/rule.jl:148 [inlined]
 [23] (::RewriteTools.var"#loop#40"{RewriteTools.var"#success#30"{…}})(term::RewriteTools.LL{Vector{…}}, bindings′::Base.ImmutableDict{Symbol, Any}, matchers′::RewriteTools.LL{Tuple{…}})
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:96
 [24] (::RewriteTools.var"#38#41"{RewriteTools.LL{Vector{…}}, RewriteTools.LL{Tuple{…}}})(b::Base.ImmutableDict{Symbol, Any}, n::Int64)
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:101
 [25] (::RewriteTools.var"#slot_matcher#36"{RewriteTools.Slot{…}})(next::RewriteTools.var"#38#41"{RewriteTools.LL{…}, RewriteTools.LL{…}}, data::RewriteTools.LL{Vector{…}}, bindings::Base.ImmutableDict{Symbol, Any})
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:0
 [26] (::RewriteTools.var"#loop#40"{RewriteTools.var"#success#30"{…}})(term::RewriteTools.LL{Vector{…}}, bindings′::Base.ImmutableDict{Symbol, Any}, matchers′::RewriteTools.LL{Tuple{…}})
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:100
--- the last 3 lines are repeated 1 more time ---
 [30] (::RewriteTools.var"#38#41"{Finch.FinchLogic.LogicNode, Tuple{RewriteTools.var"#literal_matcher#35"{…}, RewriteTools.var"#slot_matcher#36"{…}, RewriteTools.var"#slot_matcher#36"{…}}})(b::Base.ImmutableDict{Symbol, Any}, n::Int64)
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:101
 [31] literal_matcher
    @ ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:10 [inlined]
 [32] (::RewriteTools.var"#loop#40"{…})(term::Finch.FinchLogic.LogicNode, bindings′::Base.ImmutableDict{…}, matchers′::Tuple{…})
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:100
 [33] (::RewriteTools.var"#term_matcher#39"{Tuple{…}})(success::RewriteTools.var"#success#30"{Finch.var"#1819#1820"{…}}, data::Tuple{Finch.FinchLogic.LogicNode}, bindings::Base.ImmutableDict{Symbol, Any})
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/matchers.jl:105
 [34] (::RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{Tuple{…}}, Finch.var"#1819#1820"{Dict{…}}})(term::Finch.FinchLogic.LogicNode)
    @ RewriteTools ~/.julia/packages/RewriteTools/ncmWH/src/rule.jl:149
 [35] (::RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{Tuple{…}}, Finch.var"#1819#1820"{Dict{…}}}})(x::Finch.FinchLogic.LogicNode)
    @ RewriteTools.Rewriters ~/.julia/packages/RewriteTools/ncmWH/src/rewriters.jl:122
 [36] iterate
    @ ./generator.jl:47 [inlined]
 [37] collect_to!(dest::Vector{Nothing}, itr::Base.Generator{Vector{Finch.FinchLogic.LogicNode}, RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{Tuple{…}}, Finch.var"#1819#1820"{Dict{…}}}}}, offs::Int64, st::Int64)
    @ Base ./array.jl:892
 [38] collect_to_with_first!(dest::Vector{Nothing}, v1::Nothing, itr::Base.Generator{Vector{Finch.FinchLogic.LogicNode}, RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{…}, Finch.var"#1819#1820"{…}}}}, st::Int64)
    @ Base ./array.jl:870
 [39] _collect(c::Vector{Finch.FinchLogic.LogicNode}, itr::Base.Generator{Vector{Finch.FinchLogic.LogicNode}, RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{…}}}, ::Base.EltypeUnknown, isz::Base.HasShape{1})
    @ Base ./array.jl:864
 [40] collect_similar(cont::Vector{Finch.FinchLogic.LogicNode}, itr::Base.Generator{Vector{Finch.FinchLogic.LogicNode}, RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{Tuple{…}}, Finch.var"#1819#1820"{Dict{…}}}}})
    @ Base ./array.jl:763
 [41] map(f::RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{Tuple{…}}, Finch.var"#1819#1820"{Dict{…}}}}, A::Vector{Finch.FinchLogic.LogicNode})
    @ Base ./abstractarray.jl:3285
 [42] (::RewriteTools.Rewriters.Postwalk{RewriteTools.Rule{RewriteTools.Term, RewriteTools.var"#term_matcher#39"{Tuple{…}}, Finch.var"#1819#1820"{Dict{…}}}})(x::Finch.FinchLogic.LogicNode)
    @ RewriteTools.Rewriters ~/.julia/packages/RewriteTools/ncmWH/src/rewriters.jl:120
 [43] (::RewriteTools.Rewriters.Rewrite)(x::Finch.FinchLogic.LogicNode)
    @ RewriteTools.Rewriters ~/.julia/packages/RewriteTools/ncmWH/src/rewriters.jl:38
 [44] compute_impl(args::Tuple{Finch.LazyTensor{Any, 3}}, ctx::Finch.DefaultOptimizer)
    @ Finch ~/Projects/Finch.jl/src/interface/compute.jl:393
 [45] compute(args::Tuple{Finch.LazyTensor{Any, 3}}; ctx::Finch.DefaultOptimizer)
    @ Finch ~/Projects/Finch.jl/src/interface/compute.jl:369
 [46] compute(arg::Finch.LazyTensor{Any, 3}; kwargs::@Kwargs{})
    @ Finch ~/Projects/Finch.jl/src/interface/compute.jl:368
 [47] compute
    @ ~/Projects/Finch.jl/src/interface/compute.jl:368 [inlined]
 [48] copy
    @ ~/Projects/Finch.jl/src/interface/eager.jl:30 [inlined]
 [49] materialize
    @ ~/Projects/Finch.jl/src/interface/eager.jl:22 [inlined]
 [50] map
    @ ~/Projects/Finch.jl/src/interface/eager.jl:44 [inlined]
 [51] +(::Tensor{DenseLevel{Int64, DenseLevel{Int64, DenseLevel{Int64, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}}}, ::Tensor{DenseLevel{Int64, DenseLevel{Int64, DenseLevel{Int64, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}}})
    @ Finch ~/Projects/Finch.jl/src/interface/eager.jl:76
Some type information was truncated. Use `show(err)` to see complete types.
willow-ahrens commented 5 months ago

In this case, it looks like we were trying to sort indices based on where they occur in a reorder statement, but one of them did not occur in the statement. Usually this means that we dropped some dimensions, but we aren't supposed to drop dims here.

mtsokol commented 5 months ago

The dims are (1, 10, 10). I guess singleton 1 got dropped somewhere?

willow-ahrens commented 5 months ago

Yes, I don't think we're really supposed to drop here

willow-ahrens commented 5 months ago

I think I have a fix up and running