On Fri, 20 Mar 2020 06:50:29 -0700 Dan Stromberg <drsali...@gmail.com> wrote:
> On Thu, Mar 19, 2020 at 6:11 PM Cameron Simpson <c...@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 -- https://mail.python.org/mailman/listinfo/python-list