1/ Actually a pretty good question. Why would you make a virtual table with C#? Usually, you wouldn't. Unless ...
You want flexibility for interpretation AND high performance without having to create code on the fly (Roslyn or any other shenanigan).
2/ Let's say that you have the following query. What we are doing here is transforming this text into a DAG (directed acyclic graph).
3/ If you would transform that into code, it would look like the following. Keep in match the bigger the graph the more those things start to add up.
Consider another AND (BinaryMatch) statement over another of those types. It gets unwieldly FAST.
4/ The big issue is that the types start crawling back into your code. For this code, no problem... 'var' does the inference and solve the issues (the compiler have to deal with n levels of nesting, but you just see 'var'). Don't even try to reason about the type on a stack trace
5/ If you need to write code like the following, there are not many tradeoffs from here. You either hide the return type with an interface or you use Roslyn to generate dynamic code. UNLESS....
6/ You guessed it. You build a virtual table :). Why? Because neither of the other solutions gets you flexibility AND efficiency. Roslyn solution is efficient as hell (if you can amortize the upfront cost that is). On the other hand, the interface is nasty performance wise.
7/ But what does the virtual table buys you? It buys you something that is taboo on the .Net land. It buys you type erasure mechanics. Now you can write code like this.
8/ Notice that I am erasing the fact that TInner and TOuter are actually structs, BUT, the code that gets executed is the one specialized for it.
9/ This is the fun part. I will probably still keep the Term and Match difference for semantic reasons, but I can get away with a single Match to write this code if I want to.
10/ Generated is the parser version generating the code dynamically through Roslyn. That means that the JIT does know everything and will create the best code out of it.
BUT... BUT... Where's the trick??? How can you effectively erase the type and still get the same performance?
11/ This can be done thanks a group of optimization and features from the C# language working in tandem. Struct based metaprogramming (links for my talks about the subject at #DotNextConf in the last tweet) and C# new Function Pointers. Which allow us to write this.
12/ It is said that almost every problem in Computer Science can be solve with just another level of indirection. This wont be the exception. The trick requires 2 things, first your function table (these are the jump points).
13/ Second is the trigger mechanism for the JIT to get you the proper jump points. You will see some boxing and unboxing there, but as shown there the JIT does a pretty good job to get rid of them :D
14/ Third your actual type erased type.
15/ That alone will get you up to 20% of the execution cost of the Roslyn generated code. BUT, if you want to squeeze even the last bit out of it, you can do this :)
16/ And if you want to go the extra mile. You can actually apply the same trick and create a DictionaryFunctionCache that will get you the specialized version you want to execute for the cost of a dictionary lookup. That tradeoff is obviously not that clear cut there.
17/ Links to the talks at @DotNextConf
(2017) Patterns for High Performance C#:
(2018) Scratch Metal:
(2019) Metaprogramming for the masses:
18/ Go find your nails. Enjoy.
Share this Scrolly Tale with your friends.
A Scrolly Tale is a new way to read Twitter threads with a more visually immersive experience.
Discover more beautiful Scrolly Tales like this.