[Python-Dev] Document performance requirements?

[Armin Rigo]

Hi Giovanni,

On Sun, Jul 23, 2006 at 03:30:50PM +0200, Giovanni Bajo wrote:
> 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).

A big-O difference can make the difference between a program that takes
0.5 seconds or 2 hours to run.  This is more important than a constant
factor difference, which different implementations are bound to exhibit
anyway.

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

Yes, the big-O notes don't have to be too technical: the docs should
tell people to think about Python lists as simple arrays, and the O
requirements follow naturally.


A bientot,

Armin