Cannot collect Q factor of QR factorization

[cafaxo]

On current master, I get

julia> collect(qr(randn(2,2)).Q)
ERROR: MethodError: no method matching length(::LinearAlgebra.QRCompactWYQ{Float64, Matrix{Float64}, Matrix{Float64}})

Closest candidates are:
  length(::Union{Base.KeySet, Base.ValueIterator})
   @ Base abstractdict.jl:58
  length(::Union{Adjoint{T, S}, Transpose{T, S}} where {T, S})
   @ LinearAlgebra ~/julia/usr/share/julia/stdlib/v1.10/LinearAlgebra/src/adjtrans.jl:295
  length(::Base.Iterators.Drop)
   @ Base iterators.jl:807
  ...

Stacktrace:
 [1] _similar_shape(itr::LinearAlgebra.QRCompactWYQ{Float64, Matrix{Float64}, Matrix{Float64}}, ::Base.HasLength)
   @ Base ./array.jl:703
 [2] _collect(cont::UnitRange{Int64}, itr::LinearAlgebra.QRCompactWYQ{Float64, Matrix{Float64}, Matrix{Float64}}, ::Base.HasEltype, isz::Base.HasLength)
   @ Base ./array.jl:758
 [3] collect(itr::LinearAlgebra.QRCompactWYQ{Float64, Matrix{Float64}, Matrix{Float64}})
   @ Base ./array.jl:752
 [4] top-level scope
   @ REPL[23]:1

This worked in 1.8.

[barucden]

Could it be related to the changes in JuliaLang/julia#46196?

[gbaraldi]

@dkarrasch

[dkarrasch]

Could it be related to the changes in JuliaLang/julia#46196?

Yes it is. And it is on purpose, because collecting a Q is very slow, because you need to compute every index one by one, which allocates temporary memory (for each index!) and performs an algorithm (for each index!). Just replace collect by Matrix and enjoy the speed-up.

[gbaraldi]

Can't it be specialized, also to not do a separate ping, it seems this also broke the printing. #1007

[dkarrasch]

The docstring says:

collect(collection)

  Return an Array of all items in a collection or iterator. ....

The issue was/is: AbstractQs are not naturally "iterable" and are not naturally a collection. They have never been in a readily accessible format. Iterating them has always included performing an entire program instead of look-up. AbstractQs are not arrays! Of course, we could overload collect for them and make it call Matrix for legacy reasons, but that feels like cheating.

[dkarrasch]

Can this be closed?

[cafaxo]

What is the policy on breaking changes? My understanding is that a change that breaks existing code (even if that code is bad) cannot happen before Julia 2.0.

[dkarrasch]

Ok, turns out that collect was not too bad before the AbstractQ change: it was using copyto! to fill an undefed Matrix with the Q, and we had a specialized copyto! for these purposes falling back to lmul!. That was introduced in JuliaLang/julia#39533 in v1.7. Before that, we had

              _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.7 (2022-07-19)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> using BenchmarkTools

julia> using LinearAlgebra

julia> F = qr(randn(3,3));

julia> @btime collect($(F.Q));
  5.028 μs (28 allocations: 3.11 KiB)

julia> @btime Matrix($(F.Q));
  597.628 ns (3 allocations: 480 bytes)

[Seelengrab]

Triage has some thoughts:

• The way this was done was a bit breaking - seems like there were some PkgEval results that weren't fixed (those 5 failures are expecting a length fallback).
• The unfortunately most straightforward way of fixing this is to revert the PR - to be clear, triage thinks this can still work, but needs to be done very carefully not to break things (perhaps by implementing the rest of the AbstractArrays interface without actually subtyping AbstractArray. This may still break some workflows that expected this to be <: AbstractArray, but judging from PkgEval noone was doing that, so we should be good).
• The "implement collect and length" approach may also work standalone, but that needs to be discussed in a PR.

[dkarrasch]

Regarding the 5 failures, 3 of them have been fixed but haven't released the fix yet, or hadn't released it by the time of the nanosoldier run. I couldn't make sense of the Pajarito.jl and the DataAssimilationBenchmarks.jl fails, but I'm happy to contribute to whatever it takes (though in more recent pkgeval runs they didn't show up as failing). So the registered package ecosystem (at least the part that is covered by nanosoldier) was essentially completely fixed by the time of the merge. The length fallback popped up only due to collecting Q's, whose use I eliminated in the ecosystem, but can bring back in JuliaLang/julia#49714, so we can discuss over there. I don't think length(Q) is used elsewhere. So what would be missing then? Elementwise iteration and broadcasting, anything else?