| 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)) |