speed question

[Dmitri]

I've been playing around with rendering a mandelbrot set, and using
pure java it renders about 2 seconds on my machine, however it runs
about 10 times as slow in clojure, I was curious if I'm doing anything
obviously wrong, or if it's just life :) I do run it with the -server
flag, which does improve it a bit. I've got the java and clojure
source below:

import java.awt.Canvas;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.image.BufferStrategy;
import java.awt.image.ImageObserver;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Mandelbrot extends Canvas implements ImageObserver {

public static final int WIDTH = 640;
public static final int HEIGHT = 640;
private static int BAILOUT = 4;
private static int MAX_ITERATIONS = 32;

public BufferStrategy strategy;

public Mandelbrot () {
setBounds(0,0,WIDTH,HEIGHT);
setBackground(Color.BLACK);

JPanel panel = new JPanel();
panel.setPreferredSize(new Dimension(WIDTH, HEIGHT));
panel.setLayout(null);

panel.add(this);

JFrame frame = new JFrame("Mandelbrot");
frame.add(panel);

frame.setBounds(0,0,WIDTH, HEIGHT);
frame.setResizable(false);
frame.setVisible(true);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

//create a double buffer
createBufferStrategy(2);
strategy = getBufferStrategy();
requestFocus();
}

private int checkBounds(float x, float y) {
float cr = x;
float ci = y;
float zi = 0.0f;
float zr = 0.0f;
int i = 0;

while (true) {
i++;
float temp = zr * zi;
float zr2 = zr * zr;
float zi2 = zi * zi;
zr = zr2 - zi2 + cr;
zi = temp + temp + ci;
if (zi2 + zr2 > BAILOUT)
return i;
if (i > MAX_ITERATIONS)
return 0;
}
}

private void draw() {
float x = -2.1f, y = -1.5f, z = 3.0f;
int i, j;

Graphics g = strategy.getDrawGraphics();
g.clearRect(0, 0, getWidth(), getHeight());
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {

int value = checkBounds((x + z*(i/(float)WIDTH)), (y + z*(j/(float)
HEIGHT)));

if (value > 0) {
g.setColor(new Color(value*255/MAX_ITERATIONS));
g.drawRect(i, j, 0, 0);
}
}
strategy.show();
}
strategy.show();
}

public static void main(String args[]) {

Mandelbrot m = new Mandelbrot();
long startTime = System.currentTimeMillis();
m.draw();
System.out.println((System.currentTimeMillis() - startTime)/1000);
}
}

Clojure:

(ns main
(:import (java.awt Color Container Graphics Canvas Dimension)
(javax.swing JPanel JFrame)
(java.awt.image BufferedImage BufferStrategy)))

(def *width* 640)
(def *height* 640)
(def *max-steps* 32)

(defn on-thread [f] (doto (new Thread f) (.start)))

(defn check-bounds [x y]
(loop [px x
py y
zx 0.0
zy 0.0
zx2 0.0
zy2 0.0
value 0]
(if (and (< value *max-steps*) (< (+ zx2 zy2)
4.0))
(let [new-zy (+ (* 2.0 zx zy) py)
new-zx (+ (- zx2 zy2) px)
new-zx2 (* new-zx new-zx)
new-zy2 (* new-zy new-zy)]
(recur px py new-zx new-zy new-zx2 new-zy2 (inc
value)))
(if (== value *max-steps*) 0 value))))

(defn draw-line [g y]
(let [dy (- 1.25 (* 2.5 (/ y *height*)))]
(doseq [x (range 0 *width*)]
(let [dx (- (* 2.5 (/ x *width*)) 2.0)]
(let [value (check-bounds dx dy)]
(if (> value 0)
(doto g
(. setColor (Color. (* value (/ 255 *max-
steps*))))
(. drawRect x y 0 0))))))))

(defn draw-lines
([buffer g] (draw-lines buffer g *height*))
([buffer g y]
(doseq [y (range 0 y)]
(draw-line g y)
;(on-thread (draw-line g y))
(. buffer show))))


(defn draw [canvas]
(let [buffer (. canvas getBufferStrategy)
g (. buffer getDrawGraphics)]
(draw-lines buffer g)))

(defn main []

(let [panel (JPanel.)
canvas (Canvas.)
frame (JFrame. "Mandelbrot")]

(doto panel
(.setPreferredSize (Dimension. *width* *height*))
(.setLayout nil)
(.add canvas))

(doto frame
(.setDefaultCloseOperation JFrame/
EXIT_ON_CLOSE)
(.setBounds 0,0,*width* *height*)
(.setResizable false)
(.add panel)
(.setVisible true))

(doto canvas
(.setBounds 0,0,*width* *height*)
(.setBackground (Color/BLACK))
(.createBufferStrategy 2)
(.requestFocus))

(draw canvas)))

(time (main))

[CuppoJava]

From a quick glance, I think the lack of type hints is what's slowing
down your Clojure code.
You can set the global variable *warn-on-reflection* to true, to get a
sense of where to add your type hints.
-Patrick

[Dmitri]

I actually tried forcing the type hints and didn't really see a
noticeable improvement, just made the code hard to read for the most
part.

[Stuart Sierra]

On Apr 1, 9:40 pm, Dmitri <dmitri.sotni...@gmail.com> wrote:
> I've been playing around with rendering a mandelbrot set, and using
> pure java it renders about 2 seconds on my machine, however it runs
> about 10 times as slow in clojure, I was curious if I'm doing anything
> obviously wrong, or if it's just life :) I do run it with the -server
> flag, which does improve it a bit. I've got the java and clojure
> source below:

Are you running the Clojure source as a script on the command line?
Some of the delay may be Clojure starting up and parsing the script.

You should also try using primitive types in the loops. See this
thread for details:
http://groups.google.com/group/clojure/browse_thread/thread/61f236e830d98cb3/9637bba3451a30bd

-Stuart Sierra

[Dmitri]

I'm running it as a script with:
java -server -cp clojure.jar clojure.lang.Script mandelbrot.clj

as I mentioned earlier, I did try forcing all the primitives, but
didn't notice much of a difference, I also did try running the draw
function repeatedly to make sure it wasn't just the startup times
causing it to run slow.

(main []
...

(time (draw canvas))
(time (draw canvas))
(time (draw canvas))))


as a note I also tried a jython version and it runs about twice as
fast for me, which I think is comparable, and it could just mean that
there is a
hit on performance over java that only so much can be done about.

I'm mostly curious if I made any newbie mistakes that would cause it
to perform a lot worse than it should. I do expect pure java to run
faster in the end.

> thread for details:http://groups.google.com/group/clojure/browse_thread/thread/61f236e83...
>
> -Stuart Sierra

[William D. Lipe]

I did this:

(defn draw [#^Canvas canvas]
(let [#^BufferStrategy buffer (. canvas getBufferStrategy)
#^Graphics g (. buffer getDrawGraphics)]
(doseq [y (range 0 *height*)]
(let [dy (- 1.5 (* 2.5 (/ y *height*)))]

(doseq [x (range 0 *width*)]

(let [dx (- (* 3 (/ x *width*)) 2.1)
value (check-bounds dx dy)]
(when (> value 0)
(.setColor g (Color. (* value (/ 255 *max-steps*))))
(.drawRect g x y 0 0))))
(.show buffer)))
(.show buffer)))

and this:

(defn check-bounds [x y]
(let [px (float x) py (float y)]
(loop [zx (float 0.0)
zy (float 0.0)
zx2 (float 0.0)
zy2 (float 0.0)
value (int 0)]

(if (and (< value *max-steps*) (< (+ zx2 zy2) 4.0))

(let [new-zy (float (+ (* 2.0 zx zy) py))
new-zx (float (+ (- zx2 zy2) px))
new-zx2 (float (* new-zx new-zx))
new-zy2 (float (* new-zy new-zy))]
(recur new-zx new-zy new-zx2 new-zy2 (inc value)))
(if (== value *max-steps*) 0 value)))))

and it seemed to speed up notably.

[Paul Stadig]

I got it down to about 3 seconds. I did what William said, but the biggest improvement was from changing the way *width*, *height*, and *max-steps* were defined. I noticed that in the Java version they are constants, but in the Clojure version they are Vars which means that inside your tight inner loops you are dereferencing the vars multiple times. Vars are for thread local values, but these values are not expected to change. I'm not sure the best way to make these vars into constants, but I changed them into macros:

(defmacro *width* [] (float 640))

Then replaced instances of *width* with (*width*). The macros will get compiled down to floats instead of resulting in multiple Var.deref calls (and probably Number.floatValue calls) per loop iteration.

Here is the code:

(ns main
 (:import (java.awt Color Container Graphics Canvas Dimension)
          (javax.swing JPanel JFrame)
          (java.awt.image BufferedImage BufferStrategy)))

(set! *warn-on-reflection* true)

(defmacro *width* [] (float 640))
(defmacro *height* [] (float 640))
(defmacro *max-steps* [] (float 32))

(defn on-thread [#^Runnable f] (doto (new Thread f) (.start)))

(defn check-bounds [x y]
   (loop [px (float x)
          py (float y)

          zx (float 0.0)
          zy (float 0.0)
          zx2 (float 0.0)
          zy2 (float 0.0)

          value (float 0)]
      (if (and (< value (*max-steps*)) (< (+ zx2 zy2) (float 4.0)))
           (let [new-zy (float (+ (* (float 2.0) zx zy) py))

                 new-zx (float (+ (- zx2 zy2) px))
                 new-zx2 (float (* new-zx new-zx))
                 new-zy2 (float (* new-zy new-zy))]

                 (recur px py new-zx new-zy new-zx2 new-zy2 (inc value)))
           (if (== value (*max-steps*)) 0 value))))

(defn draw-line [#^Graphics g y]
   (let [dy (- 1.25 (* 2.5 (/ y (*height*))))]
     (doseq [x (range 0 (*width*))]
       (let [dx (- (* 2.5 (/ x (*width*))) 2.0)]

               (let [value (check-bounds dx dy)]
                   (if (> value  0)
                       (doto g

                           (. setColor (Color. (* value (/ 255 (*max-steps*)))))

                           (. drawRect x y 0 0))))))))

(defn draw-lines

   ([buffer g] (draw-lines buffer g (*height*)))
   ([#^BufferStrategy buffer g y]

         (doseq [y (range 0 y)]
            (draw-line g y)
            ;(on-thread (draw-line g y))
            (. buffer show))))

(defn draw [#^Canvas canvas]

   (let [buffer (. canvas getBufferStrategy)
         g        (. buffer getDrawGraphics)]
         (draw-lines buffer g)))

(defn main []

 (let [panel (JPanel.)
       canvas (Canvas.)
       frame (JFrame. "Mandelbrot")]

   (doto panel

     (.setPreferredSize (Dimension. (*width*) (*height*)))

     (.setLayout nil)
     (.add canvas))

   (doto frame
     (.setDefaultCloseOperation JFrame/EXIT_ON_CLOSE)

     (.setBounds 0,0,(*width*) (*height*))

     (.setResizable false)
     (.add panel)
     (.setVisible true))

   (doto canvas

     (.setBounds 0,0,(*width*) (*height*))

     (.setBackground (Color/BLACK))
     (.createBufferStrategy 2)
     (.requestFocus))

   (draw canvas)))

(time (main))

~$ clojure /tmp/mandelbrot.clj
"Elapsed time: 3577.128587 msecs"


Paul

[MikeM]

Starting with your version, I got about a 2x improvement with the
following:

(defn check-bounds [x y]
(let [f2 (float 2.0)
f4 (float 4.0)]

(loop [px (float x)
py (float y)
zx (float 0.0)
zy (float 0.0)
zx2 (float 0.0)
zy2 (float 0.0)
value (float 0)]

(if (and (< value (*max-steps*)) (< (+ zx2 zy2) f4))
(let [new-zy (float (+ (* (* f2 zx) zy) py))

new-zx (float (+ (- zx2 zy2) px))
new-zx2 (float (* new-zx new-zx))
new-zy2 (float (* new-zy new-zy))]
(recur px py new-zx new-zy new-zx2 new-zy2 (inc
value)))

(if (== value (*max-steps*)) 0 value)))))

f2 and f4 didn't do much, most improvement seems to come from (* (* f2
zx) zy) in place of (* f2 zx zy). Using the arity 2 multiply results
in the multiply being inlined.

[Dmitri]

like Paul said earlier changing the globals to macros makes seems to
make a huge impact.
and the check-bounds and draw-line get called for each line on the
screen so it makes sense
that optimizations there will make a big impact.

[David Sletten]

Building on your and Paul's improvements I simply wrapped (almost)
everything in a 'let' rather than using 'def' or Paul's cool macro
idea. I also pulled out a couple of divisions from draw-line. This
takes about 38% of the time of Paul's version:
(let [width (float 640)
height (float 640)
max-steps (float 32)
color-scale (float (quot 255 max-steps))
height-factor (/ 2.5 height)
width-factor (/ 2.5 width)]

(defn on-thread [#^Runnable f] (doto (new Thread f) (.start)))

(defn check-bounds [x y]

(let [f2 (float 2.0)
f4 (float 4.0)]
(loop [px (float x)
py (float y)
zx (float 0.0)
zy (float 0.0)
zx2 (float 0.0)
zy2 (float 0.0)
value (float 0)]

(if (and (< value max-steps) (< (+ zx2 zy2) f4))

(let [new-zy (float (+ (* (* f2 zx) zy) py))
new-zx (float (+ (- zx2 zy2) px))
new-zx2 (float (* new-zx new-zx))
new-zy2 (float (* new-zy new-zy))]
(recur px py new-zx new-zy new-zx2 new-zy2 (inc
value)))

(if (== value max-steps) 0 value)))))

(defn draw-line [#^Graphics g y]

(let [dy (- 1.25 (* y height-factor))]
(doseq [x (range 0 width)]
(let [dx (- (* x width-factor) 2.0)]

(let [value (check-bounds dx dy)]
(if (> value 0)
(doto g

(. setColor (Color. (* value color-scale)))

(. drawRect x y 0 0))))))))

(defn draw-lines
([buffer g] (draw-lines buffer g height))

([#^BufferStrategy buffer g y]
(doseq [y (range 0 y)]
(draw-line g y)
;(on-thread (draw-line g y))
(. buffer show))))

(defn draw [#^Canvas canvas]
(let [buffer (. canvas getBufferStrategy)
g (. buffer getDrawGraphics)]
(draw-lines buffer g)))

(defn main []

(let [panel (JPanel.)
canvas (Canvas.)
frame (JFrame. "Mandelbrot")]

(doto panel
(.setPreferredSize (Dimension. width height))
(.setLayout nil)
(.add canvas))

(doto frame
(.setDefaultCloseOperation JFrame/EXIT_ON_CLOSE)
(.setBounds 0,0,width height)

(.setResizable false)
(.add panel)
(.setVisible true))

(doto canvas
(.setBounds 0,0,width height)

(.setBackground (Color/BLACK))
(.createBufferStrategy 2)
(.requestFocus))

(draw canvas))))

Aloha,
David Sletten

[Dmitri]

Thanks a lot, that's really helpful. I never thought of using a macro
to define constants
like that, it's definitely a good trick and it does seem to result in
the biggest performance
gain.

[Bradbev]

It would seem that macros in this case should not be required. A
normal function that simply returns a constant should get inlined by
the JIT.

Cheers,
Brad

[Paul Stadig]

I think you are right, Brad.

However, I wonder though if there is a better way to define a constant. Neither the macro nor function seems clean. I like David's wrapping-the-whole-thing-in-a-let, but what if you wanted to access the value of "width" in a different file? Would one have to resort to defining a Java class (at compile time or runtime)?


Paul

[MikeM]

There is definline which seems appropriate in place of the constant
macros.

(definline my-const [] 1)
(my-const) ;= 1

[Paul Stadig]

Yeah that works the same as defining a function, just more explicit. I was looking for a way to define a constant and just use it as "my-const" without having to use the parens to call a function or a macro. I guess that would be something like a symbol macro in CL?


Paul

[Bradbev]

It seems to me that the real solution is that the Clojure compiler
needs to support global constants. You could probably emulate the
behaviour by rebinding global vars inside the let though.

(def *foo* 100)
(defn bar []
(let [foo *foo*]
...))

Brad

On Apr 2, 7:57 am, Paul Stadig <p...@stadig.name> wrote:
> I think you are right, Brad.
>
> However, I wonder though if there is a better way to define a constant.
> Neither the macro nor function seems clean. I like David's
> wrapping-the-whole-thing-in-a-let, but what if you wanted to access the
> value of "width" in a different file? Would one have to resort to defining a
> Java class (at compile time or runtime)?
>
> Paul
>

[Raffael Cavallaro]

If you change the color constructor you can get some nice color
effects:

(. setColor (let [scaled (Math/round (* value color-scale))]
(Color. 255 (- 255 scaled) scaled)))

will give you yellow and magenta for example

[Dmitri]

nifty :)

On Apr 2, 5:10 pm, Raffael Cavallaro <raffaelcavall...@gmail.com>
wrote:

[Dmitri]

yeah I definitely agree that it would be nice if constants could be
used without the parens.

On Apr 2, 11:48 am, Paul Stadig <p...@stadig.name> wrote:
> Yeah that works the same as defining a function, just more explicit. I was
> looking for a way to define a constant and just use it as "my-const" without
> having to use the parens to call a function or a macro. I guess that would
> be something like a symbol macro in CL?
>
> Paul
>

[RZez...@gmail.com]

Could Clojure have something similar to CL's 'defconstant'?

http://gigamonkeys.com/book/variables.html

[Raffael Cavallaro]

this one is nice too:

(defn draw-line [#^Graphics g y]
(let [dy (- 1.25 (* y height-factor))]
(doseq [x (range 0 width)]
(let [dx (- (* x width-factor) 2.0)]
(let [value (check-bounds dx dy)

scaled (Math/round (* value color-scale))

xscaled (Math/round (* x (/ 255 width)))]
(if (> value 0)
(. g setColor

(Color. 255 (- 255 scaled) scaled))

(. g setColor
(Color. xscaled (- 255 xscaled) xscaled)))
(. g drawRect x y 0 0))))))