How to implement parallel-or?

Questions & Answers
, ,
2

This is difficult to do with futures, because futures can potentially block, making no more parallel progress until touched, and there is no mechanism analogous to choice-evt to select whichever future is ready first.

But the new parallel threads coming in Racket 9.0 (test a candidate from https://pre-release.racket-lang.org!) will make parallel-or very convenient to express:

#lang racket

(module+ main
  (parallel-or (begin (println 'a) 'a)
               (begin (println 'b) 'b)))

(define-syntax-rule (parallel-or a-expr b-expr)
  (do-parallel-or (λ () a-expr) (λ () b-expr)))

(define (do-parallel-or a-thunk b-thunk)
  (define (spawn thunk)
    (define cust (make-custodian))
    (values (parameterize ([current-custodian cust])
              (thread #:pool 'own #:keep 'results thunk))
            cust))
  (define-values [a-thd a-cust]
    (spawn a-thunk))
  (define-values [b-thd b-cust]
    (spawn b-thunk))
  (define ready-thd
    (sync a-thd b-thd))
  (cond
    [(thread-wait ready-thd)
     => (λ (rslt)
          (custodian-shutdown-all (if (equal? ready-thd a-thd)
                                      b-cust
                                      a-cust))
          rslt)]
    [else
     (define-values [ready-cust other-thd other-cust]
       (if (equal? ready-thd a-thd)
           (values a-cust b-thd b-cust)
           (values b-cust a-thd a-cust)))
     (custodian-shutdown-all ready-cust)
     (cond
       [(thread-wait other-thd)]
       [else
        (custodian-shutdown-all other-cust)
        #f])]))

The dance with custodians is intended to arrange that a computation that either returns #f or is not chosen has all its resources cleaned up, but also to not shut down any resources from a computation that is chosen, since it might be useful to have parallel-or return a custodian-managed resource.

This implementation doesn't consider potential exceptions coming from one (or both) of the parallel computations. You could configure the threads' initial exception handlers to communicate exceptions, or further enhancements to thread (and/or integrating the new features into delay/thread) might make things more convenient:

2 Likes