L'implementazione del set di Mandelbrot in Scheme è molto lenta

Question

Sto cercando di imparare Lisp/Scheme e ho provato a implementare una versione molto semplice del mandelbrot impostato per ottenere pratica. Il problema che ho riscontrato è che il codice funziona molto, molto lentamente. All'inizio pensavo fosse perché stavo usando la ricorsione anziché i cicli imperiali, ma ho provato a riscrivere più o meno lo stesso codice (ricorsione inclusa) in python (che non ha nemmeno l'ottimizzazione del tail-call), e ha funzionato molto liscio

Quindi mi chiedo se c'è qualcosa di ovvio che mi manca nel mio codice e cosa potrei fare per farlo funzionare più velocemente.

Ecco lo snippet di codice in Schema (racket). Ho anche fatto più o meno la stessa cosa in SBCL e la velocità era paragonabile

#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) 

(spero che il blocco di codice non è troppo clustery, era difficile mettere a nudo a qualcosa di più semplice)

Inoltre, So che Scheme e Common Lisp hanno numeri complessi, ma ho voluto testarlo usando numeri reali regolari, non penso che questo sia il motivo per cui funziona così lentamente.

Il parametro "i" della funzione del brodo è il numero di iterazioni e il parametro "n" della griglia del brufolo è anche il numero di iterazioni da utilizzare per ciascun punto. Quando l'ho impostato su un valore maggiore di 10, il codice impiega un'eternità per funzionare, il che non sembra normale. Anche l'aumento del tempo impiegato non sembra lineare, ad esempio richiede circa un secondo sulla mia macchina con n = 10 ma richiede alcuni minuti con n = 15 e non finisce nemmeno con n = 20

Quindi, cos'è che rende questo codice così lento?

Grazie in anticipo

Answer 1

Guardando il tuo codice, penso che lo stia testando usando numeri razionali. Ciò significa aritmetica piuttosto accurata, con l'inconveniente che si finisce rapidamente per usare razionali con enormi bignum sia come numeratore che come denominatore.

Un modo per garantire che si sta utilizzando carri (io suggerirei di doppio-pompa) è quello di avere una funzione intermedia che converte tutti gli ingressi a doppie, per rendere più facile da digitare solo (diciamo) 0 invece di 0d0.

Una volta stabilito che l'utilizzo del doppio rende più veloce, è possibile iniziare a spargere dichiarazioni di tipo in tutto, per consentire al compilatore di generare un codice migliore per te.

Answer 2

Qui è una variante Common 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 (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))) 

Si noti l'uso di doppi costanti float. Anche iterando sia su double float che su interi.

L'esecuzione in SBCL non ottimizzata, ma compilato in codice nativo:

* (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 

Ottimizzare il codice, allora vorrebbe dire:

• superiore impostazione
• possibilmente l'aggiunta di alcune dichiarazioni di tipo compilatore ottimizzare
• sbarazzarsi della cassa mobile