Special casing small integers known at compile time

Lilith · October 17, 2021, 3:12pm

I see this sort of code sometimes and it makes me cringe

similar(a::Array{T,1}) where {T}                    = Vector{T}(undef, size(a,1))
similar(a::Array{T,2}) where {T}                    = Matrix{T}(undef, size(a,1), size(a,2))
similar(a::Array{T,1}, S::Type) where {T}           = Vector{S}(undef, size(a,1))
similar(a::Array{T,2}, S::Type) where {T}           = Matrix{S}(undef, size(a,1), size(a,2))

github.com

JuliaLang/julia/blob/0ea61fa153c69e052097f1307dafbedd00049aae/base/array.jl#L373

    
      
          original.
          
          
See also [`copy!`](@ref Base.copy!), [`copyto!`](@ref).
          """
          copy
          
          
copy(a::T) where {T<:Array} = ccall(:jl_array_copy, Ref{T}, (Any,), a)
          
          
## Constructors ##
          
          
similar(a::Array{T,1}) where {T}                    = Vector{T}(undef, size(a,1))
          similar(a::Array{T,2}) where {T}                    = Matrix{T}(undef, size(a,1), size(a,2))
          similar(a::Array{T,1}, S::Type) where {T}           = Vector{S}(undef, size(a,1))
          similar(a::Array{T,2}, S::Type) where {T}           = Matrix{S}(undef, size(a,1), size(a,2))
          similar(a::Array{T}, m::Int) where {T}              = Vector{T}(undef, m)
          similar(a::Array, T::Type, dims::Dims{N}) where {N} = Array{T,N}(undef, dims)
          similar(a::Array{T}, dims::Dims{N}) where {T,N}     = Array{T,N}(undef, dims)
          
          
# T[x...] constructs Array{T,1}
          """
              getindex(type[, elements...])

Because we already have this

similar(a::AbstractArray{T}) where {T}                             = similar(a, T)
similar(a::AbstractArray, ::Type{T}) where {T}                     = similar(a, T, to_shape(axes(a)))
similar(a::AbstractArray{T}, dims::Tuple) where {T}                = similar(a, T, to_shape(dims))
similar(a::AbstractArray{T}, dims::DimOrInd...) where {T}          = similar(a, T, to_shape(dims))
similar(a::AbstractArray, ::Type{T}, dims::DimOrInd...) where {T}  = similar(a, T, to_shape(dims))

github.com

JuliaLang/julia/blob/0ea61fa153c69e052097f1307dafbedd00049aae/base/abstractarray.jl#L781

    
      
          
          
```julia-repl
          julia> similar(falses(10), Float64, 2, 4)
          2×4 Array{Float64,2}:
           2.18425e-314  2.18425e-314  2.18425e-314  2.18425e-314
           2.18425e-314  2.18425e-314  2.18425e-314  2.18425e-314
          ```
          
          
See also: [`undef`](@ref), [`isassigned`](@ref).
          """
          similar(a::AbstractArray{T}) where {T}                             = similar(a, T)
          similar(a::AbstractArray, ::Type{T}) where {T}                     = similar(a, T, to_shape(axes(a)))
          similar(a::AbstractArray{T}, dims::Tuple) where {T}                = similar(a, T, to_shape(dims))
          similar(a::AbstractArray{T}, dims::DimOrInd...) where {T}          = similar(a, T, to_shape(dims))
          similar(a::AbstractArray, ::Type{T}, dims::DimOrInd...) where {T}  = similar(a, T, to_shape(dims))
          # Similar supports specifying dims as either Integers or AbstractUnitRanges or any mixed combination
          # thereof. Ideally, we'd just convert Integers to OneTos and then call a canonical method with the axes,
          # but we don't want to require all AbstractArray subtypes to dispatch on Base.OneTo. So instead we
          # define this method to convert supported axes to Ints, with the expectation that an offset array
          # package will define a method with dims::Tuple{Union{Integer, UnitRange}, Vararg{Union{Integer, UnitRange}}}
          similar(a::AbstractArray, ::Type{T}, dims::Tuple{Union{Integer, OneTo}, Vararg{Union{Integer, OneTo}}}) where {T} = similar(a, T, to_shape(dims))

I believe that in this case it is written to special case low low numbers of arguments to avoid packing and unpacking into an NTuple, but I’m not sure. Is this necessary for maximum performance? Is it possible to delegate those special casings to the compiler whenever the NTuple's N is known at compile time (almost always)? Does the compiler already do this?

Oscar_Smith · October 17, 2021, 3:47pm

I believe this is one where due to bootstrap order, we don’t have those methods yet. in other words, I don’t think this is necessary outside Base.

Lilith · October 17, 2021, 4:43pm

Thanks! So then Arrays.jl is bootstrapped and similar is needed before AbstractArrays.jl is bootstrapped. What is the bootstrap order?

WschW · October 17, 2021, 4:51pm

The bootstrap order looks to be in this file:

github.com

JuliaLang/julia/blob/0ea61fa153c69e052097f1307dafbedd00049aae/base/Base.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

baremodule Base

using Core.Intrinsics, Core.IR

# to start, we're going to use a very simple definition of `include`
# that doesn't require any function (except what we can get from the `Core` top-module)
const _included_files = Array{Tuple{Module,String},1}()
function include(mod::Module, path::String)
    ccall(:jl_array_grow_end, Cvoid, (Any, UInt), _included_files, UInt(1))
    Core.arrayset(true, _included_files, (mod, ccall(:jl_prepend_cwd, Any, (Any,), path)), arraylen(_included_files))
    Core.println(path)
    ccall(:jl_uv_flush, Nothing, (Ptr{Nothing},), Core.io_pointer(Core.stdout))
    Core.include(mod, path)
end
include(path::String) = include(Base, path)

# from now on, this is now a top-module for resolving syntax
const is_primary_base_module = ccall(:jl_module_parent, Ref{Module}, (Any,), Base) === Core.Main

This file has been truncated. show original

Lilith · October 17, 2021, 6:35pm

Thanks! And indeed array.jl is imported before abstractarray.jl

github.com

JuliaLang/julia/blob/0ea61fa153c69e052097f1307dafbedd00049aae/base/Base.jl#L128

    
      
          include("int.jl")
          include("operators.jl")
          include("pointer.jl")
          include("refvalue.jl")
          include("refpointer.jl")
          include("checked.jl")
          using .Checked
          
          
# array structures
          include("indices.jl")
          include("array.jl")
          include("abstractarray.jl")
          include("subarray.jl")
          include("views.jl")
          include("baseext.jl")
          
          
include("ntuple.jl")
          
          
include("abstractdict.jl")
          include("iddict.jl")
          include("idset.jl")