[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?
More information about the pypy-dev