queue versus list

[Dan Sommers]

On Fri, 20 Mar 2020 06:50:29 -0700
Dan Stromberg <drsalists at gmail.com> wrote:

> On Thu, Mar 19, 2020 at 6:11 PM Cameron Simpson <cs at cskk.id.au> wrote:
> 
> > >> 4. If it doesn't need to be thread-safe, why not try deques instead?
> > >
> > >Bingo. Performance is indistinguishable from that of the list.
> >
> > A deque is implement using a list.
> >
> 
> Actually, I think a deque is a doubly linked list of python lists.

According to the source¹:

    Data for deque objects is stored in a doubly-linked list of fixed
    length blocks.

    [...]

    Textbook implementations of doubly-linked lists store one datum per
    link, but that gives them a 200% memory overhead (a prev and next
    link for each datum) and it costs one malloc() call per data
    element.  By using fixed-length blocks, the link to data ratio is
    significantly improved and there are proportionally fewer calls to
    malloc() and free().  The data blocks of consecutive pointers also
    improve cache locality.

¹ https://github.com/python/cpython/blob/3.8/Modules/_collectionsmodule.c#L19-L78

Dan

-- 
“Atoms are not things.” – Werner Heisenberg
Dan Sommers, http://www.tombstonezero.net/dan