Subtypes() function. Why is it so slow? Why return a Vector of Any?

julia> @btime subtypes(Integer)
  11.106 ms (3959 allocations: 1.71 MiB)
3-element Array{Any,1}:
 Bool    
 Signed  
 Unsigned

It seems to strange to return an unstable return type. And why does it do anything at runtime at all? I would have assumed that this was known at compile time and would be optimised out. What am I missing here?

I’m calling subtypes() to build interface widgets from abstract types for fields of large nested structs. But it’s really slow.

You can add subtypes to Integer at any time, either by defining them yourself or by loading a module.

1 Like

Ok that makes sense… I guess this is a downside dynamic-ness that I hadn’t really got my head around. The compiler doesn’t actually “know” the type hierarchies of anything in a structured way.

Note that there is a good reason for subtypes being in the InteractiveUtils module: it is for interactive inspection of the type hierarchy, not for runtime use.

If you are using it repeatedly in runtime code so that performance matter, you are probably doing something wrong. Perhaps if you explained your problem, it could be replaced by a more appropriate solution.

I don’t think its wrong, maybe novel… But subtypes does have useful runtime applications, whatever it’s intended for.

I need a list of all the concrete types at the leaves of a abstract type hierarchies. Then I can specify the top abstract type, and get all the concrete types available beneath it. Or I can automate the process for all marked fields (with FieldMetadata.jl) of a large nested composite type.

These lists of potential concrete types can be used to construct a model in an interface or for a run of parametrisation etc. automatically. If you add a concrete type to the hierarchy anywhere, it shows up without adding any other code.

The idea is to make it easier to explore models with lots of alternate formulations visually by having all of the options in drop-downs - selecting them rebuilds the model and all the sliders, plots, whatever on the fly. Also to just parametrise all possible model combinations without doing the arduous chore of actually coding them all.

It works great. It’s just really slow to load, and this is one of the reasons. Are there other functions that would achieve the same thing??

Going the other direction is fast, and is probably what the compiler etc. is using

julia> using BenchmarkTools

julia> @btime supertype(Int32)
  0.021 ns (0 allocations: 0 bytes)
Signed

If you have a known set of concrete types, you can perhaps use supertype to build a cache yourself?

That’s the kind of performance I was hoping for!

But I don’t have known sets of concrete types, and even when I do I don’t want to type them out and get locked into pages of setup code - when it’s all discoverable with the type system anyway.

If you know the abstract types in advance, and the information is fixed after a certain point in the module, you can use this hack:

julia> using InteractiveUtils

julia> @eval mysubtypes(::Type{Integer}) = $(Tuple(subtypes(Integer)))
mysubtypes (generic function with 1 method)

julia> mysubtypes(Integer)
(Bool, Signed, Unsigned)

julia> using BenchmarkTools

julia> @btime mysubtypes(Integer)
  1.094 ns (0 allocations: 0 bytes)
(Bool, Signed, Unsigned)

Of course, you can define it for all your abstract types not just Integer.

2 Likes

“Wrong” in the sense that it doesn’t mesh well with Julia’s performance model. Inspecting the type hierarchy is an “expensive” operation.

But I guess if you are building and interactive tool, ~10ms is not so bad?

Yeah its not so bad I was just surprised that it was taking up half of my load time!

I have to call it probably a few hundred times to walk all the type hierarchies recursively, then handling the untyped vectors has some costs as well.

Maybe you could loop over all names in all modules, similar to how InteractiveUtils._subtypes works. Collect a list of all types, then build the hierarchy from the bottom up,

I’ve just found that subtypes has a very long compilation time in Julia 1.1. In particular, it take ages to show the subtypes of Function the first time:

julia> @elapsed subtypes(Number)
0.623716491

julia> @elapsed subtypes(Number)
0.046466433

julia> @elapsed subtypes(Function)
782.176772866

julia> @elapsed subtypes(Function)
2.806277427

Do you know why is compilation time so long?

1 Like

In fact, there’s something could be cached/staged, like @generated function.

julia> using BenchmarkTools

julia> @btime subtypes(Number)
  4.556 ms (997 allocations: 580.91 KiB)
2-element Array{Any,1}:
 Complex
 Real   

julia> @generated mysubtypes(::Type{T}) where T = subtypes(T)
mysubtypes (generic function with 1 method)

julia> @btime mysubtypes(Number)
  1.596 ns (0 allocations: 0 bytes)
2-element Array{Any,1}:
 Complex
 Real   

The problem is that there’s no way to trigger new abstract typing relationships:

julia> struct MyNum <: Number
       end

julia> subtypes(Number)
3-element Array{Any,1}:
 Complex
 MyNum  
 Real   

julia> mysubtypes(Number)
2-element Array{Any,1}:
 Complex
 Real   

I wonder if we could dispatch from something like the number of World Age? Like this way:

mysubtypes(::Type{T}) where T = mysubtypes(T, Val(getcurrentage()))
@generated mysubtypes(::Type{T}, ::Val{Age}) where {T, Age} = subtypes(T) 

If we could dispatch through world age number, we could cache/stage many stuffs correctly and efficiently.

1 Like

It is faster in the latest Julia version: https://github.com/JuliaLang/julia/issues/29947

1 Like