优化Common Lisp算术性能：曼德博集合代码提速方案

我正在将计算曼德博集合颜色值的Python程序转成Common Lisp（SBCL）版本。Python版本运行耗时约1.2秒，我已经参考CL性能手册做了优化，但CL版本运行极慢，肯定哪里有问题。请问怎么提升它的性能？

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

当前的Common Lisp（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*))

优化建议及修正后的代码 #

核心优化点 #

• 修正数组维度与访问逻辑：Python中是行优先（高×宽）存储，CL代码原数组定义为(宽×高)，访问时x作为第一维度会导致内存访问不连续，影响缓存效率。改为(高×宽)的数组，访问时用(aref array y x)。
• 替换abs(z)为模平方计算：abs(z)需要开根号，开销大。判断abs(z) ≤2等价于(+ (expt (realpart z) 2) (expt (imagpart z) 2)) ≤4.0d0，直接计算模平方避免开根号，大幅提升循环效率。
• 添加显式类型声明：给函数参数、局部变量指定类型，让SBCL生成更高效的机器码，比如复数用(complex double-float)，循环计数用fixnum。
• 用defconstant定义常量：defparameter是可修改变量，编译器无法做常量折叠。固定值改用defconstant，让编译器提前优化计算。
• 预计算坐标转换系数：提前计算坐标缩放的固定系数，避免每次循环重复计算除法。
• 修正颜色计算逻辑：原CL代码颜色计算逻辑错误，改用整数运算替代浮点数除法，提升速度同时保证结果与Python一致。

优化后的代码 #

(declaim (optimize speed (safety 0) (debug 0)))

(defconstant +width+ 800)
(defconstant +height+ 600)
(defconstant +max-iter+ 80)
(defconstant +re-start+ -2.0d0)
(defconstant +re-end+ 1.0d0)
(defconstant +im-start+ -1.0d0)
(defconstant +im-end+ 1.0d0)

;; 预计算坐标转换系数
(defconstant +re-scale+ (/ (- +re-end+ +re-start+) +width+))
(defconstant +im-scale+ (/ (- +im-end+ +im-start+) +height+))

(defparameter *pixels* (make-array (list +height+ +width+) :element-type '(unsigned-byte 8) :initial-element 0))

(declaim (ftype (function (fixnum fixnum) (complex double-float)) coord-to-complex))
(defun coord-to-complex (x y)
  (declare (fixnum x y))
  (complex (+ +re-start+ (* (coerce x 'double-float) +re-scale+))
           (+ +im-start+ (* (coerce y 'double-float) +im-scale+))))

(declaim (ftype (function ((complex double-float)) fixnum) mandelbrot))
(defun mandelbrot (c)
  (declare (type (complex double-float) c))
  (let ((z #c(0.0d0 0.0d0))
        (n 0))
    (declare (type (complex double-float) z)
             (fixnum n))
    (loop while (and (<= (+ (expt (realpart z) 2) (expt (imagpart z) 2)) 4.0d0)
                     (< n +max-iter+))
          do (setf z (+ (* z z) c)
                   n (1+ n)))
    n))

(declaim (ftype (function ((array (unsigned-byte 8) (* *))) null) calculate-mandelbrot))
(defun calculate-mandelbrot (array)
  (loop for x fixnum from 0 below +width+ do
    (loop for y fixnum from 0 below +height+ do
          (let* ((c (coord-to-complex x y))
                 (m (mandelbrot c))
                 (color (- 255 (truncate (* m 255) +max-iter+))))
            (declare (fixnum m color))
            (setf (aref array y x) color)))))

;; 测试运行时间
(let ((start (get-internal-real-time)))
  (calculate-mandelbrot *pixels*)
  (format t "耗时: ~,3F 秒~%" (/ (- (get-internal-real-time) start) internal-time-units-per-second)))

额外说明 #

• 开启了(safety 0) (debug 0)进一步优化性能，若需要调试可调整这两个参数。
• 数组指定了element-type '(unsigned-byte 8)，匹配颜色值的范围，减少内存占用并提升访问速度。
• 用get-internal-real-time替代 profiling 直接测试运行时间，更直观查看优化效果。

内容的提问来源于stack exchange，提问作者Unsatisfied Zebra