[issue44300] using Linked list vs dynamic array for LifoQueue class

[Raymond Hettinger]

Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:

Lists appends and pops are already amortized O(1) operations.  As they grow, they over-allocate by 12.5%.  When shrinking they reclaim memory when the size falls in half.  Together, these two strategies make lists efficient as a LIFO stack.

A straight linked list has worse performance across the board.  There would be an allocation on every append and deallocation on every pop.  Links tend to be scattered across memory causing cache locality to lost.  Also, links have more space overhead than the individual pointers used by a list.

If any change were to be made, it would likely be to use deque() instead of a list.  The timings in Tools/scripts/var_access_benchmark.py show that deques are slightly better than what we have now.  However, small deques take more space than small lists.  Also, deques are vastly outperformed by lists when running PyPy.  So we should stick with the very close second runner up.

----------
assignee:  -> rhettinger
nosy: +rhettinger
resolution:  -> not a bug
stage:  -> resolved
status: open -> closed

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44300>
_______________________________________