Mandelbrot set implementation in Scheme is very slow

Question

I am trying to learn Lisp/Scheme and I tried implementing a very simple version of the mandelbrot set in it to get practice. The problem I ran into is that the code runs very, very slow. At first I thought it was because I was using recursion instead of imperative loops, but I tried re-writing more or less the same code (recursion included) in python (which doesn't even have tail-call optimisation), and it ran very smooth

So I am wondering if there is something obvious I am missing in my code and what I could do to make it run faster.

Here is the code snippet in Scheme (racket). I also did pretty much the same thing in SBCL and the speed was comparable

#lang racket

(define-syntax dotimes 
   (syntax-rules () 
     ((_ (var n res) . body) 
      (do ((limit n) 
           (var 0 (+ var 1))) 
          ((>= var limit) res) 
        . body)) 
     ((_ (var n) . body) 
      (do ((limit n) 
           (var 0 (+ var 1))) 
          ((>= var limit)) 
        . body))))

(define (print-brot zr zc)
  (if (< (+ (* zr zr) (* zc zc)) 2)
      (display "@")
      (display ".")))

(define (brot zr zc cr cc i)
  (if (= i 0)
      (print-brot zr zc)
      (let ((z2r (- (* zr zr) (* zc zc))) (z2c (* 2 zr zc)))
        (brot (+ z2r cr) (+ z2c cc) cr cc (- i 1)))))

(define (linspace i w)
  (/ (- i (/ w 2)) (/ w 4)))

(define (brot-grid w h n)
  (dotimes (i w)
           (dotimes (j h)
                    (let ((x (linspace i w)) (y (linspace j h)))
                      (brot 0 0 x y n)))
           (newline)))

(brot-grid 40 80 20)

(I hope the code block is not too clustery, it was hard to strip it to something more simple)

Also, I know Scheme and Common Lisp have complex numbers built in but I wanted to test it using regular real numbers, I don't think this is the reason it runs so slow.

The parameter "i" of the brot function is the number of iterations, and the parameter "n" of brot-grid is also the number of iterations to use for each point. When I set it to more than like 10, the code takes forever to run, which doesn't seem normal. The increase in time taken also doesn't seem to be linear, for instance it only takes about a second on my machine with n = 10 but takes several minutes with n = 15 and doesn't even finish with n = 20

So, what is it that makes this code run so slow?

Thanks in advance

Answer 1

Looking at your code, I think you're testing it using rational numbers. This means pretty accurate arithmetics, with the drawback being atht you quickly end up using rationals with huge bignums as both numerator and denominator.

One way to ensure you're using floats (I'd suggest double-floats) is to have an intermediate function that converts all inputs to doubles, to make it easier to just type (say) 0 instead of 0d0.

Once you've established that using doubles makes it faster, you can start sprinkling type declarations throughout, to make it possible for the compiler to generate better code for you.

Answer 2

Here is a Common Lisp variant:

(defun print-brot (zr zc)
  (write-char (if (< (+ (* zr zr)
                        (* zc zc))
                     2.0d0)
                  #\@
                #\.)))

(defun brot (zr zc cr cc i)
  (loop repeat i
        for z2r = (- (* zr zr) (* zc zc))
        for z2c = (* 2.0d0 zr zc)
        until (or (> (abs zr) 1.0d50)
                  (> (abs zc) 1.0d50))
        do (setf zr (+ z2r cr)
                 zc (+ z2c cc)))
  (print-brot zr zc))

(defun linspace (i w)
  (/ (- i (/ w 2.0d0)) (/ w 4.0d0)))

(defun brot-grid (w h n)
  (terpri)
  (loop for i from 0.0d0 by 1.0d0
        repeat w do
        (loop for j from 0.0d0 by 1.0d0
              repeat h do
              (brot 0.0d0 0.0d0 (linspace i w) (linspace j h) n))
    (terpri)))

Notice the use of double float constants. Also iterating both over double floats and integers.

Running it in SBCL unoptimized, but compiled to native code:

*  (time (brot-grid 20 40 20))

........................................
....................@...................
....................@...................
....................@...................
...................@@@..................
.................@@@@@@@................
...................@@@..................
................@@@@@@@@@...............
..............@@@@@@@@@@@@@.............
............@@@@@@@@@@@@@@@@@...........
..............@@@@@@@@@@@@@.............
...............@@@@@@@@@@@..............
..................@...@.................
........................................
........................................
........................................
........................................
........................................
........................................
........................................
Evaluation took:
  0.003 seconds of real time
  0.002577 seconds of total run time (0.001763 user, 0.000814 system)
  100.00% CPU
  6,691,716 processor cycles
  2,064,384 bytes consed

Optimizing the code then would mean:

• higher compiler optimize setting
• possibly adding some type declarations
• getting rid of the float consing