[pypy-dev] [pypy-commit] pypy default: issue1059 testing

Carl Friedrich Bolz cfbolz at gmx.de
Tue Feb 21 17:21:45 CET 2012

On 02/20/2012 06:50 PM, Alex Gaynor wrote:
 > Unfortunately this commit has some bad effects.  Going through an
 > iterator in popitem() will result in O(N**2) behavior for repeated
 > calls.  If you look at the r_dict implementation of popitem() you can
 > see the fix there.

This is just the default implementation for the DictStrategy base class. 
All interesting subclasses override this default. The segfault happened 
because the dict proxy strategy doesn't override it.

So yes, calling A.__dict__.popitem repeatedly for a class A is O(N**2). 
Do we care?


Carl Friedrich

More information about the pypy-dev mailing list