Сравнение List / Make-list & Vector / Make-array в Common Lisp

Question

Код сборки для list и make-list несколько отличается (в SBCL), даже когда конечные результаты совпадают:

* (disassemble (lambda (x) (list x)))
; disassembly for (LAMBDA (X))
; Size: 77 bytes. Origin: #x10025C0064
; 64:       498B4560         MOV RAX, [R13+96]                ; no-arg-parsing entry point
                                                              ; thread.binding-stack-pointer
; 68:       488945F8         MOV [RBP-8], RAX
; 6C:       840425F8FF1020   TEST AL, [#x2010FFF8]            ; safepoint
; 73:       4D8B5D20         MOV R11, [R13+32]                ; thread.alloc-region
; 77:       498D4310         LEA RAX, [R11+16]
; 7B:       493B4528         CMP RAX, [R13+40]
; 7F:       7725             JNBE L1
; 81:       49894520         MOV [R13+32], RAX                ; thread.alloc-region
; 85: L0:   498D4307         LEA RAX, [R11+7]
; 89:       840425F8FF1020   TEST AL, [#x2010FFF8]            ; safepoint
; 90:       488950F9         MOV [RAX-7], RDX
; 94:       C7400117001120   MOV DWORD PTR [RAX+1], #x20110017  ; NIL
; 9B:       488BD0           MOV RDX, RAX
; 9E:       488BE5           MOV RSP, RBP
; A1:       F8               CLC
; A2:       5D               POP RBP
; A3:       C3               RET
; A4:       CC0F             BREAK 15                         ; Invalid argument count trap
; A6: L1:   6A10             PUSH 16
; A8:       FF142528000020   CALL QWORD PTR [#x20000028]      ; ALLOC-TRAMP-R11
; AF:       EBD4             JMP L0
NIL

* (disassemble (lambda (x) (make-list 1 :initial-element x)))
; disassembly for (LAMBDA (X))
; Size: 43 bytes. Origin: #x10025C0127
; 27:       498B5D60         MOV RBX, [R13+96]                ; no-arg-parsing entry point
                                                              ; thread.binding-stack-pointer
; 2B:       48895DF8         MOV [RBP-8], RBX
; 2F:       840425F8FF1020   TEST AL, [#x2010FFF8]            ; safepoint
; 36:       BA02000000       MOV EDX, 2
; 3B:       488BFE           MOV RDI, RSI
; 3E:       488B0593FFFFFF   MOV RAX, [RIP-109]               ; #<SB-KERNEL:FDEFN SB-KERNEL:%MAKE-LIST>
; 45:       B904000000       MOV ECX, 4
; 4A:       FF7508           PUSH QWORD PTR [RBP+8]
; 4D:       FF6009           JMP QWORD PTR [RAX+9]
; 50:       CC0F             BREAK 15                         ; Invalid argument count trap
NIL
*

Обратите внимание, что (disassemble (lambda (x) (cons x nil))) и (disassemble (lambda (x) (list x)))похоже, выдают один и тот же код.

Такое же различие проявляется для (disassemble (lambda (x) (vector x))) и (disassemble (lambda (x) (make-array 1 :initial-element x))).

Является ли один из list или make-list (и vector или make-array) более эффективным после оптимизации компилятора?

Кроме того, это один из list или vector(и make-list или make-array) более эффективный (игнорируя на данный момент, как последовательности впоследствии получают доступ и обновляются)?

Answer 1

Мне немного непонятно, как (скажем) list и make-list можно сравнивать, поскольку они имеют совершенно разные цели.Тот факт, что они оба возвращают список, не делает их похожими или сопоставимыми.

Следовательно, предположим, что кто-то хочет получить представление о том, как работает make-list.Следующий код делает это:

* (let ((lst (time (make-list 10000000 :initial-element 0)))) (if lst t nil))
Evaluation took:
  0.344 seconds of real time
  0.343750 seconds of total run time (0.187500 user, 0.156250 system)
  [ Run times consist of 0.251 seconds GC time, and 0.093 seconds non-GC time. ]
  100.00% CPU
  1,129,211,079 processor cycles
  160,170,016 bytes consed

T
* (let ((lst (time (make-list 10000000 :initial-element 0)))) (if lst t nil))
Evaluation took:
  0.188 seconds of real time
  0.187500 seconds of total run time (0.125000 user, 0.062500 system)
  [ Run times consist of 0.139 seconds GC time, and 0.049 seconds non-GC time. ]
  100.00% CPU
  632,759,465 processor cycles
  160,195,440 bytes consed

T
* (let ((lst (time (make-list 10000000 :initial-element 0)))) (if lst t nil))
Evaluation took:
  0.343 seconds of real time
  0.343750 seconds of total run time (0.187500 user, 0.156250 system)
  [ Run times consist of 0.266 seconds GC time, and 0.078 seconds non-GC time. ]
  100.29% CPU
  1,151,984,724 processor cycles
  160,170,016 bytes consed

T
* (let ((lst (time (make-list 10000000 :initial-element 0)))) (if lst t nil))
Evaluation took:
  0.203 seconds of real time
  0.203125 seconds of total run time (0.171875 user, 0.031250 system)
  [ Run times consist of 0.140 seconds GC time, and 0.064 seconds non-GC time. ]
  100.00% CPU
  648,536,502 processor cycles
  160,195,520 bytes consed

T

Первое, на что нужно обратить внимание, это то, что время выполнения не согласовано, потому что в системе слишком много других «случайных» действий (например, GC).Что еще более важно, как мы теперь пишем 10 000 000 списков нулей для передачи на list для сравнения?Используем ли мы цикл (в этом случае это цикл, который мы (в основном) будем синхронизировать)?Создаем ли мы сначала напечатанное представление в виде 1000000 длинных списков с нулями, которые затем будут считываться с read (в этом случае мы будем (в основном) рассчитывать время создания печатного представления и читателя lisp)?Выглядит как яблоки и апельсины ...

Answer 2

Насколько я понимаю, make-list и make-array более эффективны после оптимизации компилятора. Например, с помощью make-list вы контролируете размер этого списка, как только он создается, и когда вы разбираете функцию, вы должны увидеть «invalid-args-count-error», которая должна оптимизировать ваш код. Вы объявляете размер этого списка с самого начала, тогда как использование функции списка не имеет такой оптимизации, кроме ограничений максимального размера списка:

(setq x (make-list 4 :initial-element 'a))

по сравнению с

(setq x (list 'a 'a 'a 'a))

Ошибка слишком большого индекса возникла бы, если бы вы попытались добавить элемент в индекс 5 с помощью make-list, тогда как при создании списка с помощью функции list этого не произойдет. Минусы будут разбиты так, как вы описали, и больше похожи на список или вектор, потому что нет ограничений по размеру и типу:

(cons 1 '(a b c d e))

По сравнению с:

(make-array '(2 3) :initial-element nil
                   :element-type 'fixnum)

Который будет ограничивать размер и создавать указатели только на fixnums. Что касается оптимизации кода, то make-array и make-list более эффективны, но вы, конечно, можете заявить, что вектор будет определенного типа и определенного размера, который оптимизирует ваш код:

(declaim (type (vector fixnum 20) v))

После этого вектор оптимизации компилятора должен быть таким же эффективным, как и функция, такая как make-array, до того, как он будет отправлен для чтения.