Mailman 3 April 2003 - Python-Dev

RE: [Python-Dev] Dictionary tuning
by Skip Montanaro 29 Apr '03

29 Apr '03

>> Have you guys tried out the patch? I'm very interested in getting >> results from different benchmarks, processors, cache sizes, and >> various operating systems. Tim> If I can find the time I will. We're in crunch time on my project Tim> at the moment ... I'm somewhat over-allocated :( Can't you just head over to Dunkin' Donuts and resize? ;-) Skip

2 1

proposed amendments to PEP 1
by David Goodger 29 Apr '03

29 Apr '03

The following paragraph is from PEP 1, "PEP Work Flow" section: Once the authors have completed a PEP, they must inform the PEP editor that it is ready for review. PEPs are reviewed by the BDFL and his chosen consultants, who may accept or reject a PEP or send it back to the author(s) for revision. I propose adding the following text: ... The BDFL may also initiate a PEP review, first notifying the PEP author(s). In addition, I think it would be useful to add some text describing the PEP acceptance criteria. Something like the following: For a PEP to be accepted it must meet certain minimum criteria. It must be a clear description of the proposed enhancement. The enhancement must represent a net improvement. The implementation, if applicable, must be solid and must not complicate the interpreter unduly. Finally, a proposed enhancement must be "pythonic" in order to be accepted by the BDFL. (However, "pythonic" is an imprecise term; it may be defined as whatever is acceptable to the BDFL. This logic is intentionally circular.) See PEP 2 for standard library module acceptance criteria. Please comment. -- David Goodger <http://starship.python.net/~goodger> Python Enhancement Proposal (PEP) Editor <http://www.python.org/peps/> (Please cc: all PEP correspondence to <peps(a)python.org>.)

3 7

Re: [Python-Dev] proposed amendments to PEP 1
by Aahz 29 Apr '03

29 Apr '03

On Mon, Apr 28, 2003, Raymond Hettinger wrote: > > From these proposals and the annoucement earlier this week, > I sense a desire to have fewer peps and to more rapidly get > them out of the draft status. There's some truth to that. OTOH, until the BDFL declares something to be an ex-PEP, I don't think BDFL rejection of a PEP means that it is forever dead -- it just requires substantial revision to resurrect it. The point of PEPs is to prevent rehashing of old subjects in the same way, not to prevent new ideas from restarting discussions. -- Aahz (aahz(a)pythoncraft.com) <*> http://www.pythoncraft.com/ "In many ways, it's a dull language, borrowing solid old concepts from many other languages & styles: boring syntax, unsurprising semantics, few automatic coercions, etc etc. But that's one of the things I like about it." --Tim Peters on Python, 16 Sep 93

2 1

RE: [Python-Dev] Dictionary tuning
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

> From: Tim Peters [mailto:tim.one@comcast.net] > > [Delaney, Timothy C] > > That's what I was getting at. I know that (for example) most > > classes I create have less that 16 entries in their __dict__. > > With this change, each class instance would take (approx) twice > > as much memory for its __dict__. I suspect that class instance > > __dict__ is the most common dictionary I use. > > Do they have fewer then 6 entries? Dicts with 5 or fewer > entries don't > change size at all (an "empty dict" comes with room for 5 entries). No hard and fast data here. That would require grovelling through code ;) I was making an quick estimate. Off the top of my head, most classes I create have ... __init__ 3-5 other methods 3-5 instance attributes Hmm - that would only be 3-5 instance __dict__ entries, with 4-6 class __dict__ entries, correct? I was forgetting that methods are put into the instance __dict__. Bah - it's too late. It's the end of the day, and I've barely managed to get 2 hours real work done. Tim Delaney

2 1

RE: [Python-Dev] Thoughts on -O
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

> From: Daniel Berlin [mailto:dberlin@dberlin.org] > > > > 1. Any new optimisation must be introduced on the optimised path. > > > > 2. Optimisations may be promoted from the optimised path to the > > vanilla path at BDFL discretion. > > > > 3. Experimental optimisations in general will required at least one > > complete release before being promoted from the optimised > path to the > > vanilla path. > > Before everyone gets too far, are there actually concrete separate > optimizations we are talking about here? > Or is this just "in case someone comes up with an optimization that > helps" One I had in mind would be the CALL_ATTR patch, which Guido explicitly mentioned as having been implemented on the main path, not on the optimised path, and pointed out that if it had been implemented only on the optimised path a number of issues with it would have been discovered much earlier. > The only one that makes any appreciable difference is Psyco Indeed. I would love Psyco to eventually be part of Python, but suspect it will only be so in the PyPy implementation. > To put all of this in context, i'm assuming you aren't looking for > 5-10% gains, total. Instead, i'm assuming you are looking for very > significant speedups (100% or greater). Many of the recent optimisation patches have involved 5% speedups in some cases. If they all worked without impacting each other (cache effects, etc) we could probably approach 50% improvement in some cases. I have no problems if someone can get a 5% speedup across the board without introducing incredibly hairy code. I would like such optimisations to eventually become part of the main path - but I would prefer that it not become part of the main path until it has been exposed to many different environments - assuming the implementor or someone else can't come up with one or more cases where it becomes a pessimisation. > If you only want 5-10%, that's easy to do at just the bytecode level, > but you eventually hit the limit of the speed of bytecode execution, > and from experience, you will hit it rather quickly. Indeed. Every attempt so far has either been in the 5% improvement or less, standalone, and most have resulted in worse performance when combined. Tim Delaney

2 1

RE: [Python-Dev] Dictionary tuning
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

> From: Guido van Rossum [mailto:guido@python.org] > > > I've experimented with about a dozen ways to improve dictionary > > performance and found one that benefits some programs by up to > > 5% without hurting the performance of other programs by more > > than a single percentage point. > > > > It entails a one line change to dictobject.c resulting in a new > > schedule of dictionary sizes for a given number of entries: > > > > Number of Current size Proposed size > > Filled Entries of dictionary of dictionary > > -------------- ------------- ------------- > > [-- 0 to 5 --] 8 8 > > [-- 6 to 10 --] 16 32 > > [-- 11 to 21 --] 32 32 > > [-- 22 to 42 --] 64 128 > > [-- 43 to 85 --] 128 128 > > [-- 86 to 170 --] 256 512 > > [-- 171 to 341 --] 512 512 > > I suppose there's an "and so on" here, right? I wonder if for > *really* large dicts the space sacrifice isn't worth the time saved? What is the effect on peak memory usage over "average" programs? This might be a worthwhile speedup on small dicts (up to a TBD number of entries) but not worthwhile for large dicts. However, to add this capability in would of course add more code to a very common code path (additional test for current size to decide what factor to increase by). > I tried the patch with my new favorite benchmark, startup time for > Zope (which surely populates a lot of dicts :-). It did give about > 0.13 seconds speedup on a total around 3.5 seconds, or almost 4% > speedup. Nice (in relative, not absolute terms). Do we have any numbers on memory usage during and after that period? Tim Delaney

4 4

Thoughts on -O
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

Was doing some thinking in the shower this morning, and came up with some ideas for specifying optimisation. These are currently quite nebulous thoughts ... We have the current situation: -O only removes asserts -OO removes asserts and docstrings. I think this is an ideal time to revisit the purpose of -O for 2.4 or later. IMO the "vanilla" mode should be a "release" mode. Users should not have to use a command-line option to gain "release" optimisations such as asserts. I would propose that we have the following modes for python to work in. 1. Release/Production mode (no command-line switch) - asserts are turned off - well-tested/stable optimisations are included - possibly additional things, such as not calling trace functions 2. Optimised mode (-O) - more experimental optimisations are included i.e. those that may have performance improvements in some cases, but penalties in others, etc - may possibly split this up so individual optimisations can be turned on and off as required - this would leave -O by itself as a no-op 3. Docstring elimination mode (-OO) - may be specified in addition to optimised mode - it does not imply optimised mode 4. Debug mode (-D?) - will be the slowest mode - no optimisations - cannot be called with either -O or -OO - turns on asserts - turns on trace functions I would see Debug mode being used by developers in unit tests, code coverage, etc. .pyc and .pyo files would need to know which optimisations they were compiled with so that if they would be loaded again with the "wrong" optimisations they would be re-compiled. Anyway, any thoughts, rebuttals, etc would be of interest. I'd like to get some discussion before I create a PEP. Cheers. Tim Delaney

3 2

RE: [Python-Dev] Thoughts on -O
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

> From: Guido van Rossum [mailto:guido@python.org] > > > -OO removes asserts and docstrings. > > > > I think this is an ideal time to revisit the purpose of -O > for 2.4 or later. > > Hm, I would think we can wait until after 2.3 is released, lest we be > tempted to "push one more feature into 2.3". I have absolutely *no* intention of pushing any of this for 2.3. Good lord no. For a start, these would be major feature changes ... > > IMO the "vanilla" mode should be a "release" mode. Users should not > > have to use a command-line option to gain "release" optimisations > > such as asserts. > > I strongly disagree, and I expect most Python users would. I think > this idea of a default harks back to the time when computers were slow > and you would put on your special debugging hat only when you had a > problem you couldn't solve by thinking about it. These days, often > you don't care about the small gain in speed that -O or even -OO > offers, because the program runs fast enough; but often you *do* care > about the extra checks that assert offers. (I know I do.) True. I'm ambivalent about that myself. But in that case, I would argue instead that there should not be any option to remove asserts. > > .pyc and .pyo files would need to know which optimisations they were > > compiled with so that if they would be loaded again with the "wrong" > > optimisations they would be re-compiled. > > That's what the difference between .pyc and .pyo was intended to > convey; IMO this was a mistake. Yep - I know this. I would actually suggest removing .pyo and simply have the info held in the .pyc. > > Anyway, any thoughts, rebuttals, etc would be of interest. I'd like > > to get some discussion before I create a PEP. > > I'm not convinced that we need anything, given the minimal effect of > most currently available optimizations. One of my options is to create a PEP specifically to have it rejected. However, I think there are definitely a couple of useful things in here. In particular, it provides a path for introducing optimisations. One of the complaints I have seen recently is that all optimisations are being added to both paths. Perhaps this could be reduced to a process PEP with the following major points: 1. Any new optimisation must be introduced on the optimised path. 2. Optimisations may be promoted from the optimised path to the vanilla path at BDFL discretion. 3. Experimental optimisations in general will required at least one complete release before being promoted from the optimised path to the vanilla path. Tim Delaney

2 1

RE: [Python-Dev] Dictionary tuning
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

> From: Tim Peters [mailto:tim.one@comcast.net] > > That doesn't make sense. Dicts can be larger after the > patch, but never > smaller, so there's nothing opposing the "can be larger" > part: on average, > allocated address space must be strictly larger than before. > Whether that > *matters* on average to the average user is something we can answer > rigorously just as soon as we find an average user with an > average program > <wink>. I'm not inclined to worry much about it. That's what I was getting at. I know that (for example) most classes I create have less that 16 entries in their __dict__. With this change, each class instance would take (approx) twice as much memory for its __dict__. I suspect that class instance __dict__ is the most common dictionary I use. > >> This might be a worthwhile speedup on small dicts (up to a TBD > >> number of entries) but not worthwhile for large dicts. > > > Actually, it helps large dictionaries even more that small > dictionaries. > > Collisions in large dicts are resolved through other memory probes > > which are almost certain not to be in the current cache line. > > That part makes sense. Resizing a large dict is an expensive > operation too. That's not what I meant. Most dictionaries are fairly small. Large dictionaries are common, but I doubt they are common enough to offset the potential memory loss from this patch. Currently if you go one over a threshold you have a capacity of 2*len(d)-1. With the patch this would change to 4*len(d)-1 - very significant for large dictionaries. Thus my consideration that it might be worthwhile for smaller dictionaries (depending on memory memory characteristics) but not for large dictionaries. Perhaps we need to add some internal profiling, so that "quickly-growing" dictionaries get larger reallocations ;) > Since the body of the loop isn't entered often, unpredictable one-shot > branches within the body shouldn't have a measurable effect. The > unpredictable branches when physically resizing the dict will > swamp them > regardless. The surrounding if-test continues to be > predictable in the > "branch taken" direction. I didn't look at the surrounding code (bad Tim D - thwack!) but in this case I would not expect an appreciable performance loss from this. However, the fact that we're getting an appreciable performance *gain* from changes on this branch suggests that it might be slightly more vulnerable than expected (but should still be swamped by the resize). > What could be much worse is that stuffing code into the > if-block bloats the > code so much as to frustrate lookahead I-stream caching of the normal > "branch taken and return 0" path: > > if (mp->ma_used > n_used && mp->ma_fill*3 >= > (mp->ma_mask+1)*2) { > if (dictresize(mp, mp->ma_used*2) != 0) > return -1; > } > return 0; > > Rewriting as > > if (mp->ma_used <= n_used || mp->ma_fill*3 < (mp->ma_mask+1)*2) > return 0; > > return dictresize(mp, mp->ma_used*2) ? -1 : 0; > > would help some compilers generate better code for the > expected path, and > especially if the blob after "return 0;" got hairier. I find that considerably easier to read in any case ;) Cheers. Tim Delaney

3 2

RE: [Python-Dev] Dictionary tuning
by Delaney, Timothy C (Timothy) 29 Apr '03

29 Apr '03

> From: Raymond Hettinger [mailto:python@rcn.com] > > [Timothy Delaney] > > That's what I was getting at. I know that (for example) most > > classes I create have less that 16 entries in their __dict__. > > With this change, each class instance would take (approx) twice > > as much memory for its __dict__. I suspect that class instance > > __dict__ is the most common dictionary I use. > > Those dicts would also be the ones benefitting from the patch. > Their density would be halved; resulting in fewer collisions, > improved search times, and better cache performance. No question that they would benefit. The question is whether the benefit outweighs the possible penalties. Of course, we can't evaluate that until we've got some data ... > [Timothy Delaney] > > Perhaps we need to add some internal profiling, so that > > "quickly-growing" dictionaries get larger reallocations ;) > > I came up with this patch a couple of months ago and have > since tried every tweak I could think of (apply to this size > dict but not that one, etc) but found nothing that survived > a battery of application benchmarks. Note the smiley. Not at all intended seriously - the extra complication would almost certainly eliminate any possible performance gains. > Have you guys tried out the patch? I'm very interested in > getting results from different benchmarks, processors, > cache sizes, and various operating systems. If I can find the time I will. We're in crunch time on my project at the moment ... I'm somewhat over-allocated :( In case I forgot to mention it - I like the ideas in the patch, and really like the performance improvement. But with the things I'm doing at the moment, memory is proving more of a bottleneck than performance ... once we start hitting virtual memory, you can forget about a 5% performance improvement ... Tim Delaney

1 0