(The second in what seems to be a day of obscure .NET facts)
While looking at some C++/CLI code in Reflector today at work, we encountered the
try ... fault construct.
It's like a
finally block, but it's only entered in the event of an exception.
So it's like a
catch block, then?
faultblocks don't have filters like
- At the end of a
faultblock the exception is implicitly rethrown
Supposedly the benefit of a
fault block is performance: that
throw; statement at the end of a
catch block has the same overhead as any other
throw statement, whereas
fault blocks incur no runtime overhead. The stack is not unwound when a
fault block is entered:
fault blocks won't appear in the exception stack trace.
fault blocks show up?
In the code the C++/CLI compiler emits in order to make sure that local variables have their destructors called in the event of an exception.
Daniel Fortunov wrote about an obscure use of duck typing in the C# spec for enumerators:
Although it is common to implement [IEnumerable and IEnumerator] when creating an enumerable class, if you were to drop the interfaces but leave the implementation, your class would still be enumerable by foreach. Voila! Duck-typing!
You can take advantage of this fact for a couple of performance tricks, as demonstrated by many of the standard collection classes in the base class library:
- Declare your
IEnumerator<T>implementation as a struct, not a class. This saves you a heap allocation when
- Define a
Enumerator<T> GetEnumerator()method on your collection class
- Note that you're returning your own struct, not
IEnumerable<T>; this avoids a boxing operation. You'll still need to explicitly implement
IEnumerator<T> GetEnumerator(), for people who only have an
IEnumerable<T>reference to your collection. These performance tricks don't apply when you're making calls through this interface.
When somebody uses
foreach over your collection, the compiler sees a series of
MoveNext calls and accesses to the
Current property, and it emits code to call these efficiently on your struct.
What's more, the code in your struct's methods is a candidate for inlining by the JIT compiler. The segment of the
MoveNext method of
System.Collections.Generic.List<T>+Enumerator that can throw an exception is split into its own method, apparently for this reason.
I don't claim any kind of definite performance benefits from using these techniques, but it does look like the language designers put some thought into making it possible to use
foreach without incurring any overhead compared to some less elegant method.
I'd like to add tail call support to my Lisp compiler. I can think of two approaches to tail recursion:
- Use the .NET
- It's easier to spot this pattern if we put IL in our own data structure before emitting it
- Our own data structure needs to represent all the IL we use, including labels (for branching) and local variables
- The label data structure needs a way to represent the target of a branch
- Note: The
tailprefix is a hint that the JIT compiler doesn't have to obey - here's a good explanation of the limitations
- Translate functions that call themselves into loops
- Our abstract syntax tree doesn't have a way to represent a loop
- As above, it needs an AST capable of representing branches
- The F# compiler does this; it's not able to rely on the
- Can we apply this to functions that call each other recursively? At compile time we might not spot co-recursive functions: F# only allows co-recursive functions if they use the
let ... andsyntax to define both functions in the same source file.
- One entry point: no branching into the middle of the block
- One exit point: always contains one branch instruction, at the end
- Basic blocks can be connected to form a control flow graph: blocks are vertices, branch instructions are edges
- Control flow graph is: directed (A branches to B); cyclic (A is allowed to branch to A - this is a loop)
How can we represent basic blocks in F#? The intuitive approach means defining a discriminated union:
// An instruction can be a regular opcode, // or a branch to another basic block type Instruction = CallInstruction of MethodInfo * obj | Branch of BasicBlock // A basic block is a list of instructions and BasicBlock = BasicBlock of Instruction list
We have to construct a list of instructions before constructing a basic block. But how do we represent the following?
// C# pseudocode while (true) Console.WriteLine("hello");
// F# abstract syntax tree for the above C# let instructions = [ Call (writeLine, "hello"); // How can we branch to something we haven't constructed yet? Branch ??? ] let program = BasicBlock instructions
The answer is to separate identity of basic blocks from the instructions within them. We could assign names or ids to them. Or, since we're writing F# and not Haskell, we could drop immutability:
// F# abstract syntax tree with mutability - // note property assignment with <- let program = new BasicBlock() let instructions = [ Call (writeLine, "hello"); Branch program ] program.Instructions <- instructions
LLVM does something similar with its C++ API:
// LLVM equivalent in C++ // 'bb' is a basic block within func_main BasicBlock* label_bb = BasicBlock::Create("bb", func_main, 0); // First instruction in bb: call puts("hello") CallInst::Create(func_puts, const_ptr_8, "", label_bb); // Second instruction in bb: branch back to bb BranchInst::Create(label_bb, label_bb);
I'm not yet sure of all the implications for my toy compiler, but already I can see some indications about how to structure the code to allow for optimisations like tail calling:
- Structure the entire program as a graph of basic blocks linked by branch instructions
- Abstract syntax trees can't do everything; instead, they appear as instructions within basic blocks
- Construction of basic blocks must be separate from construction of the instructions within them, so that we can refer to a basic block from one of its own instructions
- As it progresses through compiler passes, the program graph starts looking less functional and more imperative, until it eventually represents actual machine instructions
- I should probably read a compiler textbook