I'm trying to convert Python -> CL for a program that calculates x,y color values for the Mandelbrot set.
The python version takes about 1.2 seconds to complete. I tried using the CL cookbook for performance tips, but my CL attempt is taking an eternity, so I'm doing something very wrong.
How can I improve its performance?
Python:
import time
t0 = time.time()
WIDTH = 800
HEIGHT = 600
PIXELS = [[None] * WIDTH for _ in range(HEIGHT)]
# Plot window
RE_START = -2
RE_END = 1
IM_START = -1
IM_END = 1
MAX_ITER = 80
def mandelbrot(c):
z = 0
n = 0
while abs(z) <= 2 and n < MAX_ITER:
z = z*z + c
n += 1
return n
for x in range(0, WIDTH):
for y in range(0, HEIGHT):
c = complex(RE_START + (x / WIDTH) * (RE_END - RE_START),
IM_START + (y / HEIGHT) * (IM_END - IM_START))
m = mandelbrot(c)
color = 255 - int(m * 255 / MAX_ITER)
PIXELS[y][x] = color
t1 = time.time()
print(t1-t0)
CL (SBCL):
(require :sb-sprof)
(declaim (optimize speed))
(defparameter *WIDTH* 800)
(defparameter *HEIGHT* 600)
(defparameter *PIXELS* (make-array `(,*WIDTH* ,*HEIGHT*) :initial-element 0))
(defparameter *MAX-ITER* 80)
(defparameter *RE-START* -2)
(defparameter *RE-END* 1)
(defparameter *IM-START* -1)
(defparameter *IM-END* 1)
(defun coord-to-complex (x y)
(complex (+ *RE-START* (* (/ x *WIDTH*) (- *RE-END* *RE-START*)))
(+ *IM-START* (* (/ y *HEIGHT*) (- *IM-END* *IM-START*)))))
(defun mandelbrot (c)
(let ((z 0)
(n 0))
(loop while (and (<= (abs z) 2) (< n *MAX-ITER*))
do (setf z (+ (* z z) c)
n (1+ n)))
n))
(defun calculate-mandelbrot (array)
(loop for x from 0 below *WIDTH* do
(loop for y from 0 below *HEIGHT* do
(let* ((c (coord-to-complex x y))
(m (mandelbrot c))
(color (- 255 (/ 255 (* m *MAX-ITER*)))))
(setf (aref array x y) color)))))
(sb-sprof:with-profiling (:max-samples 1000
:report :flat
:loop nil)
(calculate-mandelbrot *PIXELS*))
In coord-to-complex, you force the system to work with fractions. Try to replace it with
(defun coord-to-complex (x y)
(complex (+ *RE-START* (* (/ x 1.0 *WIDTH*) (- *RE-END* *RE-START*)))
(+ *IM-START* (* (/ y 1.0 *HEIGHT*) (- *IM-END* *IM-START*)))))
so that it uses floats.
There are other possible improvements (e.g., declaring types), but this itself makes it finish in second or so.
After fixing most of the sbcl optimization warnings it can get almost order of magnitude faster, see below (I picked single floats for calculation, double floats should be about same).
(defparameter *WIDTH* 800)
(defparameter *HEIGHT* 600)
(defparameter *PIXELS*
(make-array `(,*WIDTH* ,*HEIGHT*)
:initial-element 0s0
:element-type 'single-float))
(defparameter *MAX-ITER* 80)
(defparameter *RE-START* -2s0)
(defparameter *RE-END* 1s0)
(defparameter *IM-START* -1s0)
(defparameter *IM-END* 1s0)
(defun coord-to-complex (x y)
(declare (fixnum *width* *height* x y)
(single-float *re-end* *re-start* *im-end* *im-start*))
(complex (+ *RE-START* (* (/ x 1s0 *WIDTH*) (- *RE-END* *RE-START*)))
(+ *IM-START* (* (/ y 1s0 *HEIGHT*) (- *IM-END* *IM-START*)))))
(defun mandelbrot (c)
(let ((z #C(0s0 0s0))
(n 0))
(declare ((complex single-float) z c)
(fixnum n *max-iter*))
(loop while (and (<= (abs z) 2) (< n *MAX-ITER*))
do (setf z (+ (* z z) c)
n (1+ n)))
n))
(defun calculate-mandelbrot (array)
(declare ((simple-array single-float) array)
(fixnum *max-iter*))
(loop for x fixnum from 0 below *WIDTH* do
(loop for y fixnum from 0 below *HEIGHT* do
(let ((color (- 255 (* (mandelbrot
(coord-to-complex x y))
255 (/ 1s0 *MAX-ITER*)))))
(setf (aref array x y) color)))))