[summerofcode] High-level python optimizer.

[Vova]

On Friday 10 June 2005 06:32, Brett C. wrote:
> Vova wrote:
> [SNIP]
>
> > My project will use type information to do high-level code optimization
> > (see below). Type inference is the only one part of analysis. The aim of
> > the analysis is to gain the following information (when it possible): 1.
> > Variable types.
> > 2. Variable values.
> > 3. Function side-effects.
> >
> > Item 3 depends on 1. Example:
> > def sum(a,b): return a+b
> > sum(a,b) has side-effects iff a.__add__ has side-effects.
> > Another example:
> > a.some_method(5)
> > here we must guess the type of a, then check a.__getitem__ for
> > side-effects, and then check a.some_method(5) for side_effects.
> >
> > Let's look, how can we use this information to optimize program:
> >
> > 1. Constant-folding and math simplification can be done for built-in
> > types. If some variables have definite values we can use it directly.
>
> This is already done for constants by the peepholer.
Ok, but I don't know does it ever possible to do math (string, list,...) 
expression simplification for non-constants taking peepholer approach.

> > 2. Function inlining (which can be significant in python) can be done if
> > we know what function is being called. For method inlining we must know
> > the type of the object and check __getitem__ for side-effects.
>
> This is a lot harder than it might seem on the surface.  Functions can be
> replaced.
Yes. But this is handled by general algorithm. Function objects is tracked 
like any other variables, and if at the time of call it has definite value 
then function can be inlined.

> What about default arguments that are changed between 
> executions?
Again, if optimizer can't prove that default arguments have definite values 
then it won't do anything that may be illegal. Maybe in some cases default 
arguments can be evaluated in caller context. Anyway inlining is actual only 
for small functions.

> > 3. Partial evaluation can be done if some variables have known types
> > and/or values. This can be done for user function if we have proven that
> > it has no side-effects (for example replacing calls to factorial(10) or
> > sin(10) with their results at compile-type), and for python specific
> > operations, for example replacing "%some_pattern" % (some_list) by more
> > efficient code.
>
> function call replacement might be possible, although detecting
> side-effects is rather difficult thanks to descriptors allowing even
> attribute access to execute a function.
This only means that function side-effects depends on it's argument types. If 
we know the types of the arguments than we can expand any operator 
overloading. So (as I mentioned before) side-effects checking can't be done 
without type inference. Also this can't be done without value inference 
because we must know what functions are being called by current function.

> > 4. Dead code elimination can be done as part of parial evaluation. Unused
> > variable elimination (i.e. elimination of function calls if their result
> > is unused) can be done too using information about side-effects. If
> > variable is used only in one branch of execution it assignment can be
> > moved into that branch.
>
> That might buy you something, but I doubt much.
>
> > 5. Common subexpression elimination (as well as moving common code
> > outside loops) can be done if subexpression has no side-effects. This is
> > even more actual in python than in static-typed languages because the
> > code the.some.method(x)
> > the.some.method(y)
> > or
> > for x in some_big_list: the.some.method(x)
> > is very common. the.__getitem__("some").__getitem__("method") is the
> > common code.
> >
> > 6. There are also some python-specific optimization, for example
> > replacing range with xrange when possible, replacing the code
> > (a,b)=(b,a)
> > with the code
> > t=a; a=b; b=t
> > and so on.
>
> I think the peepholer does this as well, but a quick check didn't make it
> obvious.
This is only some examples that comes into my mind. There are others: 
converting lists to generators when possible, temporary lists elimination, 
memory-allocation related optimizations etc.

> You might get something out of this, but once again it will probably be
> tough.
>
> > All of this is high-level optimization, it should be used on top of the
> > low-level optimizations. Of course all of this can be done by hands if
> > programmer is clever enough, but sometimes the price for it is decreasing
> > the code readability, abusing incapsulation, and so on, the result is
> > increased maintenance cost.
>
> Right, which is why people tend not to publish major performance hacks one
> can do in Python to gain a slight performance boost.
>
> > The result of the optimizer could be either optimized python source or
> > compiled program. In the former case it can be then compiled by Jython,
> > IronPython or PyPy.
> >
> > As I said before, this optimizations will give the best results it
> > applied to the whole program with all of it's modules. The problem with
> > compile-time to run-time integrity can be partly solved by checking used
> > modules just before running the program and recompiling the program if
> > needed. Maybe we can save taken assumptions about module's functions and
> > check if that assumptions had changed, so full recompilation will be
> > needed only rarely. In real-world applications only the small amount of
> > modules actually changes often. The results of optimization of
> > stand-alone modules can be improved by adding type annotations for
> > module's functions.
>
> How would you work in the checks?  Added code by your optimizer?
Probably adding code by optimizer is the simplest solution. It won't hurt 
performance much in the case were no recompilation is needed.

> > This project is different from python-to-C++ compilation (of course some
> > correlations present). C++ can't represent a lot of python features, but
> > optimized python program preserves all of them. Optimizer touches only
> > the code that can be improved.
> >
> > Of course full implementation of all mentioned optimizations (and maybe
> > even more) will take more than two month. But two month is sufficient to
> > implement general framework and some (the most promising) optimization
> > and test it. Of course the work done by others in the field of type
> > inference algorithms can be very helpful if it is open.
>
> I personally don't know of any type inference implementations that are as
> thorough as you want and that are publicly available.
Yes, may be there is no ready-to-use code, but there are some theoretical 
work.

> I realize I sound overly negative towards this proposal, but I just want
> you to realize that this is a difficult problem.
I like critique especially when it is constructive :-) It helps to find where 
I was wrong and what I forget.

> If you can pull it off, 
> wonderful! Optimized Python code would be a great thing.  And you should
> still send in your proposal.  I just think that the situation is more
> complex than you think.
I like difficult problems.

Thanks a lot for your replies !

-- 
          Best regards,
            Vladimir