Re: [Python-Dev] python optimization
One possible way to improve the situation is, that if we really believe python cannot easily support such optimizations because the code is too "dynamic", is to allow manual annotation of functions. For example, gcc has allowed such annotations using __attribute__ for quite a while. This would allow the programmer to specify that a variable is constant, or that a function is pure (having no side effects). ___ 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] C coding experiment
On 9/1/05, Raymond Hettinger <[EMAIL PROTECTED]> wrote: > The goal is to determine whether the setobject.c implementation would be > improved by recoding the set_lookkey() function to optimize key > insertion order using Brent's variation of Algorithm D (See Knuth vol. > III, section 6.4, page 525). Brent's variation depends on the next probe position for a key being derivable just from the key and its current position. The use of perturbation in set_lookkey() prevents that, as we cannot say, given a key at a certain position, where the next probe location for that key would have been, without doing a complete lookup of that key (obviously too expensive). It would be interesting to see whether Brent's variation or perturbation give better expected overall performance -- the latter may well prove better in most cases, as it should reduce the number of probes needed for both successful and unsuccessful lookups, while Brent's variation only speeds up successful lookups. Well, this sort of question is what the experiment is meant to resolve, no? ___ 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] C coding experiment
Hi, > Brent's variation depends on the next probe position for a key being > derivable just from the key and its current position. The use of > perturbation in set_lookkey() prevents that, as we cannot say, given a > key at a certain position, where the next probe location for that key > would have been, without doing a complete lookup of that key > (obviously too expensive). I've been experimenting on this subject with Raymond H. You will find some code here: http://pitrou.net/python/sets/ - hash1.py is an algorithmic simulation of the current set implementation; it will give you statistics about e.g. the number of table walks in various test cases (that you can customize, of course) - hash2.py is a very crude benchmark of the set implementation - brent-patch.txt is a patch against CPython CVS to add Brent's variation to the set implementation; it made hash2.py between 5% slower and 2% faster depending on the test case I believe Raymond has since started experimenting on other approaches. Regards Antoine. ___ 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] python optimization
Neal Becker wrote: > One possible way to improve the situation is, that if we really believe > python cannot easily support such optimizations because the code is too > "dynamic", is to allow manual annotation of functions. For example, gcc > has allowed such annotations using __attribute__ for quite a while. This > would allow the programmer to specify that a variable is constant, or that > a function is pure (having no side effects). Raymond's constant binding decorator comes pretty close to achieving that: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/277940 It kicks in when the def statement is executed, rather than when the module is compiled, but that difference is not uncommon in Python (you don't know what half the names refer to until the top-level of the module is executed). Cheers, Nick. -- Nick Coghlan | [EMAIL PROTECTED] | Brisbane, Australia --- http://boredomandlaziness.blogspot.com ___ 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] C coding experiment
> -Original Message- > From: Andrew Durdin [mailto:[EMAIL PROTECTED] > Sent: Friday, September 16, 2005 8:25 AM > To: [EMAIL PROTECTED] > Cc: [email protected] > Subject: Re: [Python-Dev] C coding experiment > > On 9/1/05, Raymond Hettinger <[EMAIL PROTECTED]> wrote: > > The goal is to determine whether the setobject.c implementation would be > > improved by recoding the set_lookkey() function to optimize key > > insertion order using Brent's variation of Algorithm D (See Knuth vol. > > III, section 6.4, page 525). > > Brent's variation depends on the next probe position for a key being > derivable just from the key and its current position. The use of > perturbation in set_lookkey() prevents that, as we cannot say, given a > key at a certain position, where the next probe location for that key > would have been, without doing a complete lookup of that key > (obviously too expensive). Right. For Brent's variation to work, I've had to replace perturbation with a secondary hash function with linear spacing. > It would be interesting to see whether Brent's variation or > perturbation give better expected overall performance -- the latter > may well prove better in most cases, as it should reduce the number of > probes needed for both successful and unsuccessful lookups, while > Brent's variation only speeds up successful lookups. Well, this sort > of question is what the experiment is meant to resolve, no? Right again. I'm also experimenting with a simpler approach -- whenever there are more than three probes, always swap the new key into the first position and then unconditionally re-insert the swapped-out key. Most of the time that gives an improvement and it doesn't require changing the perturbation logic -- it is equivalent to changing the key insertion order. The only implementation wrinkle is that the approach needs separate lookup and insert functions (only the latter does the swap). The simpler approach is cheap to implement as it doesn't slow-down the first three probes. OTOH, te benefits are smaller than with Brent's variation -- it only relieves the worst collisions. I'm still interested in it because it helps the two most important use cases for sets (uniquification and membership testing). Raymond ___ 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] Compatibility between Python 2.3.x and Python 2.4.x
Rich Burridge wrote: >>And I forgot to give you this link: >>http://docs.python.org/whatsnew/whatsnew24.html > > > That lists the changes. It's not clear (at least to me) whether > these changes are incompatible. The section http://docs.python.org/whatsnew/node15.html is meant to cover incompatible changes. It shows that there is no 100% compatibility, but that only "borderline" code is affected. Probably the most significant change is that 0xC000 is now a positive number, when it used to be negative on 32-bit systems. Regards, Martin ___ 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] Python 2.5a1, ast-branch and PEP 342 and 343
I think this is mainly a question for Guido - where do we stand with respect to the ast-branch for Python 2.5? If we're targetting a March release for 2.5a1, then we probably need to land implementations for PEP 342 and PEP 343 at least a couple of months before that, and the current patches on Sourceforge are against HEAD, not ast-branch (for obvious reasons). So, not only does ast-branch need to be brought up to Python 2.4 compliance and checked for any memory leaks when compilation attempts fail (I suspect there are a few of those), but additional work is needed to implement PEP 342 and PEP 343 as well. For Python 2.4, Guido gave a target date well before the first alpha release for landing the ast-branch if it was going to be included. Is the same thing going to happen for Python 2.5 (setting the target date, that is - not the fact that the ast-branch didn't get included!) Cheers, Nick. -- Nick Coghlan | [EMAIL PROTECTED] | Brisbane, Australia --- http://boredomandlaziness.blogspot.com ___ 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] Variant of removing GIL.
Sokolov Yura wrote: > I think I know how to remove GIL Obviously I am an idiot. Not an idiot, just lazy :-) Please try to implement your ideas, and I predict that you will find: 1. it is a lot of work to implement 2. it requires changes to all C files, in particular to extension modules outside the Python source tree proper. 3. performing the conversion, even in a semi-mechanical way, will introduce many new bugs, in the form of race conditions because of missing locks. Optionally, you may also find that the performance of the interpreter will decrease. I haven't really tried to completely understand your proposal, but you are right, in principle, that a global lock can be replaced with more fine-grained locks. However, this is really hard to do correctly - if it were simple, it would have been done long ago. Regards, Martin ___ 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] Variant of removing GIL.
Martin> However, this is really hard to do correctly - if it were Martin> simple, it would have been done long ago. I don't believe difficulty is the only (or primary) barrier. I think *someone* would have tackled it since Greg Stein did back in 1.4(?) or his free-threading changes would have been incorporated into the core had they yielded speedups on multiprocessors and not hurt performance on uniprocessors. Skip ___ 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
