Are you my type?
How to do type lookups in ClojureCLR: some experiments and a new way forward.
Assemblies: to infinity and beyond
In a previous post – The function of naming; the naming of functions – I floated the idea of generating assemblies with abandon. The benefits were outlined in that article, primarily a simplification in handling internal naming of functions. What are the costs?
Assemblies themselves are fairly small. I ran some tests. In .NET 9, it appears that memory usage per assembly allocation is roughly 850 bytes. I also generated some simple types in those assemblies. They average around 3.5K bytes each. In a proliferation model, the extra memory overhead is not all that substantial. Even with large files and a long time spent typing at the REPL, well, what’s a few megabytes among friends?
Type lookup
There is one place where costs can grow linearly with the number of assemblies: type lookup. There is a method in Clojure(JVM and CLR) reponsible for looking up a type given a typename as a string: clojure.lang.RT.classForName(String). It gets a fair amount of work. During the loading of core.clj and other core files of the Clojure environment, it gets called about 6000 times. There are more calls when some other code such as clojure.main gets loaded.
The JVM version of RT.classForName is pretty simple. I’m happy for them. For ClojureCLR, I ended up kludging together several strategies. And the code has been bothering me ever since. But the analysis I just completed indicates that it is pretty decent given the data we see in practice. However, I do have an idea for a radically different approach, to be described at the end.
Type lookup: the classic model
There are two primary ways to look up a type: Type.GetType() and Assembly.GetType(). For a given string, you would call the former once; the latter would get called for every assembly.
Type.GetType() is only guaranteed to work with assembly-qualified names. It is intended to be called on string that look like "System.String, System.Private.CoreLib". The comma in there separates the fully-qualified name of the type from the assembly name. When Type.GetType() is given a name that is not assembly-qualified, such as "System.String", it will look in two places: the currently executing assembly and the mscorlib/System.PrivateCoreLib.dll. As it turns out, most of the types looked up during core.clj loading are in those two assemblies. Thus, it finds types for "System.String" (in System.Private.CoreLib) and "clojure.lang.PersistentVector" (in the executing assembly), but not "System.Net.Dns" (in System.Net.NameResolution.dll).
Assembly.GetType() is the recommended way to find a type from a name that is not assembly-qualified. One must call it for every assembly loaded in the application. And deal with the possibility that more then one assembly may have a type with the name in question. (In practice, though, this is unlikely. In my tests on system assemblies, the only name collisions I saw were for private types. Really, you shouldn’t be looking at those.)
To these two methods, I added two others: a map of dynamically created types and a parser for type names. The map is a cache of types that have been generated by the REPL or by AOT-compilation. The types searched for are typeically are deftypes and protocols. One sees a search for "clojure.core.VecSeq”, a type defined in gvec.clj, succeed by map lookup.
The parser is the last ditch attempt to deal with a given string. Instantiated generic types and array types are examples of strings that need to be parsed. There are not many of these looked up during the core Clojure load. We might run into it more in user code. Given "System.Collections.Generic.List1[System.String]", the parser will actually instantiate the generic type on the fly.
RT.classForName in ClojureCLR attempts the following:
- Direct lookup via
Type.GetType() - Look up in the map of generated types
- Loop through all assemblies calling
Assembly.GetType(). - Parse the string and try to construct a type.
I put some counters in clojure.lang.RT.classForName() to get some numbers from loading the core Clojure source during startup.
Here’s the data:
| Lookup type | Count | Description |
|---|---|---|
| Direct find | 5435 | Call to Type.GetType() succeedeed |
| Map find | 280 | Look up of dynamically generated type in a map |
| Assembly find | 97 | Calls to Assembly.GetType(), looping through all assemblies |
| Typename parsing | 3 | Parses the string and tries to construct a type, for things like instantiated generic types and array types |
| Failure | 172 | None of the above succeeded |
| Total | 5987 |
It should be noted that none of the strings in the data are assembly-qualified. The fact that 93% of successful attempts are handled by Type.GetType() shows that most types we are looking for are in the executing assembly or System.Private.CoreLib.
We get another 5% handled by map lookup. That doesn’t leave many names falling through to the assembly lookup.
Keep in mind that the failures – about 3% of the total – go through all four tests. Failures are expensive.
## Comparing lookup methods
In my test project, I did successful and failing lookups (typenames “System.String” and “asdf.asdf” respectively).
I timed lookups using Type.GetType() versus Assembly.GetType() (looping through all assemblies). Here are the results:
| Type name | Type.GetType() | Assembly.GetType() |
|---|---|---|
| “System.String” | 91 ms | 84 ms |
| “asdf.asdf” | 77 ms | 241 ms |
Oh, yeah. That’s for 100,000 iterations. There were 11 assemblies loaded when this ran.
For successful lookups, the two methods are about the same here.
For failures, Assembly.GetType() is slower – it has to go through all assemblies. I’m guessing System.String’s assembly is about one third of the way down the list.
The relative performance of Assembly.GetType() worsens as we add assemblies – and here we have the tie-in to the popcorn-popping proliferation of assemblies. In the test project, I added 100 dynamic assemblies with 5 classes each. The times for the same lookups were:
| Type name | Type.GetType() | Assembly.GetType() |
|---|---|---|
| “System.String” | 77 ms | 379 ms |
| “asdf.asdf” | 74 ms | 1748 ms |
We can see that the times for Assembly.GetType() have increased significantly. And failure gets significantly more expensive.
Do we have the optimal strategy for ClojureCLR? At startup, there are 37 assemblies loaded. By the time startup is done, there are 75 assemblies.
Catching most successful lookups via Type.GetType() seems like a good tactic.
The radical approach
The radical approach is to quite using both Type.GetType() and Assembly.GetType(). We can create a map from fully-qualified type names to types and do our checks via map lookup. How does performance compare?
| Type name | Type.GetType() | Assembly.GetType() | Map lookup |
|---|---|---|---|
| “System.String” | 77 ms | 379 ms | 1 ms |
| “asdf.asdf” | 74 ms | 1748 ms | 0 ms |
Umm, how do I get me one of those maps?
This approach involves the following.
- During system startup, run through all currently loaded assemblies and put entries for every public type in the map.
- At the same time, install a handler for assembly load events.
- The event handler runs whenever a new assembly is loaded. The handler runs through all the types in the assembly and put entries in the map.
- Continue registering dynamically generated types in the map as we have been doing.
- As an added bonus, whenever the typename parser generates a new type, add the string/type pair to the map.
What does RT.classForName look like in this model?
- Look up in the map of generated types.
- Parse the string and try to construct a type.
There are some details. For example, what if we do have two types with the same qualified name? We can flag those types in the map with a little extra work. If you give a name that is ambiguous, lookup should fail.
What about assembly-qualified names? The type parser knows how to handle them. And we can actually add the assembly-qualified name to the type map after a successful lookup, thus avoiding the need to parse the string again should it recur.
I’m strongly considering adopting this approach. Likely I will run it in parallel with the current strategy for a while to see if there are any issues. What do we gain? Well, not much really. But I’ll feel better looking at the code.
Copilot suggests the following continuation:
And it will be a little faster. And it will be a little simpler. And it will be a little more robust. And it will be a little more fun. And it will be a little more Clojure-y. And it will be a little more me.
Sure. I’ll go with that.