I was lately having a lot of trouble with recursive types, and eventually even triggered compiler bugs. Even worse, having a recursive type appear just once in field-of-…-field-types requires to carry it through much more complicated parametric versions of such.
It seems to me that you can always work around this though and achieve essentially equivalent functionality, with no relevant cost. Though I am interested in what I have missed. I have not been able to find the construction below, and will be glad to be pointed to contributions that have done the same.
If you want to skip the reasoning, just have a look at the last, longer code. It basically boils down to stricly necessary boxing at some point in the chain to a field-of-…-field-type using the recursive type:
Recursive types require boxing at some level:
First, trying to create a simple, recursive isbits types will fail (and a union fieldtype won`t do it either)
struct Test
t::Test
Test() = new()
Test(t::Test) = new(t)
end
sizeof(Test) # 8
isbitstype(Test) # false
What is more interesting is that an incomplete constructor in a fieldtype can change how the top type handles that field. This is due to the way Julia indicates and forwards undef.
As you can see below, the top type Wrapper{T2} of size 8 boxes its field for the sole reason that the subtype T2 (of size 16) contains an incomplete constructor:
struct Complete{S}
s::S
SubInc(s::S) where S = new{S}(s)
end
struct Incomplete{S}
s::S
SubInc() = new{S}() # equals Complete but for this constructor
SubInc(s::S) where S = new{S}(s)
end
struct Wrapper{T}
x::T
Incomplete(x::T) where T = new{T}(x)
end
T1 = Incomplete{Bool} # 1 (the "incomplete" constructor will just overtake random bits)
sizeof(T1) # 1
sizeof(Wrapper{T1}) # 1
VecVec = Tuple{Vector{Bool},Vector{Bool}}
sizeof(VecVec) # 16
T2 = Incomplete{VecVec}
sizeof(T2) # 16
sizeof(Wrapper{T2}) # 8 (! boxes)
T3 = Complete{VecVec}
sizeof(T3) # 16
sizeof(Wrapper{T3}) # 16 (does not box)
T4 = Union{Bool,VecVec}
sizeof(Wrapper{T4}) # 8 (! union fieldtype causes boxing as well)
Abstract fieldtypes where there must be a box:
These boxing barriers change how to look at recursive types. Essentially, at some point down into a field-of-…-field-type, the behaviour in regard of boxing is essentially as of a field of mutable type. Within Wrapper{T2}, the type Incomplete{VecVec} may for instance as well be replaced with a mutable version of it with const fields. But for that matter, one could then replace Incomplete{T2} just with the unionall type Incomplete or some abstract suptype altogether.
Implicitly ensuring type stability:
The remaining problem with type instability of getting that now type instable field can somewhat easily be fixed a posterior by telling getproperty what that fieldtype is intended to be, and setproperty! for a mutable type as well as any other point getfield or setfield! is used.
There is some marginal effort for Julia to check the type via ::Vector{_v_type(as)}, but at the same time, the emulated recursive type S seemingly performs marginally better at other tasks compared to the true recursive type RS.
The tests are also intended to simulate warmer and colder caches, so they cycle through vectors of different size:
if !@isdefined(AS)
abstract type AS end
struct SR <: AS
v::Vector{SR} # self-referential
SR(ell::Int) = SR(Vector{SR}(undef, ell))
SR(v::Vector{SR}) = new(v)
end
struct S <: AS
v::Vector{T} where T<:AS # implicitly set through _v_type
S(ell::Int) = S(Vector{S}(undef, ell))
S(v::Vector{S}) = new(v)
end
end
# here one sets the intended type:
_v_type(::T) where T<:AS = T
# ensure concrete return type for S (and set an artifial property call (for testing purposes)
Base.getproperty(as::AS, sym::Symbol) = sym === :ell ? length(as.v) : getfield(as, :v)::Vector{_v_type(as)}
## the rest is for testing (and avoiding infinite text output)
Base.show(io::IO, as::AS) where IO = show(io, typeof(as))
Base.display(as::AS) = show(typeof(as))
Base.display(v::Vector{<:AS}) = display(typeof(v))
Base.print(io::IO, as::AS) where IO = show(io, typeof(as))
# function that requires one getproperty(as, :v) and one getproperty(as, :ell)
foo(as::AS) = sum(x->x.ell, as.v)
function make_collection(n::Int, ::Type{T}) where T<:AS
collection = [T(n) for _ = 1:n]
for e = collection
for j = eachindex(e.v)
e.v[j] = collection[j]
end
end
return collection
end
function time(n::Int, ::Type{T}) where T<:AS
t1 = (@timed collection = make_collection(n, T)).time
t2 = (@timed for s = collection
for i = 1:n
s.v[i] = collection[i]
end
end).time
a = 0
t3 = (@timed for s = collection
a += foo(s)
end).time
return (a, t1, t2, t3)
end
function timeall(n)
println("n = $n:")
GC.gc()
GC.gc()
(a_sr, tsr1, tsr2, tsr3) = (0, 0.0, 0.0, 0.0)
(a_s, ts1, ts2, ts3) = (0, 0.0, 0.0, 0.0)
for _ = 1:Int(round(1e8/n^2))
(a_sr, tsr1, tsr2, tsr3) = (a_sr, tsr1, tsr2, tsr3) .+ time(n, SR)
end
GC.gc()
GC.gc()
for _ = 1:Int(round(1e8/n^2))
(a_s, ts1, ts2, ts3) = (a_s, ts1, ts2, ts3) .+ time(n, S)
end
r3 = x->round(x, sigdigits=3)
println("SR: $(r3(tsr1)) $(r3(tsr2)) $(r3(tsr3))")
println("S: $(r3(ts1)) $(r3(ts2)) $(r3(ts3))")
println("ratio S / SR: $(r3(ts1/tsr1)) $(r3(ts2/tsr2)) $(r3(ts3/tsr3))")
println()
end
timeall(5)
timeall(10)
timeall(100)
timeall(1000)
# n = 5:
# SR: 0.716 0.182 0.145
# S: 0.662 0.174 0.145
# ratio S / SR: 0.925 0.959 1.0
# n = 10:
# SR: 0.347 0.102 0.0839
# S: 0.322 0.114 0.0744
# ratio S / SR: 0.929 1.12 0.886
# n = 100:
# SR: 0.159 0.0763 0.0506
# S: 0.182 0.0865 0.053
# ratio S / SR: 1.14 1.13 1.05
# n = 1000:
# SR: 0.435 0.0717 0.0715
# S: 0.454 0.0748 0.0679
# ratio S / SR: 1.04 1.04 0.95
General scheme as pseudocode:
Looking at this more generally, one can always do so at the one point boxing would occur or where one purposely sets the mutable type. So, for instance, when the type C has an incomplete constructur, or is mutable, one could change
struct RecType; field::A{B{C{D{RecType}}}}; end
to
abstract type AC{T} end
struct C{T} <: AC{T}; (...); end
struct RecType; field::A{B{AC{D{RecType}}}}; end
function Base.getproperty(b::B{AC{T}}, sym::Symbol) where T
if sym === :fc_for_C
getfield(b, sym)::C{T}
else
getfield(b, sym) # or some further checks
end
# and ensuring at other points where getfield is called