Debian Codegraph @

lib/control/pmap.scm

raw
1 ;;;
2 ;;; control.pmap - parallel mapper
3 ;;;
4 ;;; Copyright (c) 2018-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (define-module control.pmap
35 (use gauche.threads)
36 (use gauche.sequence)
37 (use gauche.generator)
38 (use gauche.mop.singleton)
39 (use data.queue)
40 (use scheme.list)
41 (use srfi.19)
42 (use control.thread-pool)
43 (use control.job)
44 (export pmap pfind pany
45 sequential-mapper
46 make-static-mapper
47 make-pool-mapper
48 make-fully-concurrent-mapper))
49 (select-module control.pmap)
50
51 ;; MAPPER abstracts the parallelization strategy. We provide several
52 ;; predefined mappers.
53 ;;
54 ;; sequential-mapper - A sigleton mapper that runs in a single (current) thread.
55 ;; If the running system is single-core, this is the default mapper.
56 ;;
57 ;; pool-mapper - Use thread pool. This is ideal when each task requies
58 ;; some processing time, so that the overhead of thread pool is
59 ;; negligible.
60 ;;
61 ;; static-mapper - Create as many threads as the available cores, and
62 ;; distribute elements evenly. Low overhead, good when each task is
63 ;; lightweight and the execution time won't fractuate much.
64 ;;
65 ;; full-concurrent-mapper - Creates as many threads as the number of
66 ;; elements and run concurrently. Relatively large overhead per element,
67 ;; but works better if (1) the number of elements are not very large,
68 ;; e.g. up to a few dozens, and (2) each task is expected to block
69 ;; on I/O.
70 ;;
71 ;; A mapper class implements the following methods. This is a provisional
72 ;; interface. The protocol should be kept private, for we may change as
73 ;; we support more operations.
74 ;;
75 ;; run-map <mapper> proc <collection>
76 ;; Apply proc on each element of <collection> in parallel,
77 ;; gather the result into a list.
78 ;;
79 ;; run-select <mapper> proc <collection>
80 ;; PROC must return two values, stop? and value. The method applies
81 ;; proc on each element of <collection>. As soon as one of the proc
82 ;; returns true in stop?, it cancels other operations and returns
83 ;; the value.
84
85 ;;
86 ;; The high-level API, pmap, can be used without knowing underlying
87 ;; thread models; it uses threads if running Gauche has the thread support
88 ;; and the system has more than one cores. Otherwise, it just runs
89 ;; ordinary map (see sequential-mapper).
90 ;;
91 ;; Concurrent execution can be done in either (1) staically split
92 ;; the task according to the number of available threads, or (2) dynamically
93 ;; split it using an existing thread pool. We don't make thread
94 ;; pool every time pmap is called, for the overhead would be too big.
95
96
97 ;; Abstract class.
98 (define-class <mapper> () ())
99
100 ;; Utilities
101
102 ;; Start threads in the list.
103 (define (%start-threads threads)
104 (for-each thread-try-start! threads))
105
106 ;;
107 ;; sequential-mapper
108 ;;
109 (define-class <sequential-mapper> (<mapper> <singleton-mixin>) ())
110
111 (define (sequential-mapper) (instance-of <sequential-mapper>))
112
113 (define-method run-map ((mapper <sequential-mapper>) proc coll)
114 (map proc coll))
115
116 (define-method run-select ((mapper <sequential-mapper>) proc coll)
117 (with-iterator (coll end? next)
118 (let loop ()
119 (if (end?)
120 #f
121 (receive (s? r) (proc (next))
122 (if s? r (loop)))))))
123
124 ;;
125 ;; static-mapper
126 ;;
127
128 (define-class <static-mapper> (<mapper>)
129 ((num-threads :init-keyword :num-threads)))
130
131 (define (make-static-mapper :optional (num-threads (sys-available-processors)))
132 (make <static-mapper> :num-threads num-threads))
133
134 (define-method run-map ((mapper <static-mapper>) proc coll)
135 (let* ([cols (%split-collection coll (~ mapper'num-threads))]
136 [ts (filter-map (^c (and (pair? c)
137 (make-thread (cut map proc c))))
138 cols)])
139 (%start-threads ts)
140 (append-map thread-join! ts)))
141
142 ;; (define (%split-collection coll n)
143 ;; (define qs (list-tabulate n (^_ (make-queue))))
144 ;; (define qgen (apply circular-generator qs))
145 ;; (with-iterator (coll end? next)
146 ;; (until (end?)
147 ;; (enqueue! (qgen) (next))))
148 ;; (map dequeue-all! qs))
149
150 (define (%split-collection coll n)
151 (receive (q r) (quotient&remainder (size-of coll) n)
152 ($ remove null?
153 (values-ref (map-accum (^[k lis] (split-at lis k))
154 (coerce-to <list> coll)
155 (append (make-list r (+ q 1))
156 (make-list (- n r) q)))
157 0))))
158
159 (define-method run-select ((mapper <static-mapper>) proc coll)
160 (define signaled (atom #f))
161 (define (with-stopper proc elts threads)
162 (let loop ([elts elts])
163 (if (null? elts)
164 #f
165 (receive (s? r) (proc (car elts))
166 (if s?
167 (values-ref
168 ($ atomic-update! signaled
169 (^f (or f
170 (begin
171 (dolist (t threads)
172 (unless (eq? t (current-thread))
173 (thread-terminate! t)))
174 (values #t r)))))
175 1)
176 (loop (cdr elts)))))))
177 (letrec ([cols (%split-collection coll (~ mapper'num-threads))]
178 [ts (filter-map (^c (and (pair? c)
179 (make-thread
180 (cut with-stopper proc c ts))))
181 cols)])
182 (%start-threads ts)
183 (do ([ts ts (cdr ts)]
184 [r #f (guard (e [(<terminated-thread-exception> e) r])
185 (or (thread-join! (car ts)) r))])
186 [(null? ts) r])))
187
188 ;;
189 ;; pool mapper
190 ;;
191
192 ;; NB: You can pass an exsting thread pool and it well be reused.
193 ;; If you do so, it is your responsibility to shut down the pool properly.
194
195 (define-class <pool-mapper> (<mapper>)
196 ((external-pool :init-keyword :external-pool
197 :init-value #f)))
198
199 (define (make-pool-mapper :optional (pool #f))
200 (make <pool-mapper> :external-pool pool))
201
202 (define-method run-map ((mapper <pool-mapper>) proc coll)
203 (define (run pool)
204 ($ for-each-with-index
205 (^[i e] (add-job! pool (^[] (cons i (proc e))) #t))
206 coll)
207 ($ map cdr $ (cut sort <> < car)
208 $ map (^_ (job-result (dequeue/wait! (thread-pool-results pool))))
209 $ liota (size-of coll)))
210 (if-let1 pool (~ mapper'external-pool)
211 (run pool)
212 (let1 pool (make-thread-pool (sys-available-processors))
213 (unwind-protect
214 (run pool)
215 (terminate-all! pool)))))
216
217 (define-method run-select ((mapper <pool-mapper>) proc coll)
218 (define result (atom #f #f))
219 (define start-latch (make-latch 1))
220 (define finish-latch (make-latch (size-of coll)))
221 (define (do-job elt jobs)
222 (latch-await start-latch)
223 (receive (s? r) (proc elt)
224 (if s?
225 (receive [found? result notify?]
226 (atomic-update! result (^[f v]
227 (if f
228 (values f v #f)
229 (values #t r #t))))
230 (when notify?
231 (for-each (^j (job-mark-killed! j "solution selected"))
232 jobs)
233 (latch-clear! finish-latch))) ;ensure to open the latch
234 (latch-dec! finish-latch))))
235 (define (run pool)
236 (letrec ([jobs (map (^e (add-job! pool (cut do-job e jobs))) coll)])
237 (latch-dec! start-latch)
238 (latch-await finish-latch)
239 (atom-ref result 1)))
240 (if-let1 pool (~ mapper'external-pool)
241 (run pool)
242 (let1 pool (make-thread-pool (sys-available-processors))
243 (unwind-protect
244 (run pool)
245 (terminate-all! pool :force-timeout 0)))))
246
247 ;;
248 ;; fully concurrent mapper
249 ;;
250
251 (define-class <fully-concurrent-mapper> (<mapper>)
252 ((timeout :init-keyword :timeout :init-value #f)
253 (timeout-val :init-keyword :timeout-val :init-value #f)))
254
255 (define (make-fully-concurrent-mapper :optional (timeout #f) (timeout-val #f))
256 (make <fully-concurrent-mapper> :timeout timeout :timeout-val timeout-val))
257
258 (define-method run-map ((mapper <fully-concurrent-mapper>) proc coll)
259 (let ([unique (list #f)]
260 [ts (map (^e (make-thread (^[] (proc e)))) coll)]
261 [timeout (absolute-time (~ mapper'timeout))]
262 [timeout-val (~ mapper'timeout-val)])
263 (%start-threads ts)
264 (if timeout
265 ($ map (^r (if (and (pair? r) (eq? (car r) unique))
266 (begin (thread-terminate! (cdr r)) timeout-val)
267 r))
268 $ map (^t (thread-join! t timeout (cons unique t))) ts)
269 (map thread-join! ts))))
270
271 (define-method run-select ((mapper <fully-concurrent-mapper>) proc coll)
272 (define signaled (atom #f))
273 (define (task e threads)
274 (receive (s? r) (proc e)
275 (if s?
276 (values-ref
277 ($ atomic-update! signaled
278 (^f (or f
279 (begin
280 (dolist [t threads]
281 (unless (eq? t (current-thread))
282 (thread-terminate! t)))
283 (values #t r)))))
284 1)
285 #f)))
286 (letrec ([ts (map (^e (make-thread (^[] (task e ts)))) coll)])
287 (%start-threads ts)
288 (do ([ts ts (cdr ts)]
289 [r #f (guard (e [(<terminated-thread-exception> e) r])
290 (or (thread-join! (car ts)) r))])
291 [(null? ts) r])))
292
293 ;;
294 ;; default mapper
295 ;;
296
297 (define default-mapper
298 (make-parameter
299 (if (= 1 (sys-available-processors))
300 (sequential-mapper)
301 (make-static-mapper))))
302
303 ;;;
304 ;;; High-level API
305 ;;;
306
307 (define (pmap proc coll :key (mapper (default-mapper)))
308 (run-map mapper proc coll))
309
310 (define (pfind pred coll :key (mapper (default-mapper)))
311 (run-select mapper
312 (^e (if (pred e)
313 (values #t e)
314 (values #f #f)))
315 coll))
316
317 (define (pany pred coll :key (mapper (default-mapper)))
318 (run-select mapper
319 (^e (if-let1 r (pred e)
320 (values #t r)
321 (values #f #f)))
322 coll))