How to run long computations without running an event loop in clojurescript?
Simple (but slow) function
I would like to use clojurescript for some functional style declarative programming in the browser - for example, to be able to do lazy evaluation, like:
(def special-nums
(->> (iterate inc 1)
(filter #(= (mod % 100) 0))
(filter #(= (mod % 7001) 0))))
(time (doall (take 1 special-nums)))
(Note that this particular calculation is not interesting to me at all - this is just an example of some code that will take some time to return even its first result)
Any way to tie cpu time to chunks?
Code like this seems natural to clojure, but is not suitable to be called in a browser environment where it can bypass the event loop and leave the web page unresponsive. Being lazy doesn't help because even the first result can take too long (1500ms on my machine).
In "normal" javascript with an imperative loop, I would split the range and use setTimeout
it to return results asynchronously, limiting the work I'm willing to do in any given snippet. (I can even link to an explicit clock reference - for example, "keep running until 20ms has elapsed, then stop and schedule another chunk.)
Is there a good way to do this in clojurescript? Obviously anything is possible via js interop, but if I struggle too hard with the system the cljs value seems to be limited.
Any tips / tricks here would be appreciated.
Note
I know web workers and I understand that turning off a computation into another thread of execution is always possible, but for this question, I would like to focus on approaches that work in a single JS event loop.
Thank!
source to share
The method that inspired this answer, trampoline is a function that returns a response, or another function that returns either a response or a function ..... (insert recursive English text here).
We cannot use clojure.core / trampoline here because it will bind the JS message loop. Instead, we can use something like the following, which "bounces" internally js/setTimeout
. When a f
function returns, we call it from setTimeout
. When f
anything else returns, we call (continuation result)
.
(defn continue-trampoline [continuation f & args]
(let [result-or-fn (apply f args)
is-answer (not (fn? result-or-fn))]
(if is-answer (continuation result-or-fn)
(do (js/setTimeout #(continue-trampoline continuation result-or-fn) 1)
nil))))
This allows us to break down a problem into smaller pieces that can be solved individually in less time.
To take an example with special numbers, you can break it down like this:
(defn calculate-special-nums [n continuation]
(letfn [(accumulate-special-nums [accumulator partitions]
(if (empty? partitions) accumulator
(let [part (first partitions)
remaining-n (- n (count accumulator))
acc (->> part
(filter #(= (mod % 100) 0))
(filter #(= (mod % 7001) 0))
(take remaining-n)
(into accumulator))
is-complete (== n (count acc))]
(if is-complete acc
#(accumulate-special-nums acc (rest partitions))))))]
(let [nums (iterate inc 1)
partitions (partition 1000 nums)]
(continue-trampoline continuation
#(accumulate-special-nums [] partitions)))))
So this code will calculate 10 special numbers and warn them when all ten are calculated, without starving other users of the message loop.
(calculate-special-nums 10 #(js/alert %))
This method could probably be extended to account for the elapsed milliseconds. For your example, I can imagine using partition-by
instead partition
. Create a function that returns true after some time. for example (partition-by has-the-time-elapsed? nums)
instead of (partition 1000 nums)
.
Other problems
As you said, even in "normal" javascript you have to break down the problem - clojurescript may or may not be an exception to expensive computations. One great thing about programming with a purely functional paradigm is that each part is independently tested. The output signal is always the same for each individual input. Hopefully clojurescript makes seperated problems easier.
source to share
After learning @ agent-j's excellent batum approach, I decided to give it a try core.async
for comparison.
This works pretty well and it allows me to wrap an existing function find-special-numbers
in a calculator by-chunk
with a fairly declarative syntax:
(ns calculate.core
(:require
[figwheel.client :as fw]
[cljs.core.async :refer [chan put! <! ]])
(:require-macros [cljs.core.async.macros :refer [go-loop]]))
(enable-console-print!)
; this is the slow, dumb function -- designed to
; take a limited-size input and produce 0 or more
; results
(defn find-special-numbers [input]
(->> input
(filter #(= (mod % 100) 0))
(filter #(= (mod % 7001) 0))))
(defn now [] (-> (js/Date.) .getTime))
(defn time-slice-in-ms [ms]
(let [start (now)]
(fn [] (-> (now) (- start) (quot ms)))))
; run a single chunk, report results, and schedule
; the next chunk of work in the event loop.
(defn by-chunk-step [chunks calc-fn result-chan]
(doseq [r (calc-fn (first chunks))]
(put! result-chan r))
(js/setTimeout #(by-chunk-step (rest chunks) calc-fn result-chan)))
; transform a set of inputs into chunks, then run
; kick off job to run a calculation function on each chunk.
; meanwhile, immediately return a result-reporting channel.
(defn by-chunk [inputs [ms] calc-fn]
(let [result-chan (chan)
chunks (partition-by (time-slice-in-ms ms) inputs)]
(by-chunk-step chunks calc-fn result-chan)
result-chan))
(defn all-ints [] #(iterate inc 1))
(defn load []
(let [results (by-chunk (all-ints) [20 :ms] find-special-numbers)]
(go-loop []
(println (<! results))
(recur))))
(fw/watch-and-reload :jsload-callback (load))
Pay attention to one obtained when defining all-ints
: it is important not to save the header of this list, otherwise the use of the stack will be unlimited and the browser will crash. Hence, it all-ints
returns a function, not a lazy list directly.
source to share