ECL 中的 ffi:c-inline

Posted by David Gu on December 3, 2016

今天在 Twitter 上看到有人转发标题为 “NumPy vs. Common Lisp” 的帖子,似乎不少日本的 Lisp 程序员们对此交流甚欢。这个帖子主要围绕 Numpy 和 Common Lisp 的性能比较进行讨论,尤其是如何一步一步地优化 Lisp 代码使之变快。为了方便阅读,我们干脆把 Python 和 Lisp 的代码先都贴在下面:

Python 3.4.31 + Numpy

import numpy as np
import time

N = 100000

# Python 版
def sumup(n):
    return sum(range(1, n + 1))

# NumPy 版
def sumup(n):
    return np.arange(1, n + 1).sum()

def main():
    print("python with numpy start.")
    result = {}
    for count in range(1, N + 1):
        result[count - 1] = sumup(count)
    print("python with numpy end.")

start = time.time()
main()
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time))

SBCL 1.3.11

(defparameter *n* 100000)

;; 1. 只声明参数类型
(defun sumup1 (n)
  (declare (type fixnum n))
  (let ((sum 0))
    (loop for i from 1 to n
          do (incf sum i))
    sum))

;; 2. 同时声明参数以及局部变量的类型
(defun sumup2 (n)
  (declare (type fixnum n))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i from 1 to n
          do (incf sum i))
    sum))

;; 3. 声明参数类型、局部变量类型,同时声明 optimize 参数,放弃运行时的类型检查
(defun sumup3 (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i from 1 to n
          do (incf sum i))
    sum))

;; 4. 进一步声明 loop 内部变量的类型
(defun sumup4 (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i fixnum from 1 to n
          do (incf sum i))
    sum))

;; 5.  进一步声明函数的类型签名
(declaim (ftype (function (fixnum) fixnum) sumup5))
(defun sumup5 (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i fixnum from 1 to n
          do (incf sum i))
    sum))

(defun main ()
  (print "common lisp start.")
  (loop for count from 1 to *n*
        collect (sumup5 count))
  (print "common lisp end."))

(time (main))

作者最后还给出了一个截图,表示高度优化下的 sumup4sumup5 比 NumPy 的实现要快了三倍多:

看到这里,我不禁在想,为何不使用 ECL 的“独门秘笈”呢?ECL 全称 Embeddable Common Lisp,即“可嵌入的 Common Lisp”。在众多 Lisp 实现中,ECL 是唯一一个可以把 C 代码和 Lisp 代码混着写的一个实现。这听上去似乎很不可思议。但是通过使用 ECL 的 ffi:c-inline,我们几乎可以毫不费力的达到这个目标:

;;;; Syntax
;;;; ffi:c-inline (lisp-values) (arg-c-types) return-type c/c++-code &key (side-effects t) (one-liner nil)
;;;; lisp-values  -> 一个或多个 Lisp 表达式;
;;;; arg-c-types  -> 一个或多个有效的 FFI 类型,类如 :int, :double, 等等;
;;;;                 这里有一些类型可供参考: https://common-lisp.net/project/ecl/manual/re24.html;
;;;; return-type  -> 一个有效的 FFI 类型,或者 (values ffi-type*),即外部多重值的返回类型;
;;;; c/c++-code   -> 一段字符串形式书写的 C/C++ 代码;
;;;; side-effects -> 表明表达式是否带有副作用的布尔值,默认为 T;
;;;; one-liner    -> 一个布尔值,如果为真,则 c/c++-code 不能有 `return` 关键字出现;默认为 nil。
(defun power (base exp)
  (ffi:c-inline (base exp) (:double :int) :double
    "{ int i;
       double result = 1.0;
       for(i = 1; i<= #1; i++){
         result = result * #0;
       }
       @(return) = result;
     }"))

在上面的 power 函数中,我们把 baseexp 作为要“交待给” C 的形参,然后指明参数类型和返回类型;接着在一段 C 代码中,#0#1 分别表示第一个和第二个参数,即 baseexp;最后,@(return) 关键字返回结果 result

现在,我们用这种机制来实现一个 sumup 并且和 Python, NumPy 以及 SBCL 中的终极版本 sumup5 简略地做一下对比:

ECL-16.1.22

;;;; benchmark-ecl.lisp
(defparameter *n* (expt 10 5))

(defun sumup (n)
  (declare (optimize (speed 3) (safety 0)))
  (ffi:c-inline (n) (:fixnum) :fixnum
    "{ cl_fixnum sum = 0;
       for (cl_fixnum i = 1; i <= #0; i++){
         sum += i;
       }
       @(return)=sum;
     }"))
     
(defun main ()
  (print "ECL starts.")
  (loop for count from 1 to *n*
     collect (sumup count))
  (print "ECL ends."))

(progn
  (main)
  (ext:quit))

SBCL-1.3.12

;;;; benchmark-sbcl.lisp
(defparameter *n* (expt 10 5))

(declaim (ftype (function (fixnum) fixnum) sumup5))
(defun sumup (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i fixnum from 1 to n
          do (incf sum i))
    sum))

(defun main ()
  (print "SBCL starts.")
  (loop for count from 1 to *n*
        collect (sumup count))
  (print "SBCL ends."))

Python 和 NumPy 的代码则不做变动。

Build and Compare

Build executables for ECL and SBCL3

$ rlwrap ecl
ECL (Embeddable Common-Lisp) 16.1.2 (git:UNKNOWN)
Copyright (C) 1984 Taiichi Yuasa and Masami Hagiya
Copyright (C) 1993 Giuseppe Attardi
Copyright (C) 2000 Juan J. Garcia-Ripoll
Copyright (C) 2015 Daniel Kochmanski
ECL is free software, and you are welcome to redistribute it
under certain conditions; see file 'Copyright' for details.
Type :h for Help.
Top level in: #<process TOP-LEVEL>.
> (compile-file "benchmark-ecl.lisp" :system-p t)

;;; Loading #P"/usr/local/lib/ecl-16.1.2/cmp.fas"
;;;
;;; Compiling benchmark-ecl.lisp.
;;; OPTIMIZE levels: Safety=2, Space=0, Speed=3, Debug=0
;;;
;;; Compiling (DEFPARAMETER *N* ...).
;;; Compiling (DEFUN SUMUP ...).
;;; Compiling (DEFUN MAIN ...).
;;; End of Pass 1.
;;; Emitting code for SUMUP.
;;; Emitting code for MAIN.
;;; Emitting code for #:G5.
;;; Finished compiling benchmark-ecl.lisp.
;;;
#P"/private/tmp/benchmark-ecl.o"
NIL
NIL
> (c:build-program "benchmark-ecl" :lisp-files '("benchmark-ecl.o"))

#P"benchmark-ecl"
> ^D

$ cl -l sbcl --load benchmark-sbcl.lisp --restart main --output ./benchmark-sbcl --dump !
[undoing binding stack and other enclosing state... done]
[defragmenting immobile space... done]
[saving current Lisp image into /private/tmp/./benchmark-sbcl:
writing 4800 bytes from the read-only space at 0x20000000
writing 3216 bytes from the static space at 0x20100000
writing 1105920 bytes from the immobile space at 0x20300000
writing 13283296 bytes from the immobile space at 0x21b00000
writing 35356672 bytes from the dynamic space at 0x1000000000
done]

$ ls -lhi benchmark-*cl
20930193 -rwxr-xr-x  1 david  wheel    11K Dec  3 03:08 benchmark-ecl
20930279 -rwxr-xr-x  1 david  wheel    48M Dec  3 03:12 benchmark-sbcl

Compare4

$ ls -lhi benchmark-*
20930193 -rwxr-xr-x  1 david  wheel    11K Dec  3 03:08 benchmark-ecl
20870011 -rwxr-xr-x  1 david  wheel   280B Dec  3 03:25 benchmark-numpy
20865364 -rwxr-xr-x  1 david  wheel   247B Dec  3 03:35 benchmark-python
20930576 -rwxr-xr-x  1 david  wheel    48M Dec  3 03:24 benchmark-sbcl

$ for proc in python numpy sbcl ecl
> do
> time ./benchmark-$proc
> done
python3 start.
python3 end.
real	2m30.871s
user	2m28.757s
sys	0m0.799s

python with numpy start.
python with numpy end.
real	0m11.076s
user	0m7.845s
sys	0m2.522s

"SBCL starts."
"SBCL ends."
real	0m2.305s
user	0m2.188s
sys	0m0.039s

"ECL starts."
"ECL ends."
real	0m0.135s
user	0m0.106s
sys	0m0.019s

看到这个结果,真可谓“高下”立判。相对来讲,ECL 在这个程序上的执行效率比其它的实现都要高出很多。没准以后会有人专门为 ECL 开发一个高度优化的科学计算库也说不定啊。

  1. 在这里我闹了个笑话,因为我不知道 Python 3 中的 range 事实上返回的是一个 iterator,所以我还在 Twitter 上给作者留言,指出为什么在 Lisp 里不先生成一个数组而后再累加求和。 

  2. 你可能会发现,在这段实现里,我们把 n 的类型声明给删去了;这是因为我们的确也不需要了。但是如果把 (optimize (speed 3) (safety 0)) 也去掉的话,那么效率将会大打折扣。 

  3. 在这里所展示的编译二进制的方法看上可能很别扭,其中对于 SBCL 是采用了 ASDF 作者 @fare 的软件,[cl-launch](http://cliki.net/cl-launch);可是我今天发现 cl-launch 在 ECL 上失效了,于是只好在 REPL 里手动编译出一个二进制。 

  4. 你还可以看到,ECL 编译出来的二进制文件,比起 SBCL,容量要小很多。