queue versus list
Dan Sommers
2QdxY4RzWzUUiLuE at potatochowder.com
Fri Mar 20 10:12:45 EDT 2020
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
More information about the Python-list
mailing list