Why no documentation of basic data structure performance?

[brueckd at tbye.com]

On Tue, 12 Feb 2002, David Eppstein wrote:

> Does anyone else notice a serious lack of timing information in the Python
> documentation?

Not meaning to sound nit-picky, but languages can't have timing
information, but implementations can. My point is that information
would not necessarily be true for other implementations, e.g. Jython.

Maybe the best place for that sort of info would be in a note on the
specific implementation that accompanies the CPython distribution.

> documentation?  I have the impression that one of the biggest negative
> points for Python wrt other languages is the perception that it's slow, but
> that a lot of that perception may come from programmers not having a good
> model of how much time each Python operation takes

Possibly, but most of that perception is held by people who haven't
actually used Python that much, so timing info wouldn't help dispel the
myth much.

While the info you're talking about can be valuable in some cases, in most
cases it just doesn't matter, for example, which list operation you use -
and putting that sort of info in the main documentation encourages us to
think about optimization when we shouldn't. For example, if I'm not paying
attention I catch myself doing this too much:

meth = obj.method
for item in seq:
  meth(item)

Why? Because it saves a lookup to obj.method. But unless I'm trying to
remove a specific bottleneck I'm solving a non-problem and cluttering my
code at the same time. Shame on me!

> (Not that Python is alone in this lack -- can anyone tell me whether the
> Java Vector class uses a constant-amortized-time resizing strategy when not
> given a capacityIncrement initialization parameter?)

Again you won't and shouldn't see this in the API documentation, but in a
separate "implementation notes" doc or something.

Somebody had a Python optimization page I found useful (was it Skip?) -
maybe you could report your findings to him/her and have the page updated.
IMO, that's where this sort of info belongs - on a web page or document
that we can find when we need it but just far enough out of the way that
we don't spend too much time looking at it.

-Dave