Extracted from #33141 (review).
In Python, list pop(0) is linear, so consuming all items in the test results in quadratic iteration.
Switching to collections.deque with popleft() expresses FIFO intent and avoids the O(n^2) path.
Behavior is unchanged - for a few hundred items the perf impact is likely negligible.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33313.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | theStack, enirox001, maflcko, w0xlt |
| Stale ACK | kevkevinpal |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
448@@ -449,8 +449,7 @@ def main():
449 print("Re-compile with the -DBUILD_DAEMON=ON build option")
450 sys.exit(1)
451
452- # Build list of tests
467@@ -469,15 +468,15 @@ def main():
468 script = script + ".py" if ".py" not in script else script
469 matching_scripts = [s for s in ALL_SCRIPTS if s.startswith(script)]
470 if matching_scripts:
471- test_list.extend(matching_scripts)
472+ test_queue += matching_scripts
deque also has an extend method, it might be preferable to use that instead since it is more readable
https://docs.python.org/3/library/collections.html#collections.deque.extend
ACK 1500bb3
Looks good to me, we’re replacing list with a deque and replacing pop(0) with popleft()
737@@ -739,10 +738,10 @@ def get_next(self):
738 log_stdout,
739 log_stderr))
740 if not self.jobs:
741- raise IndexError('pop from empty list')
742+ raise IndexError('pop from empty queue')
i don’t think this is right, as explained previously. This block of code is about self.jobs, which is a list, even after the changes here.
It is just a sanity check, so a shorter way to write it would be assert(self.jobs) # Can not and must not be empty here.
737@@ -739,10 +738,10 @@ def get_next(self):
738 log_stdout,
739 log_stderr))
740 if not self.jobs:
741- raise IndexError('pop from empty list')
742+ raise IndexError('pop from empty queue')
743
744 # Print remaining running jobs when all jobs have been started.
745- if not self.test_list:
746+ if not self.test_queue:
I am not sure if this needs a rename.
So it would be better to leave this as it was previously, or at least not include the exact type in the name.
ACK https://github.com/bitcoin/bitcoin/pull/33313/commits/8c1f10233dc9a843147772c40973031f5bfdbb7c
While the impact of this PR on a few hundred items is negligible, it’s still a good practice and is likely to scale more effectively as test coverage increases.
For reference, the script below demonstrates the performance difference with 1,000,000 items on my machine:
0List pop(0): 62.790 seconds
1Deque popleft(): 0.022 seconds
0import time
1from collections import deque
2
3N = 1_000_000 # number of elements
4
5def benchmark_list():
6 lst = list(range(N))
7 start = time.perf_counter()
8 while lst:
9 lst.pop(0) # O(n) per operation
10 end = time.perf_counter()
11 return end - start
12
13def benchmark_deque():
14 dq = deque(range(N))
15 start = time.perf_counter()
16 while dq:
17 dq.popleft() # O(1) per operation
18 end = time.perf_counter()
19 return end - start
20
21if __name__ == "__main__":
22 print(f"List pop(0): {benchmark_list():.3f} seconds")
23 print(f"Deque popleft(): {benchmark_deque():.3f} seconds")
ACK 8c1f10233dc9a843147772c40973031f5bfdbb7c
While I agree with others that very likely there won’t be a notable difference in run-time any time soon (if ever), it seems conceptually the right approach.
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>
lgtm ACK 75e6984ec8c6fa196ad78c11f454da506d7c8ff1
This shouldn’t affect performance, but it seems fine as a style-cleanup/refactor.