Commit | Line | Data |
---|---|---|
0d4e6ca3 LC |
1 | ;;; -*- mode: scheme; coding: utf-8; -*- |
2 | ;;; | |
f4e45e91 | 3 | ;;; Copyright (C) 2010, 2011 Free Software Foundation, Inc. |
0d4e6ca3 LC |
4 | ;;; |
5 | ;;; This library is free software; you can redistribute it and/or | |
6 | ;;; modify it under the terms of the GNU Lesser General Public | |
7 | ;;; License as published by the Free Software Foundation; either | |
8 | ;;; version 3 of the License, or (at your option) any later version. | |
9 | ;;; | |
10 | ;;; This library is distributed in the hope that it will be useful, | |
11 | ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | ;;; Lesser General Public License for more details. | |
14 | ;;; | |
15 | ;;; You should have received a copy of the GNU Lesser General Public | |
16 | ;;; License along with this library; if not, write to the Free Software | |
17 | ;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
18 | ||
19 | (define-module (ice-9 futures) | |
20 | #:use-module (srfi srfi-1) | |
21 | #:use-module (srfi srfi-9) | |
90b2c69c | 22 | #:use-module (ice-9 q) |
0d4e6ca3 LC |
23 | #:export (future make-future future? touch)) |
24 | ||
25 | ;;; Author: Ludovic Courtès <ludo@gnu.org> | |
26 | ;;; | |
27 | ;;; Commentary: | |
28 | ;;; | |
29 | ;;; This module provides an implementation of futures, a mechanism for | |
30 | ;;; fine-grain parallelism. Futures were first described by Henry Baker | |
31 | ;;; in ``The Incremental Garbage Collection of Processes'', 1977, and | |
32 | ;;; then implemented in MultiLisp (an implicit variant thereof, i.e., | |
33 | ;;; without `touch'.) | |
34 | ;;; | |
35 | ;;; This modules uses a fixed thread pool, normally one per CPU core. | |
36 | ;;; Futures are off-loaded to these threads, when they are idle. | |
37 | ;;; | |
38 | ;;; Code: | |
39 | ||
40 | \f | |
41 | ;;; | |
42 | ;;; Futures. | |
43 | ;;; | |
44 | ||
45 | (define-record-type <future> | |
46 | (%make-future thunk done? mutex) | |
47 | future? | |
48 | (thunk future-thunk) | |
49 | (done? future-done? set-future-done?!) | |
50 | (result future-result set-future-result!) | |
51 | (mutex future-mutex)) | |
52 | ||
53 | (define (make-future thunk) | |
54 | "Return a new future for THUNK. Execution may start at any point | |
55 | concurrently, or it can start at the time when the returned future is | |
56 | touched." | |
f4e45e91 | 57 | (create-workers!) |
0d4e6ca3 LC |
58 | (let ((future (%make-future thunk #f (make-mutex)))) |
59 | (register-future! future) | |
60 | future)) | |
61 | ||
62 | \f | |
63 | ;;; | |
64 | ;;; Future queues. | |
65 | ;;; | |
66 | ||
90b2c69c | 67 | (define %futures (make-q)) |
0d4e6ca3 LC |
68 | (define %futures-mutex (make-mutex)) |
69 | (define %futures-available (make-condition-variable)) | |
70 | ||
71 | (define (register-future! future) | |
72 | ;; Register FUTURE as being processable. | |
73 | (lock-mutex %futures-mutex) | |
90b2c69c | 74 | (enq! %futures future) |
0d4e6ca3 LC |
75 | (signal-condition-variable %futures-available) |
76 | (unlock-mutex %futures-mutex)) | |
77 | ||
0d4e6ca3 LC |
78 | (define (process-future! future) |
79 | ;; Process FUTURE, assuming its mutex is already taken. | |
80 | (set-future-result! future | |
81 | (catch #t | |
82 | (lambda () | |
6c17f7bd LC |
83 | (call-with-values (future-thunk future) |
84 | (lambda results | |
85 | (lambda () | |
86 | (apply values results))))) | |
0d4e6ca3 LC |
87 | (lambda args |
88 | (lambda () | |
89 | (apply throw args))))) | |
90 | (set-future-done?! future #t)) | |
91 | ||
92 | (define (process-futures) | |
93 | ;; Wait for futures to be available and process them. | |
94 | (lock-mutex %futures-mutex) | |
95 | (let loop () | |
96 | (wait-condition-variable %futures-available | |
97 | %futures-mutex) | |
90b2c69c LC |
98 | (or (q-empty? %futures) |
99 | (let ((future (deq! %futures))) | |
100 | (lock-mutex (future-mutex future)) | |
101 | (or (and (future-done? future) | |
102 | (unlock-mutex (future-mutex future))) | |
103 | (begin | |
104 | ;; Do the actual work. | |
105 | ||
106 | ;; We want to release %FUTURES-MUTEX so that other workers | |
107 | ;; can progress. However, to avoid deadlocks, we have to | |
108 | ;; unlock FUTURE as well, to preserve lock ordering. | |
109 | (unlock-mutex (future-mutex future)) | |
110 | (unlock-mutex %futures-mutex) | |
111 | ||
112 | (lock-mutex (future-mutex future)) | |
113 | (or (future-done? future) ; lost the race? | |
114 | (process-future! future)) | |
115 | (unlock-mutex (future-mutex future)) | |
116 | ||
117 | (lock-mutex %futures-mutex))))) | |
118 | (loop))) | |
0d4e6ca3 LC |
119 | |
120 | (define (touch future) | |
121 | "Return the result of FUTURE, computing it if not already done." | |
122 | (lock-mutex (future-mutex future)) | |
123 | (or (future-done? future) | |
124 | (begin | |
125 | ;; Do the actual work. Unlock FUTURE first to preserve lock | |
126 | ;; ordering. | |
127 | (unlock-mutex (future-mutex future)) | |
128 | ||
129 | (lock-mutex %futures-mutex) | |
90b2c69c | 130 | (q-remove! %futures future) |
0d4e6ca3 LC |
131 | (unlock-mutex %futures-mutex) |
132 | ||
133 | (lock-mutex (future-mutex future)) | |
134 | (or (future-done? future) ; lost the race? | |
135 | (process-future! future)))) | |
136 | (unlock-mutex (future-mutex future)) | |
137 | ((future-result future))) | |
138 | ||
139 | \f | |
140 | ;;; | |
141 | ;;; Workers. | |
142 | ;;; | |
143 | ||
144 | (define %worker-count | |
145 | (if (provided? 'threads) | |
51fc066a | 146 | (- (current-processor-count) 1) |
0d4e6ca3 LC |
147 | 0)) |
148 | ||
f4e45e91 AW |
149 | ;; A dock of workers that stay here forever. |
150 | ||
151 | ;; TODO | |
152 | ;; 1. Allow the pool to be shrunk, as in libgomp (though that we'd | |
153 | ;; need semaphores, which aren't yet in libguile!). | |
154 | ;; 2. Provide a `worker-count' fluid. | |
155 | (define %workers '()) | |
156 | ||
157 | (define (%create-workers!) | |
158 | (lock-mutex %futures-mutex) | |
159 | (set! %workers | |
160 | (unfold (lambda (i) (>= i %worker-count)) | |
161 | (lambda (i) | |
162 | (call-with-new-thread process-futures)) | |
163 | 1+ | |
164 | 0)) | |
165 | (set! create-workers! (lambda () #t)) | |
166 | (unlock-mutex %futures-mutex)) | |
167 | ||
168 | (define create-workers! | |
169 | (lambda () (%create-workers!))) | |
0d4e6ca3 LC |
170 | |
171 | \f | |
172 | ;;; | |
173 | ;;; Syntax. | |
174 | ;;; | |
175 | ||
0c65f52c AW |
176 | (define-syntax-rule (future body) |
177 | "Return a new future for BODY." | |
178 | (make-future (lambda () body))) |