Truly Optimal CodeUsing a Metaprogramming Library.ppt

1、Generating Truly Optimal Code Using a Metaprogramming Library,Don Clugston First D Programming Conference, 24 August 2007,String mixins in D undercooked, but very tasty,Compiles to:Vindicates built-in string operations,char greet(char greeting) return writefln(“ greeting , world!”); void main() mixi

2、n( greet( “Hello” ) ); ,void main() writefln( “Hello, world!” ); ,The Challenge,Fortran: BLAS (a standard set of highly optimised routines). The crucial functions are coded in asm.y += a * xBut BLAS is limited nothing for simple things:x = y - za = r*0.3 + g*0.5 + b*0.2;,void DAXPY(double y, double

3、x, double a) for (i = 0; i y.length; +i)yi += xi * a; ,Operating overloading,Gives ideal syntax, always works Cant operate on built-in types Inefficient because: Creates unnecessary temporaries. Multiple loops, eg a=b+c+d Somehow, we need to get the expression inside the for loop!,double temp1= new

4、double, temp2 = new double;for(int i=0; ib.length; +i) temp1i = bi + ci;for(int i=0, itemp1.length; +i) temp2i = temp1i + di; a = temp2;,The Wizard Solution: Expression Templates (eg, Blitz+),Overloaded operators dont do the calculation: instead, they record the operation as a proxy type, creating a

5、 syntax tree.Example: (a+b)/(c-d): Need a good optimiser. Works in D as well as C+. BUT we are fighting the compiler!,DVExpr, DVExpr, DApDivide,Representing the Syntax Tree in D,In D, any expression can be represented in a single template.Represent types and values in a tuple. Represent expression i

6、n a char . AZ correspond to T0T25.eg: Note that A appears twice in the expression (operator overloading cant represent that).,void vectorOperation(char expression, T)(T values) ,vectorOperation!(“A+=(B*C)/(A+D)”)(x, y, z, u, v);,Finding the vectors in a tuple,Its a vector if you can index it. Imperf

7、ection cant index tuple in CTFE. Workaround create array of results.Usage:if ( isVector!(Tuple)i) ,template isVector(T.) static if (T.length = 0)const bool isVector = ;else static if( is( typeof(T00) ) )const bool isVector = true isVector!(T1$);else const bool isVector = false isVector!(T1$); ,Metap

8、rogramming For Muggles,USAGE: double firstvec, secondvec, thirdvec; VEC!(“A+=B*(C+A*D)“)(firstvec, secondvec, thirdvec, 25.7);,char muggle (char expr, Values.)() char code = “for (int i=0; i= A ,Trivial enhancements,Ensure all vectors are the same length.Assert no aliasing (vectors dont overlap). Eq

9、ualize with hand-coded asm BLAS routines.,foreach(int i, bool b; isVector!(Values)1$) if (b)code = “assert(values“ atoi(i) “.length = values0.length);”; ,static if ( expr = “A+=B*C” ,Asm code via perturbation,Its hard to determine the optimal asm for an algorithm, much easier to modify existing code

10、. Begin with Agner Foggs optimal asm code for DAXPY. Use same loop design and register allocation strategy. Ignore difficult cases fallback to D code.,X87 (stack-based),Convert the infix expression into postfix. Split += into + and =. Swap operands to avoid FMUL latency. A += B - C * D A = (A+B) - (

11、C*D) C D * A B + - A = Avoid gaps in the instruction set Eg, fewer instructions for 80-bit reals, so load them first whenever possible.,X87 code generation,Directly convert postfix to inline asm.,VEC!(“C+=B*(A+D)“)( 2213.3, vec1, floatvec, vec2); / Postfix : BAD+*C+C=L1:fld double ptr EAX + 8*ESI; /

12、Bfld double ptr EAX + 8*ESI; /Afadd double ptr EDX + 8*ESI; /D+fmulp ST(1), ST; /*fadd float ptr ECX + 4*ESI; /C+fxch ST(1), ST;fstp float ptr ECX + 4*ESI - 4; / C= L2: inc ESI;jnz L1;,SSE/SSE2 (register-based),Cant do mixed-precision operations. Unroll loop by 2 or 4, to take advantage of SIMD. Ins

13、truction scheduling is less critical, but register allocation is more complicated than for x87.,GPGPU,Use the GPU in modern video cards to perform massively parallel calculations. Uses OpenGL or DirectX calls, instead of inline asm. Full of hacks (pretend your data is a texture!) but a rational API

14、should emerge soon. This should NOT be built into a compiler!,Adding a front end,Operator overloading Same limitations as before Mixins eg, mixin(blade(“firstvec+=secondvec*2.38”); clumsy syntax BUT: Can detect aliases Allows better error messages Can unroll small loops inline Closer to proposed mac

15、ro syntax,Front end using mixins,Lex: first += second * 2.38 A+=B*C. Determine types, resolve aliases, convert constants to literals. Determine precedence and associativity Perform constant foldingWe can do most of this using mixins Compiler help is most required for 4 _traits could help,Determining

16、 types,char getSymbolTable(char symbols) char result = “;for(int i=0; i0) result =“,“;result = “typeof(“ symbolsi ).stringof, symbolsi .stringof;result = “;return result; ,When mixed in, this creates an array2 of string literals. 0 is the type, 1 is the value,Determining precedence,class AST(char ex

17、pr) alias expr text;AST!(“(“ text “+” T.text “)“) opAdd(T)(T x) return null; AST!(“(“ text “*” T.text “)“) opMul(T)(T x) return null; AST!( text “(“ T.text “)“ ) opIndex(T)(T x) return null; char getPrecedence(char expr) char code = “typeof(“;for(int i=0; i=A mixin(getPrecedence(“A+B*C*D”) ) “A+(B*C

18、)*D)”,Conclusion,Implementation and syntactic issues remain Syntax for runtime and compile-time reflection Macros, and an extended _traits syntax should help. How to clean up mixin(), yet retain its power? Yet perfectly optimal code is already possible. Libraries can perform optimisations previously required a compiler back-end.,