Multiplication of `ZZMatrix` and `zzModMatrix`, addition, promotion etc are all super-slow because `change_base_ring` is

[fingolfin]

(The following is a result from analyzing oscar-system/Oscar.jl#5550)

Consider this:

julia> R = quo(ZZ,4)[1]
Integers modulo 4

julia> MZ = matrix(ZZ, rand(Int8, (20, 20)));

julia> MR = matrix(R, rand(Int8, (20, 20)));

julia> @b MZ * MR
11.688 μs (409 allocs: 17.031 KiB)

julia> @b matrix(R,MZ) * MR
4.750 μs (9 allocs: 10.781 KiB)

So manually converting the matrix yielded a speed up by a factor 2.4, and a substantial reduction of allocations.

This is because change_base_ring is inefficient:

julia> @b change_base_ring(R, MZ)
8.167 μs (404 allocs: 9.891 KiB)

julia> @b matrix(R, MZ)
1.242 μs (4 allocs: 3.641 KiB)

julia> @b map_entries(R, MZ)
1.232 μs (4 allocs: 3.641 KiB)

Indeed, the change_base_ring method being used here is the generic one from AA:

function change_base_ring(R::NCRing, M::MatrixElem{T}) where T <: NCRingElement
   N = _change_base_ring(R, M)
   for i = 1:nrows(M), j = 1:ncols(M)
      N[i,j] = R(M[i,j])
   end
   return N
end

while for matrix the generic method delegates to map_entries; and for that we have an efficient method.

Honestly I find it bewildering that we have so many ways to do the same thing. Of course map_entries is in principle more general (the first argument can be any function, not just a parent ring)...

But in the end it is bad if matrix type implementors must remember to implement multiple of these functions. I am not sure we document anywhere which of these are supposed to delegate to which...

I guess map_entries could get a special generic method in AA that handles the case where the first argument is an NCRing, and in that case delegates to change_base_ring.

Then in Nemo, it would suffice to implement change_base_ring (instead of map_entries).

But I guess the short-term solution is to add custom change_base_ring methods here, in addition to the map_entries methods.

[thofma]

I guess map_entries could get a special generic method in AA that handles the case where the first argument is an NCRing, and in that case delegates to change_base_ring.

If this works, I would prefer this solution.

[thofma]

The same problem pops up for the polynomials while working in #2158. For polynomials we also have change_base_ring and map_coefficients and there is some redirection. Apparently both end up calling
_map, so one just has to overload _map like

function AbstractAlgebra._map(R::fpField, g::QQPolyRingElem, parent::fpPolyRing)
  @assert R === base_ring(parent)
  return fmpq_poly_to_gfp_poly_raw!(parent(), g)
end

At the moment these are implementation details, but one could make _map or map_internal(...) be part of the interface of things that can be overloaded optionally.

For the matrices I would probably either add something similar (a map_internal that should be overloaded) or just make the implementors add special methods for map_entries.