This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: using Linked list vs dynamic array for LifoQueue class
Type: performance Stage: resolved
Components: Library (Lib) Versions: Python 3.11
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: euromike21, rhettinger
Priority: normal Keywords:

Created on 2021-06-03 14:41 by euromike21, last changed 2022-04-11 14:59 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
main.py euromike21, 2021-06-03 14:41
Messages (2)
msg395004 - (view) Author: Mihai Ion (euromike21) * Date: 2021-06-03 14:41
Switching to Linked list data structure for improving performance append() and pop() run time complexity when eliminating dynamic array resizing
msg395062 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-06-04 02:27
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.
History
Date User Action Args
2022-04-11 14:59:46adminsetgithub: 88466
2021-06-04 02:27:44rhettingersetstatus: open -> closed

assignee: rhettinger

nosy: + rhettinger
messages: + msg395062
resolution: not a bug
stage: resolved
2021-06-03 14:41:35euromike21create