test/refactor: use test deque to avoid quadratic iteration
What the developer wrote
Authored by Lőrinc
test/refactor: use test deque to avoid quadratic iteration
Extracted from https://github.com/bitcoin/bitcoin/pull/33141#discussion_r2323012972.
In Python, list `pop(0)` is linear, so consuming all items is quadratic.
Switched to `collections.deque` with `popleft()` to express FIFO intent and avoid the O(n^2) path.
Behavior is unchanged; for a few hundred items the perf impact is likely negligible.
Ref: https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-queues
> While appends and pops from the end of list are fast, doing inserts or pops
> from the beginning of a list is slow (because all of the other elements have
> to be shifted by one).
Co-authored-by: maflcko <6399679+maflcko@users.noreply.github.com>
What changed, and why it matters
This is a minor internal cleanup in Bitcoin Core's Python test runner. It replaces a regular Python list used as a FIFO queue with a purpose-built deque, which avoids a theoretical slowdown when popping items from the front. The change only affects test infrastructure, not the live Bitcoin node software, and the commit message explicitly states behavior is unchanged.
No security action needed. Treat as normal code-quality/test-maintenance change.
Security signals we found
No strong security signals were identified.
Evidence from the diff
In test/functional/test_runner.py, the test_list variable is changed from a Python list to collections.deque. List.pop(0) is O(n), making repeated pops O(n^2), while deque.popleft() is O(1). The diff updates construction, extension, filtering, and popping accordingly. The only runtime-visible behavior change is replacing an IndexError(‘pop from empty list’) with an assert that self.jobs is non-empty. This is a test-only refactor with no security implications.
Changed components
test/functional/test_runner.pyInspect captured patch +6 / −7
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index 9dd10d1b..c4cf0fda 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -452,8 +452,8 @@ def main():
print("Re-compile with the -DBUILD_DAEMON=ON build option")
sys.exit(1)
- # Build list of tests
- test_list = []
+ # Build tests
+ test_list = deque()
if tests:
# Individual tests have been specified. Run specified tests that exist
# in the ALL_SCRIPTS list. Accept names with or without a .py extension.
@@ -472,7 +472,7 @@ def main():
script = script + ".py" if ".py" not in script else script
matching_scripts = [s for s in ALL_SCRIPTS if s.startswith(script)]
if matching_scripts:
- test_list.extend(matching_scripts)
+ test_list += matching_scripts
else:
print("{}WARNING!{} Test '{}' not found in full test list.".format(BOLD[1], BOLD[0], test))
elif args.extended:
@@ -507,7 +507,7 @@ def main():
remove_tests([test for test in test_list if test.split('.py')[0] == exclude_test.split('.py')[0]])
if args.filter:
- test_list = list(filter(re.compile(args.filter).search, test_list))
+ test_list = deque(filter(re.compile(args.filter).search, test_list))
if not test_list:
print("No valid test scripts specified. Check that your test is in one "
@@ -724,7 +724,7 @@ class TestHandler:
def get_next(self):
while len(self.jobs) < self.num_jobs and self.test_list:
# Add tests
- test = self.test_list.pop(0)
+ test = self.test_list.popleft()
portseed = len(self.test_list)
portseed_arg = ["--portseed={}".format(portseed)]
log_stdout = tempfile.SpooledTemporaryFile(max_size=2**16)
@@ -752,8 +752,7 @@ class TestHandler:
]
fut = self.executor.submit(proc_wait, task)
self.jobs[fut] = test
- if not self.jobs:
- raise IndexError('pop from empty list')
+ assert self.jobs # Must not be empty here
# Print remaining running jobs when all jobs have been started.
if not self.test_list:
Why this scored 15/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.