`замена` против простого` цикла` для копирования больших массивов в SBCL - PullRequest
Новая
       8

`замена` против простого` цикла` для копирования больших массивов в SBCL

4 голосов
/ 18 мая 2019

Описание проблемы

Допустим, вы хотите скопировать большие специализированные массивы в SBCL.Естественно, вы хотите, чтобы он был быстрым, занимал память и синтаксис был приятным.

Это можно сделать двумя способами: 

(defparameter *arr1* (make-array 100000 :element-type 'double-float
                                        :initial-element 1d0))
(defparameter *arr2* (make-array 100000 :element-type 'double-float
                                        :initial-element 0d0))

;; First method
(replace arr2 arr1 :start1 20000 :end1 90000)
;; Second method
(loop for i from 20000 below 90000 do
  (setf (aref arr2 i) (aref arr1 i)))

На первый взгляд, replaceкажется более приятным из-за его компактного синтаксиса, но результаты тестов не позволяют мне использовать его все время.

Сравнение производительности replace против loop

Я подозреваю, что это оченьзависит от платформы и компилятора.Я использовал SBCL 1.5.2 на Linux x86_64 5.1.3_1 на процессоре AMD Ryzen первого поколения.

Для сравнения давайте напишем несколько тестов: 

(defun spec-replace (arr1 arr2)
  (declare (type (simple-array double-float) arr1 arr2)
                 (optimize (speed 3)))
  (replace arr2 arr1 :start1 20000 :end1 90000))

(defun spec-loop (arr1 arr2)
  (declare (type (simple-array double-float) arr1 arr2)
                 (optimize (speed 3)))
  (loop for i from 20000 below 90000 do
    (setf (aref arr2 i) (aref arr1 i))))

(declaim (inline spec-loop spec-replace))

(let ((arr1 (make-array 100000 :element-type 'double-float
                               :initial-element 1d0))
      (arr2 (make-array 100000 :element-type 'double-float
                               :initial-element 0d0)))
  (time (spec-replace arr1 arr2))
  (time (spec-loop arr1 arr2)))

У вас есть выбор:

  • Переключение (speed 3) для каждой функции.
  • Переключение объявления inline для каждой функции.

Результаты выглядят так:

  • spec-loop и spec-replace связаны числом циклов ЦП, когда оптимизированы или неоптимизированы, но оба не встроены.
  • spec-loop имеет огромное преимущество, когда обе функции встроены.Между х3 или х4 скорость.
  • Выход disassemble для полностью оптимизированного spec-loop немного короче, чем для spec-replace.

Вопросы

  1. Поскольку оба метода довольно просты и концептуально выполняют одну и ту же операцию, почему SBCL не может оптимизировать их до тех же самых скомпилированных инструкций?Есть ли другая причина, кроме того, что она еще не реализована в SBCL?
  2. Будет ли полезной запись макроса с синтаксисом replace, который расширяется до метода loop?
  3. Я предполагаю, что оптимизация loop происходит за счет более высокого использования памяти, поскольку существует разница между оптимизацией по умолчанию и (speed 3).Достигну ли я точки убывающей отдачи в крупных проектах, в которых интенсивно используются операции такого типа?

Конечно, ответ на все это таков: тестирование в каждом конкретном случае.Но может ли кто-нибудь поделиться мудростью по поводу такого рода проблем?

1 Ответ

4 голосов
/ 18 мая 2019

Запрос источника REPLACE приводит к различным возможным источникам (Emacs + Slime, M -. (meta-dot)): 

..../sbcl/src/code/seq.lisp
  (DEFUN REPLACE)
..../sbcl/src/compiler/seqtran.lisp
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY CHARACTER (*)) SIMPLE-BASE-STRING &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-BASE-STRING (SIMPLE-ARRAY CHARACTER (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-VECTOR SIMPLE-VECTOR &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (COMPLEX DOUBLE-FLOAT) (*)) (SIMPLE-ARRAY (COMPLEX DOUBLE-FLOAT) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (COMPLEX SINGLE-FLOAT) (*)) (SIMPLE-ARRAY (COMPLEX SINGLE-FLOAT) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 64) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 64) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY FIXNUM (*)) (SIMPLE-ARRAY FIXNUM (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 32) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 32) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 16) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 16) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 8) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 8) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 64) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 64) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 63) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 63) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 62) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 62) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 32) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 32) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 31) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 31) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 16) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 16) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 15) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 15) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 8) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 8) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 7) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 7) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 4) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 4) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 2) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 2) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-BIT-VECTOR SIMPLE-BIT-VECTOR &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY DOUBLE-FLOAT (*)) (SIMPLE-ARRAY DOUBLE-FLOAT (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY SINGLE-FLOAT (*)) (SIMPLE-ARRAY SINGLE-FLOAT (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY CHARACTER (*)) (SIMPLE-ARRAY CHARACTER (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-BASE-STRING SIMPLE-BASE-STRING &REST T) "optimize")
..../sbcl/src/compiler/knownfun.lisp
  (:DEFOPTIMIZER REPLACE SB-C:DERIVE-TYPE)
..../sbcl/src/compiler/fndb.lisp
  (DECLAIM REPLACE SB-C:DEFKNOWN)

Тот, который нас интересует, этооптимизатор для SIMPLE-ARRAY DOUBLE-FLOAT.После перекрестной ссылки в sbcl/src/compiler/seqtran.lisp появляется несколько подозрительная строка, вызов макроса (define-replace-transforms) (в строке 999), который в конечном итоге опирается на !make-replace-transform в том же файле.

Функцияпредшествует большой комментарий о том, как реализован цикл.

Код разветвляется на разные реализации, но есть один, непосредственно видимый в функции, который может быть полезен для тестирования, в качестве другого теста, основанного накомментарий функции;это выглядит следующим образом: 

    (do ((i start1 (1+ i))
         (j start2 (1+ j))
         (end (+ start1 replace-len)))
        ((>= i end))
      (declare (optimize (insert-array-bounds-checks 0)))
      (setf (aref seq1 i) (aref seq2 j)))

Например, вот что дает цикл do явно: 

(deftype double-array () '(simple-array double-float (*)))

(declaim (type double-array *arr1* *arr2*))

(defparameter *arr1*
  (make-array 100000 :element-type 'double-float
                     :initial-element 1d0))

(defparameter *arr2*
  (make-array 100000 :element-type 'double-float
                     :initial-element 0d0))

(defun spec-from-source (&aux (arr1 *arr1*) (arr2 *arr2*))
  (declare (type double-array arr1 arr2)
           (optimize (speed 3) (debug 0) (safety 0)))
  (let ((start1 20000) (start2 0) (replace-len #.(- 90000 20000)))
    (do ((i start1 (1+ i))
         (j start2 (1+ j))
         (end (+ start1 replace-len)))
        ((>= i end))
      (declare (optimize (sb-c::insert-array-bounds-checks 0)))
      (setf (aref arr1 i) (aref arr2 j)))))

Тесты следующие:

замените 

(time
 (dotimes (i 2000)
   (spec-replace)))

Evaluation took:
  0.201 seconds of real time
  0.200000 seconds of total run time (0.200000 user, 0.000000 system)
  99.50% CPU
  481,862,984 processor cycles
  0 bytes consed

loop 

(time
 (dotimes (i 2000)
   (spec-loop)))

Evaluation took:
  0.130 seconds of real time
  0.132000 seconds of total run time (0.132000 user, 0.000000 system)
  101.54% CPU
  312,538,278 processor cycles
  0 bytes consed

, как и ожидалось, прочитав исходный код 

(time
 (dotimes (i 2000)
   (spec-from-source)))

Evaluation took:
  0.097 seconds of real time
  0.096000 seconds of total run time (0.096000 user, 0.000000 system)
  98.97% CPU
  231,766,644 processor cycles
  0 bytes consed

Я не похож на код, который вы написали, расширяется, как этотвыше, в зависимости от того, как производительность отличается.Разборка из SPEC-REPLACE показывает 

; C2B:       E828AAB6FD       CALL #x2036D658                 ; #<FDEFN SB-KERNEL:UB64-BASH-COPY>

Вызывает одну из так называемых функций bash-copy , первый случай в COND в !make-replace-transform.Немного исследования дает !define-byte-bashers и frob-bash-transform в качестве интересных функций для изучения.Кажется, что функция, на которую ссылается unary-bash-name, проделывает большую работу, чтобы найти способ написания специализированного кода для различных случаев.

  1. Я не знаком с этим кодом, но по крайней мереисточник доступен;однако, требуется гораздо больше времени, чтобы понять, как он работает, и как компилятор выбирает тот или иной путь при оптимизации.

  2. Это может быть хорошим вопросом для разработчиков SBCL (список рассылки sbcl-help).

  3. Обратите внимание, что подход DO является наиболее быстрым, если вам нужно много оптимизировать этот случай.Кажется, что семейство функций "byte-basher" может быть даже более специализированным, но я не уверен в этом.Если вы когда-нибудь узнаете об этом подробнее, рассмотрите возможность добавления ответа.

...