Hi, I'm a norwegian applied mathematics student with an interest in compilers, and I've been a long-time python user and a python-dev lurker for some time. I'm very happy that you've integrated the AST branch into mainline, but I noticed that the AST compiler does not perform much optimization yet, so I though I'd take a crack at it.
I just submitted the following patches: http://www.python.org/sf/1346214 http://www.python.org/sf/1346238 which adds better dead code elimination and constant folding of the AST representation to Python. The constant folding patch adds two new files, Include/optimize.h and Python/optimize.c, which includes a general visitor interface abstracted from exisiting visitor code for easy optimization pass creation. The code is in new files in order to make room for more AST optimization passes, and since Python/compile.c is already quite crowded with byte code generation and bytecode optimization. If desired, this patch could changed to add code to Python/compile.c instead. Further work: A limited form of type interference (e.g. as a synthesized attribute) could be very useful for further optimizations. Since python allows operator overloading, it isn't safe to perform strength reductions on expressions with operands of unknown type, as there is no way to know if algebraic identities will hold. However, if we can infer from the context that expressions have the type of int, float or long, many optimizations become possible, for instance: x**2 => x*x x*2 => x+x x*0 => 0 x*1 => x 4*x + 5*x => 9*x (this optimization actually requires common subexpression elimination for the general case, but simple cases can be performed without this) and so forth. Another interesting optimization that can potensially bring a lot of additional speed is hoisting of loop invariants, since calling python methods involves allocating and creating a method-wrapper object. An informal test shows that optimizing lst = [] for i in range(10): lst.append(i+1) into lst = [] tmp = lst.append for i in range(10): tmp(i+1) will yield a 10% speed increase. This operation is of course not safe with arbitrary types, but with the above type interference, we could perform this operation if the object is of a type that disallows attribute assignment, for instance lists, tuples, strings and unicode strings. Regards, Rune Holm _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com