Mailing List Archive: Python: Dev

compiler optimizations: collecting ideas

Index | Next | Previous | View Threaded

daniel.furrer at gmail

Nov 14, 2008, 6:27 AM

Post #1 of 6 (441 views)
Permalink

compiler optimizations: collecting ideas

Hello everybody,

As part of an advanced compiler design course at our university (ETH
Zurich), we have to implement an optimization (or various thereof).
I've spoken with a couple of people who are, like me, very fascinated by
Python.
So I would just like to ask if somebody has any ideas on what we could do?

Our constraints:
- We are 4 persons, each willing to potentially spend around 4-6 full days
of work.
- We've been working on generating Control Flow Graphs, generating Static
Single Assignment Form (inserting phi-nodes) and removing it again. We've
also implemented techniques like constant folding, copy propagation, Common
Subexpression Elimination etc.

We're looking for:
- Hints as to which python compiler would be best to work on. (The official
Python compiler package seems very nice to work with actually...)
- If there are any requests in the area of optimization that we could have a
look at

Any feedback would be highly appreciated as well as pointers to specific
bugs in the tracker and other relevant discussions.

Best regards,
Daniel

steve at pearwood

Nov 14, 2008, 7:06 AM

Post #2 of 6 (410 views)
Permalink

Re: compiler optimizations: collecting ideas [In reply to]

On Sat, 15 Nov 2008 01:27:54 am Daniel Furrer wrote:
[snip]
> We're looking for:
> - Hints as to which python compiler would be best to work on. (The
> official Python compiler package seems very nice to work with
> actually...) - If there are any requests in the area of optimization
> that we could have a look at

Even though the PEP has been rejected, I do like the idea of optimising
chains of if...elif:

http://www.python.org/dev/peps/pep-0275/

--
Steven
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

ncoghlan at gmail

Nov 14, 2008, 8:42 AM

Post #3 of 6 (407 views)
Permalink

Re: compiler optimizations: collecting ideas [In reply to]

Daniel Furrer wrote:
> Hello everybody,
>
> As part of an advanced compiler design course at our university (ETH
> Zurich), we have to implement an optimization (or various thereof).
> I've spoken with a couple of people who are, like me, very fascinated by
> Python.
> So I would just like to ask if somebody has any ideas on what we could do?
>
> Our constraints:
> - We are 4 persons, each willing to potentially spend around 4-6 full
> days of work.
> - We've been working on generating Control Flow Graphs, generating
> Static Single Assignment Form (inserting phi-nodes) and removing it
> again. We've also implemented techniques like constant folding, copy
> propagation, Common Subexpression Elimination etc.
>
> We're looking for:
> - Hints as to which python compiler would be best to work on. (The
> official Python compiler package seems very nice to work with actually...)
> - If there are any requests in the area of optimization that we could
> have a look at
>
> Any feedback would be highly appreciated as well as pointers to specific
> bugs in the tracker and other relevant discussions.

Some random (hopefully helpful) thoughts:
- the Python compiler package is a bit of a dead end (we dropped it for
Py3k because converting/maintaining two full compilers would have been a
lot of work and seemed somewhat redundant now that the AST can be
manipulated from Python code)
- 3.0's syntax is cleaner than that of 2.x (since some of the old
backward compatibility issues are gone), but 2.x is in more widespread
use (unsurprisingly, since 3.0 isn't even expected to be released until
next month)
- there is a branch in SVN where Thomas Lee (IIRC) is working on moving
some of the current optimisations from the bytecode generation phase
back to the AST generation phase.

Cheers,
Nick.

--
Nick Coghlan | ncoghlan[at]gmail.com | Brisbane, Australia
---------------------------------------------------------------
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

stefan_ml at behnel

Nov 14, 2008, 10:24 AM

Post #4 of 6 (397 views)
Permalink

Re: compiler optimizations: collecting ideas [In reply to]

Steven D'Aprano wrote:
> On Sat, 15 Nov 2008 01:27:54 am Daniel Furrer wrote:
> [snip]
>> We're looking for:
>> - Hints as to which python compiler would be best to work on. (The
>> official Python compiler package seems very nice to work with
>> actually...) - If there are any requests in the area of optimization
>> that we could have a look at
>
> Even though the PEP has been rejected, I do like the idea of optimising
> chains of if...elif:
>
> http://www.python.org/dev/peps/pep-0275/

As a side note: Cython does this optimisation and translates a series of
if-else statements (as well as "or" expressions) into C switch statements. The
speedup is pretty impressive at times.

Stefan

_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

stefan_ml at behnel

Nov 14, 2008, 10:59 AM

Post #5 of 6 (396 views)
Permalink

Re: compiler optimizations: collecting ideas [In reply to]

Daniel Furrer wrote:
> As part of an advanced compiler design course at our university (ETH
> Zurich), we have to implement an optimization (or various thereof).
> I've spoken with a couple of people who are, like me, very fascinated by
> Python.
> So I would just like to ask if somebody has any ideas on what we could do?

Plenty! :)

> Our constraints:
> - We are 4 persons, each willing to potentially spend around 4-6 full days
> of work.
> - We've been working on generating Control Flow Graphs, generating Static
> Single Assignment Form (inserting phi-nodes) and removing it again. We've
> also implemented techniques like constant folding, copy propagation, Common
> Subexpression Elimination etc.
>
> We're looking for:
> - Hints as to which python compiler would be best to work on. (The official
> Python compiler package seems very nice to work with actually...)

Cython is a Python-to-C compiler that is itself written in Python. It's good
enough to compile major parts of itself already, and the generated C code is
fast enough to challenge even experienced C programmers.

http://cython.org/

A really nice thing about Cython is that it targets efficient C code, not
optimised assembly. This allows Cython to focus its optimisations on things
that the C compiler cannot do, i.e. it tries to generate C code that makes it
clear to the C compiler what the intentions of the Python code were, and can
then leave the platform specific and low-level optimisations to the C compiler.

The optimisation infrastructure works in tree transformations through the
Visitor pattern, so it's actually quite simple to add new optimisations. A
couple of examples:

http://hg.cython.org/cython-devel/file/tip/Cython/Compiler/Optimize.py
http://hg.cython.org/cython-devel/file/tip/Cython/Compiler/AutoDocTransforms.py

> - If there are any requests in the area of optimization that we could have a
> look at

Our Wiki has a some (more or less up-to-date) enhancement proposals (CEPs):

http://wiki.cython.org/enhancements

But a major thing that Cython currently lacks (and that would definitely allow
many new optimisations) is a real Control Flow Graph. It has some initial flow
control tracking, but that mainly targeted variable initialisation at the
time. Many other optimisations, especially type inference attempts, largely
depend on better flow control tracking.

There are some initial thoughts here:

http://wiki.cython.org/enhancements/FlowGraph

It's not very complete yet, but this is definitely something that is worth
some more discussion on our mailing list.

Stefan

_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

dreamingforward at gmail

Nov 14, 2008, 2:07 PM

Post #6 of 6 (400 views)
Permalink

Re: compiler optimizations: collecting ideas [In reply to]

"Daniel Furrer" <daniel.furrer[at]gmail.com> wrote:
> As part of an advanced compiler design course at our university (ETH
> Zurich), we have to implement an optimization (or various thereof).
> I've spoken with a couple of people who are, like me, very fascinated by
> Python.
> So I would just like to ask if somebody has any ideas on what we could do?
>
> - We've been working on generating Control Flow Graphs, generating Static
> Single Assignment Form (inserting phi-nodes) and removing it again. We've
> also implemented techniques like constant folding, copy propagation, Common
> Subexpression Elimination etc.

How about a graphical program-visualization meta-tool that would allow
making optimizations (as well as debugging) easier. Take your control
flow graph data put it into fractal or recursive/foldable graphical
"cloud" and visualize the running program therein. Find interesting
audio and visual constructs (color, intensity, etc) to isomorphically
map interesting programming data into non-arbitrary visual iconography
and design. Each entrance into a code-block is like a photon entering
a molecular form, and as more photons enter a given block in a given
time frame, heat is generated in that code block, causing it to glow
for an amount of time. Code that runs for a long time, glows as it is
run. If it returns a value all that warmth in the code block gets
turned into a flash of light and the code-block goes dark again. The
description is pretty sloppy, but I know there's a killer app there
somewhere. I've been wanting such a tool for awhile. (Imagine using
such a tool with a powerful abstract language like LISP. It would
remove all the obtuse parenthetical list expressions and put it into a
graphical visual language where nodes consisting of subgraphs could be
moved around as needed. Language syntax would become more-or-less
obsolete!)

Go even further and imagine the internet in such a cloud, where users
can navigate by looking at "heat" activity therein. Each time a user
visits and "looks" at a given site eventually condenses into "water"
and you have pools of interest....

Please tell me this is a cool idea or not so I don't wonder why no one
else is thinking about such things. And on your way, save the
world... Oh, and, if it is a cool idea, is there any company
interested in hiring? haha

marcos
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact lists@gossamer-threads.com