Did you ever follow up on this?

[jzabroski]

The README says you would... would be nice to update the README to a pointer to a new blog post. Either way, thanks for all the references on your blog post.

[tokenrove]

I haven't, but thanks for the ping; I have a backlog of related blog posts that I should get back to. Also, I have some more recent architectural considerations to add to this one (e.g. some of my recent work has got me thinking about dispatch on SIMT machines). No promises but I will get back to it. Thanks for your interest.

[jzabroski]

In case you are wondering, I was provoked by recent discussion on the .NET Core runtime between Neal Gafter and Jan Kotas regarding whether the .NET Runtime should support a new IL instruction for TypeSwitch. I am a bit shy talking to such giants (Neal pretty much built Gmail among other great software), but thought it would be an excellent opportunity to learn more. I had also read Bjorne Sjoustrup's 2012 paper on adding Open TypeSwitch to C++, where he had mentioned a fantastic 1983 paper by Schubert.

One thing that has potentially dawned on me about the nature of efficient dispatch is that all dispatch optimization is effectively a sort optimization problem. In this sense, there are two kinds of sorting algorithms: comparison sorts and non-comparison sorts (like counting sort, bucket sort and radix sort). It seems like most optimizing compilers handle sealed object hierarchies/algebraic data types using a non-comparison sort by basically tagging each type with a number. This and Schubert's total ordering trick seem to be the most space-time efficient for TypeSwitch.

One of the interesting things Jan said was that he did not want to rush to put a new IL instruction in the runtime. Downsides to adding new IL instructions include reduced portability of the runtime, reduced backward compatibility of generated IL with older runtimes, and just general person-hours of labor required to optimize the hell out of this (your reference to Sayle's work taking a decade of time is probably what Jan just knows in his bones from being a great compiler architect).

However, something Jan said stuck out to me as interesting: He felt that much of what could be done with a TypeSwitch optimization was better done by hot path optimization and inlining static fields. He didn't give any examples as to his intuition so I was trying to both understand what mechanisms the .NET Runtime supports today, as well as what other JITs might support today to enable such beliefs. In particular, I was wondering how it could be the PFLUA (Packet Filtering Lua) was extremely faster than C-implemented packet filtering, considering some of the instruction sequences are remarkably similar to TypeSwitch.

I mention thinking about approaches to switch statements as an algebraic sort classification problem, because I am making mental notes as to whether thinking about the deep algebraic structure of the problem might lead to unique insights for dynamic assembly calls.

It also occurred to me that there could be potential for probabilistic data structures for optimizing switch statements, based on work done with Stable Bloom Filters, where you basically knowingly don't optimize for certain "key values" (type handles), because you don't think you will hit them. However, given the tightness you outline of just 4 labels, and Neal's tightness criteria of just 10 labels for using a hash table, it's not clear to me how a Stable Bloom Filter/probabilistic data structure would be much better. Yet, the core idea is to trade-off space (caching type handles) by accepting a certain error rate (errors would result in slower performance when an error occurs - the error rate is proportional to the frequency at which unlikely type handles are switched on).

[tokenrove]

Oh, that's really interesting! My own work on this dropped off as, at the time, I was working on low-latency network software and considering compilation strategies for improving dispatch in that context (as well as for bytecode VM implementations), which is not something I'm actively working on right now.

Those cases are, I think, "more dynamic" than many of the cases in which TypeSwitch might be applied; at least I think that's what Jan Kotas is alluding to here — I feel like a lot of the work around method dispatch optimization is focused on cases where you can either statically guess, or where you can specialize the path after a single invocation and be right 99% of the time, which I think is common in a lot of object-oriented programs. (The Strandh paper I cite in the blogpost is interesting, here, since the interactive nature of CL makes those kinds of static optimizations more painful.)

In particular, I was wondering how it could be the PFLUA (Packet Filtering Lua) was extremely faster than C-implemented packet filtering, considering some of the instruction sequences are remarkably similar to TypeSwitch.

It would be interesting to disassemble specific examples and see if it ended up doing specialization (much easier to do in a JIT than elsewhere), carefully-tuned search, or even self-adjusting search (which one could imagine a JIT compiler doing, although I imagine it's such a specialized case maybe no one has bothered; I feel this is where compiler optimization starts to cross over with database query execution optimization).

all dispatch optimization is effectively a sort optimization problem.

Yes, I think for me realizing that everything around search applied here (and that there might be heap-like solutions where you only partially sort) was extremely helpful in seeing the space of optimizations.

It also occurred to me that there could be potential for probabilistic data structures for optimizing switch statements

Yes, I think this is worth pursuing. I think in general the need for these kinds of approaches is probably specialized, but I'm sure someone out there has the special cases where this ends up being a big win.

[jzabroski]

Yes, I think for me realizing that everything around search applied here (and that there might be heap-like solutions where you only partially sort) was extremely helpful in seeing the space of optimizations.

Yes! That's EXACTLY what I was thinking. I was wondering if anyone has implemented a "lazy heap", where you not only partially sort, but also only partially build the heap and keep track of your incomplete heap build. - This would be useful in the OO case where you may not know all the types ahead of time, because the type hierarchy is not sealed.

Thanks for the interesting discussion.

[tokenrove]

I don't know if it would be useful at all in this case, but maybe some of the ideas might spark other useful ones: a structure that I was very interested in for a similar case (maintaining timers, as an alternative to timing wheels, which have another set of the same sorting tradeoffs, and the radix sort idea again): Chazelle's soft heap (https://en.wikipedia.org/wiki/Soft_heap).