using Linked list vs dynamic array for LifoQueue class

[euromike21]

BPO	44300
Nosy	@rhettinger, @euromike21
Files	main.py

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2021-06-04.02:27:44.921>
created_at = <Date 2021-06-03.14:41:35.629>
labels = ['invalid', '3.11', 'library', 'performance']
title = 'using Linked list vs dynamic array for LifoQueue class'
updated_at = <Date 2021-06-04.02:27:44.918>
user = 'https://github.com/euromike21'

bugs.python.org fields:

activity = <Date 2021-06-04.02:27:44.918>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2021-06-04.02:27:44.921>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2021-06-03.14:41:35.629>
creator = 'euromike21'
dependencies = []
files = ['50086']
hgrepos = []
issue_num = 44300
keywords = []
message_count = 2.0
messages = ['395004', '395062']
nosy_count = 2.0
nosy_names = ['rhettinger', 'euromike21']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue44300'
versions = ['Python 3.11']

[euromike21]

Switching to Linked list data structure for improving performance append() and pop() run time complexity when eliminating dynamic array resizing

[rhettinger]

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.