From what I understand, compiled methods (for clarity I’ll call them MethodInstances) are invalidated when methods are defined, e.g. f(x) = 1; f(1); f(x::Real) = 2. I imagine the most wasteful algorithm would be to check every existing MethodInstance for a function to see if it would involve the newly defined method. What is the actual algorithm doing and how does it scale with number of MethodInstances for a function?
(For anyone who stumbles on this thread in the future, implementation details can change freely).
As I understand it, this happens through backedges in the dependency call graph. So each method (or function?) knows what it gets called by and can invalidate existing callers if a new specialization gets added that’s more specific than an existing call.
Invalidating caller MethodInstances by following backedges surely happens after finding the affected callee MethodInstance in the first place, like f(::Int) when an f(x::Real) method is defined. What I’m wondering is how that initial search happens, but I have doubts that it is brute-force-checking whether every existing MethodInstance for f would be compiled for f(x::Real) and not the other methods for f.
I think Julia internally use a type splitting tree to arrange Method into disjoint parts. So you can firstly find out invalidated Method (approximately computed by a fast type intersection algorithm), then invalidate associated method instance. This can save a great deal of work if you have a lots of different method instance and you only invalidate a few Methods. You may need to read Julia’s method selection and invalidation code to find out more details.
I don’t know where to find the code and I probably wouldn’t be able to read internal Julia or whatever language it’s in. I had hoped the devdocs could describe method invalidation internals in plainer language, but I couldn’t find anything about it, just some information on method call dispatch and method tables.
Now I think about it, I don’t even know if MethodInstances are marked invalid at method definitionf(x::Real) = 2, for all I know it could happen at the next method call f(1). But I do have doubts about that because it would require a caller method call g(1) to recursively check every callee function including f just in case their method tables were altered. Besides, f has backedges to g, I’ve never heard of g having forwardedges to f.
If you really really want to know it, I can provide a simple explanation, though not 100% accurate.
Firstly some terminology, take this for example.:
f(x::Real) = 0 # Generic function, with only one Method f(x::Int)
f(1.0) # Create one method instance and one code instance `f(x::Float64) for f(x::Real)`
f(x::Real) = 1 # Redefinition of Method `f(x::Int)`. Method instance is kept untouched, code instance is invalidated recursively using back edges.
f(x::Float64) = 1 # Add a new Method `f(x::Real) `to the generic function f, invalidate of Method instance and code instance
f(1) # create a new code instance and one code instance `f(x::Float64) for f(x::Real)`
So we have generic function f, methods (3 methods, where one method overwrites the previous one), method instance and code instance here. Method instances cache the result of method selection, so we don’t need to perform method specialization every time we look up method for a given input types combination. Code instances cache the result of compilation, it’s actually a function pointer which points to function entry in the machine code(like those in C). And they will both be invalidated when redefinition happens.
Invalidation happens in the following process:
Firstly invalidation happens when method table changes (adding or deleting methods), and the goal of invalidation is to “evict” out-of-date method instance and code instance (the process of “evict” will be explained later). So we won’t invoke wrong machine codes or method specializations. Notice that we only need to calculate an approximate invalidated targets. For example, we can always invalidate all the method instances and functions.
The general process of method dispatching looks like this: firstly we get the generic function and the input types, then we peek into the method tables to find (or generate a new one) a method instance, which is a cache of method specialization. Then it looks into the associated code instance to get the machine code. Notice that this lookup procedure requires a “world age” parameters (explained later).
We we mutate method table, we need to find what caches are still usable. That is, if the method table before mutation is M, after mutation is M + \Delta M, then the problem is to determine for a input type combination types, whether specialize(M, types) == specialize(M + \Delta M, types) . Here specialize donates the method selection procedure, it returns a dispatched method instance just as depicted above.
It’s easy to see that if \Delta M is disjoint with M, then no method instances will be invalidated. Or if \Delta M is more concrete than M. These two cases are roughly the so called (no) “type privacy”. So to invalidate method instance, we can actually check intersected method (and this can be done with fast type intersection algorithm), instead of iterating all the method instances. Then we check associated method instances. Note that we can always invalidate every thing. So even if types are complicated and the intersection is hard to calculate, we can conservatively invalidate them for safety.
Suppose we indeed need to invalidate something, we now need to use world age and back edges. Back edges tell us what other method instances are using this method instance and they need to be invalidated recursively. Now we increment the world age by one and move to the new world. Every code instance has a world interval which indicates the world in which it’s valid. When we invalidate a method instance, we will modify its associated code instance’s world interval to mark the end of current active code instance. We we invoke the method the next time, a new code instance will be created with the new world age as the start of the world, and we always look up the code instance in the current new world.
That’s the rough picture of whole invalidation pipeline. If you want to know more concrete details (which I doubt), I guess you still have to read Julia’s internal code or maybe Jeff’s thesis.
The terminology is a bit confusing. I’ve never heard of code instances before, only method instances, and I’m still not really sure what their separate roles are and which has backedges (code example said code instances do, but (4) says method instances do).
But I think the part I’m asking about is being described in (3). It’s not very clear to me what the “fast type intersection algorithm” is doing. You mentioned before that “Julia internally use a type splitting tree to arrange Method into disjoint parts”, is it just a matter of finding the affected node of a method table tree and invalidating the method+code instances in the node?
It’s also hard for me to imagine how a tree would be made with multiple dispatch, it’s not as easy as a type hierarchy. But I suppose dispatching does have more to less specific methods. Is it technically a tree if a node can have multiple parents, e.g. a more specific method that resolves method ambiguities?
Code instance has associated world ages and function pointers, and method instance has back edges. It’s quite natural that they have separate roles. A method instance can have multiple code instances due to invalidation (for example, you might delete a method then add it back, so you need two separate code instance to represent two disjoint world intervals).
I think it works much like this, but it is quite complicated and I don’t know how it works exactly (I haven’t read that part of code carefully). I do know some splittings are done on types and argument positions. So…