Other ideas welcome.

This sounds like pretty much the same use-case that sync.Map is optimized for, although I suspect you'd have to reimplement sync.Map at a much lower level to be able to use it that deeply within the runtime.

Other ideas welcome

Could the compiler generate a perfect hash for this data? That would save CPU by avoiding walks altogether and initialization at startup. The downside being longer compile time, larger object size, and it might not work well with plugins.

@huguesb It is possible to perfect hash the startup data, but that seems overkill. Just sizing the table appropriately would be enough. We'd need a dynamic table anyway, as not all of the data is available at startup. If we move itabs to the dynamic table on first lookup (the hot/cold table idea), the speed of the static tables is ~irrelevant.

How do you feel about graph coloring? For a type T that implements interfaces I1, I2, I3, create a clique on I1, I2, I3, to indicate that they must have different colors.

Color the resulting graph, and construct tables (slices) mapping colors (now integers) to itabs.
Each itab/table entry also needs to indicate the interface it is for.

To convert Ix to Iy, extract Cx from Ix, then
(itab, iface) := Cx.iitable[color(Iy)]
if iface = Iy, success, otherwise failure.

Problem with this is that the graph coloring could be large-ish, I don't really know. It could happen at link time, might be interesting to figure out if there was a way to do it on-demand.

Yes, I know it's an NP-complete problem. So is register allocation.

@dr2chase I totally don't understand what you are suggesting. What is this graph of? Interfaces? Why are two different interfaces interfering? Is this just to make a small index out of an interface name?

We need to do this lookup even when the compiler never sees any of these types together (they are in different packages, say). So I don't think we could construct a complete interference graph at compile time anyway. Maybe link time, but then plugins break it.

Goal is to make a small index out of an interface name. Two interfaces I1 and I2 interfere if type T implements both of them (they can't both have the same index in T's table).

Plugins, the risk is either a new type TP collides two previously non-colliding interfaces, thus extending all the tables by one. A new interface IP also potentially extends all the tables.

Conceivably, "failure" can continue the probe by some other means.

How much of an event is loading a plugin?

More on the graph:

graph nodes are interfaces, graph edges indicate that two interfaces interfere (cannot share the same color) because they are both implemented by the same type. This is much the same as register allocation graph coloring, where nodes are variables, and an edge exists whenever two variables have overlapping lifetimes. In both cases, coloring is used to find and reuse small indices.

I think it would be worth doing some dynamic examination of real programs to see what dynamic types actually appear during specific interface-to-interface conversions. Where are all the interface-to-interface conversions coming from? How many are the fmt package checking for Formatter, GoStringer, and Stringer? Is it worth optimizing those specific cases, by, for example, having special hash tables just for those types?

I note that a type with methods always an uncommonType struct as part of its type descriptor. I note that uncommonType has 48 unused bits. That gives us plenty of room to identify the method index of the standard String method, if that is indeed one of the most common methods to look up.

In general, my guess is that the great majority of interface-to-interface conversions are converting to an interface with a single method. Perhaps we could add a pointer to the type descriptor of an interface type with a single method that points to a hash table mapping concrete types to the appropriate itab or nil if the type does not support the interface. The idea here is to simply split up the hash table.

Once we understand the nature of the table use (per Ian), I think a good next step would be to construct a benchmark program that reproduces the problem at different scales, so we can easily profile and experiment.

Of the static entries, there were more than 30,000 proto.Message, plus another 3000 or so helpers, like the additional Oneof types.
I don't have any dynamic counts, unfortunately. That requires being able to run the binary, which isn't easy.
I do have a benchmark which demonstrates the problem. I'll send it out tomorrow.

I think it would make sense to dynamically resize the itab hash table so that we can address both the dynamic and static itab entries cases in one go.

I think this can be simpler than sync.Map: the hash table would need to be a slice (instead of a fixed size array) and there would be an atomic pointer to the hash table slice. Lookups would follow the same "look twice - once without lock, once with" pattern as today. If the entry is not found the second time, we proceed to the insertion case which could be made to resize the table when above a given load factor.

During runtime init we may not be able to handle memory allocation (?); if that is a problem we can just disable hash resizing during early init.

Another issue is that the itab hash modulo would not be a constant anymore. We may want to avoid having an integer divide on that path. Is there a strong requirement for the prime hash size ? I suspect power of two hash sizes could be made to work too...

Another option is to precalc the prime sequence and the magic factors (libdivide style)

CL https://golang.org/cl/44338 mentions this issue.

CL https://golang.org/cl/44339 mentions this issue.

CL https://golang.org/cl/44341 mentions this issue.

CL https://golang.org/cl/44472 mentions this issue.