Short-circuiting futures in clojure

Question

I've got two futures that resolve to booleans. I basically want to do something like

(if (or @future1 @future2) 
  ...)

but, with the optimization that whichever one finishes first, if it's true, then I don't wait for the remaining future to finish; just go. Of course if the value is false, then wait for the remaining future to finish. Is there a straightforward way of doing this?

Answer 1

This is now possible with core.async, as described in my answer to the new with Clojure threading long running processes and comparing their returns question. That answer defines thread-and; this question calls for thread-or:

(defn thread-or
  "Call each of the fs on a separate thread. Return logical
  disjunction of the results. Short-circuit (and cancel the calls to
  remaining fs) on first truthy value returned."
  [& fs]
  (let [futs-and-cs
        (doall (for [f fs]
                 (let [c (chan)]
                   [(future (>!! c (f))) c])))]
    (loop [futs-and-cs futs-and-cs]
      (let [[result c] (alts!! (map peek futs-and-cs))]
        (if result
          (do (doseq [fut (map first futs-and-cs)]
                (future-cancel fut))
              result)
          (let [new-futs-and-cs (remove #(identical? (peek %) c)
                                        futs-and-cs)]
            (if (next new-futs-and-cs)
              (recur new-futs-and-cs)
              (<!! (peek (first new-futs-and-cs))))))))))

Test with (constantly false) and (constantly true):

(thread-or (constantly true) (constantly true))
;;= true

(thread-or (constantly true) (constantly false))
;;= true

(thread-or (constantly false) (constantly false))
;;= false

Also note that short-circuiting does indeed work:

;; prints :foo before returning true
(thread-or #(do (Thread/sleep 3000) true)
           #(do (Thread/sleep 1000) (println :foo)))

;; does not print :foo
(thread-or #(do (Thread/sleep 3000) true)
           #(do (Thread/sleep 7000) (println :foo)))

Answer 2

Assuming that you don't want to poll the futures every X millis and that you cannot control the creation of the futures/threads or the fn that they are executing, the solution is just to create yet more threads, each thread waiting for a future:

(defn wait-for-any [& futures]
  (let [how-many-left (atom (count futures))
        p (promise)
        wait-and-notify (fn [f]
                         (fn []
                           (if @f
                             (deliver p true)
                             (when (zero? (swap! how-many-left dec))
                               (deliver p false)))))]
    (dorun (map (comp future-call wait-and-notify) futures))
    @p))

 (defn sleep-and-return [what-to-return sleep-time]
  (future
    (Thread/sleep sleep-time)
    what-to-return))


(time (println (wait-for-any
                (sleep-and-return false 1000)
                (sleep-and-return false 2000)
                (sleep-and-return false 3000)
                (sleep-and-return false 4000)
                (sleep-and-return false 5000))))

>>>false
>>>"Elapsed time: 5000.933906 msecs"

(time (println (wait-for-any
                (sleep-and-return false 1000)
                (sleep-and-return true 2900)
                (sleep-and-return true 3000)
                (sleep-and-return false 4000)
                (sleep-and-return false 5000))))
>>>true
>>>"Elapsed time: 2901.309695 msecs"

Answer 3

I absolutely love this question. Maybe I'm surprised that to see a novel question that is so simple. Anyways, drooling aside, I think I have something that would work for you.

Instead of doing:

(if (or @future1 @future2)
  ...)

Do:

(if (or (and (realized? future1) @future1)
        (and (realized? future2) @future2))
  ...)

The trick is testing whether something is realized before asking whether it is true or false.

This could be generalized to a macro like so:

(defmacro future-or [& futures]
  `(or ~@(for [f futures]
          `(and (realized? ~f)
                (deref ~f)))))

And then used like:

(if (future-or future1 future2)
  ...)

Wait a second. Maybe I'm understanding your problem incorrectly. Perhaps you want to block execution until EITHER one of the futures is done and returns true, in which case you do the then clause of your if, OR both of your futures are done and neither returns true, in which case you do the else clause of your if. That's a different story.

The most succint way I could come up with isn't exactly pretty, but it's not hideously long either:

(if (loop []
        (cond (or (and (realized? future1) @future1)
                  (and (realized? future2) @future2)) true
              (and (realized? future1) (realized? future2)
                   (not @future1) (not @future2)) false
              :else (recur)))
    ...)

Now, this uses loop to repeatedly loop until one of two things happen: either one of the futures is both realized and true, in which case, the loop returns with true; or all of the futures are realized and all of them false, in which case, the loop returns with false. It's important to have the (not ...) expressions at the end of their parent (and ...) expression, so that you don't get stuck checking whether any futures are true or false until they are all realized.

This new solution could be generalized as:

(defmacro future-or [& futures]
  `(loop []
     (cond (or ~@(for [f futures]
                   `(and (realized? ~f)
                         (deref ~f)))) true
           (and ~@(for [f futures]
                    `(realized? ~f))
                ~@(for [f futures]
                    `(not (deref ~f)))) false
           :else (recur))))

And used in the same way as the above future-or example.

Now, I know next to nothing about optimization. But as far as I can tell, this certainly isn't as efficient as it theoretically could be, because once any given future is realized, there is no real need to test its value more than once. Well, here are two solutions, which I've titled future-some. Since the futures being tested has to potentially change dynamically after every loop iteration, I had to make it a function. In that way, this new method is analogous to some, not or. In kind, I changed the behavior to take a collection of futures (as opposed a variable number of single arguments--another difference between some and or). One solution does no double-checking (I think):

(defn future-some [futures]
  (if (empty? futures)
    false
    (let [res (reduce (fn [unrealized f]
                        (if (realized? f)
                          (if @f
                            (reduced true)
                            unrealized)
                          (cons f unrealized)))
                      ()
                      futures)]
      (if (true? res)
        true
        (recur res)))))

There's a lot to detail here, but the gist is this: if there are no futures to test, it returns false, otherwise, it iterates down the list of futures, testing whether any of them are realized. If a future is realized, and also dereferences to true, the iteration breaks to return true. If a future is realized but does not dereference to true, then the iteration continues to the next item. If a future is unrealized, it is added a list to be used in the next recursion of future-some.

And the other solution is more concise, but somewhat less optimal:

(defn future-some [futures]
  (if (empty? futures)
    false
    (let [realized (filter realized? futures)]
      (if (some deref realized)
        true
        (recur (remove (set realized) futures))))))

Similar to the other one, except that it filters out the realized first, then tests, then filters again (this time inverse--to get the unrealized) if it needs to recur. This second filtering is the inefficient step.

A problem with all the solutions I propose are that future cancellations would result in errors upon dereferencing, when they should probably simply go on as though that future were false. This is solvable by placing (not (future-cancelled? ...)) expressions inside every single (and ...) expression, prior to any dereferencing. Or, for the future-some functions, you'd have to substitue the realized? predicate with (some-fn (comp not future-cancelled?) realized?), or #(and (not (future-cancelled %)) (realized? %)) for the faint of heart.

Again, seriously, thank you for that question.

Answer 4

In the general case, you can give the same promise to the two deliverers. E.g.:

(defn foo []
  (let [p (promise)]
    (future
      (Thread/sleep (rand-int 1000))
      (deliver p :a))
    (future 
      (Thread/sleep (rand-int 1000))
      (deliver p :b))
    @p))

Calling (foo) will randomly yield :a or :b as soon as the first deliver occurs; the other deliver will be a no-op.

To your specific case, you're requiring two booleans be returned. The only thing I can think of (and it's a bit messy) would be to use a third promise shared between the deliverers:

(defn foo []
  (let [a (promise)
        b (promise)
        link (promise)]
    (future
      (Thread/sleep (rand-int 5000))
      (let [res (rand-nth [true false])]
        (deliver link res)
        (deliver a res)))
    (future
      (Thread/sleep (rand-int 5000))
      (let [res (rand-nth [true false])]
        (deliver link res)
        (deliver b res)))
    {:or (or @link @a @b)  
     :a? (realized? a) 
     :b? (realized? b)
     :link @link
     :a @a 
     :b @b}))

• If a delivers true first, the or completes immediately.
• If a delivers false first, the @a returns immediately, then blocks on @b.
• If b delivers true first, the or completes immediately.
• If a delivers false first, it blocks on @a.

Repeatedly invoke (foo) and you should see expected results, specifically, when :or is true, then sometimes :a? or :b? will be false, but both will always be true if :or is false.