Bytecode optimisation

[Corran Webster]

In article <m3k8u6aj7i.fsf at atrus.jesus.cam.ac.uk>,
Michael Hudson  <mwh21 at cam.ac.uk> wrote:
>cwebster at math.tamu.edu (Corran Webster) writes:
>
>I'm impressed (and slightly scared - people are actually *using* my
>code...).

I think your code is potentially the most interesting development in the
past few months - it has a _lot_ of potential.  A couple of other
possibilities for using bytecodehacks which have occurred to me include:

  * A bytecode assembler - might give more speed in critical places
    without having to go to C.  Also allow you to make Python dump
    core when you mess up  :)

  * A back-end to John Aycock's little languages package to write
    Python bytecode.  I haven't looked closely at this, so it may already
    be done or easily done without bytecodehacks.  PyJava, anyone?

And it seems that there must be other useful macros and hacks out there.

>Have you looked at Skip Montanaro's optimizer:
>
>http://www.automatrix.com/~skip/python/spam7/optimizer.html
>
>This does some similar work. Unfortunately is distributed as a patch
>against Python 1.4 sources, so I had to hack at it with sed to get the
>bits I was interested in out.

Thanks.  Looking at the web page, there is a version which is patched
against 1.5.1.

>>   * Optimisation is probably only worthwhile when speed is essential.
>
>Isn't this a tautology? Repest after me "Premature optimization is
>..."

Maybe it is a tautology the way I wrote it :)

But what I meant is that in it's present state at least, this is not
something you want to be doing every time you compile to bytecode.  If
the cost of optimisation was small or the gains were large, then you
may as well just automatically optimise.

But it ain't there yet.

>>   * More complex optimisation is certainly possible, although a lot more 
>>     work would be required.  I've made a first stab at block-level analysis
>>     and it seems feasible.  In particular it would be nice to detect and 
>>     shift loop invariant code.
>
>The problem is you can't, at least not without potentially changing
>the meaning of the code.

I'm well aware of this :)  It will require some amount of type-guessing,
but since it'll need data flow analysis in any case, the additional cost
may not be excessive.

Or as I mentioned in my reply to Mark-Andre Lemburg, there may be a case
for an optimisation level which assumes sanity for many standard things,
so that

for x in range(1000):
  for y in range(1000):
    do_stuff()

could assume that do_stuff() doesn't change the meaning of range and so
this could be optimised to:

r = range(1000)
for x in r:
  for y in r:
    do_stuff()

>I was thinking that maybe you could `tag' variables as numeric or
>commutative or whatever like so:
>
>def func(x):
>    numeric(x)
>    c = 0
>    while c < 1:
>        c = c + (x*x - 2) # could be hoisted
>
>Then a bytecodehacks optimizer would strip the tags out but could use
>the information so gleaned to perform more sophisticated
>optimizations.

'assert' seems the right way to do this.  This could be written:

def func(x):
  assert operator.isNumberType(x)
  ...

and something like this is easy to spot in bytecode.  It does again assume
standard meanings for 'operator' and 'types', though.

>if-you-get-better-than-twenty-percent-speed-up-I'll-be-impressed-ly y'rs 
>Michael

and-I'll-be-as-impressed-as-you-are-if-I-do-ly y'rs
Corran