&rest引数をとる関数の最適化 - lisp-cookbook-ja/common-lisp GitHub Wiki
&rest引数をとる関数では、可変長の引数を処理するためのルーチンがオーバーヘッドとなり意図したパフォーマンスが得られない場合があります。
大抵の処理系では、可変長引数の関数は下請けに2引数の関数を持っていますが、 最適化の際には、可変長の引数を処理するためのルーチンを回避して下請けの固定長引数の関数を直に利用しているかどうか確かめる必要があるでしょう。
確かめる方法にはdisassemble等を利用する、等がありますが、何が効いてくるかは処理系次第になります。
(defconstant 100_000_000 (expt 10 8))
;;; 一億の要素を持つbit-vector
(declaim ((simple-bit-vector *) *big-vector-simple-bit-vector*))
(defvar *big-vector-simple-bit-vector*
(make-array 100_000_000 :element-type 'bit))
そのまま+を使った場合
(reduce #'+ *big-vector-simple-bit-vector*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
22.724 seconds of real time
22.593413 seconds of total run time (21.861367 user, 0.732046 system)
[ Run times consist of 3.092 seconds GC time, and 19.502 seconds non-GC time. ]
99.42% CPU
54,401,620,446 processor cycles
3,200,049,712 bytes consed
Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz
|------------------------------------------------------------|#
引数が2つであることがコンパイラに分かるように書いた場合(SBCLの場合)
(reduce (lambda (x y) (+ x y))
*big-vector-simple-bit-vector*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
4.905 seconds of real time
4.904307 seconds of total run time (4.900307 user, 0.004000 system)
99.98% CPU
11,742,306,462 processor cycles
164,368 bytes consed
Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz
|------------------------------------------------------------|#
+と (lambda (x y) (+ x y))の違い (sbclの場合)
(disassemble (lambda (x y) (+ x y)))
; disassembly for (LAMBDA (X Y))
; 515CAEED: 498B442450 MOV RAX, [R12+80] ; no-arg-parsing entry point
; EF2: 4883C010 ADD RAX, 16
; EF6: 48C740F851000000 MOV QWORD PTR [RAX-8], 81
; EFE: 488968F0 MOV [RAX-16], RBP
; F02: 4989442450 MOV [R12+80], RAX
; F07: 4981BC24E000000017001020 CMP QWORD PTR [R12+224], 537919511
; F13: 7402 JEQ L0
; F15: CC0F BREAK 15 ; single-step trap (before)
; F17: L0: 488B55F8 MOV RDX, [RBP-8]
; F1B: 488B7DF0 MOV RDI, [RBP-16]
; F1F: 4C8D1C25E0010020 LEA R11, [#x200001E0] ; GENERIC-+
; F27: 41FFD3 CALL R11
; F2A: 480F42E3 CMOVB RSP, RBX
; F2E: 498B442450 MOV RAX, [R12+80]
; F33: 48C740F000000000 MOV QWORD PTR [RAX-16], 0
; F3B: 48C740F800000000 MOV QWORD PTR [RAX-8], 0
; F43: 4883E810 SUB RAX, 16
; F47: 4989442450 MOV [R12+80], RAX
; F4C: 488BE5 MOV RSP, RBP
; F4F: F8 CLC
; F50: 5D POP RBP
; F51: C3 RET
; F52: CC0A BREAK 10 ; error trap
; F54: 02 BYTE #X02
; F55: 18 BYTE #X18 ; INVALID-ARG-COUNT-ERROR
; F56: 54 BYTE #X54 ; RCX
(disassemble #'+)
; disassembly for +
; 00CA6240: .ENTRY +(&REST ARGS) ; (FUNCTION
; (&REST T) ..)
; 278: 8F4508 POP QWORD PTR [RBP+8]
; 27B: E34B JRCXZ L2
; 27D: 4C8BD1 MOV R10, RCX
; 280: 49F7DA NEG R10
; 283: 4A8D6495D0 LEA RSP, [RBP+R10*4-48]
; 288: 488BD9 MOV RBX, RCX
; 28B: 4883E906 SUB RCX, 6
; 28F: 761A JBE L1
; 291: 4E8D4C9510 LEA R9, [RBP+R10*4+16]
; 296: 4D31C0 XOR R8, R8
; 299: L0: 4F8B1401 MOV R10, [R9+R8]
; 29D: 4E891404 MOV [RSP+R8], R10
; 2A1: 4983C008 ADD R8, 8
; 2A5: 4883E902 SUB RCX, 2
; 2A9: 75EE JNE L0
; 2AB: L1: 488BCB MOV RCX, RBX
; 2AE: 488955C8 MOV [RBP-56], RDX
; 2B2: 4883F902 CMP RCX, 2
; 2B6: 7414 JEQ L3
; 2B8: 48897DC0 MOV [RBP-64], RDI
; 2BC: 4883F904 CMP RCX, 4
; 2C0: 740A JEQ L3
; 2C2: 488975B8 MOV [RBP-72], RSI
; 2C6: EB04 JMP L3
; 2C8: L2: 488D65D0 LEA RSP, [RBP-48]
; 2CC: L3: 488D748CF8 LEA RSI, [RSP+RCX*4-8]
; 2D1: BB17001020 MOV EBX, 537919511
; 2D6: E35A JRCXZ L7
; 2D8: 488D14CD00000000 LEA RDX, [RCX*8]
; 2E0: 49896C2440 MOV [R12+64], RBP
; 2E5: 4D8B5C2418 MOV R11, [R12+24]
; 2EA: 4C01DA ADD RDX, R11
; 2ED: 4939542420 CMP [R12+32], RDX
; 2F2: 0F86CA000000 JBE L14
; 2F8: 4989542418 MOV [R12+24], RDX
; 2FD: 498D5307 LEA RDX, [R11+7]
; 301: L4: FD STD
; 302: 488BDA MOV RBX, RDX
; 305: EB08 JMP L6
; 307: L5: 4883C210 ADD RDX, 16
; 30B: 488952F1 MOV [RDX-15], RDX
; 30F: L6: 488B06 MOV RAX, [RSI]
; 312: 4883EE08 SUB RSI, 8
; 316: 488942F9 MOV [RDX-7], RAX
; 31A: 4883E902 SUB RCX, 2
; 31E: 75E7 JNE L5
; 320: 48C7420117001020 MOV QWORD PTR [RDX+1], 537919511
; 328: FC CLD
; 329: 49316C2440 XOR [R12+64], RBP
; 32E: 7402 JEQ L7
; 330: CC09 BREAK 9 ; pending interrupt trap
; 332: L7: 4881FB17001020 CMP RBX, 537919511
; 339: 0F847F000000 JEQ L13
; 33F: 488B4B01 MOV RCX, [RBX+1]
; 343: 488B53F9 MOV RDX, [RBX-7]
; 347: F6C201 TEST DL, 1
; 34A: 741A JEQ L8
; 34C: 80FA19 CMP DL, 25
; 34F: 7415 JEQ L8
; 351: 8BC2 MOV EAX, EDX
; 353: 240F AND AL, 15
; 355: 3C0F CMP AL, 15
; 357: 7558 JNE L12
; 359: 8B42F1 MOV EAX, [RDX-15]
; 35C: 3C15 CMP AL, 21
; 35E: 7606 JBE L8
; 360: 2C1D SUB AL, 29
; 362: 3C0C CMP AL, 12
; 364: 774B JNBE L12
; 366: L8: EB3A JMP L10
; 368: 90 NOP
; 369: 90 NOP
; 36A: 90 NOP
; 36B: 90 NOP
; 36C: 90 NOP
; 36D: 90 NOP
; 36E: 90 NOP
; 36F: 90 NOP
; 370: L9: 48895DF0 MOV [RBP-16], RBX
; 374: 8BC1 MOV EAX, ECX
; 376: 240F AND AL, 15
; 378: 3C07 CMP AL, 7
; 37A: 7561 JNE L15
; 37C: 488BC1 MOV RAX, RCX
; 37F: 488B4001 MOV RAX, [RAX+1]
; 383: 488945F8 MOV [RBP-8], RAX
; 387: 488B79F9 MOV RDI, [RCX-7]
; 38B: 4C8D1C25E0010020 LEA R11, [#x200001E0] ; GENERIC-+
; 393: 41FFD3 CALL R11
; 396: 480F42E3 CMOVB RSP, RBX
; 39A: 488B5DF0 MOV RBX, [RBP-16]
; 39E: 488B4DF8 MOV RCX, [RBP-8]
; 3A2: L10: 4881F917001020 CMP RCX, 537919511
; 3A9: 75C5 JNE L9
; 3AB: L11: 488BE5 MOV RSP, RBP
; 3AE: F8 CLC
; 3AF: 5D POP RBP
; 3B0: C3 RET
; 3B1: L12: 488B0578FEFFFF MOV RAX, [RIP-392] ; 'NUMBER
; 3B8: CC0A BREAK 10 ; error trap
; 3BA: 03 BYTE #X03
; 3BB: 1F BYTE #X1F ; OBJECT-NOT-TYPE-ERROR
; 3BC: 95 BYTE #X95 ; RDX
; 3BD: 15 BYTE #X15 ; RAX
; 3BE: L13: 31D2 XOR EDX, EDX
; 3C0: EBE9 JMP L11
; 3C2: L14: 492B542418 SUB RDX, [R12+24]
; 3C7: 52 PUSH RDX
; 3C8: 4C8D1C2540354200 LEA R11, [#x423540] ; alloc_tramp
; 3D0: 41FFD3 CALL R11
; 3D3: 5A POP RDX
; 3D4: 488D5207 LEA RDX, [RDX+7]
; 3D8: E924FFFFFF JMP L4
; 3DD: L15: CC0A BREAK 10 ; error trap
; 3DF: 02 BYTE #X02
; 3E0: 02 BYTE #X02 ; OBJECT-NOT-LIST-ERROR
; 3E1: 55 BYTE #X55 ; RCX