[Python-Dev] Document performance requirements?

[Giovanni Bajo]

Armin Rigo wrote:

> 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).

I'm not sure big-O tells the whole truth. For instance, do we want to allow
an implementation to use a hash table as underlying type for a list? It
would match big-O requirements, but would still be slower than a plain array
because of higher overhead of implementation (higher constant factor).

And if this is allowed, I would like to find in CPython tutorials and
documentations a simple statement like: "to implement the list and match its
requirements, CPython choose a simple array as underlying data structure".
-- 
Giovanni Bajo