List Performance

[Gerhard Häring]

Larry Bates wrote:
> [...]
> So its actually faster to append to a long list than an empty one?  That 
> certainly would not have been intuitively obvious now would it?

Maybe not intuitively, but if you know how dynamically growing data 
structures are implemented, it's plausible. They overallocate, and the 
amount of overallocation is dependent on the current size. Relevant 
source snippet from Python 2.6:

     /* This over-allocates proportional to the list size, making room
      * for additional growth.  The over-allocation is mild, but is
      * enough to give linear-time amortized behavior over a long
      * sequence of appends() in the presence of a poorly-performing
      * system realloc().
      * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
      */
     new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

If, on the other hand, we knew beforehand how big the list will get 
approximately, we could avoid all these reallocations. No problem with 
Python's C API:

PyAPI_FUNC(PyObject *) PyList_New(Py_ssize_t size);

But you can't do it directly from Python, unless you (ab)use ctypes.

-- Gerhard