<div class="gmail_quote"><div>As the futures implementation stands right now, yes, recursively spawning futures is a bad idea - 'future' is currently treated like any other blocking primitive. This is something that we've discussed and is very likely to make it into a subsequent release (it's on the todo list). </div>
<div><br></div><div>But you can usually take the more elegant version of a program and rewrite it in such a way that you can avoid recursively spawning futures, albeit at the expense of a little readability and expressiveness. For example you could rewrite your code with something like this, where the recursion is sort of lifted out of the future calls: </div>
<div><br></div><div><div><div>#lang racket</div><div>(require racket/future</div><div> rackunit)</div><div><br></div><div>(define (sum values)</div><div> (foldr + 0 values))</div><div><br></div><div>(define (best vals-1 vals-2 target)</div>
<div> (if (< (abs (- target (sum vals-1)))</div><div> (abs (- target (sum vals-2))))</div><div> vals-1</div><div> vals-2))</div><div><br></div><div>(define (closest values target)</div><div> (cond [(= 1 (length values))</div>
<div> values]</div><div> [(= 0 target)</div><div> '()]</div><div> [else</div><div> (let ([wout-first</div><div> (future (λ () (closest (rest values) target)))]</div>
<div> [with-first </div><div> (future (λ () (closest (rest values) (- target (first values)))))])</div><div> (best (touch wout-first) (cons (first values) (touch with-first)) target))])) </div>
<div><br></div><div>;new-closest : (list-of-number) : number -> (list-of-number)</div><div>(define (new-closest vs target) </div><div> (let* ([fs (spawn-closest '() vs target (/ (log (processor-count)) (log 2)))]</div>
<div> [cands (map (λ (p) (append (car p) (touch (cdr p)))) fs)])</div><div> (cond </div><div> [(zero? target) '()]</div><div> [(null? (cdr vs)) vs]</div><div> [else </div><div> (let loop ([cur-best (first cands)] [cur-cands (rest cands)]) </div>
<div> (cond </div><div> [(null? (cdr cur-cands)) cur-best] </div><div> [else </div><div> (loop (best cur-best (second cur-cands) target) (rest cur-cands))]))])))</div><div><br></div>
<div>;closest-seq is the sequential version of the original 'closest'.</div><div>;This is called within our futures.</div><div>;closest-seq : (list-of-number) : number -> (list-of-number)</div><div>(define (closest-seq vals target)</div>
<div> (cond </div><div> [(null? (cdr vals)) vals] </div><div> [(zero? target) '()]</div><div> [else</div><div> (let ([wout-first (closest-seq (rest vals) target)]</div><div> [with-first (closest-seq (rest vals) (- target (first vals)))])</div>
<div> (best wout-first (cons (first vals) with-first) target))])) </div><div><br></div><div>;s-closest : (list-of-number) : (list-of-number) : number : number -> (list-of-((list-of-number) * future)</div><div>;depth = log (base 2) of the number of processors in the machine.</div>
<div>(define (spawn-closest fixup vs target depth) </div><div> (cond </div><div> [(or (zero? depth) (null? (cdr vs))) </div><div> (list (cons fixup (future (λ () (closest-seq vs target)))))]</div><div> [else </div>
<div> (append (spawn-closest fixup (rest vs) target (- depth 1)) </div><div> (spawn-closest (cons (first vs) fixup) (rest vs) (- target (first vs)) (- depth 1)))]))</div><div><br></div><div>(check-equal? </div>
<div> (closest-seq '(0 23 67 1 9 1 4) 0)</div><div> (closest '(0 23 67 1 9 1 4) 0))</div><div><br></div><div>(check-equal? </div><div> (closest-seq '(0 1 2 3) 2)</div><div> (closest '(0 1 2 3) 2))</div><div>
<br></div><div>(check-equal? </div><div> (closest-seq '(1) 88)</div><div> (closest '(1) 88)) </div><div><br></div><div>(check-equal? </div><div> (closest-seq '(3 5 9 3) 9)</div><div> (closest '(3 5 9 3) 9))</div>
<div><br></div><div>(check-equal? </div><div> (closest-seq '(1 2 3 4 5) 100)</div><div> (closest '(1 2 3 4 5) 100))</div><div><br></div><div>(check-equal? </div><div> (closest-seq '(1 2 3 4 5) 15)</div><div> (closest '(1 2 3 4 5) 15))</div>
<div><br></div><div>(check-equal? </div><div> (closest-seq '(15 1 3) 15)</div><div> (closest '(15 1 3) 15))</div><div><br></div><div>(check-equal? </div><div> (closest-seq '(3 1 15) 15) </div><div> (closest '(3 1 15) 15))</div>
<div><br></div><div>(check-equal? </div><div> (closest-seq '(1 15 3) 15) </div><div> (closest '(1 15 3) 15))</div><div><br></div><div>(check-equal? </div><div> (sort (new-closest '(0 23 67 1 9 1 4) 0) <)</div>
<div> (sort (closest '(0 23 67 1 9 1 4) 0) <))</div><div><br></div><div>(check-equal? </div><div> (sort (new-closest '(0 1 2 3) 2) <)</div><div> (sort (closest '(0 1 2 3) 2) <))</div><div><br></div><div>
(check-equal? </div><div> (sort (new-closest '(1) 88) <)</div><div> (sort (closest '(1) 88) <)) </div><div><br></div><div>(check-equal? </div><div> (sort (new-closest '(3 5 9 3) 9) <)</div><div> (sort (closest '(3 5 9 3) 9) <))</div>
<div><br></div><div>(check-equal? </div><div> (sort (new-closest '(1 2 3 4 5) 100) <)</div><div> (sort (closest '(1 2 3 4 5) 100) <))</div><div><br></div><div>(check-equal? </div><div> (sort (new-closest '(1 2 3 4 5) 15) <)</div>
<div> (sort (closest '(1 2 3 4 5) 15) <))</div><div><br></div><div>(check-equal? </div><div> (sort (new-closest '(15 1 3) 15) <)</div><div> (sort (closest '(15 1 3) 15) <))</div><div><br></div><div>(check-equal? </div>
<div> (sort (new-closest '(3 1 15) 15) <)</div><div> (sort (closest '(3 1 15) 15) <))</div></div></div><div><br></div><div>Note that here one of the test cases fails - I rewrote the code assuming that your original version would accept lists of values that are in any order. But in the failing case, my code rebuilds the 'candidate' lists in reverse order before calling 'closest-seq'. So here my code calls (closest-seq '(1 15 3) 15), which returns an incorrect answer just as closest does (there's a test case above to show this). Maybe this was a bug in your original code, or you knew ahead of time you wouldn't have to account for input lists with strange orderings like that (or I might be missing something)?</div>
<div><br></div><div>Even though this code avoids the blocking caused by recursively spawning futures, there is still blocking that's being caused by other primitives. Most of these primitives are coming from the use of list operations (there are a few surprising ones here, like list? and length). Primitives like this that would intuitively seem side-effect free usually may actually do some sort of mutation on data structures at the runtime level. list? is a good example of this - to write this function in Racket, you would do something like this: </div>
<div><br></div><div><div>(define (list? x) </div><div> (cond </div><div> [(null? x) #t]</div><div> [(pair? x) </div><div> (cond </div><div> [(null? (cdr x)) #t]</div><div> [(is-list (cdr x))])]</div>
<div> [else #f]))</div></div><div><br></div><div>So you have to do O(n) work to do the check. The actual implementation (in the runtime) sets a type flag bit on the car of the list object indicating it's a list, so each subsequent call to list? for that object can be done in constant time. These kinds of things are obviously tricky when we have multiple threads. In all likelihood this function is already race-free even with the type flag setting, so we may be able to declare this function future-safe at some point. I've got a (growing) list of functions like this that are sort of deal-breakers for people who want to do serious programming with futures.</div>
<div><br></div><div>I should also say, though, that futures are really not intended for everyday, direct use in garden-variety programs - they were designed as building blocks for higher-level parallel abstractions. So we sort of envision the low-level futures implementation (what is available today) as evolving in support of that kind of 'better, friendlier' API, but yes, this will most likely include making 'future' parallel-safe. </div>
<div><br></div><div>(Also, one other note - it's generally not a good idea to rebind an identifier such as 'values', since it is already being used for a pretty common primitive found in the language). </div>
<div><br></div><div>Hope this helps, </div><div>James Swaine </div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
------------------------------<br>
<br>
Message: 6<br>
Date: Wed, 28 Jul 2010 16:35:57 -0400<br>
From: Joe Snikeris <<a href="mailto:joe@snikeris.com" target="_blank">joe@snikeris.com</a>><br>
To: <a href="mailto:users@racket-lang.org" target="_blank">users@racket-lang.org</a><br>
Subject: [racket] Using Futures<br>
Message-ID:<br>
<<a href="mailto:AANLkTimJLOL_ia5oxZ8zuj6wYzrp4VPZqyXiWh7hk-75@mail.gmail.com" target="_blank">AANLkTimJLOL_ia5oxZ8zuj6wYzrp4VPZqyXiWh7hk-75@mail.gmail.com</a>><br>
Content-Type: text/plain; charset=ISO-8859-1<br>
<br>
All,<br>
<br>
Please see: <a href="http://pastie.org/1064484" target="_blank">http://pastie.org/1064484</a><br>
<br>
Apparently, spawning futures recursively is a bad idea. This problem<br>
seems like it should be easily parallelizable. What am I doing wrong<br>
here?<br>
<br>
Thanks,<br>
Joe<br>
<br>
<br>
End of users Digest, Vol 59, Issue 99<br>
*************************************<br>
</blockquote></div><br>