Python
common-lisp
numpy

NumPy vs Common Lisp

More than 1 year has passed since last update.

これはNextremer Advent Calendar 2016の1日目の記事です。

半年以上前の記事ですが、この記事(スクリプト言語の流儀〜C言語、Python、Ruby速度比較)が気になったのでNumPy vs Common Lispでやってみました。

Pythonのコードについてはhamukazu氏のコード(あるいは、さらにその元の参照できなくなってる記事のコード?)を使わせてもらっています。


コンピュータ

実行に使用したコンピュータは次の通り。


  • Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz

  • Ubuntu 16.04.1 LTS


Python


実行環境

Minicondaを利用して環境を構築しました。

バージョンは次の通りです。

$ python --version

Python 3.5.2 :: Continuum Analytics, Inc.


NumPy版

NumPy版のコードと実行時間は次の通りです。

N = 10000

import numpy as np

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.")

main()

$ time python benchmark-numpy.py 

python with numpy start.
python with numpy end.

real 0m0.238s
user 0m0.216s
sys 0m0.020s


Python版

NumPyを使わないPython版のコードと実行時間は次の通りです。

N = 10000

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

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

main()

$ time python benchmark-python.py 

python without numpy start.
python without numpy end.

real 0m0.945s
user 0m0.940s
sys 0m0.004s


Common Lisp

NumPyがPython本体に含まれてないライブラリという話も出ていたので、Common Lisp版は標準の範囲内で実装します。


実行構築

roswellを経由してSBCLを使用します。

バージョンについては次の通りです。

$ ros --version

roswell 0.0.6.68

$ ros run -- --version

SBCL 1.3.11

今回は標準ライブラリのみでquicklispを使用しないのでroswellの引数に+Qをつけて実行します。


loop版

普通にループで書く。

(defconstant +n+ 10000)

(defun sumup (n)
(let ((sum 0))
(loop for i from 1 to n
do (incf sum i))
sum))

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

$ time ros +Q benchmark-common-lisp.ros 

"common lisp start."
"common lisp end."
real 0m0.332s
user 0m0.320s
sys 0m0.008s


dotimes版

dotimesで書く。

(defconstant +n+ 10000)

(defun sumup (n)
(let ((sum 0))
(dotimes (i n)
(incf sum (1+ i)))
sum))

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

$ time ros +Q benchmark-common-lisp-dotimes.ros 

"common lisp start."
"common lisp end."
real 0m0.426s
user 0m0.404s
sys 0m0.016s

ちょっと遅くなった。1+使ってるからかな?


色々チューニング

Common Lispの売り(?)はdisassembla標準装備なのでloop版をdisassembleします。

(disassemble 'sumup)

; disassembly for SUMUP

; Size: 156 bytes. Origin: #x100340308D
; 08D: 498B4C2460 MOV RCX, [R12+96] ; thread.binding-stack-pointer
; no-arg-parsing entry point
; 092: 48894DF8 MOV [RBP-8], RCX
; 096: 31F6 XOR ESI, ESI
; 098: 488B4DF0 MOV RCX, [RBP-16]
; 09C: 8D41F1 LEA EAX, [RCX-15]
; 09F: A801 TEST AL, 1
; 0A1: 750E JNE L0
; 0A3: 3C0A CMP AL, 10
; 0A5: 740A JEQ L0
; 0A7: A80F TEST AL, 15
; 0A9: 7574 JNE L3
; 0AB: 8079F11D CMP BYTE PTR [RCX-15], 29
; 0AF: 776E JNBE L3
; 0B1: L0: BB02000000 MOV EBX, 2
; 0B6: EB3E JMP L2
; 0B8: 0F1F840000000000 NOP
; 0C0: L1: 48895DE8 MOV [RBP-24], RBX
; 0C4: 488BD3 MOV RDX, RBX
; 0C7: 488BFE MOV RDI, RSI
; 0CA: 41BBA0020020 MOV R11D, 536871584 ; GENERIC-+
; 0D0: 41FFD3 CALL R11
; 0D3: 488B5DE8 MOV RBX, [RBP-24]
; 0D7: 488BF2 MOV RSI, RDX
; 0DA: 488975E0 MOV [RBP-32], RSI
; 0DE: BF02000000 MOV EDI, 2
; 0E3: 488BD3 MOV RDX, RBX
; 0E6: 41BBA0020020 MOV R11D, 536871584 ; GENERIC-+
; 0EC: 41FFD3 CALL R11
; 0EF: 488B75E0 MOV RSI, [RBP-32]
; 0F3: 488BDA MOV RBX, RDX
; 0F6: L2: 48895DE8 MOV [RBP-24], RBX
; 0FA: 488975E0 MOV [RBP-32], RSI
; 0FE: 488B7DF0 MOV RDI, [RBP-16]
; 102: 488BD3 MOV RDX, RBX
; 105: B9E0040020 MOV ECX, 536872160 ; GENERIC->
; 10A: FFD1 CALL RCX
; 10C: 488B75E0 MOV RSI, [RBP-32]
; 110: 488B5DE8 MOV RBX, [RBP-24]
; 114: 7EAA JLE L1
; 116: 488BD6 MOV RDX, RSI
; 119: 488BE5 MOV RSP, RBP
; 11C: F8 CLC
; 11D: 5D POP RBP
; 11E: C3 RET
; 11F: L3: 488B45F0 MOV RAX, [RBP-16]
; 123: CC0A BREAK 10 ; error trap
; 125: 40 BYTE #X40 ; OBJECT-NOT-REAL-ERROR
; 126: 00 BYTE #X00 ; RAX
; 127: CC10 BREAK 16 ; Invalid argument count trap

ジェネリックな関数が呼ばれているので、一目見て遅そうなのが分かります。


optimize speed 3版

optimizeを指定してみます。

(defconstant +n+ 10000)

(defun sumup (n)
(declare (optimize (speed 3) (debug 0) (safety 0)))
(let ((sum 0))
(loop for i from 1 to n
do (incf sum i))
sum))

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

$ time ros +Q benchmark-common-lisp-optimize-speed-3.ros 

"common lisp start."
"common lisp end."
real 0m0.356s
user 0m0.348s
sys 0m0.004s

(disassemble 'sumup)

; disassembly for SUMUP

; Size: 115 bytes. Origin: #x100364AFB2
; AFB2: 31F6 XOR ESI, ESI ; no-arg-parsing entry point
; AFB4: 48897DF8 MOV [RBP-8], RDI
; AFB8: BB02000000 MOV EBX, 2
; AFBD: EB3D JMP L1
; AFBF: 90 NOP
; AFC0: L0: 48895DE8 MOV [RBP-24], RBX
; AFC4: 488BD3 MOV RDX, RBX
; AFC7: 488BFE MOV RDI, RSI
; AFCA: 41BBA0020020 MOV R11D, 536871584 ; GENERIC-+
; AFD0: 41FFD3 CALL R11
; AFD3: 488BC2 MOV RAX, RDX
; AFD6: 488B5DE8 MOV RBX, [RBP-24]
; AFDA: 488BF0 MOV RSI, RAX
; AFDD: 488975F0 MOV [RBP-16], RSI
; AFE1: BF02000000 MOV EDI, 2
; AFE6: 488BD3 MOV RDX, RBX
; AFE9: 41BBA0020020 MOV R11D, 536871584 ; GENERIC-+
; AFEF: 41FFD3 CALL R11
; AFF2: 488BC2 MOV RAX, RDX
; AFF5: 488B75F0 MOV RSI, [RBP-16]
; AFF9: 488BD8 MOV RBX, RAX
; AFFC: L1: 488975F0 MOV [RBP-16], RSI
; B000: 48895DE8 MOV [RBP-24], RBX
; B004: 488B7DF8 MOV RDI, [RBP-8]
; B008: 488BD3 MOV RDX, RBX
; B00B: B9E0040020 MOV ECX, 536872160 ; GENERIC->
; B010: FFD1 CALL RCX
; B012: 488B5DE8 MOV RBX, [RBP-24]
; B016: 488B75F0 MOV RSI, [RBP-16]
; B01A: 7EA4 JLE L0
; B01C: 488BD6 MOV RDX, RSI
; B01F: 488BE5 MOV RSP, RBP
; B022: F8 CLC
; B023: 5D POP RBP
; B024: C3 RET

出力アセンブリは微妙に変化してるが、速度的には変わらず。


type fixnum n版

引数nにfixnum型を指定します。

(defconstant +n+ 100000)

(defun sumup (n)
(declare (type fixnum n))
(let ((sum 0))
(loop for i from 1 to n
do (incf sum i))
sum))

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

$ time ros +Q benchmark-common-lisp-type-fixnum-n.ros 

"common lisp start."
"common lisp end."
real 0m0.200s
user 0m0.180s
sys 0m0.012s

(disassemble 'sumup)

; disassembly for SUMUP

; Size: 72 bytes. Origin: #x1003D2B65A
; 5A: 498B4C2460 MOV RCX, [R12+96] ; thread.binding-stack-pointer
; no-arg-parsing entry point
; 5F: 48894DF8 MOV [RBP-8], RCX
; 63: 31C9 XOR ECX, ECX
; 65: BB01000000 MOV EBX, 1
; 6A: EB26 JMP L1
; 6C: 0F1F4000 NOP
; 70: L0: 488D141B LEA RDX, [RBX+RBX]
; 74: 48895DE8 MOV [RBP-24], RBX
; 78: 488BF9 MOV RDI, RCX
; 7B: 41BBA0020020 MOV R11D, 536871584 ; GENERIC-+
; 81: 41FFD3 CALL R11
; 84: 488BCA MOV RCX, RDX
; 87: 488B5DE8 MOV RBX, [RBP-24]
; 8B: 488B75F0 MOV RSI, [RBP-16]
; 8F: 48FFC3 INC RBX
; 92: L1: 4839F3 CMP RBX, RSI
; 95: 7ED9 JLE L0
; 97: 488BD1 MOV RDX, RCX
; 9A: 488BE5 MOV RSP, RBP
; 9D: F8 CLC
; 9E: 5D POP RBP
; 9F: C3 RET
; A0: CC10 BREAK 16 ; Invalid argument count trap

実行時間としては約0.2秒なので、NumPy版と同じくらいになりました。


type fixnum sum版

type fixnum nのアセンブリを見ると、まだジェネリック関数が残っています。

変数sumにもfixnum型を指定します。

(defconstant +n+ 100000)

(defun sumup (n)
(declare (type fixnum n))
(let ((sum 0))
(declare (type fixnum sum))
(loop for i from 1 to n
do (incf sum i))
sum))

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

$ time ros +Q benchmark-common-lisp-type-fixnum-sum.ros 

"common lisp start."
"common lisp end."
real 0m0.154s
user 0m0.140s
sys 0m0.008s

(disassemble 'sumup)

; disassembly for SUMUP

; Size: 70 bytes. Origin: #x100436CB56
; 56: 498B4C2460 MOV RCX, [R12+96] ; thread.binding-stack-pointer
; no-arg-parsing entry point
; 5B: 48894DF8 MOV [RBP-8], RCX
; 5F: 31D2 XOR EDX, EDX
; 61: B901000000 MOV ECX, 1
; 66: EB23 JMP L1
; 68: 0F1F840000000000 NOP
; 70: L0: 488BD9 MOV RBX, RCX
; 73: 488BC2 MOV RAX, RDX
; 76: 48D1F8 SAR RAX, 1
; 79: 488D1403 LEA RDX, [RBX+RAX]
; 7D: 488BC2 MOV RAX, RDX
; 80: 48D1E0 SHL RAX, 1
; 83: 7011 JO L2
; 85: 48D1E2 SHL RDX, 1
; 88: 48FFC1 INC RCX
; 8B: L1: 4839F1 CMP RCX, RSI
; 8E: 7EE0 JLE L0
; 90: 488BE5 MOV RSP, RBP
; 93: F8 CLC
; 94: 5D POP RBP
; 95: C3 RET
; 96: L2: CC0A BREAK 10 ; error trap
; 98: 35 BYTE #X35 ; OBJECT-NOT-FIXNUM-ERROR
; 99: 12 BYTE #X12 ; RDX
; 9A: CC10 BREAK 16 ; Invalid argument count trap

これで実行時間がNumPy版よりもCommon Lispの方が速くなりなりました。

プリント文を使うとPython側と結果が一致してるように見えるけど、これで本当に計算してるんだろうか?


build版

標準の機能からは外れるのかもしれませんが、roswellのビルド機能を使ってコンパイル済みオブジェクトを作ってみます。

まずはファイルの先頭に色々追加します。

#!/bin/sh

#|-*- mode:lisp -*-|#
#|
exec ros +Q -- $0 "$@"
|#

(defconstant +n+ 10000)

(defun sumup (n)
(declare (type fixnum n))
(let ((sum 0))
(declare (type fixnum sum))
(loop for i from 1 to n
do (incf sum i))
sum))

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

roswellでビルドします。

$ ros +Q build benchmark-common-lisp-ros-build.ros 

[undoing binding stack and other enclosing state... done]
[saving current Lisp image into benchmark-common-lisp-ros-build:
writing 4912 bytes from the read-only space at 0x20000000
writing 3216 bytes from the static space at 0x20100000
writing 782336 bytes from the immobile space at 0x20300000
writing 0 bytes from the immobile space at 0x21b00000
writing 44400640 bytes from the dynamic space at 0x1000000000
done]

ELFファイルが生成されます。

$ file benchmark-common-lisp-ros-build

benchmark-common-lisp-ros-build: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.18, BuildID[sha1]=aad09922bc365e5911ed48273a824d4aca017382, not stripped

$ time ./benchmark-common-lisp-ros-build 

"common lisp start."
"common lisp end."
real 0m0.065s
user 0m0.060s
sys 0m0.004s

さらに0.1秒くらい速くなりました。


まとめ

言語
実行時間 (ms)

Python (NumPy版)
238

Python版
945

Common Lisp (loop版)
332

Common Lisp (dotimes版)
426

Common Lisp (optimize speed 3版)
356

Common Lisp (type fixnum n版)
200

Common Lisp (type fixnum sum版)
154

Common Lisp (build版)
65

NumPy版よりもCommon Lisp版の方が速くなりました。