[Python-Dev] Re: collections module

[Tim Peters]

[Terry Reedy]
> On enhancing list object: queue vs. deque.
>
> My general impression is that queues, while less common than stacks,
> are used enough in enough different algorithms that adding one
> implementation field to list headers so that pop(0) is an O(1)
> pointer move might be an overall win for Python.  The current O(n)
> move everything every time behavior is certainly a nuisance when
> queues are needed.

See the other msgs in this thread today -- I'm not convinced that queue-like
behavior can be supported that efficiently.

> Deques, on the other hand, seem to be more a theoretical construct.
> Algorithm books include them for completeness in describing possible
> list disciplines, but generally ignore them thereafter.  I am hard
> put to remember an algorithm that actually needs them.  They are
> certainly much rarer than queues.  So I do not think trying to make
> prepends O(1) should be considered further.

I expect that if queue-like behavior *can* be supported efficiently using an
always-contiguous vector, efficient dequeue-like behavior will fall out for
free.

> My possibly naive thought is that before reallocating, look at the
> ratio of left free to total.

I don't know what that means (neither the "left free" part nor what exactly
"total" is counting).  The devil is in the details here.

> If memmove would result in as much, or perhaps nearly as much,
> over-allocation as realloc,

memmove() leaves the total number of unused slots unchanged.  realloc can do
that too, or increase it by any amount, or decrease it by any amount.   I
just don't know what you're trying to say ... explain how it works, step by
step, in the

    q = [incoming() for i in range(1000)]
    while True:
        q.append(incoming())
        consume(q.pop(0))

example.

> then just do that.  Certainly if the ratio is small (like say .1),
> don't bother with memmove.  The exact cutoff is a tuning matter.
>
> Separate issue: for best performance, one would like to be able trade
> space for time and preallocate a large enough block so that most
> append faults result in a memmove back to the left.  Does the current
> builtin shrinkage discipline would allow this.  Or does "q=[0]*1000;
> q[:]=[]" shrink the space for q back to nearly nothing?

Python *offers* to give 992 slots back; whether the platform realloc()
accepts the offer is up to it.  In the "details are everything" department,
Python *also* creates a temp vector of length 1000, and copies all of q[:]
into it before it deletes any of q:  emptying a list is a linear-time
operation, not constant-time.  That's because it's not safe to decref
anything in a list while tearing it down (e.g., the list may be visible to a
__del__ method, which must not be allowed to see NULL pointers, or reclaimed
objects, in the list).

> (One might also want to do same for stack.  And yes, I remember:
> 'user tuning' is a 'bad idea'.  But....)