[racket] Using Futures

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

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:

#lang racket
(require racket/future
         rackunit)

(define (sum values)
  (foldr + 0 values))

(define (best vals-1 vals-2 target)
  (if (< (abs (- target (sum vals-1)))
         (abs (- target (sum vals-2))))
      vals-1
      vals-2))

(define (closest values target)
  (cond [(= 1 (length values))
         values]
        [(= 0 target)
         '()]
        [else
         (let ([wout-first
                (future (λ () (closest (rest values) target)))]
               [with-first
                (future (λ () (closest (rest values) (- target (first
values)))))])
           (best (touch wout-first) (cons (first values) (touch with-first))
target))]))

;new-closest : (list-of-number) : number -> (list-of-number)
(define (new-closest vs target)
  (let* ([fs (spawn-closest '() vs target (/ (log (processor-count)) (log
2)))]
         [cands (map (λ (p) (append (car p) (touch (cdr p)))) fs)])
    (cond
      [(zero? target) '()]
      [(null? (cdr vs)) vs]
      [else
       (let loop ([cur-best (first cands)] [cur-cands (rest cands)])
         (cond
           [(null? (cdr cur-cands)) cur-best]
           [else
            (loop (best cur-best (second cur-cands) target) (rest
cur-cands))]))])))

;closest-seq is the sequential version of the original 'closest'.
;This is called within our futures.
;closest-seq : (list-of-number) : number -> (list-of-number)
(define (closest-seq vals target)
  (cond
    [(null? (cdr vals)) vals]
    [(zero? target) '()]
    [else
     (let ([wout-first (closest-seq (rest vals) target)]
           [with-first (closest-seq (rest vals) (- target (first vals)))])
       (best wout-first (cons (first vals) with-first) target))]))

;s-closest : (list-of-number) : (list-of-number) : number : number ->
(list-of-((list-of-number) * future)
;depth = log (base 2) of the number of processors in the machine.
(define (spawn-closest fixup vs target depth)
  (cond
    [(or (zero? depth) (null? (cdr vs)))
     (list (cons fixup (future (λ () (closest-seq vs target)))))]
    [else
     (append (spawn-closest fixup (rest vs) target (- depth 1))
             (spawn-closest (cons (first vs) fixup) (rest vs) (- target
(first vs)) (- depth 1)))]))

(check-equal?
 (closest-seq '(0 23 67 1 9 1 4) 0)
 (closest '(0 23 67 1 9 1 4) 0))

(check-equal?
 (closest-seq '(0 1 2 3) 2)
 (closest '(0 1 2 3) 2))

(check-equal?
 (closest-seq '(1) 88)
 (closest '(1) 88))

(check-equal?
 (closest-seq '(3 5 9 3) 9)
 (closest '(3 5 9 3) 9))

(check-equal?
 (closest-seq '(1 2 3 4 5) 100)
 (closest '(1 2 3 4 5) 100))

(check-equal?
 (closest-seq '(1 2 3 4 5) 15)
 (closest '(1 2 3 4 5) 15))

(check-equal?
 (closest-seq '(15 1 3) 15)
 (closest '(15 1 3) 15))

(check-equal?
 (closest-seq '(3 1 15) 15)
 (closest '(3 1 15) 15))

(check-equal?
 (closest-seq '(1 15 3) 15)
 (closest '(1 15 3) 15))

(check-equal?
 (sort (new-closest '(0 23 67 1 9 1 4) 0) <)
 (sort (closest '(0 23 67 1 9 1 4) 0) <))

(check-equal?
 (sort (new-closest '(0 1 2 3) 2) <)
 (sort (closest '(0 1 2 3) 2) <))

(check-equal?
 (sort (new-closest '(1) 88) <)
 (sort (closest '(1) 88) <))

(check-equal?
 (sort (new-closest '(3 5 9 3) 9) <)
 (sort (closest '(3 5 9 3) 9) <))

(check-equal?
 (sort (new-closest '(1 2 3 4 5) 100) <)
 (sort (closest '(1 2 3 4 5) 100) <))

(check-equal?
 (sort (new-closest '(1 2 3 4 5) 15) <)
 (sort (closest '(1 2 3 4 5) 15) <))

(check-equal?
 (sort (new-closest '(15 1 3) 15) <)
 (sort (closest '(15 1 3) 15) <))

(check-equal?
 (sort (new-closest '(3 1 15) 15) <)
 (sort (closest '(3 1 15) 15) <))

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

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:

(define (list? x)
  (cond
    [(null? x) #t]
    [(pair? x)
     (cond
       [(null? (cdr x)) #t]
       [(is-list (cdr x))])]
    [else #f]))

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.

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.

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

Hope this helps,
James Swaine




> ------------------------------
>
> Message: 6
> Date: Wed, 28 Jul 2010 16:35:57 -0400
> From: Joe Snikeris <joe at snikeris.com>
> To: users at racket-lang.org
> Subject: [racket] Using Futures
> Message-ID:
>        <AANLkTimJLOL_ia5oxZ8zuj6wYzrp4VPZqyXiWh7hk-75 at mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
>
> All,
>
> Please see: http://pastie.org/1064484
>
> Apparently, spawning futures recursively is a bad idea.  This problem
> seems like it should be easily parallelizable.  What am I doing wrong
> here?
>
> Thanks,
> Joe
>
>
> End of users Digest, Vol 59, Issue 99
> *************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100818/5b2f8f36/attachment.html>