Simplify checked_dims, improving its effects, theoretical runtime, and practical runtime for >=3 dims

[LilithHafner]

Test for no allocations at dimensionality up to 15 (above that the use of tuples allocates)
Allow malloc(Nothing, very_big_dims...)

[nsajko]

FWIW recursion has its own drawbacks, such as the compiler refusing to propagate constants through it, at least on current versions. Constant folding works fine, though, as long as a call is known to terminate, of course.

[LilithHafner]

main

julia> c_d(x...) = PtrArrays.checked_dims(x...; message="c_d")
c_d (generic function with 1 method)

julia> Base.infer_effects(c_d, NTuple{2, Int})
(+c,+e,!n,+t,!s,!m,+u,+o,+r)

julia> Base.infer_effects(c_d, NTuple{3, Int})
(+c,+e,!n,+t,!s,!m,+u,+o,+r)

julia> Base.infer_effects(c_d, NTuple{4, Int})
(+c,!e,!n,!t,!s,!m,!u,!o,!r)

julia> @b free(malloc(Int, 2, 2, 2))
381.640 ns (6 allocs: 160 bytes)

pr

julia> c_d(x...) = PtrArrays.checked_dims(x...; message="c_d")
c_d (generic function with 1 method)

julia> Base.infer_effects(c_d, NTuple{2, Int})
(+c,+e,!n,+t,!s,!m,+u,+o,+r)

julia> Base.infer_effects(c_d, NTuple{3, Int})
(+c,+e,!n,+t,!s,!m,+u,+o,+r)

julia> Base.infer_effects(c_d, NTuple{4, Int})
(+c,+e,!n,+t,!s,!m,+u,+o,+r)

julia> @b free(malloc(Int, 2, 2, 2))
7.971 ns

shell> git diff --stat main src
 src/PtrArrays.jl | 27 ++++++++++-----------------
 1 file changed, 10 insertions(+), 17 deletions(-)

Nightly failures same as main (JuliaLang/julia#57064)

I decided that I don't like producing arrays with length greater than or equal to typemax(Int), even if the eltype is Nothing. For example, length overflows and returns the wrong answer.

[LilithHafner]

FWIW recursion has its own drawbacks

I could just tack on @assume_effects :terminates_locally. Is that what you do in CheckedSizeProduct.jl?

[nsajko]

just tack on @assume_effects :terminates_locally

Yeah. There's a macro to only apply it when @assume_effects is available in Base:

https://github.com/JuliaArrays/CheckedSizeProduct.jl/blob/13347f5aa6641f7065c8b73bb2eb9eca0cd47aeb/src/CheckedSizeProduct.jl#L60-L78

const NonemptyNTuple = Tuple{T, Vararg{T, N}} where {T, N}

macro assume_terminates_locally(x)
    if isdefined(Base, Symbol("@assume_effects"))
        :(Base.@assume_effects :terminates_locally $x) 
    else
        x
    end 
end

@assume_terminates_locally function checked_dims_impl(t::NonemptyNTuple)
    a = first(t)
    have_overflow = false
    for i ∈ eachindex(t)[2:end]
        b = t[i]
        (m, o) = Base.Checked.mul_with_overflow(a, b)
        a = m 
        have_overflow |= o
    end 
    (a, have_overflow)
end

@assume_terminates_locally function any_impl(f, t::NTuple)  # basically an implementation of `any`
    a = false
    for i ∈ eachindex(t)
        e = t[i]
        b = f(e)::Bool  # assuming no `missing`
        a |= b
    end 
    a   
end