Debian Codegraph @

Lib/test/test_free_threading/test_heapq.py

raw
1 import unittest
2
3 import heapq
4
5 from enum import Enum
6 from threading import Barrier, Lock
7 from random import shuffle, randint
8
9 from test.support import threading_helper
10 from test.support.threading_helper import run_concurrently
11 from test import test_heapq
12
13
14 NTHREADS = 10
15 OBJECT_COUNT = 5_000
16
17
18 class Heap(Enum):
19 MIN = 1
20 MAX = 2
21
22
23 @threading_helper.requires_working_threading()
24 class TestHeapq(unittest.TestCase):
25 def setUp(self):
26 self.test_heapq = test_heapq.TestHeapPython()
27
28 def test_racing_heapify(self):
29 heap = list(range(OBJECT_COUNT))
30 shuffle(heap)
31
32 run_concurrently(
33 worker_func=heapq.heapify, nthreads=NTHREADS, args=(heap,)
34 )
35 self.test_heapq.check_invariant(heap)
36
37 def test_racing_heappush(self):
38 heap = []
39
40 def heappush_func(heap):
41 for item in reversed(range(OBJECT_COUNT)):
42 heapq.heappush(heap, item)
43
44 run_concurrently(
45 worker_func=heappush_func, nthreads=NTHREADS, args=(heap,)
46 )
47 self.test_heapq.check_invariant(heap)
48
49 def test_racing_heappop(self):
50 heap = self.create_heap(OBJECT_COUNT, Heap.MIN)
51
52 # Each thread pops (OBJECT_COUNT / NTHREADS) items
53 self.assertEqual(OBJECT_COUNT % NTHREADS, 0)
54 per_thread_pop_count = OBJECT_COUNT // NTHREADS
55
56 def heappop_func(heap, pop_count):
57 local_list = []
58 for _ in range(pop_count):
59 item = heapq.heappop(heap)
60 local_list.append(item)
61
62 # Each local list should be sorted
63 self.assertTrue(self.is_sorted_ascending(local_list))
64
65 run_concurrently(
66 worker_func=heappop_func,
67 nthreads=NTHREADS,
68 args=(heap, per_thread_pop_count),
69 )
70 self.assertEqual(len(heap), 0)
71
72 def test_racing_heappushpop(self):
73 heap = self.create_heap(OBJECT_COUNT, Heap.MIN)
74 pushpop_items = self.create_random_list(-5_000, 10_000, OBJECT_COUNT)
75
76 def heappushpop_func(heap, pushpop_items):
77 for item in pushpop_items:
78 popped_item = heapq.heappushpop(heap, item)
79 self.assertTrue(popped_item <= item)
80
81 run_concurrently(
82 worker_func=heappushpop_func,
83 nthreads=NTHREADS,
84 args=(heap, pushpop_items),
85 )
86 self.assertEqual(len(heap), OBJECT_COUNT)
87 self.test_heapq.check_invariant(heap)
88
89 def test_racing_heapreplace(self):
90 heap = self.create_heap(OBJECT_COUNT, Heap.MIN)
91 replace_items = self.create_random_list(-5_000, 10_000, OBJECT_COUNT)
92
93 def heapreplace_func(heap, replace_items):
94 for item in replace_items:
95 heapq.heapreplace(heap, item)
96
97 run_concurrently(
98 worker_func=heapreplace_func,
99 nthreads=NTHREADS,
100 args=(heap, replace_items),
101 )
102 self.assertEqual(len(heap), OBJECT_COUNT)
103 self.test_heapq.check_invariant(heap)
104
105 def test_racing_heapify_max(self):
106 max_heap = list(range(OBJECT_COUNT))
107 shuffle(max_heap)
108
109 run_concurrently(
110 worker_func=heapq.heapify_max, nthreads=NTHREADS, args=(max_heap,)
111 )
112 self.test_heapq.check_max_invariant(max_heap)
113
114 def test_racing_heappush_max(self):
115 max_heap = []
116
117 def heappush_max_func(max_heap):
118 for item in range(OBJECT_COUNT):
119 heapq.heappush_max(max_heap, item)
120
121 run_concurrently(
122 worker_func=heappush_max_func, nthreads=NTHREADS, args=(max_heap,)
123 )
124 self.test_heapq.check_max_invariant(max_heap)
125
126 def test_racing_heappop_max(self):
127 max_heap = self.create_heap(OBJECT_COUNT, Heap.MAX)
128
129 # Each thread pops (OBJECT_COUNT / NTHREADS) items
130 self.assertEqual(OBJECT_COUNT % NTHREADS, 0)
131 per_thread_pop_count = OBJECT_COUNT // NTHREADS
132
133 def heappop_max_func(max_heap, pop_count):
134 local_list = []
135 for _ in range(pop_count):
136 item = heapq.heappop_max(max_heap)
137 local_list.append(item)
138
139 # Each local list should be sorted
140 self.assertTrue(self.is_sorted_descending(local_list))
141
142 run_concurrently(
143 worker_func=heappop_max_func,
144 nthreads=NTHREADS,
145 args=(max_heap, per_thread_pop_count),
146 )
147 self.assertEqual(len(max_heap), 0)
148
149 def test_racing_heappushpop_max(self):
150 max_heap = self.create_heap(OBJECT_COUNT, Heap.MAX)
151 pushpop_items = self.create_random_list(-5_000, 10_000, OBJECT_COUNT)
152
153 def heappushpop_max_func(max_heap, pushpop_items):
154 for item in pushpop_items:
155 popped_item = heapq.heappushpop_max(max_heap, item)
156 self.assertTrue(popped_item >= item)
157
158 run_concurrently(
159 worker_func=heappushpop_max_func,
160 nthreads=NTHREADS,
161 args=(max_heap, pushpop_items),
162 )
163 self.assertEqual(len(max_heap), OBJECT_COUNT)
164 self.test_heapq.check_max_invariant(max_heap)
165
166 def test_racing_heapreplace_max(self):
167 max_heap = self.create_heap(OBJECT_COUNT, Heap.MAX)
168 replace_items = self.create_random_list(-5_000, 10_000, OBJECT_COUNT)
169
170 def heapreplace_max_func(max_heap, replace_items):
171 for item in replace_items:
172 heapq.heapreplace_max(max_heap, item)
173
174 run_concurrently(
175 worker_func=heapreplace_max_func,
176 nthreads=NTHREADS,
177 args=(max_heap, replace_items),
178 )
179 self.assertEqual(len(max_heap), OBJECT_COUNT)
180 self.test_heapq.check_max_invariant(max_heap)
181
182 def test_lock_free_list_read(self):
183 n, n_threads = 1_000, 10
184 l = []
185 barrier = Barrier(n_threads * 2)
186
187 count = 0
188 lock = Lock()
189
190 def worker():
191 with lock:
192 nonlocal count
193 x = count
194 count += 1
195
196 barrier.wait()
197 for i in range(n):
198 if x % 2:
199 heapq.heappush(l, 1)
200 heapq.heappop(l)
201 else:
202 try:
203 l[0]
204 except IndexError:
205 pass
206
207 run_concurrently(worker, n_threads * 2)
208
209 @staticmethod
210 def is_sorted_ascending(lst):
211 """
212 Check if the list is sorted in ascending order (non-decreasing).
213 """
214 return all(lst[i - 1] <= lst[i] for i in range(1, len(lst)))
215
216 @staticmethod
217 def is_sorted_descending(lst):
218 """
219 Check if the list is sorted in descending order (non-increasing).
220 """
221 return all(lst[i - 1] >= lst[i] for i in range(1, len(lst)))
222
223 @staticmethod
224 def create_heap(size, heap_kind):
225 """
226 Create a min/max heap where elements are in the range (0, size - 1) and
227 shuffled before heapify.
228 """
229 heap = list(range(OBJECT_COUNT))
230 shuffle(heap)
231 if heap_kind == Heap.MIN:
232 heapq.heapify(heap)
233 else:
234 heapq.heapify_max(heap)
235
236 return heap
237
238 @staticmethod
239 def create_random_list(a, b, size):
240 """
241 Create a list of random numbers between a and b (inclusive).
242 """
243 return [randint(-a, b) for _ in range(size)]
244
245
246 if __name__ == "__main__":
247 unittest.main()