[Python-Dev] 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 ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] compiler optimizations: collecting ideas
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 [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] compiler optimizations: collecting ideas
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 | [EMAIL PROTECTED] | Brisbane, Australia --- ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
[Python-Dev] Summary of Python tracker Issues
ACTIVITY SUMMARY (11/07/08 - 11/14/08) Python tracker at http://bugs.python.org/ To view or respond to any of the issues listed below, click on the issue number. Do NOT respond to this message. 2179 open (+31) / 13969 closed (+15) / 16148 total (+46) Open issues with patches: 716 Average duration of open issues: 713 days. Median duration of open issues: 2016 days. Open Issues Breakdown open 2162 (+31) pending17 ( +0) Issues Created Or Reopened (49) ___ re module treats raw strings as normal strings 11/11/08 http://bugs.python.org/issue4185reopened akuchling cycle created by profile.run 11/07/08 http://bugs.python.org/issue4273reopened benjamin.peterson Version Checker 11/07/08 http://bugs.python.org/issue4280created cjw Idle - incorrectly displaying a character (Latin capital letter 11/08/08 CLOSED http://bugs.python.org/issue4281reopened amaury.forgeotdarc exec(unicode): invalid charset when #coding:xxx spec is used 11/08/08 http://bugs.python.org/issue4282created shidot patch "python3.0 setup.py install --user" raises AttributeError11/08/08 CLOSED http://bugs.python.org/issue4283created hagen patch Python 2.6 64-bit + Vista 64 = Bad MSVCRT11/08/08 CLOSED http://bugs.python.org/issue4284created DaGoodBoy Use a named tuple for sys.version_info 11/09/08 http://bugs.python.org/issue4285created brett.cannon easy Discrepancy in format string documentation 11/09/08 CLOSED http://bugs.python.org/issue4286created dlfjessup Broken URL in documentation style guide 11/09/08 CLOSED http://bugs.python.org/issue4287created facorreia parsermodule and grammar variable11/09/08 http://bugs.python.org/issue4288created rpetrov patch Python 2.6 installer crashes when selecting 'advanced' and cance 11/09/08 http://bugs.python.org/issue4289created fabioz 2to3 fails with sympy11/09/08 CLOSED http://bugs.python.org/issue4290created certik Allow Division of datetime.timedelta Objects 11/09/08 http://bugs.python.org/issue4291created Jeremy Banks 2to3 fails to convert "from something import (a, b, c)" 11/10/08 CLOSED http://bugs.python.org/issue4292created certik patch Thread Safe Py_AddPendingCall11/10/08 http://bugs.python.org/issue4293created krisvale patch, patch Macros for PyLong: sign, number of digits, fits in an int11/10/08 http://bugs.python.org/issue4294created haypo patch closing stdout in a child process on cygwin means that process d 11/10/08 http://bugs.python.org/issue4295created zooko Python assumes identity implies equivalence; contradicts NaN 11/11/08 CLOSED http://bugs.python.org/issue4296created mikecurtis patch Add error_log attribute to optparse.OptionPars
Re: [Python-Dev] compiler optimizations: collecting ideas
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 [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] compiler optimizations: collecting ideas
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 [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] compiler optimizations: collecting ideas
"Daniel Furrer" <[EMAIL PROTECTED]> 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 [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
[Python-Dev] datetime and timedelta enhancement
Hi, There are some interresting tickets about the datetime module: #1673409: datetime module missing some important methods #1083: Confusing error message when dividing timedelta using / #2706: datetime: define division timedelta/timedelta #4291: Allow Division of datetime.timedelta Objects Wanted features: 1- convert a datetime object to an epoch value (numbers of seconds since the 1st january 1970), eg. with a new totimestamp() method 2- convert a timedelta to a specific unit (eg. seconds, days, weeks, etc.) 3- compute the ratio of two timedelta, eg. for a progress bar -- About (1), no patch is available yet. Some points are not fixed yet: a- use an integer to avoid floating point problems? b- use a float to keep the microseconds? c- limit the datetime to the time_t type (32 bits signed integer)? Which mean the following range: >>> from datetime import datetime, timedelta >>> t0 = datetime(1970, 1, 1, 0, 0, 0) >>> print t0 + timedelta(seconds=-2**31), "-", t0 + timedelta(seconds=2**31-1) 1901-12-13 20:45:52 - 2038-01-19 03:14:07 The following point may answer to questions (a) and (b)... -- For the points (2) and (3): webograph and belopolsky proposed to use the division of two timedelta objects. Examples (using the patch attached to #2706): >>> from __future__ import division >>> from datetime import datetime, timedelta >>> one_second = timedelta(seconds=1) >>> print timedelta(hours=1, minutes=1, microseconds=3) / one_second 3660.03 >>> print timedelta(hours=1, minutes=1, microseconds=3) // one_second 3660 >>> print divmod(timedelta(hours=1, minutes=1, microseconds=3), one_second) (3660L, datetime.timedelta(0, 0, 3)) We have the float representation, the integer part of the division, and the integer part + the remainder as a timedelta object. You have the choice to use the best format for your needs :) Use another denominator to get other units, eg. weeks = dt / timedelta(days=7) Then come the question of the accepted types: timedelta / float? divmod(timedelta, int)? etc. -- About the conversion of a datetime object to time_t, the division can be reused like that: >>> epoch = datetime.fromtimestamp(0) >>> print epoch 1970-01-01 01:00:00 >>> d = datetime.fromtimestamp(34930.5) >>> (d - epoch) / timedelta(seconds=1) # integer 34930.5 >>> (d - epoch) // timedelta(seconds=1) # float 34930L datetime.totimestamp() can be implemented to produce a float in range [-2**31; 2**31-1]. Why a float? To be symetric with fromtimestamp()! If you need older/newer timestamp or you want integers, use the examples with the divison. -- Victor Stinner aka haypo http://www.haypocalc.com/blog/ ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] datetime and timedelta enhancement
> datetime.totimestamp() can be implemented to produce a float in range > [-2**31; 2**31-1] An implementation of this method is proposed as a patch in issue #2736. -- Victor Stinner aka haypo http://www.haypocalc.com/blog/ ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] datetime and timedelta enhancement
> 1- convert a datetime object to an epoch value (numbers of seconds since >the 1st january 1970), eg. with a new totimestamp() method > 2- convert a timedelta to a specific unit (eg. seconds, days, weeks, etc.) Another solution is proposed by Christian Heimes: "implement __int__ and __float__ on timedelta objects: int(timedelta) -> seconds, float(timedelta) -> seconds.micros". This solution only answer to the need "conversion to seconds" (which is the most common case). To get week, you would have to write: int(dt) / (3600*24*7) which feels me less natural (pythonic?) than: dt // timedelta(days=7) -- Victor Stinner aka haypo http://www.haypocalc.com/blog/ ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] datetime and timedelta enhancement
Le Saturday 15 November 2008 02:01:42 Victor Stinner, vous avez écrit : > > 1- convert a datetime object to an epoch value (numbers of seconds since > >the 1st january 1970), eg. with a new totimestamp() method > > 2- convert a timedelta to a specific unit (eg. seconds, days, weeks, > > etc.) > > Another solution is proposed by Christian Heimes: "implement __int__ > and __float__ on timedelta objects (...) The solution was implemented as patch in: http://bugs.python.org/issue1665292 The issue is closed and there was a problem with hash(): timedelta(0, 1) == 1 but hash(timedelta(0, 1)) != hash(1) -- Victor Stinner aka haypo http://www.haypocalc.com/blog/ ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
[Python-Dev] Getting Set Up doc now online
The Setup doc I sent to the list a little while back has now been put online at http://www.python.org/dev/setup/ . I also fleshed out the dev FAQ so that technical details are all in there while the Setup doc just outlines basically key points. -Brett ___ Python-Dev mailing list [email protected] http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
