Mandelbrot implementation on the diagram is very slow

Question

I am trying to learn Lisp / Scheme and I tried to implement a very simple version of the mandelbrot kit in it to get practice. The problem I ran into is that the code is very slow. At first I thought it was because I used recursion instead of imperative loops, but I tried to rewrite more or less the same code (including recursion) in python (which didn't even optimize the tail) and it ran very smooth

So, I am wondering if there is something obvious in my code and what I can do to make it work faster.

Here is the code snippet in Scheme (racket). I also did almost the same 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 iw) (/ (- i (/ w 2)) (/ w 4))) (define (brot-grid whn) (dotimes (iw) (dotimes (jh) (let ((x (linspace iw)) (y (linspace jh))) (brot 0 0 xyn))) (newline))) (brot-grid 40 80 20) 

(I hope the code block is not too clustered, it was difficult to separate it from something simpler)

In addition, I know that Scheme and Common Lisp have built-in complex numbers, but I wanted to test them using regular real numbers, I do not think that this is the reason why it works so slowly.

The i parameter of the brot function is the number of iterations, and the n parameter of the brot grid is also the number of iterations to use for each point. When I install it more than 10, the code runs forever, which does not seem normal. The increase in time also does not seem linear, for example, it takes about a second on my machine with n = 10, but takes several minutes with n = 15 and does not even end with n = 20

So what makes this code so slow?

Thank you in advance

Answer 1

Looking at your code, I think you are testing it using rational numbers. This means fairly accurate arithmetic, with the disadvantage that you quickly end up using rational solutions with huge bonuses, both the numerator and the denominator.

One way to ensure that you are using float (I suggest double-floats) is to have an intermediate function that converts all inputs to paired ones to make it easy to just enter (say) 0 instead of 0d0 .

Once you have found that using doubles makes it faster, you can start spatter-type declarations all over, so that the compiler can generate more efficient code for you.

Answer 2

Here is a generic version of Lisp:

 (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 (iw) (/ (- i (/ w 2.0d0)) (/ w 4.0d0))) (defun brot-grid (whn) (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 iw) (linspace jh) n)) (terpri))) 

Pay attention to the use of double float constants. Also iteration of both double floats and integers.

Running it in SBCL is not optimized, but compiled into 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 

Code optimization would then mean:

• setting up a higher compiler
• it is possible to add ads of a certain type
• get rid of consing float