Mandelbrot set function does not perform as expected

Question

Here is an example from Clojure Programming Paperback by Chas Emerick:

(import 'java.awt.image.BufferedImage
        '(java.awt Color RenderingHints))

(defn- escape
  [^double a0 ^double b0 ^long depth]
  (loop [a a0, b b0, iteration 0]
    (cond
      (< 4 (+ (* a a) (* b b))) iteration
      (>= iteration depth) -1
      :else (recur (+ a0 (- (* a a) (* b b)))
                   (+ b0 (apply * [2 a b]))
                   (inc iteration)))))

(defn mandelbrot [rmin rmax imin imax
                  & {:keys [width height depth]
                     :or   {width 80 height 40 depth 1000}}]
  (let [mandelbrot-help
        (fn [^double rmin ^double rmax
             ^double imin ^double imax
             ]
          (let [stride-w (/ (- rmax rmin) width)
                stride-h (/ (- imax imin) height)]
            (loop [x 0
                   y (dec height)
                   escapes []]
              (if (== x width)
                (if (zero? y)
                  (partition width escapes)
                  (recur 0 (dec y) escapes))
                (recur (inc x) y (conj escapes
                                       (escape (+ rmin (* x stride-w))
                                               (+ imin (* y stride-h))
                                               depth)))))))]
    (mandelbrot-help rmin rmax imin imax)))

(defn render-text
  [mandelbrot-grid]
  (doseq [row mandelbrot-grid]
    (doseq [escape-iter row]
      (print (if (neg? escape-iter)
               \*
               \space)))
    (println)))

(defn render-image
  [mandelbrot-grid]
  (let [palette
        (vec (for
               [c (range 500)]
               (Color/getHSBColor 0.0 0.0 (/ (Math/log c) (Math/log 500)))))
        height (count mandelbrot-grid)
        width (count (first mandelbrot-grid))
        img (BufferedImage. width height BufferedImage/TYPE_INT_RGB)
        ^java.awt.Graphics2D g (.getGraphics img)]
    (doseq [[y row] (map-indexed vector mandelbrot-grid)
            [x escape-iter] (map-indexed vector row)]
      (.setColor g (if (neg? escape-iter)
                     (palette 0)
                     (palette (mod (dec (count palette)) (inc escape-iter)))))
      (.drawRect g x y 1 1))
    (.dispose g)
    img))


(do (time (mandelbrot -2.25 0.75 -1.5 1.5
                      :width 1600 :height 1200 :depth 1000))
    nil)

Everything works except that it takes 60s on my machine, and only 8s according to the book (results on my laptop are consistently better in other examples).

Is there something that I did wrong?

are other examples using java.awt? could be something system-specific in terms of graphics. also, maybe some profiling will bring something to light: https://stackoverflow.com/questions/2974916/profiling-tool-for-clojure — user2524973, May 13 '15 at 13:22
On my i7 it ran for about a minute and a half. Maybe Chas has a real beast of a machine? Are there other similar time reports in the book that don't match up with your results? — A Sammich, May 14 '15 at 18:45

score 4 · Accepted Answer · answered May 16 '15 at 16:47

Where did you get that code from? It is definitely not what appears either in the book (based on my PDF copy of it, page 449-452), or the code sample on github. In particular, the (apply * [2 a b]) in escape is crazy; that'll never be fast (at least not without any degree of [trivial] source-level optimization, which Clojure unfortunately doesn't apply). Even weirder, that particular snippet doesn't appear anywhere in the book, nor can I find it in the history of the git repo we used to collaborate on the writing of the book.

Maybe you were just tinkering with the examples? If not, I really would like to know where the sample you have came from, as it's absolutely not representative of our intent or best practice (obviously, given the timings you're seeing).

Anyway, here's the "fast escape" function from the book / github samples repo:

(defn- escape
  [^double a0 ^double b0 depth]
  (loop [a a0
         b b0
         iteration 0]
    (cond
      (< 4 (+ (* a a) (* b b))) iteration
      (>= iteration depth) -1
      :else (recur (+ a0 (- (* a a) (* b b)))
              (+ b0 (* 2 (* a b)))
              (inc iteration)))))


user> (do (time (mandelbrot -2.25 0.75 -1.5 1.5
                  :width 1600 :height 1200 :depth 1000))
          nil)
"Elapsed time: 1987.460104 msecs"

Hinting the depth arg as ^long (something that I should have included in the book example) drops that to 1450ms on my laptop.

Ah, I didn't copy those snippets, but typed them by hand, and I thought `(apply * [2 a b])` should be equivalent to your version. This will make me think twice before I use `apply`... Thanks! — qed, May 16 '15 at 19:16
BTW, what do you mean by the trivial source-level optimization? — qed, May 16 '15 at 19:25
Oooh-kay, that's a relief. Glad to know there's an innocuous explanation. `apply` is fundamental to FP, it's just useless overhead when the arity to a fn is known. — cemerick, May 16 '15 at 21:03
Many compilers apply optimizations to source (or near-source) code that will transform an application of a fn to a data structure literal to a direct invocation, e.g. `(apply * [a b c])` => `(* a b c)`. A similar optimization would be to eliminate directly-applied lambdas, e.g. `(#(+ 5 %) 8)` => `(+ 5 8)`. — cemerick, May 16 '15 at 21:07

Mandelbrot set function does not perform as expected

1 Answers1