[Python-Dev] Document performance requirements?

[Armin Rigo]

Hi,

On Sat, Jul 22, 2006 at 12:33:45PM +1000, Nick Coghlan wrote:
> Agreed, but there's more to doing that than just writing down the O() implied 
> by the current CPython implementation - it's up to Guido to decide which of 
> the constraints are part of the language definition, and which are 
> implementation accidents

I think that O-wise the current CPython situation should be documented
as a "minimal requirement" for implementations of the language, with
just one exception: the well-documented "don't rely on this" hack in 2.4
to make repeated 'str += str' amortized linear, for which the 2.3
quadratic behavior is considered compliant enough.

I suppose that allowing implementations to provide better algorithmic
complexities than required is fine, although I can think of some
problems with that (e.g. nice and efficient user code that would perform
horribly badly on CPython).


Armin